### Lewin's blog

By Lewin, history, 5 years ago,

Didn't notice a post from cgy4ever.

Topcoder SRM 718 will happen in ~4 hours.

• +83

 » 5 years ago, # |   +35 I was the author of this round. You can see some short explanations here: div2RelativeHeightsWe can just simulate what's asked in the problem. Be careful about comparing arrays for equality. codeclass RelativeHeights(): def countWays(arr): def normalize(r): w = list(sorted(r)) return [r.index(x) for x in w] print len(set(tuple(normalize(arr[:i] + arr[i+1:])) for i in range(len(arr))))  InterleavingParenthesisDiv2Hint: This is a DP problem. What do we need to remember? How exactly are correct parenthesis sequences formed? hint1First, 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. hint2We 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. codepublic class InterleavingParenthesisDiv2 { public int mod = 1000000007; public int countWays(String s1, String s2) { int n = s1.length(), m = s2.length(); int[] p1 = new int[n+1], p2 = new int[m+1]; for (int i = 1; i <= n; i++) p1[i] = p1[i-1] + (s1.charAt(i-1) == '(' ? +1 : -1); for (int i = 1; i <= m; i++) p2[i] = p2[i-1] + (s2.charAt(i-1) == '(' ? +1 : -1); int[][] dp = new int[n+1][m+1]; dp[0][0] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (p1[i] + p2[j] < 0) { dp[i][j] = 0; continue; } if (i>0) dp[i][j] += dp[i-1][j]; if (j>0) dp[i][j] += dp[i][j-1]; dp[i][j] %= mod; } } return p1[n] + p2[m] == 0 ? dp[n][m] : 0; } }  ChainCityhint1Look at example 3. hint2Example 3 suggests if we want to split our line into k parts such that the maximum length part is minimized. hint3Let's try to reverse the problem and use binary search instead. Now, we can see that we can proceed greedily. codepublic class ChainCity { public int findMin(int[] dist, int k) { int n = dist.length; int sum = 0; for (int x : dist) sum += x; int lo = 0, hi = sum; while (lo < hi) { int mid = (lo + hi) / 2; long curlen = 0; int nums = 1; for (int x = 0; nums <= k && x < n; x++) { if (dist[x] + curlen > mid) { nums++; curlen = 0; } else { curlen += dist[x]; } } if (nums <= k) hi = mid; else lo = mid+1; } return lo; } }  div1InterleavingParenthesisYou 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). codepublic class InterleavingParenthesis { public int mod = 1000000007; public int countWays(String s1, String s2) { int n = s1.length(), m = s2.length(); int[] p1 = new int[n+1], p2 = new int[m+1]; for (int i = 1; i <= n; i++) p1[i] = p1[i-1] + (s1.charAt(i-1) == '(' ? +1 : -1); for (int i = 1; i <= m; i++) p2[i] = p2[i-1] + (s2.charAt(i-1) == '(' ? +1 : -1); int[][] dp = new int[n+1][m+1]; dp[0][0] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (p1[i] + p2[j] < 0) { dp[i][j] = 0; continue; } if (i>0) dp[i][j] += dp[i-1][j]; if (j>0) dp[i][j] += dp[i][j-1]; while (dp[i][j] >= mod) dp[i][j] -= mod; } } return p1[n] + p2[m] == 0 ? dp[n][m] : 0; } }  CircleCityhint1Think about what happens if this is a line. Also, see example 3. hint2Read the solution for ChainCity in div2. codepublic class CircleCity { public int findMin(int[] dist, int k) { int n = dist.length; int sum = 0; for (int x : dist) sum += x; int lo = 0, hi = sum; while (lo < hi) { int mid = (lo + hi) / 2; boolean ok = false; for (int start = 0; !ok && start < n; start++) { long curlen = 0; int nums = 1; for (int x = 0; nums <= k && x < n-1; x++) { int curpos = (start + x) % n; if (dist[curpos] + curlen > mid) { nums++; curlen = 0; } else { curlen += dist[curpos]; } } ok |= nums <= k; } if (ok) hi = mid; else lo = mid+1; } return lo; } } Challenge: Originally, I had proposed this with constraints n <= 200,000. You can try to solve this version. PermutationSubsequencehint1When do we have f(arr, |arr|-1) = |arr|? hint2Can we generalize this condition to when f(arr, |arr|-k) = (|arr| choose k)? hint3Try 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? codepublic class PermutationSubsequence { public boolean ok(int[] brr, int[] arr, int idx, int used, int k) { if (idx == brr.length) return true; for (int i = 0; i < brr.length; i++) { if (((used >> i) & 1) == 0 || arr[idx] == i) { boolean ok = true; for (int j = 0; ok && j < idx; j++) { if (idx - j + Math.abs(i - brr[j]) < k) ok = false; } if (ok) { brr[idx] = i; if (ok(brr, arr, idx+1, used|(1<= 0) uu |= 1 << x; for (int i = n; i >= 1; i--) { if (ok(ret, arr, 0, uu, i)) { return ret; } } return null; } } 
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 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...
•  » » 5 years ago, # ^ |   +18 CircleCity for n ≤ 200 000.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 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.
 » 5 years ago, # |   +10 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.
•  » » 5 years ago, # ^ |   +8 Your condition is close, but you also need to consider nonadjacent elements. More specifically you need to look at this expression spoilermin(|i-j| + |a[i] - a[j]|) over distinct positions i,j
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Is this condition Spoilermin(|i-j| + |a[i] — a[j]|) <= X sufficient for X > 1? Otherwise, what would you do to compute g(arr)?
•  » » » 5 years ago, # ^ |   0 How to prove this?
 » 5 years ago, # |   +28 jiry_2's color is red in yellow..., so mysterious! I think it's a bug, right? (His topcoder rating is 2808)