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

1 | tourist | 3682 |

2 | ecnerwala | 3603 |

3 | Benq | 3549 |

4 | Radewoosh | 3494 |

5 | Petr | 3452 |

6 | ksun48 | 3413 |

7 | maroonrk | 3406 |

8 | Miracle03 | 3314 |

9 | scott_wu | 3313 |

10 | Um_nik | 3299 |

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

1 | 1-gon | 214 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 177 |

7 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 172 |

10 | -is-this-fft- | 169 |

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 20:36:53 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can we submit the problems after the contest ?

How to solve B? Especially interesting that "Shanghai Jiao Tong U" has solved it on the 10th minute after the start:

_Problem B: given a sequence of Ws and Ls, find a set of segments of maximum total length such that each segment has more Ws than Ls._

Interesting problem ,anyone know how to solve it ?

EDIT: totally wrong, as shown by reply below. Thanks for the counterexample!

I haven't tested this yet, but I think it might work. Warning: like most of the algorithms I thought of.. they sounded good in my head, but might turn out to be crap/nonsense in reality, but read on to disprove/ if you think this might inspire a solution.

From the given example, WLWLLLWWLWLWLLWL,

create an array that stores the current elevation after reading k characters, where reading a W gives you a +1 elevation, and L a -1 elevation. From the example, we will get [0 1 0 1 0 -1 -2 -1 0 -1 , etc] So now the problem is, find the maximum set of intervals where each interval.endElevation > interval.startElevation

Then, for each index of the elevation array, find the rightmost index in the elevation array that is greater than elevation[index]. We create an interval object out of this, with start time = index, end time = right most index with elevation > current elevation.

Now the problem is just interval scheduling, and total runtime is O(n log n).

Interval scheduling maximizes number of tasks, not total duration of them.

Nevertheless it is not always optimal to find the rightmost index.

For WLLLWWWLLWLLW optimal solution is W, WWWLLWLLW, not WLLLWWW, W, W

Think how you would solve this using DP in O(n^2) time. Then make it O(n log n) using a tree structure. Maybe there's a greedy that works, but I'm not aware of one.

There are several options how to solve this problem using DP in

O(n^{2}).For example, state can be:

iand having sum equal tolastsum.What DP-solution do you talk about?

Well, which one do you think you can make faster? :)

dp[i][0] = max(dp[i-1][sum] | sum > 0)

The first one looks more promising, but the second is also not very difficult. It is not obvious how

n*log(n)-speed-up can be made.what about dp[i] = max(dp[i-1], dp[i-value[i]] + value[i])? value[i] is the maximum length of the valid segment ending at i. We can precompute value[i] first. If value[i] == 0, dp[i] = dp[i-1].

It is not always optimal to take longest segments.

For example WLLWLLWWWLWLLLW. In optimal solution last W is not connected to anything.

The first formula is nice. Now observe that the second maximum is equal to i + max(dp[j]-j over j such that sum[0..j] > sum[0..i]). So for every j store a pair (dp[j]-j, sum[0..j]) and then on every step you need to take a maximum of the first coordinate over all pairs where the second coordinate is big enough. All you need is a tree allowing to take maximums over segments and to change elements.

thanks for explanation

:) 10 minutes is enough to code a dp with fenwich tree

How To Solve C ?

"It looks like the connecting graph in problem A can always be represented as: a path connecting two of the chosen nodes, another path connecting two of the chosen nodes, then a path connecting those paths. Then we can do the following: first, for each vertex in the graph, let's find the shortest distance to each of the chosen nodes. Then, by summing two of those, we obtain "the cheapest way to connect two nodes with a path going through vertex X". And then, we can run another Dijkstra starting with those values that would deduce "the cheapest way to connect two nodes with a path and then connect that path to vertex X". Finally, summing those numbers for two different pairs of nodes should give the answer."

Second part of the solution is not clear. We have N variants for vertex X, and run Dijkstra O(M log N), then we find within O(N) vertex Y, that the way (X-Y-two other nodes) is cheapest. Solution is C(2,4)*O(N*(M log N + N)) = ~10^10. Is 4.5 seconds enough for this solution?

I think that D is the similar problem as SPOJ SUBLEX, which is solvable by using a Suffix Automaton.