SRM 535 editorial: The making of

The editorial for SRM 535 is up: link. I know exactly what you are not wondering. How are editorials made? More so, you are probably not interested at all in knowing how was this specific editorial made. And you have better things to do than read this post.

That's the reason I am going to explain it!

The ominous email
It all begins when I get an email by the topcoder contest director, rng_58. "We are looking for someone to write an editorial" it say. To me, that email is always a sign of ill fate to come as, once the admins get to the point of asking for editorial writers by email, there is a 80% chance I will be assigned to write the editorial. (Or is it 99%?) (This happens because no one else wants to write editorials). I always say that I have time to write the editorial, even when I do not. (Fear not, I have never delivered an editorial with more than an hour of delay, and if that happens it is rare and for strange reasons). Because I have the silly idea that no matter how busy I am, I am always going to finish the editorial in time anyway. This time, I knew that of the 48 hours limit, I was likely to spend most of the last 24 hours in class (Monday) or preparing for it (Sunday night). That didn't stop me!

There is something special about this editorial, it is the first time in more than 2 months that the problem set writer does not write the editorial himself. It has been two months without editorial writing and I was missing it. I was also feeling weaker in contests because making these editorials is the closest thing to practice I do.

How do you actually write editorials, considering that you are not so good in contests to ever solve the hard problem and rarely solve the medium problem?
Wow, that is a very specific question. Well, in reality the job of the editorial writer is not that much to solve a problem but to explain them. It is always possible to ask the admin for help on how to solve the problems.

With time I learned that it is best to right away ask for the div1 1000's solution. Without admin help, maybe I could solve the problem, but I would take very long to do it and there is a 48 hours deadline.

In fact, most of the time, what takes most of the time to write an editorial to me is solving the problems and that includes with admin help.

So, the first thing I did when telling rng_58 that I was available to write the editorial is that I would need the solution for div1 1000 right away. I have to accept I didn't even read the problem when I said that. Nevertheless, it was a wise move. This is what rng_58 sent me after assigning the editorial to me.

Quick comments on 1000:
Let's count the number of grids whose greedy path passes through (0,0) -> (H-2,i) -> (H-1,i) -> (H-1,W-1).
This is the sum of F1(a) * F2(b) * F3(c) * (S+1)^something * comb(H-2+i,H-2) s.t. a+b+c = S where F1, F2, F3 are defined as follows:

F1(a): The number of sequence of integers (x_0, x_1, ..., x_(H-2), y_0, y_1, ..., y_(H-2)) that satisfies x_0 + x_1 + ... + x_(H-2) = a and x_k > y_k for each k.
F2(b): The number of sequence of integers (x_0, x_1, ..., x_(i-1), y_0, y_1, ..., y_(i-1)) that satisfies y_0 + y_1 + ... + y_(i-1) = b and x_k <= y_k for each k.
F3(c): The number of sequence of integers (y_0, y_1, ..., y_(W-i-2)) that satisfies y_0 + y_1 + ... + y_(W-i-2) = c.

Here F1 corresponds to vertical moves between (0,0) and (H-1,i), F2 corresponds to horizontal moves between (0,0) and (H-1,i), and F3 corresponds to moves after (H-1,i).
F1, F2, F3 can be calculated by simple DP.

This is the moment by which you start to wonder [what exactly is vexorian getting a pay for?]. Well, I have wondered that a lot of times. As you can see the admins are perfectly capable of explaining any problem in just a few paragraphs. Apparently it is my job to add a lot of text around the paragraphs they send to me.

After receiving the email confirmation that I have been assigned the editorial. I procastinate. A looot. I remember that the very Saturday was the first time in months I actually played Starcraft 2. Gosh, I wonder why I even paid for that game. It is so annoying to have to download a whole patch before being able to play the game. Then I checked out if there are finally maps that actually have decent custom models. Something that was over 100 MB long seemed promising, but it turns out that such a popular Dota-like map was so large because it comes with tons and tons of music. And pirated music.

I have a rule not to ever, ever write any part of the editorial the first 24 hours of the deadline. Instead, I have to use them to understand the problems. This time, it was different, because given the circumstances it was better to try to finish the editorial before Monday (The deadline ended Monday night). But still, I ended up following the rule anyway.

The first parts are easy, I already solved div1 250. I have to open div2 250 and div2 1000 from the web site. It is usually enough to read those problem statements to solve the problems. The rest was spent focusing on div1 1000. It seemed hard. After many hours of trying to decipher what the text rng sent me means and how to use that to solve the problem (all while playing more video games and dumping all my money on used LEGO, like I do all Sundays). I eventually came up with the solution. By the time I was able to finish coding it, I noticed that the time is very tight. When the time of a problem is tight, I always switch to Java and make sure that the solution I am explaining works in Java under a second or slightly more. It was quite hard this time to adapt the solution to Java. I think the constraints were too large for this problem.

By the time I finished understanding the div1 1000, it was already Sunday late night. I had to go to sleep.

Normally in all the time between understanding the problems and writing the editorial, I think about what exactly should I write in the editorial. This is when I think of any picture. Any dirty trick to introduce a solution. Etc.

I woke up very early and did my best to smuggle writing the explanation for div1 1000 so that I can finish it before going to class. My Mondays this semester are quite awful because I have three classes, but scattered over the day, so I had little amounts of free time between each class. There was a period of about 1 hour between the time I arrive home at night and the end of the deadline.

Yes, that's right, I write editorials from hardest problem to easiest problem. I noticed that if I need to cut time I can usually write explanations for div1 250 and div2 250 very quickly. And in fact, that's what I do all the time the second after the match finishes. But larger problems can't allow such rush. So it is best to finish them while there is time.

Crisis averted
As I finished writing the explanation for div1 1000. I moved to div2 1000 (Which although easier than div1 500, had a far longer explanation). While I did this I noticed that I didn't really understand the solution for div1 500... Uh oh. There really wasn't time to ask the admins, and it is embarassing to admit when you can't even solve the div1 500. At that second, I printed the statement of div1 500 and the source code of one of the best score solutions (Almost everyone solved this problem doing exactly the same thing, with a couple of variations). My plan was to tinker what the solution did during Expert System class.

It seemed to work, but when I came back home I noticed that I didn't really understand the solution yet. I understood quite well what it does, but was not sure of why it works. During the match I managed to find a formula for the time spent by each employee, and also for the overall variable you would have to multiply to totalWork based on the previous formula. But I had no idea how the solutions handled the time. As my free time was ending and I was 30 minutes away of the next time I had to jump to a new class, I decided to do div1 250 and div2 250 and try to ponder div1 500 in the new class once again.

I was lucky, because the third class only lasted 15 minutes. The deus ex machina involved Professor having a reunion or something. I gained around 1.5 extra hours and I only had the write up for div1 500 left!

I was still pretty clueless for a while. Until I began to remove the time variable from my mind entirely. That's the reason the editorial begins saying that you have to disregard that variable. I began to write the editorial as I was figuring that out. I wonder if that's very noticeable, the first couple of paragraphs don't really have much idea of what the objective will be later. The part with the in-equation in the editorial is not just copying it, I am actually solving it right away and finding the rule at the same time as I am writing the editorial. I am not kidding, this explanation was very nice to me. While writing it I felt that everything made sense. I really wonder/hope it will have the same effect.

Corrections and stuff
Forgot to mention before, the div1 hard explanation is not the first thing I write in an editorial. The hardest thing to me is the cheesy introduction at the beginning of the editorial. So that's what I write first. It is also the first thing I correct after everything is done.

I'll admit that I only give a lot of time to corrections when there is plenty of time left before the deadline arrives. I was lucky that this time that thing happened. I am generally blind to my own mistakes so I try to look for things that look odd. This match is the first time I actually use a spell checker. I noticed plenty of mistakes in the editorial I wrote before so I decided to try to find a HTML editor that can spell check the non-HTML parts. I didn't, so I just opened the web page in open office. If it found any badly written word, I would correct it in the HTML source. Ironically enough, I could only find one badly written word using the spell checker this time. I am sure that if I did this with the last match I would have found at least 20 horrible typos.

Send the editorial, apparently wait 24 more hours until gets published, and it is done. Expect the voting inquisition, though.