Egor's blog

Google CodeJam World Finals
By Egor, 13 years ago, translation, In English

Google CodeJam World Final will be conducted on July 29th at 9:00 AM Tokyo time

Tags gcj
  • Vote: I like it
  • +17
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Good luck in defending your title, Egor!

Any advice for the rest of us mere mortals on how to go about improving our problem solving skills, so one day we too can make it to the on sites? And yes I know the "practice a lot" one :) May be something related to mathematics? I am thinking nowadays about going for an MS in Mathematics, just so I become good at algorithm contests ;)


→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Math is so much, much more than contests :) But learning is always great.

    To Egor: Good Luck! +1 to your TopCoder Quote.
    → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
What is the main place where the spectators discuss what's going on?
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Apparently the contest gets postponed over and over again :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Do you know what is the reason?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      No. I'm on vacation without contact with the event :)
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I'd guess people are still setting up because of some previous event (breakfast? :)) running late.
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Problems: http://code.google.com/codejam/contest/dashboard?c=1327485
→ Reply
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Still no submissions at 15 minutes. Apparently the problems are tough, good!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Or maybe too tough? 25 minutes, still not even an easy input submission.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Four people with non-zero scores now, all from Russia: pashka, Evgeny Kapun (no CF handle?), RAD, vepifanov.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    And hanshuai. None of the submitters is a TopCoder target, while 5 of the competitors are. What are the heavyweights doing?
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
There's also a long-standing attempt at D-small which I guess was unsuccessful since it's been more than 4 minutes.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ivan.metelsky gets A-small.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    So does donehl
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      There's probably too much submissions now to enumerate them. ACRush is the first TC target to submit a problem. B-small, after 2 wrong attempts. A 8-minute penalty to carry through the entire contest.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        And a time-expired for him on B-large. Ouch.
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
More than an hour into the contest, still just 11 contestants with successful submissions.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
1h18m - pashka still leading with 30 points. He was in the lead (shared for the first 25ish minutes) during the entire contest so far!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
ACRush and vepifanov now have non-zero scores on two problems. Both just small inputs yet, though.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    And vepifanov submits A-large to take the lead from pashka, despite the latter submitting B-small.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Now meret takes the lead by solving A-small and A-large in addition to E-small.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        At mid-contest, he's still in the lead. The problems solved by at least one contestant are A-small, A-large, B-small, E-small, but nobody got all of them (yet?).
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          meret finally solves all "opened" problems. Since he doesn't have wrong submissions, one needs to solve something else to overtake him.
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Wow, an unexpected submit from voover - I didn't even know he was participating - apparently somebody from http://apps.topcoder.com/forums/?module=Thread&threadID=706558&mc=114#1387375 couldn't make it.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Somebody else has attempted B-large. We'll learn who in 8 minutes :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It was Egor - a timeout for him as well.

    Meanwhile, still no submissions from winger, zyz915, rng_58, darnley. There's one unknown incorrect submission on B-small and one on E-small, but at least two of them thus have no attempts at all!

    neal was the first to solve D-small. 
    → Reply
13 years ago, # |
  Vote: I like it +19 Vote: I do not like it
That long silence from rng_58 was for a reason - E-small+E-large and tentative second place!
→ Reply
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
winger submits A-small and we now know that the unknown wrong on E-small was due to him. 

zyz915 submits B-small and the unknown wrong there was probably due to him.

There are no more unknown wrongs, and darnley is the only one with no submissions.
→ Reply
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
Meanwhile, we have a new leader - ivan.metelsky leads with 77 points by solving D-small. If we add up points for all datasets solved by at least one contestant, though, we get 140.
→ Reply
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
47 minutes to go, 3 people with 77.
→ Reply
13 years ago, # |
  Vote: I like it +20 Vote: I do not like it
darnley is the first to solve C-small - here is the reason for his silence!

Meanwhile, rng_58 leads after solving A-small and A-large with 90 points.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
But meret retakes the lead with B-large and 100 points.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And the contest is over with no major changes at the top. meret with 100, then rng_58 with 90, then ivan.metelsky with 77. Let's wait for the large results to be revealed.
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Problem C is brilliant! I think it is the best Code Jam problem I ever seen. The idea is original and fresh and the code is quite short, however it requires careful implementation. Quite strange that only one person has tried to submit it.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Really? Turing state machine, second year of CS university. Yes, the actual problem is quite funny, but I cannot really call it so brilliant.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Can you fit it into 30 instructions and 150000 steps for N=5000?
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes.
        For small test one just need to write down the N in binary on the tape (it takes 9 instructions), and iteratively substract 1 from this number, and move the flag one cell to the right.
        For large test it takes slightly more instructions than allowed (because of hard-coden writing of N), so we can just increase the base of numeral system :)
        Number of steps is O(N logb N), where b is the chosen base (5 is enough).

        P.S. It took me 10-15 minutes to get with an algo for small test, and after that enhancion for large test was obvious. Really, one cemester of computability theory at the second year of university — and problem is quite straightforward :)
        P.P.S. To be honest, careful implementation of this idea might take a while.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          The tricky part here is max. input on hard. You have to balance between 30 instructions limit and an average of 150.000 / 5000 = 30 operations per subtraction. Every design and parameter choice here matters (at least, that was so for me).
          → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          And the number of steps for the basic flag approach is not O(NlogN), but O(N^2) (we perform N rounds of subtractions with O(1)...O(N) operations per each).
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Yesterday, in the evening, I was intrigued by your description of the problem and decided to look at it. The first part (small input) turned out to be not very hard and I've managed to find the solution within an hour.

    However, the second part was much trickier and I've spent hours trying to solve it and eventually managed to do it and successfully passed the hard test submission. That was fun, and pretty interesting task optimizing the final idea. Thanks for noticing this problem :)
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I like the concept of the problem, but dislike the process of solving it=)

    For anyone familiar with Turing machines the solution with O(NlogN) runtime and (log2(N) + C) program size should be obvious. I spent a lot of time optimizing the constant C to fit 30 commands limit.

    The final submission contained: writing the binary number (13cmd), left-pass with decrease (7cmd) and right-pass with move (8cmd) with total of 28cmd for large output.

    It's quite interesting what is the minimal number of commands required for large output. Also I don't understand how increasing the alphabet size can help in optimizing the program, since a lot of states must be sensitive to all the possible chars.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you describe how you've managed to fit left-pass descrease and right-pass move into 7 and 8 commands? What are the states?
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        First of all, higher bits of the number should be placed to the left. Otherwise you won't be able to easily decrement in left-pass. So left-pass decrement is iterating over digits from lower-valued to higher-valued.

        For decrement, there are two working states. The difference is: whether we have to decrement the rest of the number or not. For these two working states we have to write commands for all possible input chars (empty/0/1), so we get 6 commands. Also we need one special state and one command to step left from initial(empty) position to the first digit of number. When the decrementing robot steps on the empty slot, it either drops the cake (if still wants to dec) or simply steps to the right (if does not want to dec).

        For right-shifting the number, there are also two working states. The difference is: whether the previous digit was 0 or 1. Of course we have to react to all possible chars (empty/0/1), so we require 6 commands for these working states. However, we need one special state and two commands to handle the first digit properly, because previous digit for the first digit is "empty".

        So for each of the decrement and move passes there are three states, one of them is "starting state" and the other two are "working states". And of course there are other 13 states+commands for initialization.

        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          In my solution most significant digits are at the right side. However, I'm using base 5 instead of base two.
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks, now I understand and it is quite straightforward, when I'm looking at it like that :)

          I, myself, while solving this task and thinking over the optimization of the "moving" idea (I've failed to compress it good enough for the large input), came up with the combined approach of flagging and moving at the same time. Now I can do n=0..8 in 1..9 instructions and for n > 8 in 26  instructions. This was the solution that passed tests for large input. 

          And, actually, I'm using ternary system - for my particular approach this seems to be the best choice (8 digits instead of 13 for binary), since I have only one state that reacts to digits 1 and 2 (all other states don't need to work with these digits). 
          → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I still don't get how can one achieve N log N runtime. Whatever way of solving this problem I come up with, it requires at least N^2 of operations.
      Can someone elaborate more on the way to improve runtime?

      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Store N-13 in first 13 cells (base 2 is enough here), least significant bit to the right.

        Each step now consists of:
        - subtracting 1 - takes one pass from right to left and 2 states (whether we still have to subtract)
        - shifting the entire counter 1 cell to the right - takes one pass from left to right and 3 states (carrying empty/zero/one)

        If we have to subtract from empty cell on the left edge, that means we've finished, so do final pass to the right (1 special state) and halt.

        Total runtime is approx. 2 * N * logN, which is about 130000 with N=5000.

        I squeezed it into 29 rules (not much optimization was really needed) and it passed in practice.

        UPD: final pass is actually not needed if we encode N+1 instead of N-13 (and halt at left edge), that fits in 27 rules.
        → Reply
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
"...and the winner of Code Jam 2011 and the title of Code Jam Champion goes to JAPAN'S RNG_58!"
→ Reply
13 years ago, # |
  Vote: I like it +19 Vote: I do not like it

GCJ 2012 will be held in Paris, as it was said on the awards ceremony.

→ Reply
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
hey Rad, congrats for your great performance in GCJ 2011!!!
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it


In rng_58's submission for problem A, he computes the modular inverse for all i modulo MOD:

inv[1] = 1;
    for(i=2;i<MOD;i++) inv[i] = (MOD - MOD/i) * inv[(int)(MOD%i)] % MOD;
   

How do justify this algorithm?  Thanks in advance!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it
    he is a wizard
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Yep.  It's much shorter than using the extended Euclidean algorithm.
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Ok, I figured it.  First, MOD - i*MOD/i == MOD%i

    so i*(MOD-MOD/i) == MOD%i   modulo MOD

    then i*inv[i] modulo MOD simplifies to 1:

    i*inv[i] == i *(MOD-MOD/i) * inv[MOD%i]

    i*inv[i] == (MOD%i) * inv[MOD%i] modulo MOD

    i*inv[i] == 1 modulo MOD
    → Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem B, "Rains Over Atlantis", there is a very nice algorithm by g201513.
The complexity is O((RC)^2).

The idea is to modify the map, by increasing some fields, without changing the
result:

1)  If the height of each field is increased up to the nearest multiple of M,
        the result is unchanged.

With that property, each erosion decreases heights by either 0 or M.
We can rescale the map by dividing everything by M, and assume from now on that
M=1.

2)  If a field needs d days to reach the level 0, then it's as if its
         height is d.

3) If each field with positive height has a lower neighbour, then the result is
     the maximum height over the map.





→ Reply