Saturday, July 21, 2012

SRM 550: I regret nothing!

I wrote SRM 550. The editorial is coming soon-ish. I will use this entry not so much to explain the problems (will do in the editorial). But to comment about the match.

I was assigned this match on Thursday. I had something that looked like a match but not a very complete proposal. Was looking more to first confirm something in div1 hard difficulty before getting a match. But I think the admins had difficulty finding something better, and I was the one with the closest thing to a div1 hard (we really thought the problem that was ultimately used as a 850 pointer was not hard enough.

Those two days of development were intense. We replaced many problems with other problems. Most of the difficulty in the 850 pointer comes from nice modifications from rng_58 and mystic_tc.

This 850 pointer turned out to be the big screw up of the match. Just as the contest started, lyrically was already reporting bugs with the statement. Later Petr found out we did not have a constraint that specified that only a,b and c are allowed in the input. And ir5 got confused about something - apparently, the statement was never clear enough to say that each letter is changed one at a time.

Ultimately, it turns out that the 850 points problem was actually normal div1 hard difficulty and not deserving of the low score value. What happened? Maybe the statement was too confusing? Seems not, because we did not receive many complaints about this. Apparently, we tweaked the original version of the problem (only moves a->b, b->a , max cost <= 3, length <= 33) so much that we turned the problem that seemed like a div1 600 at best into a legit div1 hard.

But besides div1 850, I regret nothing!.

Q. Please stop writing problems*

A. No sorry, can't do. This is part of what I do for a living. And it is always fun. The only viable way in which I can stop writing problems is if admins stop accepting them.

If you are interested in traveling to the past and stopping me from writing this match, a good fix would have been to give the admins an alternative to my problem set so that they did not have to use mine for this SRM in the rush of two days missing.

*Actual quote.

Q. Example #5 in div1 300/div2 550 is wrong/ do not get why it is wrong / etc

A. We got this a lot during the match. No, it was not wrong.

We decided to include this example and many others to make sure the success rate stayed high in this problem. So, yes, you should be happy this case was in the examples...

To be honest, I intended this problem as an easy problem for TCO rounds like round 3 or maybe the semifinals. The original version had movements < 1000000000. I had to use this problem for a normal SRM unfortunately, because the previous problem idea I had available fro this slot turned out to be a very tricky problem. That is right, we used this problem because it was the least tricky problem available for div1 easy.

My post there explains it.

Q. Div1 500 is too mathematical!

A. I call humbug!. When I thought of this problem it was because I had an assignment that said "Design a cell automaton to generate Sierpinski's triangle". It turns out this task was rather standard and everybody knows how to do this triangle from top to bottom (Using Pascal's triangle modulo 2). Yet I somehow thought of a solution for the assignment that does it diagonally.

I thought I could capitalize this strange idea - This fractal triangle is a very easy fractal, and I really like this fractal. So I thought of this problem that can be solved by two steps: a) Find out the pattern is a fractal. And b) Use simple recursion to generate the fractal for each requested cell.

So, to me, this has always been a problem that is meant to be solved through programming (recursion). All those guys that used a formula related to combinations and modulo 2, well, you used that formula because YOU are Mathematically-inclined, not because the problem is Mathematically-inclined :). I am more of a programming-inclined guy, so I was not aware of those formulas until the admins told me :)

4 comments :

Balaji Ganesan said...

please don't take offense. i'm a MediocreCoder but div2 550 problem statement could have been better written. i was in a hurry and just ignored example 5 and submitted my 'wrong' solution. other than example 5, no where does it mention that hitting the wall is the only way for the robot to turn 90 degrees. and since you also said that manual operation is possible, its only fair to 'wrongly' assume that manual rotate was also possible.

one of the things that makes TopCoder a whole lot better than Codejam/Codeforces is that it tests programming ability instead of reading comprehension. i wish it stays that way.

vexorian said...

" no where does it mention that hitting the wall is the only way for the robot to turn 90 degrees."

It does, explicitly:

If a step forward does not cause the robot to break the above rules, the robot takes the step.

"Otherwise, the robot rotates, "


"since you also said that manual operation is possible,"

But it does not say that. It says that the program can be terminated manually.

---
If an example case seems wrong to you ask the admins. In this match we would have replied that the example is correct. If the admins tell you that the example is correct, then no, you should not submit a solution that fails the example.

If I would do it again, I would have added an annotation to example 5. But I really think that the problem statement was unambiguous about this and the only thing anyone needed to do to understand example 5 was just draw it in paper. The bullet list is really a program for the robot, and reading and understanding a program is part of what it takes. Simulating a robot's movement in paper is as much of a part of "programming" as it can be.

PS: The problem statement was rewritten by misof. I just provided the original draft of the statement. I think that he did a good job. If the sentences of the statement were really ambiguous I would be in trouble right now, but I have to thank misof because every sentence is very well-specified. All the questions I received during the match were NOT about ambiguity with the statement but about people wanting the admins to explain example #5 to them. We couldn't do that, because plenty of coders solved this example correctly and understood it without admins explaining the case explicitly.

vexorian said...

It indeed becomes a problem when the problem has many examples.

But if a problem has a lot of example cases, then you really have to check them all. A problem with many examples means it is really tricky.

I think the best alternative is to use an Arena plugin. They run all the examples at once without clicking, so you don't lose a lot of time when there are many examples. And you could have noticed example #5 fails.

I use KawigiEdit, but there are alternatives like FileEdit, and some funny sounding things like Moj? Check the plugin forum for more info: http://apps.topcoder.com/forums/?module=ThreadList&forumID=148126

dave said...

It was indeed very kind of you to include testcase 5 in div1-300. Luckily I was too asleep to compete in this round. Problem Statements were great, looking forward to seeing your round in near future. I love problems with short code but hard thinking.