Can anyone please explain the analysis to problem F? Unfortunately this time the editorial is in japanese.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Can anyone please explain the analysis to problem F? Unfortunately this time the editorial is in japanese.
Name |
---|
Consider the sequence of cards that will be taken until the end of the game. For example, if n = 5, m = 4, k = 6 then it can look like:
Alice wins if the sequence consists of exactly n a's, no more than m b's and no more than k c's. Let's say there are s b's and c's totally. The rest of cards may be chosen with 3m + k - s ways, and the revealed cards may be chosen with ways where f(s) is the number of strings consisting of s characters a and b in total from which no more than m are a's and no more than k are b's.
It's easy to see that
If we draw a Pascal Triangle, this is a section of rectangle (0, 0) — (m, k) with a diagonal line that looks like a segment consisting of binomial coefficients with fixed first argument. There is no closed form for such sum, but it's easy to see thath f(s + 1) is almost equal to 2f(s), you only need to carefully consider O(1) binomial coefficients at the border. So, the solution is: calculate using DP the function f(s + 1) = 2f(s) + [O(1) binomial, 2016 - 09 - 12 coefficients], and then output the answer . Binomial coefficients may be calculated in O(1) if we precompute all factorials. Overall complexity is O(n + m + k).
Can someone explain problem E also..
I have not solved the problem but it seems plain dijkstra. The state is: (node, color). Even though there may be many node's and many color's but, number of interesting (node, color) pair is not more than number of edges.
Not Dijkstra but BFS, actually, since all edge lengths are 0/1.
Can you please elaborate the solution a little..
First, find connected components of railway lines. Two railway lines are in the same connected components if they belong to the same company and they are connected through rails of this company.
Then, construct a bipartite graph. The vertices on the left correspond to stations. The vertices on the right correspond to connected components. Add an edge between a left vertex and a right vertex if the station is incident to one of the rails in the connected component.
The solution is (the shortest path in this bipartite graph) / 2.
Can you please explain how finding the shortest path in the constructed bipartite graph would be equivalent to finding shortest path between nodes 1 to n.
All the vertices of the original graph are on the left and components of the edges on the right. Moving from 1 vertex to another (on the left side) passes over two edges in the bipartite graph but is of actual cost 1 in the original graph (hence we divide by 2). Also each such movement (left->right->left) is equivalent to changing the edge-component (or rather changing the company whose edge you are travelling on in the original graph which incurs a cost of 1). This is precisely what you are asked to minimize.