SuprDewd's blog

Google Code Jam World Finals 2016
By SuprDewd, history, 8 years ago, In English

The 2016 Google Code Jam World Finals just started. Relevant links:

Edit: The contest is over. Results:

  1. tourist
  2. kevinsogo
  3. Egor
  4. eatmore
  5. Merkurev
  6. mnbvmar
  7. scott_wu
  8. simonlindholm
  9. gs12117
  10. semiexp
  11. ffao
  12. vepifanov
  13. pashka
  14. KAN
  15. rng_58
  16. yosupo
  17. Xhark
  18. Nore
  19. Marcin_smu
  20. s-quark
  21. jcvb
  22. nika
  23. xllend3

Congratulations!

  • Vote: I like it
  • +87
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seriously, why bother and hold a Code Jam World Finals every year? they can simply give it to tourist. Wouldn't that be easier? :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +105 Vote: I do not like it

    It's for others to compete for the second place of course.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Well, now it makes much more sense :D

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Then, kevinsogo is considered as the winner of the Codejam 2016 World Final! :D

      → Reply
»
8 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Interesting things I noticed during the Live Stream :-

  • tourist named one of his files stupid.cpp -___-

  • MAGIC = 200 :)

Anyway, the live stream was pretty bad!
The arena was dimly lit for some reason. Also, they only showed tourist's monitor throughout the contest, and said they didn't make arrangements for others' screens. Towards the end of the contest I really wanted to see what kevinsogo and Egor were working on since the scoreboard was so close! There were tedious and long breaks in the stream very frequently as well. They should really show somebody's screen during those breaks instead of playing pathetic music :P

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Wut is weird with those things? Everyone sometimes needs a magic number and giving stupid names to files is also rather common. I for example sometimes name files like "ass.cpp" or "nothing" (but in Polish). Just because tourist did this doesn't make that fact extraordinary :P.

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

      Sometimes I want to create a file nic.cpp (what means "nothing" in Polish) but it already exists so I create nothing.cpp. I will burn in hell for programmers.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +42 Vote: I do not like it

        I usually just give up after checking meow.cpp, meow2.cpp and meow3.cpp and realizing they are all in use.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Lol I use meow.cpp too. But now that I have meow, meow2, meow3 already in use, I type meowX where X is some random number as the file name xD

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I think stupid.cpp is not just a random stupid name. It means a stupid solution (for a small input, for example).

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Swistakk, I never said that it's weird or extraordinary. For E in the codejam finals, he was tweaking his MAGIC and staring at outputs. He submitted large input with only a few minutes to go. Most people (including the panel) did not expect it to pass, but it did xD

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        It's very common for tourist to submit his last solution with only a few minutes to go. It's a good strategy, he knows he doesn't have time to code anything else so he might as well make sure his solution is correct.

        In this specific case, although his approach for problem E is the simplest (conceptually), it looks really difficult to get precise enough. He must have had a feeling for those magic constants!

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

The improvement in kevinsogo's performance is quite remarkable from 26th last year to 2nd this year

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As there was no analysis of the finals (sadly), I am asking here. Can anyone explain the idea behind the first problem? The statement is beautifully simple: given a regular expression describing integers, count how many integers there are <= N, which match the pattern.

I remember finite automata and regular expressions from CS classes fairly well, but haven't come up with a good idea to efficiently solve this problem, because N can be huge, up to 10^18. For small N I could just implement the RE as a FA and try one by one. For bigger N... maybe the pumping lemma comes into play, but I don't see how.

Just the main idea or even a hint would be great; I don't want to start reading solutions without trying a bit more first. Thanks!

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    The main idea is pretty simple: use dynamic programming over digits, and have one parameter denote the current state of the automata.

    Edit: Also note that they gave solution ideas in the live stream: this problem.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! That tells me exactly what to do. Great idea.

      Now I'm reviewing in my mind the process of (a) RE parsing, (b) RE->NFA and (c) RE->DFA conversion, which, although algorithmically straightforward, I cannot imagine how someone programmed all of those things PLUS the DP in about an hour.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        RE parsing is simple in this specific case because all operators are necessarily grouped by brackets, so whenever you meet an opening bracket you just need to check if there's a * after the closing bracket and you know if the operator is * or |. NFA->DFA conversion is not complicated because all you need to do is keep a subset of states of the NFA you could be in and you automatically get the DFA without having to actually do the conversion.

        RE->NFA is the really difficult part, and what I had to spend about an hour debugging during the competition -.-'

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does one ensure that the duplication is taken care of? For e.g., given a regular expression (12|34|56)*(123|456)* , there are two ways to arrive at 123456. Through the DP, we can be sure that the same number will not be arrived at through the same state more than once, but some other set of states could give the same result. How to avoid that?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is only an issue if you're working with an NFA. But if you first turn it into a DFA (or keep a subset of the states as a DP parameter), then that won't be an issue. The length of the expression is small enough to allow 2^(number of states).

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The trick is to count valid arrangements of digits using DP. A more detailed explanation of this approach: https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258

    → Reply