Monday, April 13, 2020

A cheese week

Codeforces hosted its Round 631 during the Mar 30 - Apr 5 week (problems, results, top 5 on the left, analysis). I had a relatively good start on the first four problems, but could not make progress in the last one and switched to challenging with about 20 minutes remaining, also without success. Um_nik, on the other hand, had an even better start and did not give up so easily on E, earning the ultimate reward of being the only contestant to solve all problems. Great job!

When solving problem C, I could not come up with a solution analytically for quite some time, so I've used the adage "so many people got it accepted, the solution must be simple!" and started thinking in terms of what a simple solution might look like. I've came up with the [ultimately] correct greedy very quickly, but could not prove that it works. After some more time, I've decided to just implement and submit it, relying on pretests and the adage to help :)

When this approach works, it is satisfying, but I feel that using it might be detrimental in the long run: it greatly reduces the motivation when solving the problems analytically, the opportunity to just start submitting good-looking solutions is too tempting. Or maybe it really is a part of the game?

Thanks for reading, and check back for more!

7 comments:

  1. What do you mean by solving a problem "analytically"? Is it proving before submitting? I don't think you mean that...

    ReplyDelete
    Replies
    1. By "analytically" I mean trying to make progress not with ideas "out of the air", but with trying to dissect the problem, find sub-problems that one can solve, and so on. Trying to pinpoint where the difficulty lies and how it could be overcome.

      Delete
    2. Well then, I think most construction problems cannot be solved analytically, can they? I have never solved a construction problem by trying to pinpoint where the difficulty lies, but you are Petr Mitrichev, so who knows. :)

      Delete
    3. Well, I think it depends on the problem, but they often can. In this particular case, I think one could arrive at the greedy solution analytically by saying: "we would like to always remove the largest element, as that would mean that the smallest elements will remain, and the largest element is always in the root. But that can lead to the final tree having incorrect shape. But is it the only blocker? In other words, if after removing the root all the top g layers of the tree are still filled, is it always optimal to do so? Well, let's try to build an exchange argument to prove it..."

      Delete
    4. In fact, I did use some version of that argument to come up with it during the contest, I just didn't even try to build the exchange argument.

      Delete
  2. This is the first time i read your post and I am going to do it again.

    ReplyDelete