I am writing this before the match starts. For obvious reasons, I won't publish it until the end of the challenge phase. But please keep in mind I am writing this with no info on what will happen during the match.
So, last Friday after pushing for months to receive attention for my problems, I was asked if I was going to have time to problem set SRM 538. I accepted immediately, then noticed that there were four days left for it. I was focused on SRM 537 which was the next day.
I was nervous. Of course I have time to develop the problems and do all in 4 days. But the problem is that in four days there may not be enough time to have complete feedback cycles with testers.
At the end the development of the match got quite the obstacles. But we were able to come up with something that looks like a match. Hopefully it will not be tremendously hated by everyone, but I expect it to be. I am rather sure that nobody will solve either hard problem. Division 2 will be much harder than usual and division 1 much easier than usual. And division 2 prefer easy sets while division 1 prefer hard sets...
div2 300
This problem seems to me harder than usual. Nothing much to say about it. Other than I think it is cute.
div2 500, div1 250.
For a long time I had a dream of a problem that seems to have an easy solution that is almost a one liner but (unlike what became frequent) is actually wrong and you need to do a more complicated thing. But I couldn't. The closest thing I could do is this problem, which has two very easy solutions, but one is wrong and the other isn't.
I tried very, very hard to make people likely to get fooled into thinking the easy solution is correct. I really hope people fall for it. The whole objective of the problem is to punish anyone who enters an easy solution, passes and then does not bother asking himself why it works at all. The correct solution is itself very easy though, but hopefully people that rush into things are more likely to think of the wrong solution.
At first , the problem was about "Mr. K" claiming to solve the traveling salesman version of this typical Cartesian plane problem. And so the whole parity thing was about that. But misof thought adding a fake problem first was too confused. I sort of agree, so I preferred to remove the funnier story in exchange of an easier to follow problem.
div1 450
This problem is easy, but also cute, like the div2 250. Nothing much to say other than I do not really have a formal proof, but rng_58 claims to do. So, it is all good and dandy.
div2 1050 and div2 1050
I thought of this problem for months, yet I didn't really get to understand them fully until ... yesterday. These problems are evil and I doubt anyone will solve them during the match.
If I had a little more time, I would have come up with a different div1 hard, and swapped div2 hard with div1 medium.
We found so many mistakes in our solutions during development that I know for sure these problems are evil and will open the gates of hell. The Mayan 2012 apocalypse may be triggered by them.
But I did try to make the example cases as strong as possible, specially in the div2 hard.
---
End of predictions, now some comments about events during the match:
During the match
9 minutes after the start of the match. I figure out that the div1 hard statement does not explain what the B argument was. This was caused by a last minute language update of the statement that somehow missed it. Sorry.
- Many people are surprising me with a different (wrong) solution for div1 250 / div2 500 that I didn't expect.
- It is surprising to me that the tests for div1 450 were so weak some solutions that do not even do the dp and just sum the angles together are passing examples.
- Someone asked us what value of PI to use. Then I noticed div1 450 didn't have the usual note about relative and absolute error. Damn.
- 55 minutes after the start of the match, Egor makes a submission for 1050!.
- Sometime later, bmerry does the same thing!
- Later: What a humongous amount of div2 hard submissions! I am impressed.
- In the challenge phase, dolph was genre-savvy enough to blind challenge Egor right at the beginning of the phase. That was impressive.
- Many people actually got the typical issue with %2 and negative numbers, but that's very strange because I made sure to include a example case that detected that bug. Apparently, it was possible to make the bug with some slight changes from what I tested and pass the example cases. That's too bad. I'd hate failing for this bug.
Tuesday, March 20, 2012
Subscribe to:
Post Comments
(
Atom
)
11 comments :
Sorry to anyone who got overflow bug in div1 450. I really didn't expect that to happen. The problem is that my solution saves the total forward and backward commands in a double, so I never got the chance to make this mistake.
Ok. This was evil, but still nice.
I must be the only one whose 450 failed because it exceeded the time limit.
could you explain how solved the div2 550 problem.
It is so easy it is offensive.
The path must finish at one of the points in the arrays. What's funny is that the parity of the path depends solely on the last cell visited by the path. So, parity = 0 is always possible when there is at least one even cell (x + y is even) in the input and parity = 1 is always possible when there is at least one odd cell (x + y is odd).
thanks vexorian:
sorry for the offense, but my level is negligible compared to yours, I'm still in college and recently starting to compete in TopCoder.
I didn't communicate correctly.
The problem is offensive, once you find out the easyness after trying a lot of silly stuff. This problem offended me because I first thought it was a cute cuadratic time dp problem and then rng_58 said to me that it depended on the last cell, and I felt like a fool.
I am in college :/
I also correct it:
I'm still in high school, this was my first SRM.
Achieve do DIV2 300, 550 TIME LIMIT.
What advice would you give me to do better in my second SRM?
I would appreciate the advice of a master like you.
The allowance that each point can be visited more than once made final answer of div2 500 depend only on last step.. But had this nt been allowed i.e. Had problem mentioned that each point must be visited exactly once, then how would have been the solution? Would Ur initial intuition of "cuadratic" dp help? (i heard that word fr first tym..:O )
P.s.- ur hard wrk paid off n many in our room got fooled for wrng easy solutn of div 2 500.. :(
Nice SRM, I competed in Div2. I got correct solutions for 300 and 500 (sweet easy solution btw). After the match I solved 1050. The 1050 I first misread and thought you had to use all cubes, which results in a little more difficult problem.
The original version of the problem required you to use all cubes. The div2 1050 is still doable (you do need to keep a reference of the minimum and maximum possible slots) and so is the div1 1050, but it adds two time factors to time complexity and one to memory. I dropped the idea because I found out my solution to that version of the problems was wrong, barely one day ahead of the match...
Post a Comment