### cgy4ever's blog

By cgy4ever, history, 6 years ago,

Topcoder SRM 714

At the same time there will be an onsite contest: https://tco17.topcoder.com/regional-events/st-petersburg-russia/. We will share problems for both SRM and this regional contest.

Calendar: https://www.topcoder.com/community/events/ (Note: Still not updated)

• +20

 » 6 years ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 5 years ago, # |   0 Update: added start time and link to regional contest.
 » 5 years ago, # |   +13 Contest coming!
 » 5 years ago, # |   +13 We will share problems for both SRM and this regional contest.Will the onsite regional event have div. 2 or div. 1 problemset?
•  » » 5 years ago, # ^ |   +38 We need a problemset that are good for both first time player and TCO winner, we will use Div2 Easy, Div1 Easy and Div1 Hard, so hopefully everyone can enjoy it.
 » 5 years ago, # |   +8 Registration open. Update: start time is 2:00 pm instead of 1:30.
 » 5 years ago, # |   +61 Is topcoder down at the moment, I can't enter Arena?
•  » » 5 years ago, # ^ |   +8 Same. It's down for me as well.
 » 5 years ago, # |   +40 Hard is very nice!What's the intended solution of Med? Straightforward solution works in O(KlogMAX * memoizationcost), but I struggled a lot with TL.
•  » » 5 years ago, # ^ |   0 I'm extremely sorry if what i'm gonna explain now is wrong, as i am incredibly inexperienced -> each time from f(n) we use f(n / 2) and f((n + k) / 2), Look at this tree of states, in each level the difference between the state with minimum number and maximum number is at most k, so that's why we can use an array of size k for each level, that would make the memoization cost O(1), of course please correct me if i'm wrong
•  » » 5 years ago, # ^ |   +15 Since all subtasks we get are in form of "calculate answer on segment [1, n / 2^x + y]", y <= K, n is L or R, memorization can be a simple array lookup. It works fast even in Java.
•  » » 5 years ago, # ^ |   +10 My submitted solution was buggy, but I still think it can be solved like this (not sure what are your solutions memoizing, so I don't know how different it is; skipping some +/-1 adjustements): we compute the values for even numbers [L, L+K) directly, as well as for odd numbers in (R-K, R]. The rest of [L, R] can be split into even numbers from [L+K, R], and odd numbers that directly correspond to them. So we can solve recursively for the [(L+K)/2, R/2].memoization_cost is then replaced by the cost of directly compuing Klog MAX values, so I guess by log MAX with a low constant.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +23 No memoization: Go from the end, fix finishing number x ≤ K. Now if we look at the tree of numbers generated by going backwards from x, they will be of the form x2p - kq, where 0 ≤ q < 2p - 1 . Number of applications of f for such number is simply p + numberOfBits(q). Now it can be easily summed up over numbers from [L, R] if x and p are fixed.
•  » » 5 years ago, # ^ |   +20 It seems the only thing I needed to do was to replace a map with unordered_map.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +25 Another one, without memoization :Let Si = sum of g(i) for [K + 1, i + K]. Then, Si = i + (Si / 2) + (S(i - K) / 2 + i / 2). However, we can naively calculate g(i) in O(lgN) time. So, If we know S(i - K) / 2, we can know Si / 2 in O(KlgN) time. T(N) = O(KlgN) + T(N / 2) = O(K(lgN)2).
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Can you please explain the proof?
•  » » » » 5 years ago, # ^ |   0 Well, what requires proof?
•  » » » » » 5 years ago, # ^ |   0 I'm not quite sure how you derived Si = i + Si / 2 + S(i - K) / 2 + i / 2? Just intuition behind it would be useful. Thanks in advance.
•  » » » » » » 5 years ago, # ^ |   +3 That is a recursive definition, try to separate cases for odd / even number in interval, and write what happens next for both numbers.
 » 5 years ago, # |   +41 I was the author of this round except for div1 medium. I hope you enjoyed the round!After this round, I've got 99 problems on Topcoder.Here is some of the code and hints for the problems. div2RangeEncodinghint1All numbers are distinct, and they are given in increasing order. hint2A range will take consecutive elements in this list. hint3We can try greedy. codeclass RangeEncoding(): def minRanges(self,a): return len(a)-sum(y==x+1 for x,y in zip(a,a[1:]))  RemovingParenthesishint1How many distinct strings can we possibly generate? answerAn easy upper bound is 2^20. hint2We can try to simulate the process, but memoize answers. codeimport java.util.*; public class RemovingParenthesis { Map memo = new TreeMap<>(); public int countWays(String s) { if (memo.containsKey(s)) { return memo.get(s); } if (s.isEmpty()) { return 1; } int balance = 1; int ans = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == '(') { balance++; continue; } ans += countWays(s.substring(1, i) + s.substring(i + 1)); balance--; if (balance == 0) { break; } } memo.put(s, ans); return ans; } }  SaleswomanThere are two approaches approach 1hint1Try dp hint2We can satisfy the demands from left to right. So, we just need to keep track of the rightmost person who's demands have satisfied. Similarly, we need to keep track of the rightmost person who's supply we have taken. Lastly, we need another parameter for where are currently at. code#include using namespace std; int n; int where[301]; int sumDemand[301]; int sumSupply[301]; int mem[301][301][301]; int f(int cur, int demandClear, int arrived) { if(demandClear == n) return abs(where[n] - where[cur]); if(mem[cur][demandClear][arrived] != -1) return mem[cur][demandClear][arrived]; int ret = 1000000001; if(arrived != n) ret = min(ret, f(arrived+1, demandClear, arrived + 1) + abs(where[cur] - where[arrived+1])); if((demandClear < arrived) && (sumDemand[demandClear+1] <= sumSupply[arrived])) ret = min(ret, f(demandClear+1, demandClear + 1, arrived) + abs(where[cur] - where[demandClear+1])); mem[cur][demandClear][arrived] = ret; return ret; } class Saleswoman { public: int minMoves(vector pos, vector delta) { n = pos.size(); where[0] = 0; sumDemand[0] = 0; sumSupply[0] = 0; for(int i = 1; i <= n; i++) { where[i] = pos[i-1]; sumDemand[i] = sumDemand[i-1]; sumSupply[i] = sumSupply[i-1]; if(delta[i-1] < 0) sumDemand[i] += -delta[i-1]; else sumSupply[i] += delta[i-1]; } memset(mem, 0xff, sizeof(mem)); return f(0, 0, 0); } };  approach 2hint1Try greedy hint2We can satisfy demands from left to right. One example of Alice's optimal strategy is to only turn back if she can satisfy every person behind her. codepublic class Saleswoman { public int minMoves(int[] pos, int[] delta) { int n = pos.length; int chave = 0; int cneed = 0; int goback = 0; int cdist = pos[n-1]; for (int i = 0; i < n; i++) { if (delta[i] < 0) { if (cneed == 0 && chave >= -delta[i]) { chave -= -delta[i]; } else { if (cneed == 0) { goback = pos[i]; } cneed += -delta[i]; } } else { chave += delta[i]; if (cneed > 0 && chave >= cneed) { chave -= cneed; cneed = 0; cdist += 2 * (pos[i] - goback); } } } return cdist; } }  div1ParenthesisRemovalhint1Let x[i] be the number of openining parenthesis before the i-th closing parenthesis. Then, we need this parenthesis to be removed at turn x[i] or before. hint2This is also a sufficient condition. To show this, we will show that if the balance for a particular closing parenthesis goes below zero, then it will be removed after turn x[i].In particular let's look at the leftmost parenthesis whose balance goes negative. At this point we matched i-1 closing parenthesis to its left correctly and this does not effect the balance. In addition for its balance to go negative, we need to match at least x[i]-i+1 other closing parenthesis on its right. So the first turn we can match this closing parenthesis is strictly after turn x[i] which completes the claim. hint3Using those conditions, we can see the answer is x[0] * (x[1]-1) * (x[2]-2) * ... code#include using namespace std; long long mod = 1000000000 + 7; class ParenthesisRemoval { public: int countWays(string s) { long long ret = 1; int balance = 0; for(int i = 0; i < s.length(); i++) { if(s[i] == '(') balance ++; else { ret *= balance; ret %= mod; balance --; } } return (int)ret; } };  Salesmanhint1Try to solve Saleswoman (div2 hard) in linear time. hint2WLOG, suppose we go to leftmost point first. This allows us to fix the leftmost visited point. What is the rightmost point we need to visit in this case? hint3We need to deal with the fact that we can end anywhere we want. We can do that while we are simulating our greedy solution. codepublic class Salesman { public int minMoves(int[] pos, int[] delta) { int n = pos.length; int ans = solve1(pos, delta); for (int i = 0, j = n-1; i < j; i++, j--) { int t = pos[i]; pos[i] = pos[j]; pos[j] = t; t = delta[i]; delta[i] = delta[j]; delta[j] = t; } for (int i = 0; i < n; i++) pos[i] = -pos[i]; ans = Math.min(ans, solve1(pos, delta)); return ans; } public int solve1(int[] pos, int[] delta) { int n = pos.length; int rightneed = n-1; while (rightneed >= 0 && delta[rightneed] >= 0) rightneed--; if (rightneed < 0) return 0; int[] ndemand = new int[n+1]; ndemand[n] = n; for (int i = n-1; i >= 0; i--) { if (delta[i] < 0) ndemand[i] = i; else ndemand[i] = ndemand[i+1]; } int ans = 1 << 30; outer : for (int left = 0; left < n; left++) { int right = rightneed; int csum = 0; for (int i = left; i <= right; i++) { csum += delta[i]; } while (csum < 0) { right++; if (right >= n) break outer; csum += delta[right]; } int cdist = Math.abs(pos[left]) + (pos[right] - pos[left]); int chave = 0; int cneed = 0; int goback = 0; for (int i = left; i <= right; i++) { if (delta[i] < 0) { if (cneed == 0 && chave >= -delta[i]) { chave -= -delta[i]; } else { if (cneed == 0) { goback = Math.max(goback, pos[i]); } cneed += -delta[i]; } } else { chave += delta[i]; if (cneed > 0 && chave >= cneed) { chave -= cneed; cneed = 0; cdist += 2 * Math.max(0, pos[i] - goback); } } int bb; if (cneed > 0) { bb = goback; } else { bb = pos[Math.min(right, ndemand[i+1])]; } ans = Math.min(ans, cdist + Math.max(0, (pos[right] - bb))); } if (delta[left] < 0) break; } return ans; } } 
•  » » 5 years ago, # ^ |   +10 Can we solve RemovingParenthesis in O(n)? Somebody in my room did it using stack.
•  » » » 5 years ago, # ^ |   +6 Yes, see ParenthesisRemoval from div1.
•  » » 5 years ago, # ^ |   +3 I know that one of the submitted hard are wrong. For example, on test where we should shuffle for a lot of times: (pos=-1+1000*k,delta=-1),(pos=1000*k,delta=1) for k in [1..100]. Do you have such a test?
•  » » 5 years ago, # ^ |   0 My Div500 passed without memorization
 » 5 years ago, # |   +13 Is TOPCODER Arena Down???
•  » » 5 years ago, # ^ |   -13 Yes, I also can't enter
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Works now, but active contests are gone :Dedit: back now :)