SRM 590 recap and editorial

Another week another Topcoder match. Not a great day. I had a bad flu and still do.

Div1 500: The one with Xor

Given a list of cards with numbers on it count the number of subsets that give a total binary xor value less than or equal to limit.

I actually got close to solve this problem though I started with dumb ideas about dynamic programming. I actually even started to code a bad dp solution. I noticed in the middle of the code process that it didn't make any sense. Too much dependency between decisions and no way to order them.

I figured that it was possible to reduce it to the exact case instead of <= case, and I noticed "We can create a condition for each bit, then we just need to count the number of ways to follow those conditions". For some reason though, it never occurred to me that this meant "System of modular linear equations". I am disappointed because I learned to count solutions to those systems just recently, when writing round 2A's editorial .

Div1 250: The one with pawns

You have a row of cells . Some pawns on the cells can only move right, some can only move left. Is it possible to reach a given configuration?

With only 10 minutes left before the end of the coding phase. I felt like the solution was going to be tricky to code. For some lame reason I thought of trying a bipartite matching. While that was technically correct, it turns out that a bipartite matching didn't make the problem any less tricky. I took long to code a solution, and the first version was going to fail system tests anyway.

When challenge phase started, I thought that this problem was challenge material. I did find a wrong code in my room, got 50 points thanks to this. I think that these 50 points prevented me from losing my yellow rating.

Editorial

It is up: SRM 590.

There were a couple of problems that gave me ... err ... problems when explaining them. Div2 easy and div2 medium are the sort of problems I don't like seeing in a SRM I am writing the editorial for. Too obvious of a solution and I felt like there was nothing to explain really.

For div1 easy and div2 hard, I was going to show a much more complicated solution. It was not until today at 5:00 AM when I noticed that I was not sleeping at all that I noticed that there could be an easier idea.

Not sure I like my explanation for div1 hard. Not sure if I explain how to get the solution or just the solution itself.