ADDSQURE - Editorial

editorial
, , ,
21

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.

1 Like
22

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.

C++17 Code

5 Likes
23

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

24

Finally editorial.

1 Like
25

What is the time complexity of the setter’s solution?

26

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})

27

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
28

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
29

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
30

Thanks for this nice editorial from which I learned new things like good and effective use of bit manipulation and fft.

1 Like
31

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
32

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
33

You explained it very well,thanks

34

what a lovely question and lovely explanation…swaaad aagya :smile: :smile: :heart_eyes:

35

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

36

https://www.codechef.com/viewsolution/38913362
Please tell where it is going wrong i have use same concept as in editorial.

37

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

38

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.

39

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.

40

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.