TsunamiNoLetGo's blog

Google Code Jam Round 3
By TsunamiNoLetGo, 8 years ago, In English

Hi all,

Very soon the last elimination round of Google Code Jam will kick off.

The top 25 contestants, along with last year's champion tourist, will advance to the onsite final round.

Let's discuss the problems here after the round.

Good luck!

UPD: contest starts in less than one hour, you can load the dashboard now.

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

»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it

How many problems do you expect? 4 or 5?

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

Quite strange problemset.

During the contest I bet no C-large will pass (geometry with no example). Surprisingly 19 passes!

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

    But only one of them ranked in top 25.

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

      Probably because the better strategy turned out to be to focus on D rather than C.

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

        That's because points assigned to C and D are a bit strange

        You were getting bonus points for believing that D-large is not much harder than D-small. Much more bonus points than for solving C-large, for example.

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

          I looked at what score was generally needed to advance to the finals in the previous years and thought that it would be enough to have everything but D-large. (But my C-large failed anyways)

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

          How to solve D-large? For D-small, I used "1"*(L - 1) and "0?"*L

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

            Let b = a1... an.
            If s[i]! = b for all i, output

            and

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

              Code Jam has been playing a lot of tricks this year! This one being that the good set is completely irrelevant as long as it doesn't contain B.

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

    There is almost nothing from geometry in the solution. You only need to find a time interval in which two particular asteroids are closer than a particular distance, and that is just an inequality.

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

      Figuring out the coefficients from those asteroids and then solving quadratic inequality is something nobody likes and also not that straightforward for most people and it demands a slight part of geo3D library (however one that most people should be able to write during contest, but again not something people like). However when preparing to WF16 I coded problem A from WF12 about asteroids, so it was very tempting for me to solve that problem, because I simply copy-pasted all of the needed code for geometry part :P. I made a bet that D large will be sufficiently hard so that it won't be required to qualify and I have big advantage in problem C, so I will solve it significantly faster than others. Turned out both assumptions were very wrong...

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

        I didn't manage to solve C. But about that interval of times, I think that you can find the optimal t(which generates smallest distance) for each pair of asteroids through ternary search. Than, I thought that you may want to bynary search the answer so for a maxD, you can binary search the t in each of the two segments [0, t] and [t, inf) where t is that optimal time for those two fixed asteroids. Unfortunately, after determining these intervals of time, I was unable to solve the remaining problem (which I guess was the hard part).

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

          Yeah, you're right, I also noted it in the meantime. This way it is definitely easier.

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

    I needed just a few extra minutes to finish solving C-large. The problem is not very hard if solved the right way. My solution maintains a graph, where there is an edge between two asteroids if it is possible to jump between them. A list of events (edge added, edge removed) is generated and processed while maintaining the set of reachable asteroids. For isolated asteroids, there is also a "time limit", but it is only checked when this asteroid is connected again (if this is done too late, it is marked as unreachable). I think that the complexity is , because, while many asteroids may become reachable as the result of event, only at most two can stop becoming reachable. The only "geometric" part is to compute, for two asteroids, the time when they become within distance d from each other and when they stop being within such a distance.

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

I need 6 dropouts. Fat chance :(

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

    Too bad. :( The scoring was really weird; IMO solving C-large is a lot more impressive than solving D-large!

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

      If the points for C-large were >= than the points on D-large, then I would expect the contest to go the other way: almost everybody would try to get C-large, since that problem is difficult but it's clear in which direction to move and one can make progress, whereas with D-large one may get stuck for a long time and only then see the solution.

      As a result, most if not all people in top 25 would end up solving C-large, and there would be many people disappointed for two reasons: failing C-large because there are a few tiny implementation details that are easy to get wrong, and not advancing despite solving the difficult D-large.

      Also, I didn't expect so many people to solve D-large — it seemed harder to me.

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

        I see your reasoning: C-large was the only problem this GCJ where the Small input didn't help you at all with debugging the Large. But it seems worse to not go to the finals after getting C-large because you didn't realize D-large was mandatory. :) (I'm not bitter; I didn't solve either of them!)

        I agree D is a hard problem, but it's a math problem with no implementation, and there are a lot of reeeeeally clever people competing...

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

    You could get a WF ticket last year, and I also need 6 dropouts in this year. Wish me luck! :)

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

It turned to rather has no meaning, but "8+17" was a really strange partition of point for C. I would rather set 1+24.

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

Can someone please explain how to solve problem B?

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

    Randomly generate 100,000 valid sequences. Note that probability must be higher for strings that can occurs multiple times, this is done by assigning weights to all courses: weight(u) = #descendants(u).

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

      So, you choose a random node from all current tree roots according to this weight (= size of the subtree)?

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

        Yes

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

          Your description sounds a bit like one has to guess the correct weight, whereas it's not that hard to actually find it by reasoning.

          More specifically, if we were to count the number of valid sequences, after some thought we can see that their number is n! divided by the product of sizes of all subtrees. Now we can use that to count the number of valid sequences with course A on first place, course B on first place, etc, and it turns out that those numbers are proportional to the sizes of subtrees of those courses.

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

      I just guess that solution when see more then 40 AC solutions and got AC. It's interesting how many participants proved their solution during the contest?

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

        I implemented it in overcomplicated way (by calculating number of outcomes for each choice using DP and binomial coefficients instead of these simple formulas); I remember Petr giving quite similar problem with same idea behind it at Petrozavodsk training camp some time ago, so during a round I was sure about correctness of solution and pretty sure that I know who prepared this problem as well:) But still I completely missed the fact about "size of the subtree magic".

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

          Could you tell which problem are you referring to? The most similar one I remember is "Random Domino Placements", but it seems to me that it didn't share any ideas with this one.

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

            I had problem Number of Close Strings from the same contest in my mind; I rechecked exact statement now indeed these two tasks are very different... Yet remembering idea from that one helped me in this problem somehow :)

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

              Thanks! I think the common part is essentially the Central Limit Theorem, which was indeed useful in both problems.

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

                Going a little offtopic, but "Number of Close Strings" is one of my favourite problems!

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

            Talking about Random Domino Placement — this one has been bouncing in my head for a long time. Would you mind giving some hints :)? Should we generate those placements "really uniformly" or is the trick within creating them as a result of some Markov chain?

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

              It's Markov chain this time. You have to come up with some Markov chain where transitions are quick to do and stationary distribution is uniform.

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

        I read somewhere that you can make a fair shuffle of an array using mergesort, but when you merge you have to weight the selection according to the number of elements in each part.

        Then I just assumed it worked like that for trees too and YOLO submitted, it's Small anyway :P

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

          I think that the hardest part is to come up with the size of subtree.

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

Btw, why GCJ doesn't ignore additional whitespaces? I was struggling for a long time with B, because I put an additional endline after "Case" templated thingy, because I remembered empirically observed rule that if output is not of constant size then there used to be end of line there :.

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

    Yeah, I guess this is mostly for historical reasons (wow, it's our 9th Code Jam using this platform now!). We try to write the problem statement clearly (in this case it said "For each test case, output one line..."), but I agree that ideally we would not care about newlines in your output.

    Sorry you had to struggle with this.

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

Maybe points weren't adjusted properly but problems were very nice! I feel bad for my bad score because topics were perfect for me :/

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

Fun fact: There doesn't exist a person so that taking all his points he earned in C or giving him all points in C he didn't earn changes whether he qualified. Null. Zero. Nada. Nil. Zilch. Zippo.

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

    what about those with 58 points? (time penalty would matter in that case though)

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

      Ahhh, I missed fact that two last finalists didn't get Csmall, you're right.

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

How to solve A?

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

    It's obvious following greedy works: if last problem set requested is the same as current mood today, submit it for 10 points; otherwise request a new one. The problem sets that remain can be paired for 5 points each.

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

I get 7-th position, I'm very happy ^_^.

But there are the exam in my university in 8/5 (;_;).

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

Contest editorial is available at last.

→ Reply