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.
11 Likes
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!
3 Likes
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 .
2 Likes
Thanks for this nice editorial from which I learned new things like good and effective use of bit manipulation and fft.
1 Like
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
2 Likes
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.
18 Likes
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.
I don’t think this improvisation would be enough to bring down the TC.
Check the following code, where the counter is not used to bound the loops in lines 11 and 12.
Check the following code where the counter is not used to bound the loops in lines 11 and 12.
https://www.codechef.com/viewsolution/38916115
Note that the number of times the statement in the inner loop of the exhaustive search is executed is O(N^2). Suppose that N = 4, and a =[1~2~3~4]. Then, a_{\max} = 4, a_{\min} = 1, and the number of possible distinct distances is 3. The three distinct distance 1, 2 and 3 are found during the first iteration of the our loop, and the bounded search using the distinct distances counter stops without checking more pairs.
Could you explain what you did?
Thanks for such a great problem and this detailed Editorial!
Let us consider case for any 1 set of lines(horizontal or vertical)
The first problem that we are facing is calculating all possible differences that can be obtained by a set of lines.
But here is a small thing, N \leq W+1, so the larger the value of N, the more cramped the lines will be in the space. Hence we start removing differences by consecutive values at a time(a_i-a_{i-1}), and quite a few of all possible differences will be removed beforehand.
However let us think about the worst case, where W=N=10^5, here all differences are possible, so we can just find ( a_i-a_0) and mark those differences. So we get all differences in a meagre O(n) for the worst scenarios. And finally, for the differences we missed, we can check them out by a simple nested loop.
We do this for both sets of lines and then find out the differences that can be made for a but cannot be made for b, our task is to find a line so that we can make the maximum number of these differences for b. Let’s call this set of differences D.
Now we have cannot place lines everywhere, so we can do 2 things-
- choose the line from H which can form the maximum number of differences from D.
- pick all lines in b and see where our optimal line can be placed. Then will will select the line which can make maximum differences with lines of b
Our answer = (number of differences common in both a and b) + (value obtained from 1 or 2)
Choosing 1 or 2 depends on number of iterations that we have to face if we perform each procedure, and since its O(n^2), the maximum number of iterations can be computed easily.
You can look at my code here.
This isn’t a very perfect approach and so I asked the editorialist if the TC were weak, but then again, who cares about procedure anyway? The target in a contest is to get that green tick.
PS-It would be great if anyone could find a TC where this apparently incorrect code would TLE out.
2 Likes