Thursday, October 13, 2011

SRM 521: Meh

So, after the disaster from SRM 520, I tried to recover rating. Wanted 2000 back. I think I was really close but I made a terribly bad mistake.

Div1 500
Didn't like this match mostly because of this problem. At first it was hard to understand and it had an ambiguity in the statement. Later it turned out that I still didn't understand it correctly even after the intermission phase.

Div1 250
When there were 14 minutes left I opened the 250. I knew I should be able to solve it in under that time. I saw very high scores for this problem. In fact, hundreds of it.

It was a very easy problem. Too easy, to be honest. Worse, it seems it appeared in Codeforces last year:

I solved it but I was failing examples. After a couple of seconds debugging I find the mistake, and get 246 score. That was bad, because with 246 you get position 200+, but with 248 you get 100+.

At first, I got lucky because I found a wrong solution for the 250. Someone was checking for the sign of the number of open parenthesis before changing it instead of after. So a simple ) was enough to challenge it.

Later I really screwed up. With the 296 score I had a very good place, and 50 points wouldn't improve that position. -25 points would really break the position though, so there was really no good reason to try any more challenges. Yet I did, and I did it because I misread a min() as a max() function. Without this mistake I would have returned to 2000+ rating.

To make matters worse, it seems that the 1000 was easier than the 500 and had many successful solutions.

And here is an explanation for the div1 250
The problem asks for you to fix a sequence of parenthesis: (())()( so that it becomes correct adding the minimum number of parenthesis.

We will go from left to right and for each open parenthesis, increase a counter and for each closed parenthesis decrease it.

If the count becomes negative, then we have too many closed parenthesis. It is best to add an open parenthesis right before the newest closed parenthesis we found. Then we have to set the count back to 0.

At the end, the count may be non-zero, this means there are too many open parenthesis, it is best to add just as many closed parenthesis.

No comments :