riadwaw's blog

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

Round starts at 14:00 UTC today and 25 participants will advance to final round in Dublin.

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

Comments Comments (49)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +89 Vote: I do not like it

Now I finally feel old. I opened the problem C, and the first thing that came to my mind was "Oh, this problem may be solved with the same idea as in the problem K from NCPC 2010".

Thanks for the contest! Problems B and C were great, problem A made me lose some time on it and it wasn't a pleasant time, and I'm not sure about problem D if it has a solution that does not require lots of coding.

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

What were your solutions to problem A? I couldn't think of one.

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

    We need to find the number of nodes that can reach our node in a graph (of size (L + 1)L). If the sum of digits of a number is > L, it can't be reached from any other node. Thus we may only consider the numbers with sum of digits <= L, and there are only about 50000 when L=9.

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

    Precompute everything using bruteforce. (My program ran in 4m51s on A-large, and my penalty was 1m35s too high for 26th ;_;)

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

      Well, I tried to do this as well but my shitty computer kept crashing :( Don't understand why such problem was including in GCJ...

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

26th, my ass.

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

    Did you read "There are a total of 26 spots in the Finals, including Gennady.Korotkevich's spot. So, if he places in the top 25, the top 26 contestants will all advance to the finals. Otherwise, the top 25 plus Gennady.Korotkevich will advance." ?

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

    tourist is ahead of you, so I think you have a spot. On the other hand, I'm 27th :(

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

      So, mnbvmar will be on internship in Google, you also got sure spot.

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

        Let's keep going like that, only 53 more people on internships or something and I'm going to the finals!

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

        I'm 28'th. Do you have one more?

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

          I have no more tricks up my sleeve ;p. However I have heard that one year ago participants up to 32nd place were allowed, so there is still a big chance for you :). On the other hand, Dublin is much more convenient place to go for most participants than USA (closer and easier to get visa if necessary), so who knows.

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

          From 2009 to 2016, even 30th place was always enough. You have a very good chance.

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

            Do you have stats for each year? It would be interesting to see the distribution

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

              I did it manually but I lost the data — if my memory is correct, it distributed around 31-37th.

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

        why can't he take part? Can't he just take leave for the contest?

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

          Google employees are not allowed to take part in GCJ. And he will be a Google employee (intern) at the time of the final.

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

        I would resign from internship in such a case. In my opinion GCJ final is worth much more than internship.

        Edit: Or at least postpone it after the finals.

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

          if you postpone it, you would probably only have 1 month left for the internship...

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

          Maybe if you are P___ then it would be unique opportunity, but if you are mnbvmar then it is not :). And internship can make for a living of whole family for 2 years in Poland which is not a case with GCJ ;p.

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

            but if you are mnbvmar, you can easily find 10 other internship as good as google :)

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

    Man, you mast feel angry!

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

Seeing as in 2:08 I was 18th and watching scoreboard for next 22 minutes as I fall to 41st place before judging larges and 36th after was really painful :(. Stupid A xdd

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

    This year the number of late submissions was exceptional. Usually we can estimate the cutoff from first AC time. At 40 minutes, I was confident that fast 50 points is enough. The cutoff of 74 points was surprising.

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

Editorial is already posted. How unusual for them.

→ Reply
»
8 years ago, # |
  Vote: I like it +57 Vote: I do not like it
not so hard solution of D
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    my solution
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    CF was down for a while after GCJ, finally connected :)

    It reminded me your problem from Codechef Lunch.

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

To other contest organizers: It is still possible in 2017 to have original and interesting problems in online rounds, huh?

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

    Yes, I still see lots of new interesting problems, but the probability of collision is higher now.

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

    Does it mean that GCJ succeeded on it or not? As for me, their problems were pretty original (even though I knew the key idea of problem C, but I'm sure this idea is not very popular) for all rounds. Of course, not 100% of the problems were really interesting (today's problem A, for example, or R2's 2sat problem), but overall I liked problemsets of GCJ pretty much among all the contests I participated this year.

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

      Yeah, GCJ is known for having good problems every year. AtCoder and TopCoder problems are focused on new ideas instead of known ideas and just time consuming stuff — which should reduce the probability of collisions.

      In many years of solving TopCoder contests can't remember many reused problems. But I can remember that, for example, there was a pretty difficult ICPC World Finals problem some years ago that was exactly the one from old TopCoder.

      I was joking with a friend before some other online contest that if I see any problem having usual "answer these queries efficiently" style I would not participate and surprise — last 3 problems had similar statement :)

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

    Not if you have two such contests in a row

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

I can't understand why a bridge existence makes a solution impossible to exist in B. Can someone clarify, please? Thanks :)

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

    Consider a bridge that connects two components A and B. Define the difference between the ingoing and outgoing edges in the vertex as its value. Suppose that the flow through bridge is non-zero and remove it from graph: the total value of all vertices in A is now different from zero. On the other hand, sum of all values of vertices in a connected component should be zero since each edge is accounted twice with opposite signs, i.e. we can not fix the disbalance in component A. That leads us to contradiction.

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

I got 32nd in HackerCup this year, and got 32nd again :(

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

Problem B has a very large range. It is known that you can solve it even with range of [-5, 5] (search "nowhere-zero flow" on Wikipedia). A reasonably simple algorithm can do it on range of [-7, 7].

→ Reply