SRM 511: And thus the good times end

I haven't blogged in a while, so here it goes: SRM 511, my rating was 2072, there was a good chance I would become red, but on the other hand it has been a good while since I lost rating, so I knew I had to lose rating eventually.

I was very expectant of this SRM, I knew all the possibilities: I could become red, I could get a small rating gain, I could lose a small amount of rating or I could drop back to 19XX. IMHO the worst possibilities would be losing a lot of rating or getting a small rating gain. One because it would put me back to 2009, and the other because I would be in the same situation as today.

It was 11:15 AM, and I was still waiting. I sent mystic_tc some messages about the SRM voting results (Now they include the rank numbers) and then... My ISP went down. Gosh , I was really mad about that, I waited and waited, by 11:55 AM it seemed that it was not coming back, so I went for plan B and decided to go to a cybercafe. I don't like solving SRM in another computer. For starters, you have to use windows. Then you don't have your plugins nor a local compiler so testing takes ages. I have also personalized my local testing quite a big deal (for example, I rely a lot on valgrind). It is also difficult to get used to programming in other screens, and then we have loud people playing DOTA (Which BTW blows). It is an awful experience.

I nevertheless had to accept my fate and went to have a SRM.

Div1 500 - FiveHundredEleven
Link to statement
"Fox Ciel and Toastman" somebody is having fun... I thought. So, we have these cards. Each card does | (binary or) and when 511 is reached you lose. I was really out of ideas on this one. Tried many things during the match.

511 is a small number, so we can have something exponential on the number of bits to remember which bit has been hit. The problem is how to remember which cards are left. There are 50 of them. For some reason I just couldn't get a working recursion because of this detail. So the number of states is something like 511*2^50 or other optimizations that turn too small.

I look at the division summary and Petr has already solved 250 and 500... (Note that this was early in the match just "some time" after thinking about 500. This tells me that Petr found both problems to be straightforward o_O. Many submissions for 500 could come, so I better solve it if I want a good position.

The other idea was to try learning a greedy approach. Then each player could use it and you would not need dynamic programming (and thus a good way to save the state would not be needed). The problem is how to think of one and prove it. (I am not sure right now if such an approach is possible.)

If Greedy was needed, they wouldn't have gone with such a low constraint (511). So I kept trying to somehow optimize the number of states.

If we take a card 1110 (binary) and there are other cards 0001, 0010, 0111, then all the other cards could become 1,0,1 after you pick the 1110 card because we can ignore those bits that we turned to 0. This was the main idea I could get but I couldn't advance from it (to either think of something greedy or to optimize the state).

It is getting late. Division summary kind of looks like a fast 250 was going to be enough for a good position, so I switch. What scares me is that many people have high scores for 250, so speed was going to be important and I was going to be slower due to the lack of a local tester.

Div1 250 - Zoo
Link to statement
Cats and rabbits... yeah having fun... I am initially confused about this. The scores made it look like a problem that can be solved by many with 242+ pòints. This thing didn't seemed so easy...

...until I start to wonder if the heights are unique, re-read and they are! Knowing that the heights are unique, then the set of rabbit answers and the set of cat answers would each be in the form: 0,1,2,...number-1. Where number is the number of animals of that species. For example, three cats would HAVE to say {0,1,2} and 5 rabbits {0,1,2,3,4}. Then we can iterate for the number of rabbits r (then the number of cats is n-r). If there are r rabbits then the elements {0,1,2,...r-1} should exist in the input. IF there are c cats then the elements {0,1,2,...c-1} should exist in the input, but an animal cant be both a rabbit and a cat. So, for each i less than min(r,c) there should be TWO elements in the input equal to i. Each of these elements could be a cat or a rabbit, so we have to multiply by two. Finally for each i from min(r,c) to max(r,c)-1 there should be EXACTLY one element equal to that i. For each valid pair (r,c) we add 2^min(r,c), that's the result.

Fun fact: Second Div1 250 that does not need a 64 bit integer as the result yet it uses it anyway.

I was lucky that my first code turned out to compile right away and pass all example cases. I submitted it. I would say that not having a local tester did not affect my score much. I got 227 points, I would say tht with a local tester I would have gotten 228 at most because I wouldn't have to manually click the test button so much to try all examples. Not a big deal.

Challenge phase
By the time I ended 250, everything was looking badly. A lot of people ended up submitting 500. I kept trying but I couldn't think of anything. My rank seemed very low before the challenge phase. I tried to prepare challenge cases. I noticed that The div1 500 - as usual - had very weak examples. For starters, besides a few special cases Fox Ciel always wins in thos cases. So I thought, what about a non-trivial case in which Toastman wins? I ended up trying 510,510,511,511.

When the challenge phase started, I opened my first 500 hoping to see a trivial mistake. Then I saw this state [511][2]. And that was when the solution to 500 finally hit me, but that's another topic.

I opened someone's 500 and noticed that he tried some sort of greedy thing. It looked odd. So I tried simulating 510,510,511,511 on it mentally, and it semeed that it would return "Fox Ciel". So I was about to challenge when I hesitated - Maybe I did not read something correctly. I re-read and while looking a way someone else already challenged it.

The match ended and I lost rating, but not that much, I think this was one of the best results possible given the circumstances. I am also glad that the ISP issues didn't affect my result much (This was really my fault for not solving 500).

Back to Div1 500 - Zoo
The idea was actually very simple. When you pick 01110 and there are cards 00101 and 11101, then they can become 1 and 1 and we ignore the other bits, remember? Well. In fact, this also means that they could become 01111 and 11111. Or rather, we can just represent the state as the current total bit-wise or current. Then all cards would get affected by it. How do you know which cards you have picked yet? All those that are subsets of current could have been picked before. For example, we could just apply current to all the cards. After picking 01110 the other cards become 01111 and 11111, the cards that are equal to current after doing this could be used cards, but maybe some of them are not used and are just unused cards that turned "useless" (Cannot change the state if you use them).

In order to handle useless cards, note that once cards are made useless, their values do not matter, only the number of useless cards. The number of useless cards can be found if we remember the turn number. Turn number - number of cards that could be used = useless cards. We can use 'use' one of these useless cards by increasing the turn number. So, a recurrence (number of turns, current) that returns ture if the next player to pick a card loses can solve the problem.


Sorry if the blog is more vague than usual, I am still without an internet connection at home, so I am doing this once again from another computer :(.