Didn't notice a post from cgy4ever.
Topcoder SRM 718 will happen in ~4 hours.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Didn't notice a post from cgy4ever.
Topcoder SRM 718 will happen in ~4 hours.
Name |
---|
I was the author of this round. You can see some short explanations here:
We can just simulate what's asked in the problem. Be careful about comparing arrays for equality.
Hint: This is a DP problem. What do we need to remember? How exactly are correct parenthesis sequences formed?
First, let '(' denote +1, and ')' denote -1. Then, a sequence is correct if all prefixes have nonnegative sum, and the overall sequence has sum 0. Let's ignore the constraint about overall sum being 0 (we can easily check this before doing anything). So, correct sequence can be extended from a previous correct sequence as long as its prefix sum stays nonnegative. So, this helps us write a dp state dp[i][j][k] -> # ways to form a correct sequence given we've used i characters from the first sequence, j characters from the second sequence, and our current prefix sum is k. This is fast enough for this problem.
We don't actually need to store the actual prefix sum, since it's uniquely determined by the first i characters of the first string and first j characters of the second string.
Look at example 3.
Example 3 suggests if we want to split our line into k parts such that the maximum length part is minimized.
Let's try to reverse the problem and use binary search instead. Now, we can see that we can proceed greedily.
You can look at the solution for the div2 version of this problem (it is almost exactly the same, but you just need to make the observation in hint2 also).
Think about what happens if this is a line. Also, see example 3.
Read the solution for ChainCity in div2.
Challenge: Originally, I had proposed this with constraints n <= 200,000. You can try to solve this version.
When do we have f(arr, |arr|-1) = |arr|?
Can we generalize this condition to when f(arr, |arr|-k) = (|arr| choose k)?
Try to come up with a way to compute g(arr) in polynomial time. Then, this means we can run a brute force over all permutations. This might be a bit slow for n=12, so are there ways to prune?
Why such a big size in d1-250? I got tle just because I used the map instead of an array...
Edit. I just checked that |si| <= 1000 would fit within time limit, yet the incorrect O(n^3) solutions would still tle. I really don't get a point in such a huge string size...
Edit2. Ok — my bad, looks like some O(n^3) solutions might have passed or maybe my test was too weak. Anyway sad that I failed that task. True story is that even though I had O(|s1|*|s2|) solution, I stored a third parameter in the map. After the contest I realized that I do not need this parameter and hence I can use an array, without changing logic...
CircleCity for n ≤ 200 000.
Maybe it's quarterly true, though, I think you should return CircleCity to the problem of Zeptolab's (it means if you solve CircleCity you can solve Zeptolab's if the constraints are same, but not vice versa). Because CircleCity is "placing k teleporters" and after a few ideas it can return the problem of "for given cycle graph you can erase atmost k edges, what is the maximum length of component?". After that it is easy greedy + binary-search because n ≤ 2000, so maybe it is not a main part. And also, Lewin already solved this Zeptolab's problem.
Any hints for 1000 pointer?
I could prove that for f(P, k) = C(n, k) we must have difference between adjacent elements of P ≥ n + 1 - k. But it seems it is not a sufficient condition.
Your condition is close, but you also need to consider nonadjacent elements. More specifically you need to look at this expression
min(|i-j| + |a[i] - a[j]|)
over distinct positions i,jIs this condition
min(|i-j| + |a[i] — a[j]|) <= X sufficient for X > 1?
Otherwise, what would you do to compute g(arr)?
How to prove this?
jiry_2's color is red in yellow..., so mysterious! I think it's a bug, right? (His topcoder rating is 2808)