You are adding all lines and then considering how many squares are formed. You are only allowed to add a single horizontal line.
Hi @spaanse I was stuck at thinking how to reduce the complexity to nSqrt(n) or nlg(n).
How did you come to conclusion that it can’t be done in nSqrt(n) or nlg(n).
Can you answer this please?
\mathcal{O}(n\log n) is also possible, see this comment by @freeloop. It’s just much more complicated.
1 Like
Gotcha!
One more question!
In which situations/problems we can use this bitset thing to lower down complexity speed up the algorithm?
If you have an array of booleans that is a big hint.
The reason a bitset is called a bit-set is because it can represent subsets. So if bit i is set then element i is in the subset, and if bit i is not set then element i is not in the subset. Then and, or, not and xor correspond to intersection, union, complement and symmetric difference. So in cases where you have some subset of a finite set (in this problem a subset of all horizontal/vertical lines) you can often use bitset’s to speed up the algorithm.
2 Likes
Thankyou 
Thank you for pointing out.
My treatment of the latter part is wrong or at least incomplete. However, it got AC, so I did not continue to think about it. I’m so sorry about it, I had to delete my solution so as not to mislead more people…
I haven’t figured out how to fix the latter part. If you have any ideas, please let me know. Thanks a lot. 
No No No.
You are the fastest man.
1 Like
Can’t you remove the double counting easily.
we double count because the line y=8 is midway between y=6 and y=10. now multiplying (a^6+a^{10})(a^6+a^{10}) we get a^{12}+2a^{16}+a^{20} which indicates that 8 is midway between a pair of lines because the coefficient of a^{2\cdot 8} is positive. We could (?) use this to compensate for the double counting.
I haven’t thought of a good way to deal with double counting. As you said, it is easy to find the lines that may be repeated, but it is not easy to determine how many times they have been repeated 
Really loved this solution.
Is there a way to shift bits in bitset of java, because in java it does not work
Apparently you can use the .get(fromIdx, toIdx) for this. See the Java documentation and this post on Stackoverflow
1 Like
Java implementation is sometimes tricky 
Thanks for helping!
You may try biginteger instead. That should do the job.
Can you explain a bit, please?
Store the binary number as an integer using the big integer library then you can use the OR,AND,XOR, shift operator in it easily.
Just make a string of binary number and create an object as “BigInteger(string,2)” ( radix=2 , meaning the string is in binary format)
where for example string =“101110” that you want to store in the bitset.
https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html
It also contains the functions available in bitset like set bit and clear bit. So you may want to use this.
1 Like
it will not be tricky with biginteger library 
1 Like
https://www.codechef.com/viewsolution/38949407
I have tried numerous times but still not able to get even 50 marks. Two test cases from 50 marks part are not able to pass