tag:blogger.com,1999:blog-29632375.post7821912860452579785..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Topcoder SRM 543 - The non-fail shockUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-29632375.post-74041762682760529432012-05-21T06:53:26.301-07:002012-05-21T06:53:26.301-07:00Hi. Thank you for 500 explanation. It was fun to o...Hi. Thank you for 500 explanation. It was fun to observe there was no same solutions for xor problem. I can explain O(1) for 250. Here it comes...<br /><br />Consider xor result for sequence [0..N]. While the calculation the last bit would have a period of 4: 011001100110... and reminding bits would have period of 2. That's why we can treat them differently and finally merge to one number.<br /><br /><br />struct EllysXors {<br /> long long solve(long long n) {<br /> // for last bit calculation we must xor last and last but one bits<br /> long long lastBit = ((n / 2) ^ n) % 2;<br /> // the reminding bits comes to 0 for every odd number in sequence<br /> long long residue = n % 2 == 0 ? n : 0;<br /> // replace last bit in residue by lastBit<br /> return lastBit | (residue & ~1);<br /> }<br /> long long getXor(long long L, long long R) {<br /> return solve(R) ^ solve(L - 1);<br /> }<br />};Boris Dibrovnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-69883507066866859012012-05-20T19:53:37.755-07:002012-05-20T19:53:37.755-07:00Another alternative 250 approach: if x is even, t...Another alternative 250 approach: if x is even, then x^(x+1) = 1. Further, if. Is a multiple of 4, then the range from x to x+3 xors to 0. So, removing cases where r-l is small, you have to XOR a maximum of 8 numbers. <br /><br />Either way, thanks as was said above. These are fantasticd editorialsConnect4https://www.blogger.com/profile/12685291269427383239noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-41830945837057322892012-05-20T11:19:05.706-07:002012-05-20T11:19:05.706-07:00I love your explanations.. So clear to understand....I love your explanations.. So clear to understand.. and every time i learn something new about the language as well.. Keep writing the editorials..max_ashinoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-38276627452048411952012-05-20T06:12:52.208-07:002012-05-20T06:12:52.208-07:00I actually had quite a mistake in the explanation ...I actually had quite a mistake in the explanation of 500. The updated paragraph is this:<br /><br />{For the bottom right example, consider that E(M+1)-E(M) is smaller than E(M+2)-E(M+1). Once again, the derivative. Just imagine the straight lines, as the height increases, the differences of the lengths of the lines increases. Take the derivative of the Euclidean distance in case of doubt.}<br /><br />It used to say basically the opposite :)vexoriannoreply@blogger.com