SRM 509

The Editorial for SRM 509 has been published. Lately I have been writing many editorials, it appears that all the other approved editorial writers have gotten a life. This is probably a good moment to try a recap.

I felt the pressure since the beginning of the match, I had reached my maximum rating after two years, and I noticed that I have been in a very good streak. The streak will eventually end, and this match was decisive, I could either continue earning rating or once again drop back and delay the trip for another 2 years.

Div 1 500: PalindromizationDiv1
At first it seemed like a complicated problem, then I said to myself "Why? It is just the usual palindrome problem, try each substring in a dp). So I begun to try to write that problem. I eventually noticed that it was not as simple. While coding the simple solution, I could see that maybe it would be necessary to change the letters to other values before trying another change or a removal/addition. So I was doing a 26*26 loop to find the new values, that's when I thought to change the dp state to (substring limits, new value of word[a], new value of word[b-1]). So I implemented it, and I had bugs. I overcomplicated everything because I couldn't estimate a good bound for the final result, so my INFINITE constant was 64 bits long and I had to use 64 bits numbers everywhere. Of course, simple logic would tell you that the return type of this problem is int, and the problem setter did not specify what to do if the value is higher than the return value, so most likely the answer was going to fit an int.

Eventually, I noticed that the recurrence had cycles, and cycles + memoization do not get along. So I added another parameter that could be 00, 01, 10, or 11 (in binary) and held two boolean values, one for each side of the word if it is assigned or not). And it passed the examples, so I submitted it.

This is of course very wrong. But I really did not suspect it at all.

Div 1 250: LuckyRemainder
After checking the division summary, I thought to myself that it should be possible to score 240+ points in this problem, and perhaps necessary to get a good position and insurance in case the 500 points problem fails.

For some reason, after reading the problem I thought that you just needed to take each digit and multiply by 2^n-1. This originated from misreading something. After implementing this solution, I was getting a wrong answer. So, I re-read the problem, and noticed that I was supposed to multiply by powers of 10. So I went to code the overcomplicated solution that I ended up submitting:

sum = 0;
for (int i=0; i<n; i++) {
    //For X[i]:
    for (int k=0; k<=n-i-1; k++) {        
        int y = pow(2,i);
        //There are y ways to append the numbers to the left of X[i] to it.
        
        int z = pow(10,k);
        //We are considering only X[i]*10^K
        
        // Combinations(n-i-1, k) ways to pick k digits out
        // of the n-i-1 digits to the right of X[i].
        
        sum += (y * z * C[n-i-1][k] * (X[i]-'0') ) % 9;
    }
    sum %= 9;
}

It ... was ... still ... failing the example cases. Before I melted down, I was lucky to find out that , at the end I was just doing a (return sum). What is the problem with that? Well, the issue is that it was supposed to be (return sum%9).

In fact, the lack of the %9 at the end was what caused the original X[i]*(pow(2,n-1)) solution fail. That solution was correct, although not because of how I misread the problem but because powers of 10 area always 1 modulo 9. If I actually had sum%9 in the return of the original problem, I could have gotten around 246 points out of sheer ant total luck. Instead I ended up with very low ~220 points.

Since I had very low scores for both the 250 and the 500, and many, many people submitted something for the 500, I was actually in a very low position. I decided to make sure the problems I correct. I kept triple checking everything and all seemed fine (It was not). When there were around 5 minutes left for the match, I decided to try to find challenge cases. When first reading the constraints for 500 I first thought that equal operations but with different costs were allowed, so I took care of that. When I tried to craft a case for solutions that did not consider that, it turns out that the constraints actually specified that they were not allowed.

Second try, I also noticed that change operations are uni-directional. I also noticed that when I changed the solution to believing that change operations work both ways, it still passed the examples. So I tried to craft a case that made such solutions fail. I ended up creating: "vex", {"change s v 1", "erase x 1", "add s 1"}. (Never miss a chance to sign your challenge cases when it is possible).

My original solution returned -1 in that case, but if I made that solution consider bidirectional change operations, it returned 3.

... Wait a second, that's when I noticed that 3 is actually the correct result for this case!. But not because of considering "change s v" equal to "change v s", but because it is possible to first erase x, then add s and change s to v. That is something I completely failed to notice! But at the same time, just after I noticed that my solution was wrong, coding phase ended.

Challenge phase
That test case led me to notice that there are many, many things to do in div1 500. It also helped me notice that the example cases are very weaks. Before the challenge phase I whispered to the admins that I think they are probably preparing themselves to watch a challenge phase spectacle.

With a failed 500 and a slow submission for 250, I knew that my last chance was to have a successful challenge, and that with so many submissions for 500 in my room, it was going to be perfectly possible.

For a second , I considered using my challenge phase on all the solutions, but I am not so aggressive. So, I just opened the solution for a blue coder, but not the lowest rated blue coder, because that's where aggressive challengers usually begin to challenge. After reading the solution a bit I noticed that it was only considering the add operation once and not combining it with erase or change. So, I gave it my challenge case and it was successful.

I tried to challenge more solutions, but I wasn't so lucky, every time I considered challenging someone, the solution already got challenged. I also noticed many clever things like using Floyd-Warshall, that is something I should have tried.

Outcome
Thankfully, my successful challenge was good enough to reach top 140. Which was exactly what I needed to reach 2100 rating. There is a red stripe in my rating graph! This was my dream objective of the first semester of 2011, so I am glad. But this will only increase the pressure in the upcoming matches.

The editorial
After the challenge phase ended I could not really write a blog post explaining the problems, for once because I still didn't have a good idea to solve div1 500. I knew how to solve it using transitive closure in a way like Floyd-Warshall, except that also reducing the add , remove, and change operations including the other operations in between but boy was that hard to implement and explain. I then had to go do a very time consuming, unrewarding group assignment.

I was once again, assigned an editorial. I still had the problem of not knowing an explainable solution for 500.

One of the many things I thought of while trying to come up with an easy solution for 500 was Dijkstra. If you consider it, it is never necessary to add a character to the left if the left most character is not equal to the character in that position in word. The same happens to the right side. So, you can represent a state as [a][b][wa][wb] , where a and b are the limits of a substring and wa, wb the current characters in those limits. Dijkstra because the graph is cyclic. So, in each state, you can remove characters, modify them or add characters (just make sure not to ever add a character to a side if the letter in that side is already different). I thought that there are 2500*26*26 different vertices and 50 edges, so Dijkstra was supposed to work. After implementing Dijkstra, I was disappointed to see that it timed out on exactly one case. Apparently the overhead was too large.

I eventually decided to open the writer's solution in the practice room. It was genius. The idea to use an empty letter as a valid letter, so an add operation is a change from LAMBDA to 'a'. This is the solution I explained in the editorial, and it makes everything so nicer.