Code Jam R2 starts today at 14:00 UTC. Don't miss!
Top 1000 contestants will receive t-shirts.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Code Jam R2 starts today at 14:00 UTC. Don't miss!
Top 1000 contestants will receive t-shirts.
Name |
---|
The top 500 contestants will advance to Round 3 to compete for finalist spots and a free trip to Google Los Angeles. :)
Как решать задачу B?
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.
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?
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
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.
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.
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).
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.
Can anyone explain how D-large is solved? Tks~
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.
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.
Можно подробнее про переходы в динамике? Как считать dp[i][j] = ???
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 putmin(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 ofmin(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:
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
over all sons of v
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 andusing 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
)
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.
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.
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).
Does Google also ship the T-Shirts outside of the US? When will they ship them?
Last year, I got mine at the end of August. If you hope to get it soon, you'll probably be disappointed...
In my case, it was shipped around 6 to 7 months later.