nik1996's blog

By nik1996, 6 months ago, ,

Hello codeforces!!

Recently I was attempting an hiring test and came across the following problem which I could not solve. Could anybody help me in solving this problem?

You are given a special type of array — an expanding array. An expanding array is an array which has only distinct elements and keep expanding based on the following process:

• Pick any 2 integers (A and B, A > B) randomly from the existing expanding array. If integer part of A / B (lets call it Z) is not present in the array, we expand our original expanding array and add Z to it.

Keep repeating above operation until array cannnot be extended further. Find the final size of expanding array.

Constraints: Array size <= 500, each array element Arr[i]: 1<=Arr[i]<=1000.

Example: I/P : Arr = [9, 4], O/P : 3, Final expanding array is :[9,4,2].

• +4

 » 6 months ago, # | ← Rev. 3 →   +17 Let's consider a smart brute force approach.For every unique value in the array, store a list of unique elements that are less than it. Now we do A / B for every A > B. For each A, when you do A / B, remove B from A's list. Now, when the new integers are generated, add them to the corresponding lists. Remember not to add the new integer to a list if it was previously removed.Since every number is inserted into every list once and removed from every list once. And there are at most 1000 numbers and 1000 lists, the time complexity of this solution is O(N^2) where N = Max(Arr[i]).
 » 6 months ago, # | ← Rev. 8 →   0 Edit: Wrong solution is wrong, thanks LTDT. WrongBitsets: (1000*1000) time, 1000/32 space. Tested and works with example. int main () { vector nums = {9,4}; bitset<1001> cur,next; for(int a:nums) cur.set(a); for(int i=1000;i>1;i--) if(cur.test(i)) { next.set(i); for(int j=i-1;j>1;j--) if(cur.test(j)) next.set(j),next.set(i/j); swap(cur,next); } cout<
•  » » 6 months ago, # ^ |   +19 Consider this test case:7 4 10 8 3We can take $\lfloor{\frac{4}{3}}\rfloor = 1$, $\lfloor{\frac{8}{4}}\rfloor = 2$ and $\lfloor{\frac{10}{2}}\rfloor = 5$.The final array will be:7 4 10 8 3 1 2 5So the correct answer should be 5 + 3 = 8.Your program prints 7.
•  » » » 6 months ago, # ^ |   0 I stand corrected, could you write (pseudo) code of your solution? It's not very clear to me.
•  » » » » 6 months ago, # ^ | ← Rev. 5 →   0 The pseudocode below varies quite a bit from my original description to simplify implementation.Let the original array be A. Keep an array, X, of n indexes. Initialize all values to 0. Do an infinite loop. Let this be loop 1 Loop through X within the infinite loop. Let this be loop 1.1 For the ith value in X, if i is not equal to X[i] and A[i] > A[X[i]], append A[i] / A[X[i]] to A if not already present. Add an additional 0 to X to account for any new element in A. Increment X[i] by 1. Once X[i] has reached the end of A, we go to the next element in X. If loop 1.1 does not add any new numbers to A, we break from loop 1. Print size of A. You can clearly see that there are at most 1000 elements in X. And any X[i] can be incremented at most 1000 times. Hence, this algorithm is O(max(A[i])^2).
•  » » » » 6 months ago, # ^ |   0 I have implemented my solution as a proof of concept.The logic is exactly the same as that in the pseudocode. My code#include #include using namespace std; int n, a; bool dat[1005]; vector v, x; int main() { cin >> n; for(int i = 0; i < n; i++) { cin >> a; dat[a] = 1; v.push_back(a); } x.assign(n, 0); while(1) { bool has = false; for(int i = 0; i < (int) x.size(); i++) { while(x[i] < (int) v.size()) { int new_num = v[i] / v[x[i]]; if(v[i] > v[x[i]] && dat[new_num] != 1) { v.push_back(new_num); x.push_back(0); dat[new_num] = 1; has = true; } x[i]++; } } if(!has) break; } cout << v.size() << "\n"; } 
 » 6 months ago, # | ← Rev. 3 →   0 Simple 2 nested for loops with marking already added numbers and trying a new with each of the others O(N^2) time, O(N) space: #include using namespace std; int main () { vector nums = {2,100}; bitset<1001> seen; for(int a:nums) seen.set(a); for(int i=0;i