| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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(n2).
For example, state can be:
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
I think that D is the similar problem as SPOJ SUBLEX, which is solvable by using a Suffix Automaton.