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

Top 1000 contestants will receive t-shirts.

# | User | Rating |
---|---|---|

1 | tourist | 3628 |

2 | Um_nik | 3534 |

3 | Petr | 3341 |

4 | wxhtxdy | 3329 |

5 | ecnerwala | 3305 |

6 | LHiC | 3300 |

7 | mnbvmar | 3291 |

8 | sunset | 3278 |

9 | V--o_o--V | 3275 |

10 | dotorya | 3188 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 187 |

2 | Errichto | 183 |

3 | rng_58 | 161 |

4 | PikMike | 159 |

5 | Petr | 157 |

6 | Vovuh | 156 |

7 | Ashishgup | 153 |

8 | 300iq | 151 |

9 | Um_nik | 148 |

9 | majk | 148 |

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

Top 1000 contestants will receive t-shirts.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2019 21:56:17 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The top

500contestants 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≤Ncalculate maximum number of nodes if subtree is stored onnservers.Actually, for each node of the trie, count the number

eof 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 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:

s[v] ≥Nand 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 ofvmust span over allNserverss[v] ≥Nand at least 1 of its sons has , the strings ending in each son's subtree must be put into distinct serversin 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<Nstrings intomservers out ofN— 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 puttingmstrings (from a specific subtree) intonservers (m≥N≥n) in such a way that there's at least 1 string in each server (the strings span over allnservers), andP_{0}(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 exactlyn-k> 0 servers emptywe can calculate

P_{0}by realizing that each of`e[v]`

strings can go into any server and each son ofv(the subtree's root) must satisfy the condition above, and these rules are independent, soP_{0}is the product ofe[v]^{n}and over all sons ofvusing modular exponentiation, we can calculate

P_{0}(m,n) for any subtree in time; then, we can DP allP(m,n) up toP(m,N) (which is the actual number of ways that satisfy the basic condition forv) in time; over all vertices, we get worst-case , whereLis the total length of strings in the inputthe 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.