Topcoder SRM 575

This was one exciting SRM. I started off very badly. It took me long while to figure out the easy problem. I was the second last to submit it in my room, getting a very low score. Fortunately, medium was an easy game theory problem, and I was able to submit it fast. At the end of coding session, I was somewhere in the middle of the room, score wise. In challenge phase, I was able to get two successful challenges, while lots of other players tried failed challenges. I ended up being at the top of the room after challenge phase, which was very surprising given my totally disastrous start to the match. Both of my problems passed system tests, and I got a +64 in rating. Yay!

DIV-2 Easy; The Swaps:

This problem asks for total number of permutations possible of a given sequence, if you are allowed to swap only two elements. Starting sequence doesn’t count, as you must make a swap in order to get a permutation. Trick is that there can be duplicate values. We can easily calculate number of possible permutations if we swap any two non identical elements, by counting all non ordered pairs of their indices (i, j), where sequence[i]!=sequence[j] and i<j.

What about swapping identical elements? If there are any duplicate elements, if we swap any two of them, we will only generate our starting permutation. So this allows us to count one more possible permutation in our final result. If there are no duplicate elements, we can not generate our starting permutation with a swap and thus won’t count it in our final result.

DIV-2 Medium; The Number Game:

This was a simple game theory problem. There are two players, John and Brus. They are given an integer N. John takes first turn, and subtracts any factor of N other then 1 and N itself, from N. Brus does the same in his turn to new integer that John’s step generated. If anyone of them can’t make a move, he loses. We know that if N=1, player whose turn it is, loses. With this base case, we generate results for values of N greater than 1. For any N greater than 1, we see whether subtracting any of its factors from it takes it to an integer that is a losing position for the player whose turn it is next. If yes, then N is a winning number, otherwise it is a losing number.

Conclusion:

Even with a bad start, I ended up pretty good in rating. Which is cool. I did try the hard problem and could make sense of what was required. Unfortunately couldn’t come up with a working solution in time. Must try it in practice room.

Be Sociable, Share!

Leave a Reply