I use 10^9 ops/s to estimate if an algorithm is feasible, so then it would have some room to spare. It is however difficult to seperate \mathcal{O}(n^2) and \mathcal{O}(\frac{n^2}{64}), so the bounds are almost guaranteed to be a bit tight.
I used a different approach to reduce the time-complexity of generating all possible horizontal and vertical side lengths. The key observation is that the number of distinct horizontal distances between any pair of the n vertical lines dos not exceed a_{\max}-a_{\min}, and the number of distinct vertical distances between any pair of the m horizontal lines does not exceed b_{\max}-b_{\min}. A counter is used to store the number of distinct side lengths that have been already identified. The counter is incremented each time a new side length is found, and the exhaustive search stops when the counter reaches the maximum possible value.
really nice way of solving questions i had the same concept but was not taking advantage of bit manipulation thanks for such a explanation every ploblem should be discussed in this way
Finally editorial.
What is the time complexity of the setter’s solution?
The FFT is \mathcal{O}(n\log n), but he still uses bitsets to find common distances between horizontal lines and vertical lines. So his entire algorithm is \mathcal{O}(\frac{n^2}{64})
upd: My solution is wrong, thanks to @vg_codechef for pointing it out.
If there is any nlogn solution, please @ me and Thanks very much.
I didn’t think that O(n^{2}/64) will work. I used FFT and tried to find a O(n\log{}n) solution. Anyways It was a very good problem and It made me learn FFT. Thank You!
I have never manipulate bit this way. I guess until and unless i have not seen this uses of bit before I seldomly can think this way that using bitmask i can calculate the difference of all numbers .
Thanks for such a good editorial .
Thanks for this nice editorial from which I learned new things like good and effective use of bit manipulation and fft.
For the second segment I need to introduce a new bitset. This will be revHorizontal
, which is the reverse of horizontal
. So revHorizontal[i]
is set if there is a horizontal line y=\text{height}-iy=height−i. We need this new bitset because it also allows us to update distances to lines below the new line quickly. horizontal
and revHorizontal
will be shifted by yy and \text{height}-yheight−y respectively, so that after shifting horizontal[k]
is set if there is a line at y=c+ky=c+k, and similarly revHorizontal[k]
will be set if there is a line at y=c-ky=c−k.
Can you please explain with an example ? @spaanse
Let the existing horizontal lines be at y=0, y=1, y=4, y=5, y=7 and height=7
.
Then horizontal
will be 10110011 (note that bits are indexed from the right instead of the left). revHorizontal
then is 11001101 (so the reverse of horizontal
)
Now y=2 is the first y that does not yet have a horizontal line. In the two bitsets the new line would then end up in the following two places
horizontal revHorizontal
10110011 11001101
^ ^
Now we shift both of them to the right so the indicated bit is the rightmost one
horizontal revHorizontal
00101100 00000110
^ ^
Next we take the bitwise or of both values to get
00101100
00000110 OR
------------
00101110
So introducing this new line would form 4 differences because there are 4 bits set.
You explained it very well,thanks
what a lovely question and lovely explanation…swaaad aagya
Can you please explain your code bit more…looks good… But not clear by taking some small example also how counter working and how you ensuring that max - min is 10^5 how you reduced time
https://www.codechef.com/viewsolution/38913362
Please tell where it is going wrong i have use same concept as in editorial.
thank you very much for this excellent explanation.This is the first time I completely understood the editorial. I am mostly scared of editorial because the language they use are easily understood by 8 star coders only
I suspect it does not return anything because an IllegalArgumentException is thrown in shiftRight and catched in main. Either modify the solution a bit so only shifts of one are used, or modify shiftRight to allow for larger shifts than 64.
can you tell how to do that i am not able to do Please…
Actually in java bitset store the index number in set
and shifting it by greater than 64 will be wrong so i am confused.
You split the amount to be shifted in multiples of 64 and singles. Then you use the multiples of 64 to determine which long longs to shift into and the singles to determine how much to shift.