Topcoder SRM 543; A lesson in initializing your variables

Topcoder SRM 543 could have been my best performing SRM, and I was pretty sure before the systests update for me, that it is going to be so. I was bound to end up in the top 10, what with my quick submission to easy problem, reasonably quick submission to medium, and three successful challenges. But there were surprises in the wait for me, and not happy ones.

DIV-2 Medium; EllysXors:

The naive implementation for this problem is straight forward. Just calculate the xor of all the integers between L, and R. This is going to fail the time test though, as the upper limit on R is 4*10^9. So we need to figure out some optimization. I ended up calculating xor of numbers from 1 and sequentially to upper limits, using a quick Python script, to figure out that there is a pattern to xoring numbers. A quick googling confirmed my observation, and amusingly, actually lead me to a complete solution to the medium problem. Let f(N) be the xor of all the numbers from 1 to n, then we can define f(N) as

f(N) = N if N=4*k

f(N) = 1 if N=4*k+1

f(N) = N+1 if N=4*k+3

f(N) = 0 if N=4*k+3

So for our problem of finding xor of numbers between L to R, we can define f(L, R) = f(R) xor f(L-1). This is because xoring with the same number twice, cancels the effect of xoring, so when we find out f(R), we can xor it one more time with numbers in the range 1-(L-1) to cancel the effect of those numbers, and thus we have our answer.

DIV-2 Easy; EllysTSP:

Surprisingly, a lot of people took quite some time to solve this one. All you need to notice is that between the numbers of cities and villages, you can visit all of the minimum occurring place, because you just need to start at the place that occurs more. Once you start with the place that occurs more, lets call it X, you will be able to visit all of the other type of places, and return back to another X, if it exists. That makes a total of 2*min(cities, villages), plus a 1 if number of cities!=villages.

Unfortunately, I forgot to initialize my counter variables for villages and cities. While this worked on my local compiler which is an llvm-gcc, I failed systests. A little warning from the compiler on topcoder would have helped, but I got no warning, and thus didn’t bother initializing the variables. BIG MISTAKE!

Challenge Phase:

It was a fun challenge phase. Lots of submissions got challenged. My medium survived a challenge, while 3 other participants couldn’t survive my challenges. ;) A failed easy problem took me from top 10 to something in 70s. Bummer, but I took home a lesson.



Be Sociable, Share!

Leave a Reply