Topcoder SRM 647 will be held tomorrow (Saturday) at 12:00 Noon EST; details here. Discuss the problems here after the contest!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
2 | atcoder_official | 162 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | nor | 150 |
Topcoder SRM 647 will be held tomorrow (Saturday) at 12:00 Noon EST; details here. Discuss the problems here after the contest!
Название |
---|
a very similar problem to div1 500 discussed here
Один я как дурак линии в 500-й пересекал формулками и кучу кода писал из-за этого? :(
Откуда эти магические решения с "/ 3" в десять строчек?
Рассмотрим случай с двумя роботами. Понятно, что роботу с маленьким баком выгодно израсходовать 1/3 часть топлива, на еще 1/3 часть вернуться в начало, а оставшуюся 1/3 отдать второму роботу.
Если роботов 3, то первый отдает второму 1/3 топлива, как в первом случае, а далее аналогично рассматриваем второго робота и третьего. Ну и т.д.
В точке Х у тебя два ограничения — ты не можешь отдать больше Х топлива (потому что у напарника нету места, чтобы принять больше) и не можешь отдать больше ((Volume - X) - X), потому что тогда тебе самому не хватит на дорогу назад.
Это как раз две прямые, твое решение — нижняя огибающая этого набора, максимум будет в точке пересечения.
Volume - 2 * X = X — отсюда X = Volume / 3.
Так что "магические решения" прямо из пересечения линий и выходят.
A как правильно решать hard?
Выкинем все вершины недостижимые из начала, и из которых недостижим конец. Добавим к каждому ребру обратное бесконечное ребро. Найдём maxflow.
Ой, действительно, из-за новых ребер может появится путь через вершины, через которые раньше пути не было. Почему-то на контесте я об этом не подумал:(
Я сдал в практис руме такое:
В начале сожмем граф по компонентам сильной связности. Если вершины 0 и N — 1 находятся в одной компоненте, то ответ -1. Дальше выбросим все ребра, оба конца которых лежат в одной компоненте. Еще выбросим все вершины, которые не лежат ни на одном пути из старта в финиш.
Теперь если бы не было ограничения на то, что на каждом пути должен быть ровно один чекпоинт, то задача была бы эквивалентна поиску минимального разреза в графе. Сведем нашу задачу к минимальному разрезу следующим образом. Пусть у нас есть ребро a -> b, тогда добавим ребра вида x -> b и a -> y пропускной способности +inf для всех x, которые достижимы из b и для всех y из которых достижима a. Тогда как раз если ребро a -> b попадет в разрез, то никакое другое ребро на пути содержащем a -> b в разрез уже попасть не сможет. EDIT: исходя из комментария выше вместо всех этих махинаций с дополнительными ребрами можно было просто добавить ребро b -> a пропускной способности +inf, обоснование почему это правильно останется примерно таким же.
Если в итоге поток вышел бесконечный, то ответ -1, иначе ответ — величина потока.
How to solve 1000? I get that it's some kind of modified mincut, but...
I did it this way.
Let's find all strongly connected components. If the start and the end vertex are in the same component, the answer is -1.
Now we can build a graph where the vertices are strongly connected components and there are all edges from the original graph(except those that lie inside the same component, of course).
If there wasn't an additional condition that we can block only one edge on each path, we could have just found the minimum cut in the graph. But we can adjust the graph in such a way that this condition is satisfied. That is, for each pair of edges (A -> B) and (X -> Y), we should add an edge from X to B with cost = INF if and only if A is reachable from the start vertex, the end vertex is reachable from Y and X is reachable from B.
The minimum cut(or the maximum flow) in this graph is the answer(if it is < INF, otherwise the answer is -1).
I probably should've specified what I know better than "modified mincut", since I only needed point 3 :D
but nice one.
It's enough to add all inversed edges with cost INF, and then find mincut.
But you should remove vertices, which are not on paths from 1 to n. I lost this.
How can you proof this works? At least what is the idea?
Consider a node v which lies on some path from S to T. One can prove that either 1) there is exactly one marked road on any path from S to v, or 2) exactly one marked road on any path from v to T. And if you know what is the case for each node, then you need to mark every road leading from a node of type 1 to a node of type 2. Also, roads mustn't lead from a node of type 2 to a node of type 1.
And you just find the optimal partition using mincut.
If you have 2 cut edges
a->b
andc->d
on a path0--->a->b--->c->d--->(N-1)
, the only case where you can't just remove one of them from the cut to make a smaller valid cut is when there's a path from vertex 0 to some vertex on the pathb--->c
and another path from an earlier (in DAG ordering) vertex onb--->c
to N - 1.If we add an edge
c->b
that can't be cut, it would stop being a valid cut.You can't block any edge of a SCC (because cycles), so join all SCCs into a single vertex, and add costs for every edge between SCCs to get new costs.
Now we still have to enforce "can't go through two blocks" condition. To do this, for every edge in the forward direction, make an edge in the reverse direction with infinite capacity.
And please remember to delete all SCCs that aren't part of any 0 to N-1 path before the mincut, otherwise the troll test will hunt you at night.
For each building compute its maximum possible height. For each constraint t[i] on x[i] it gives t[i] + |x[i] - j| constraint on j. The answer is maximum over the computed heights.
If we have robots a0 ≥ a1 ≥ ... ≥ ak then we can reach distance . We use simple dp[budget][prefix] to compute best value.
I thought it was scc and then flow. But many solutions fails. So there are some tricky cases...
can you provide the explanation for 2nd problem?, please
First part is to get this formula for best reachable distance. Just solve it for 2,3 robots and then some induction argument.
For 2 robots a ≥ b the answer is 0.5(a + b / 3). 2nd robot should turn around in the first moment s such that no fuel will be lost. So first robot should have b - 2s place in his tank (for fuel which is useless for b), so s = b - 2s and s = b / 3.
If we have more robots then we can compute moments in which they have to turn around in the same way. i.e. Each robot should turn around in the first moment such that no fuel will be lost (next robot has already place for useless fuel of actual robot).
After careful computations we get the formula 0.5(a0 + a1 / 3 + a2 / 9 + ...).
The second part is standard dp. We sort robots by increasing capacity. For each prefix of robots k and budget b we compute dp[b][k] which is best distance if we can use only k-first robots and have b dollars. The transition formula is
dp[b][k] = max(dp[b][k - 1], 0.5ak + dp[b - cost[k]][k - 1] / 3).
We can take k-th robot or not.
I couldn't understand div1-500. In the sample test #0, why 2 robots with capacity 1 must stop at 1/3 first? They can stop at very close 0 point, then robot 1 can donate amount of fuel to robot 2 more than when they stop at 1/3. Hence, the largest distance robot 2 can go will as far as possible.
The amount of fuel a robot can contain is limited by its capacity
Can someone please explain how to solve the div-1 500?
Sort the robots by their capacity in increasing order , then apply this dp:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] / 3 + cap[i])
then the final answer is max(dp[n - 1][i]) / 2
I am interested to know about solving Div 2 1000, I got binary search as the only idea which gives wrong answer. Any better ideas?
Betlista wrote a short editorial for Div 2 here. You can see a more detailed discussion for the 1000 problem in the comments.
can anyone please comment on this? I have a problem with understanding what is wrong with my solution:
http://codeforces.me/blog/entry/16046