https://mirror.codeforces.com/contest/1945/problem/H
Hey cfers hope all are doing well can anyone please tell me how to solve this please do share your code and logic thanks.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 162 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
https://mirror.codeforces.com/contest/1945/problem/H
Hey cfers hope all are doing well can anyone please tell me how to solve this please do share your code and logic thanks.
Name |
---|
Hints for reaching the solution
1945H - НОД больше
Fact 1 : It is always better to just have 2 numbers in the gcd.
This can be easily proven, by the test cases.. uhm, we can just say that if there are greater than 2 numbers in the gcd then we can keep removing them from there and add them in AND, gcd might increase but can't decrease and AND might decrease but can't increase.
Let cnt[bit] be the number of elements in the array that have this bit off (0). We also store the elements for every bit in a vector[bit] as well.
Now, if there are more than 2 elements for this bit then no matter which 2 elements we chose for our gcd the AND will have this bit off.
Hence, we come to this idea that if there are <= 2 elements for this bit, then just check them manually. This will take O(2 * LG * n * LG) (LG = 19, and second LG is for computing gcd).
Now, if we found the answer there then good. But, if not then, we can now just ignore them, we will never keep them in our gcd (because we tried that). Let's say we have marked these elements in our boolean array mark.
Therefore, if cnt[bit] > 0 then this bit is surely off in our AND and otherwise it's surely on.
if cnt[bit] > 2, then since we are just choosing 2 elements for gcd the other elements will go in AND and turn it off.
if 0 < cnt[bit] <= 2, then we just checked those elements that if we put them in gcd, do they give us the answer, they did not, so we are now putting them in AND.
So, we are making every bit off which can be turned off.
So, now our AND is fixed. We just want gcd of two numbers to be greater than some X (X = Fixed_AND + x). Now, we can just do a cnt of multiples that how many multiples does this d have, not considering marked elements.
Now, we say (gcd = max_element; gcd > X; gcd--) and see if muls[gcd] >= 2, if yes then just find them (again don't consider the marked ones here) and print. Otherwise, if the for loop ends then the answer is NO.
Time Complexity : O(n * LG * LG + n * LG + MAX_element) = O(n * LG * LG)
n * LG * LG, for the brute force, manual check.
n * LG, for the sieve (to compute muls[d]).
MAX_element, for finding the answer, note that it is mentioned in the input of the problem that sum of max_a[i] <= 4 * 10 ^ 5.
we don't need to store the cnt[bit], we just say vec[bit].push_back(a[i]), if a[i] does not contain this bit.
Then we go over all the bits, and check if vec[bit].size() <= 2. If yes, then we iterate on those elements and add them in our GCD, and check if they give the answer. We get the other element which will be paired with it. Let the first element be at position i and the second element at position j, we can compute gcd(a[i], a[j]), but how to do AND(a[0..(i-1)]) & AND(a[(i+1)..(j-1)] & AND[(j+1)..(n-1)]. The first one is prefix AND, the last one is suffix AND but the middle one, uh oh, have to use sparse table, but wait we can just iterate on j in such a way that we don't need that. We first say j = i + 1 and keep moving forward while updating the middle AND each time we go forward, and then later we say j = i-1 and keep decreasing it and updating the middle AND.
I was in a hurry during the contest, so my implementation was not much neat, here is it anyway 252257639.
This was all but, if somebody have any questions, I will be happy to answer.
True. But if you do store it, your implementation will become a lot simpler. If you have the count of zeroes at each position, then, when you remove $$$a[i]$$$ and $$$a[j]$$$ from the set, you simply decrease the count by $$$0$$$ or $$$1$$$ or $$$2$$$ (depending upon whether the outgoing element has that bit set or unset). Then, if the count is zero, the bitwise AND would contain $$$1$$$ at that position. We can repeat for each bit.
Sample Submission
Thank you
I've added hints for H : GCD is Greater on CF Step
I loved the editorial I performed all the 4 soln that mention including the wa3 of nlogn too made my clear concepts thnks you