Can anyone please explain the analysis to problem F? Unfortunately this time the editorial is in japanese.

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

1 | MiFaFaOvO | 3520 |

2 | tourist | 3430 |

3 | apiadu | 3351 |

4 | mnbvmar | 3332 |

5 | Benq | 3290 |

6 | LHiC | 3276 |

7 | TLE | 3270 |

8 | Radewoosh | 3251 |

9 | ecnerwala | 3241 |

10 | Um_nik | 3240 |

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

1 | antontrygubO_o | 190 |

2 | Errichto | 188 |

3 | tourist | 178 |

4 | Radewoosh | 172 |

5 | pikmike | 166 |

6 | vovuh | 165 |

7 | ko_osaga | 162 |

7 | Um_nik | 162 |

9 | rng_58 | 155 |

10 | majk | 154 |

Can anyone please explain the analysis to problem F? Unfortunately this time the editorial is in japanese.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/18/2020 01:59:57 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

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

na's, no more thanmb's and no more thankc's. Let's say there aresb's and c's totally. The rest of cards may be chosen with 3^{m + k - s}ways, and the revealed cards may be chosen with ways wheref(s) is the number of strings consisting ofscharacters a and b in total from which no more thanmare a's and no more thankare 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 thathf(s+ 1) is almost equal to 2f(s), you only need to carefully considerO(1) binomial coefficients at the border. So, the solution is: calculate using DP the functionf(s+ 1) = 2f(s) + [O(1)binomial, 2016 - 09 - 12coefficients], and then output the answer . Binomial coefficients may be calculated inO(1) if we precompute all factorials. Overall complexity isO(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.

is the following approach expected to pass?

Make new graph of form {

color,node}. In this graph, one can argue it has at mostMnodes(number of edges in original graph). Dijkstra on this graph using map or similar DS, and find shortest path to any node with second parameter as the last node? I suppose dragoon was also suggesting this approach(and not the one you suggest).I tried implementing this using dijkstra and using 0/1 BFS, both got TLE(maybe my implementation is poor :/).

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.