Zlobober's blog

Google Code Jam Round 2
By Zlobober, 11 years ago, In English

Code Jam R2 starts today at 14:00 UTC. Don't miss!

Top 1000 contestants will receive t-shirts.

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

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The top 500 contestants will advance to Round 3 to compete for finalist spots and a free trip to Google Los Angeles. :)

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

Как решать задачу B?

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

    I used a greedy algorithm that moves the numbers in increasing order one after another to the correct places. You can always move the number either to the left or to the right and select the direction that minimizes the number of swaps.

    For example, if the array is [6, 4, 1, 5, 2, 3], we first move number 1. If we move it to the left, we need 2 swaps, and if we move it to the right, we need 3 swaps. So we move it to the left and the array becomes [1, 6, 4, 5, 2, 3]. After this, we move number 2 etc.

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

Fellow coders,

Can someone explain why this solution for A fails to terminate for small testcase in Xcode IDE? Can you find any other IDE where it behaves the same way?

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

I pulled a rng_58 :D

I submitted A's output file for B and was debugging for 45 minutes. It doesn't matter because I am still getting a tshirt, which was my target :P

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

    Actually, you pulled a jodik. In March 2012 on Slovak OI nationals (practical day: 2 problems, 15 points each, IOI scoring, full feedback, last submission counts), he resubmitted one problem's solution on another problem (for which he had full score), and then again on the correct one, where he found out that it's still a wrong solution, giving him 0 points total :D

    Fortunately, he managed to convince the organizers to accept his earlier solution, so he did get the points in the end.

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

      What do you mean by 'full feedback'? Didn't he have the time to resubmit or what?

      In Russia we have the rule that your submission for a problem should pass example test cases (ones from the statement) to be accepted for a full testing, no matter what. It's very useful to avoid such mistakes and double-check I/O issues.

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

        This happened about 5 minutes before the end of the contest... and the testing takes a while. Because full feedback. And because Jodik, of course — after seeing that he's suddenly got 0 points, he panicks and starts trying to find out what happened, starting from the least probably causes.

        I've had 1 or 2 submissions that passed all but 1 sample, so it can be a bit tricky. Besides, it can be annoying in case of partial scoring (hardwiring an output for a particular input).

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

      Ages ago, when USACO didn't had online submission server and all the submissions were done via e-mail, one participant's code was mixed up and submitted for another problem.

      The unique element of this story is that it still scored 40% of points.

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

Can anyone explain how D-large is solved? Tks~

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

    Dynamic programming in subtrees — for every node of trie, for every 0 ≤ n ≤ N calculate maximum number of nodes if subtree is stored on n servers.

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

      Actually, for each node of the trie, count the number e of strings ending in its subtree; the answer (first part) is then the sum of over all nodes. It obviously works, since you can just split the strings ending in each subtree into as many servers as possible.

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

      Можно подробнее про переходы в динамике? Как считать dp[i][j] = ???

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

    My solution:

    • construct the original trie; for each vertex, remember how many strings ended exactly in it (e[v]) and how many ended in its subtree (s[v]); it's clear that we can put min(s[v],N) strings (as many as possible) from its subtree into distinct servers, so each vertex appears this many times and the first part of the answer is the sum of min(s[v],N) over all vertices (including the one corresponding to the empty prefix)

    • it's also clear that we can only achieve this many vertices in total if these bounds are exactly satisfied for each vertex, so:

      • if a node has s[v] ≥ N and all its sons have , the strings ending in each son's subtree must be put into distinct servers and the strings ending in the subtree of v must span over all N servers
      • if a node has s[v] ≥ N and at least 1 of its sons has , the strings ending in each son's subtree must be put into distinct servers

    • in the second case, if the strings in some son's subtree span over all servers, then the ones in the parent's subtree also do; also, if the strings in a parent's subtree are all in distinct servers, then the strings in any son's subtree also are, so the conditions for the remaining vertices are automatically satisfied; this set of conditions is also necessary

    • feel free to pre-calculate all factorials, their modular inverses and binomial coefficients up to 5000x5000

    • there are ways to put m < N strings into m servers out of N — we choose the servers with one string and then the order of placing the strings; in the second type of vertices, m = s[v]

    • let P(m, n) be the number of ways of putting m strings (from a specific subtree) into n servers (m ≥ N ≥ n) in such a way that there's at least 1 string in each server (the strings span over all n servers), and P0(m, n) the number of ways when we allow some server to not contain any of these strings; then , because we just subtract the choices that end up with exactly n - k > 0 servers empty

    • we can calculate P0 by realizing that each of e[v] strings can go into any server and each son of v (the subtree's root) must satisfy the condition above, and these rules are independent, so P0 is the product of e[v]n and over all sons of v

    • using modular exponentiation, we can calculate P0(m, n) for any subtree in time; then, we can DP all P(m, n) up to P(m, N) (which is the actual number of ways that satisfy the basic condition for v) in time; over all vertices, we get worst-case , where L is the total length of strings in the input

    • the second part of the answer is just the product of ways to satify the conditions for all vertices, for which they need to be satisfied (P(m, N) or )

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

C was a very interesting problem in my opinion. I created a graph where building and left and right (not up and down) banks were vertices and cost of edge was maximum od distance between those two things on x and on y axis (minimum number of diagonally touching cells we have to mark to connect those two vertices) and found a shortest way from left to the right bank. Complexity O(b^2 log b) (Dijkstra). This is computing a mincut which is in fact also a maxflow. h and w don't matter for me.

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

    I agree. C was a beautiful problem. Mincut -> Maxflow is a common theme in programming contests, but it's so rare to see it go the other way around.

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

      There was a discussion in Russian about this problem.

      I told that this problem definitely isn't a "brand new problem", because it's idea is pretty similar to one for problem 600 from TCO 2013 3A.

      Others have found other contests where exactly this problem was given.

      But I still agree that this problem is beautyful (the problem from TCO is even more beautiful IMHO).

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

Does Google also ship the T-Shirts outside of the US? When will they ship them?

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

    Last year, I got mine at the end of August. If you hope to get it soon, you'll probably be disappointed...

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

    In my case, it was shipped around 6 to 7 months later.

    → Reply