Some late SRM reports

I have not been logging things correctly into my blog, so I will try to do some recap.


SRM 498: A most horrendous rating drop. This SRM made me notice that the Hard-medium-easy strategy was not working. Case in point, due to it being justifiable for me to do badly when using this strategy, I was not taking SRMs seriously. I failed the easy problem because of not doing a O(n^5) even though everything indicated it would work fine. For some reason I thought that this time, doing ad hoc checks was going to be simpler to code than a n*n*n*n loop. Although in a way it was, it was very easy to miss a single mistake which was not caught by the example tests. Blunder: Trying clever code instead of one you know is going to work is not a good idea. It is going to take a while to recover the 145 rating points that were lost that day.

SRM 499: I decided to move to a new strategy which is similar to the one I was using until 2010. I start with the medium-difficulty problem first. However, instead of switching to the easy when there are 30 minutes left, I wait until there are only 15 minutes left. This way, I will force myself to take the medium more seriously than before, and also to be fast at solving the 250. I was tired of taking whole half hours to solve the "Easy" problem, I'd rather get 0 points...

This match's results were nice, they gave me hope about the new strategy. After trying the 500 problem for a while, I got very close to the dp solution, but I was having trouble with some of the example cases. I had to switch to the easy problem when there were only 15 minutes left. But it turned out to be a very easy problem that only took me 4 minutes to solve. When I returned to the 500, my mind was refreshed and it finally struck-me : I had cycles in the recurrence. Before doing memoization, always make sure your recurrence is cyclic, it is the basic thing to do. I managed to fix the cycle, and submit. Everything went well.

I was assigned to write the editorial for this match. I think the 1000 points problem was very nice, but that's probably because I don't usually get the chance to see Strongly-Connected-Components used in problems that are not easily simplified to them.

SRM 500: Did not like this match. I think that a harder than usual 250 was not suitable for a celebration kind of match. It became a downer. Actually there were some other old timers in my room and we were all saying basically the same during intermission. The 500-pointer was nice. I actually had something that resembled a correct solution to it but had problems debugging it. I made the mistake to switch to the other problem at a very bad time. I should have switched much earlier or not switch at all.

Member SRM 501
I open the 500 first. I was able to think of a dynamic programming solution very quickly. So much that I initially thought that the challenge in this problem was that O(n⁵) was not going to work and O(n⁴) was required. But I noticed that with memoization you can do plenty of cropping if your recurrence includes the current sum and also that the constraint for the length was 40 and not 50. Those things gave me enough of a reason to try and code the O(n⁴) solution and try it in the worst case. It turns out it solved the worst case - an array full of -1 - in less than 0.8 seconds.

The easy was a different story. At first, I noticed that it is probably never necessary not to do all the additions consecutively. So operations are always in the form BB...BAA...ABB..B , the first B operations do nothing because they are multiplied with 0. Then the other ones multiply nA * a (The result of all the additions). I unfortunately make the mistake to, after reading the examples, assume that the number of times to multiply b is either 0 (When it is not convenient to multiply at all), nB (When it is convenient to multiply as much as possible) or nB-1 (when the factor b is negative, it pays to do multiply only an even number of times). This passed the example tests, and I submitted the solution. But I had many doubts.

Blunder: nB was actually constrained to be less than or equal to 50. I could have actually just picked all possible values of t=0,1,...nB to raise b to before multiplying it to nA*a. Instead, I only picked 0, nB and nB-1, this was an unnecessary assumption.

I had my suspicions after noticing the low constraints for nA and nB. Tried to make a dynamic programming solution, but I was unfortunately having issues implementing it correctly. Blunder: I switched to the 1000 points problem before making sure the 250 was correct. Some time after, I noticed I really had no clue how to solve the 1000-pointer. So, I kept opening 500 and 250 trying to find typing errors. I eventually figured I could just code a bruteforce solution for 250, that would only work when nA+nB<=10, so I could call both of my solutions with random cases and see if they always agree. After finishing the bruteforce solution and making a program that would generate random cases for the solutions, it didn't took the random number generator much time before finding a case my original solution failed: {1, 8, -2.097, -0.883} After some inspection, I noticed that in that case we need to multiply b exactly once. This is the moment where I finally noticed that I can pick any number of times to multiply b between 0 and nB. After changing the solution to do that, I ran the random number generator again, and it was not finding any mistake. I submitted the new solution, but a long time had passed since the first submission, I ended up getting only 79 points for it.

During the challenge phase, I knew that the test case I found during the coding phase was going to make plenty of solutions to fail, but I just couldn't find the wrong solutions, and parse them well enough to notice they didn't resist that case before they were challenged. After the match I noticed that if I just used that challenge blindly on all the lower rated coders in the room I would have been able to recover all that I lost because of the resubmission. But I am not really an aggressive challenger, and I am not sure how well this sort of blind challenging strategy would work in general. What I can tell is that aggressive challenges are not my style, so I am probably not going to try it soon.

I am not sure if the 500 was too easy or if I am just too used to dynamic programming problems. I could tell many of the submissions had very long, complicated codes for some reason.