### cgy4ever's blog

By cgy4ever, history, 3 years ago, ,

Topcoder SRM 715

• +21

 » 3 years ago, # |   0 Holy Mike and Mother of TopCoder! Schedule announced up to end of May!
•  » » 3 years ago, # ^ |   +10 We will announce TCO schedule (online and regionals) very soon — it will be up to September. :P
•  » » 3 years ago, # ^ |   +15 Yes but only 2 rounds a month, how I miss the old days when there were 4 rounds every month :(
 » 2 years ago, # |   +19 Starts in 1 day.
•  » » 2 years ago, # ^ |   +10 Another reminder because participation in rounds at this time is very less.
 » 2 years ago, # |   +31 What was the point of making div1-250 incredibly easier than usual?
•  » » 2 years ago, # ^ |   0 To test people's speedcoding / give randoms a chance to beat reds :)
 » 2 years ago, # | ← Rev. 2 →   +37 I was the writer for this round. Here is the code and some short explanations. div2ImageCompressionFor each pixel, we can find the topleft pixel of the corresponding block. This pixel much match that pixel in order to be compressible. codepublic class ImageCompression { public String isPossible(String[] image, int k) { int n = image.length; int m = image[0].length(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (image[i].charAt(j) != image[i/k*k].charAt(j/k*k)) { return "Impossible"; } } } return "Possible"; } }  MaximumRangeDiv2We can do dp -> dp[a][b][c][d] -> Can we reach the state where we've processed the first a instructions, we currently have X = b, the lowest value of X we saw is c, and the highest value of x we saw is d?.Alternatively, you can notice that one optimal solution will just take all the characters of one sign. codepublic class MaximumRangeDiv2 { public int findMax(String s) { int w = 0; for (char c : s.toCharArray()) if (c == '+') w++; return Math.max(w, s.length()-w); } }  InPrePostNotice that the pre and post traversals tell us what the root is. We can then look into the in order traversal to know what the size of the left and right subtrees are and recurse. The idea for this is relatively simple, but the implementation can get very complicated if you are not careful. codeimport java.util.HashSet; public class InPrePost { public final int PRE = 0, IN = 1, POST = 2; public int[][] child; public int[][] a; public String isPossible(String[] s, int[] a1, int[] a2, int[] a3) { child = new int[3][2]; for (int i = 0; i < 6; i++) { child[i/2][i%2] = getIdx(s[i]); } a = new int[][] {a1, a2, a3}; int n = a1.length; return pok(new int[]{0,0,0}, new int[]{n-1,n-1,n-1}, new int[]{0,1,2}) ? "Possible" : "Impossible"; } public int getIdx(String s) { switch(s) { case "pre": return PRE; case "in": return IN; case "post": return POST; default: throw new RuntimeException(); } } public int[] getId(int[] x) { int[] w = new int[3]; for (int i = 0; i < 3; i++) w[x[i]] = i; return w; } public boolean pok(int[] s, int[] e, int[] cmode) { int clen = e[0] - s[0] + 1; if (clen == 0) return true; if (clen == 1) { if (a[0][s[0]] == a[1][s[1]] && a[1][s[1]] == a[2][s[2]]) { return true; } else { return false; } } int[] w = getId(cmode); int root = a[w[PRE]][s[w[PRE]]]; if (a[w[POST]][e[w[POST]]] != root) { return false; } for (int i = s[w[IN]]; i <= e[w[IN]]; i++) { if (a[w[IN]][i] == root) { int szleft = i - s[w[IN]]; int szright = e[w[IN]] - i; int[] ls = new int[3], le = new int[3], rs = new int[3], re = new int[3], lmode = new int[3], rmode = new int[3]; for (int j = 0; j < 3; j++) { ls[j] = s[j]; re[j] = e[j]; if (cmode[j] == PRE) ls[j]++; if (cmode[j] == POST) re[j]--; lmode[j] = child[cmode[j]][0]; rmode[j] = child[cmode[j]][1]; le[j] = ls[j] + szleft - 1; rs[j] = re[j] - szright + 1; } return pok(ls, le, lmode) && pok(rs, re, rmode); } } return false; } }  div1MaximumRangeOne optimal solution is to take all the characters of the same sign. codepublic class MaximumRange { public int findMax(String s) { int w = 0; for (char c : s.toCharArray()) if (c == '+') w++; return Math.max(w, s.length()-w); } }  ClassicTowersConsider how to compute the minimum number of moves given a configuration. We can iterate through biggest disk to smallest disk. Initially, we'll fix the target rod as the rod containing the largest disk. So now, we have some a target rod, and the current disk we are considering. If the current disk is already at the target rod, we do nothing. Otherwise, WLOG, suppose our target is A, and our current disk is on B. Then, we want to recursively solve the problem when the target is C with one fewer disk, then add 2^(current disk number) (this can be derivied by knowing how towers of hanoi work).We can use this solution to constuct a dp with state (s1, s2, s3, want), meaning we need si disks on the i-th rod, and we want to move them all the the rod want. We can then look at the binary representation of k to determine when we need to switch our target or stay at the current target. codepublic class ClassicTowers { public String findTowers(long k, int[] count) { int ndisks = count[0]+count[1]+count[2]; if (k >= 1L << (ndisks - 1)) return ""; boolean[][][][] dp = new boolean[3][ndisks+1][ndisks+1][ndisks+1]; dp[0][0][0][0] = true; dp[1][0][0][0] = true; dp[2][0][0][0] = true; int[][][][] sw = new int[3][ndisks+1][ndisks+1][ndisks+1]; for (int d = ndisks-1; d >= 0; d--) { if (((k>>d)&1) == 1) { // must switch for (int w = 0; w < 3; w++) { for (int h1 = 0; h1 < ndisks; h1++) { for (int h2 = 0; h2 < ndisks; h2++) { for (int h3 = 0; h3 < ndisks; h3++) { for (int nxt = 0; nxt < 3; nxt++) { if (nxt == w) continue; if (h1+h2+h3 == ndisks-d-1 && dp[w][h1][h2][h3]) { int nh1 = h1, nh2 = h2, nh3 = h3; if (3-nxt-w == 0) nh1++; if (3-nxt-w == 1) nh2++; if (3-nxt-w == 2) nh3++; dp[nxt][nh1][nh2][nh3] = true; sw[nxt][nh1][nh2][nh3] = w; } } } } } } } else { // must stay for (int w = 0; w < 3; w++) { for (int h1 = 0; h1 < ndisks; h1++) { for (int h2 = 0; h2 < ndisks; h2++) { for (int h3 = 0; h3 < ndisks; h3++) { if (h1+h2+h3 == ndisks-d-1 && dp[w][h1][h2][h3]) { int nh1 = h1, nh2 = h2, nh3 = h3; if (w == 0) nh1++; if (w == 1) nh2++; if (w == 2) nh3++; dp[w][nh1][nh2][nh3] = true; sw[w][nh1][nh2][nh3] = w; } } } } } } } for (int i = 0; i < 3; i++) { if (dp[i][count[0]][count[1]][count[2]]) { String ret = ""; int cp = i; for (int j = 0; j < ndisks; j++) { int d = sw[cp][count[0]][count[1]][count[2]]; int which = cp == d ? cp : (3 - d - cp); ret += (char)('A' + which); count[which]--; cp = d; } return ret; } } return ""; } }  PreInPostWe can solve this by dp. We'll let dp[L][R] tell us whether or not it is possible to match the numbers in a1[L..R] with the corresponding numbers in a2. Of course, if the numbers in a2 are not adjacent it is impossible.If t1 or t2 is in "in", this is easy, we can find the root and know the size of the left/right childs and recurse. If they are "post" and "pre", we'll need to try all roots. Overall, this means in the worst case, each dp state may take O(n) time to check.Overall, the idea for this problem is not too complicated, but implementation can get very complicated if you are not careful. codeimport java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; public class PreInPost { public final int PRE = 0, IN = 1, POST = 2; public int getIdx(String s) { switch(s) { case "pre": return PRE; case "in": return IN; case "post": return POST; default: throw new RuntimeException(); } } public int[][] child; public int[][] a; public int x1,x2,x3; public int[] findMissing(String[] s, int[] a1, int[] a2, String e1, String e2) { int[] x; x = new int[]{2,1,3,5,4}; if (check(s,a1,a2,x,e1,e2).equals("")) return x; child = new int[3][2]; for (int i = 0; i < 6; i++) { child[i/2][i%2] = getIdx(s[i]); } int n = a1.length; x1 = getIdx(e1); x2 = getIdx(e2); x3 = 3-x1-x2; a = new int[3][]; a[x1] = a1; a[x2] = a2; mp = new HashMap<>(); ArrayList z = get(new int[]{0,0,0}, new int[]{n-1,n-1,n-1}, new int[]{0,1,2}); if (z.size() > 0) { int[] ret = new int[z.size()]; for (int i = 0; i < z.size(); i++) ret[i] = z.get(i); return ret; } else { return new int[]{}; } } public HashMap> mp; public int[] getId(int[] x) { int[] w = new int[3]; for (int i = 0; i < 3; i++) w[x[i]] = i; return w; } public long hash(int... x) { long ret = 0; for (int b : x) { ret *= 400; ret += b; } return ret; } public ArrayList get(int[] s, int[] e, int[] cmode) { long key = hash(s[x1],s[x2],e[x1],e[x2],cmode[x1],cmode[x2]); ArrayList ret = mp.get(key); if (ret != null) return ret; mp.put(key, ret = new ArrayList<>()); int clen = e[0] - s[0] + 1; if (clen == 0) return ret; if (clen == 1) { if (a[x1][s[x1]] == a[x2][s[x2]]) ret.add(a[x1][s[x1]]); return ret; } int[] w = getId(cmode); int rootpr = x3 == w[PRE] ? -1 : a[w[PRE]][s[w[PRE]]]; int rootpo = x3 == w[POST] ? -1 : a[w[POST]][e[w[POST]]]; if (rootpr != -1 && rootpo != -1 && rootpr != rootpo) return ret; int root = rootpr == -1 ? rootpo : rootpr; for (int szleft = 0; szleft <= clen-1; szleft++) { int szright = clen-1-szleft; if (x3 == w[IN] || a[w[IN]][s[w[IN]]+szleft] == root) { ListPair p = tryRoot(szleft, szright, s, e, cmode); if (p.ok()) { if (x3 == w[PRE]) ret.add(root); ret.addAll(p.left); if (x3 == w[IN]) ret.add(root); ret.addAll(p.right); if (x3 == w[POST]) ret.add(root); break; } } } return ret; } static class ListPair { public ArrayList left, right; public ListPair(ArrayList left, ArrayList right) { this.left = left; this.right = right; } public boolean ok() { return left != null && right != null; } } public ListPair tryRoot(int szleft, int szright, int[] s, int[] e, int[] cmode) { int[] ls = new int[3], le = new int[3], rs = new int[3], re = new int[3], lmode = new int[3], rmode = new int[3]; for (int j = 0; j < 3; j++) { ls[j] = s[j]; re[j] = e[j]; if (cmode[j] == PRE) ls[j]++; if (cmode[j] == POST) re[j]--; le[j] = ls[j] + szleft - 1; rs[j] = re[j] - szright + 1; lmode[j] = child[cmode[j]][0]; rmode[j] = child[cmode[j]][1]; } ArrayList left = get(ls, le, lmode); ArrayList right = get(rs, re, rmode); return new ListPair(left.size() == szleft ? left : null, right.size() == szright ? right : null); } } 
•  » » 2 years ago, # ^ |   +11 You were also the writer for the last 2 contests(w/o this SRM) I participated in :O
 » 2 years ago, # |   +20 How to solve hard? I thought that if the solution is not unique (if it exists) then it will be kinda hard to check it. So I wrote some bruteforce with breaks hoping that bad branches will be very short. And it passes.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 You can see div2 hard on how to check (in essence, you know the root from pre and post, and the in order traversal tells you how to split into left and right subtrees).I'm not sure if it's possible to break a solution like yours.
•  » » » 2 years ago, # ^ |   0 I'm stupid, yeah. I use all that ideas in my bruteforce :)
•  » » 2 years ago, # ^ |   0 Haha also thought about some kind of backtracking hoping it will crash shortly :P. But too late in the contest :<.Actually checking if solution is good is pretty easy. I tried to solve problem recursively and in every execution I was given two orders and two types, but that didn't suffice to make good transitions. But if you are given three orders and three types then you always know what is the root (because you are given both preorder and postorder and can take first/last one in those), what belongs to left subtree and what belong to right (because you know where is root in inorder), so you can proceed recursively and recover whole tree in unique way.
 » 2 years ago, # | ← Rev. 2 →   +57 Div1Easy : competitive typingDiv1Med : no clueWe in range 1400-1500 need an intermediate.
•  » » 2 years ago, # ^ |   +37 I had the following problem when I was an admin:D1 Easy shouldn't be too hard. Otherwise many people will get zero.E ≤ 1500D1 Hard shouldn't be too hard. Otherwise targets will get bored.H ≥ 3000The difference between Easy and Medium should be small. Otherwise intermediate people will get bored.M - E ≤ 700For the same reason, the difference between Medium and Hard should be small.H - M ≤ 700
•  » » » 2 years ago, # ^ |   0 Infeasible (´；ω；｀)
•  » » » 2 years ago, # ^ |   +5 What is E, H, M? The rating that have 50% chance to solve?Btw, do you remember why we wanted to set about 1% solve rate for Div1-Hard? (Even bmerry told me that Div1-Hard is unsolvable in recent years, so I'm thinking about lower the difficulty.)
•  » » » » 2 years ago, # ^ |   0 Please don't take the values very seriously, I just wanted to say that it's very hard to find a problemset that suits everyone.If my memory is correct, CF changed the cutoff between D1 and D2 a few years ago. I think if TC do the same (without changing the difficulties of problems) the situation becomes better. For blue coders D2 Hards look very suitable (they are somewhere between d1 easies and d1 mediums).I don't remember about 1% rate, but that can be outdated given that recently only around 300 people participate in D1 and still lots of very strong people participate. Now I think anywhere between 1 person and 5% is suitable.
•  » » » » 2 years ago, # ^ |   0 Btw why cant topcoder have more problems in a round? Even 1 extra problem would help decrease the massive jumps in difficulty.
•  » » » » » 2 years ago, # ^ |   0 You think the system and the applet are designed enough extensible and tough so that it's possible?
•  » » » » » » 2 years ago, # ^ |   +25 Maybe not. But IMO, topcoder is losing popularity and they have to do something about it before its too late.
•  » » » » » » » 2 years ago, # ^ |   0 I relay think so too :,(
•  » » 2 years ago, # ^ |   +9 I have 1800 and it's the same for me. Solve easy in 10 min and go AFK — that's my typical round. I stopped competing at Topcoder because of that.
•  » » » 2 years ago, # ^ |   +5 I agree. I have 1799 in Topcoder, but last time (SRM 714), I solved easy in 4 min but I can't solve medium. What I feel strongly recently is "Div1-Med difficulty is increasing". The SRM 715-710 Med solved are 20, 45, 22, 2, 107, 6. (Average numbers of competitor is about 270) But SRM 515-510 Med solved are 57, 39, 159, 67, 173, 32. (Average numbers of competitor is about 600) So, I think people who rating is 1500-2200 can solve easy rapidly, but can't solve medium especially Div1-Med's solved is 1-digit. Recently, I'm practicing in Div1-Med. If I could gain performance to 2000+,... but I couldn't solve Div1Med and I would be sad in contest that Div1-Med's solved is 1-digit.
 » 2 years ago, # |   0 Thank you always for the round that has a lot to learn, lewin :)
 » 2 years ago, # |   0 As for Div2-1000, if I assume that preorder and inorder are correct, and generate the postorder traversal of my own as the pseudocode says. Then, if I compare a3 with my_post_traversal, can this be the answer? Please correct me if I'm wrong.
 » 2 years ago, # |   0 wow, it's my first srm, and the result is no too bad, just learn and try.
 » 2 years ago, # | ← Rev. 2 →   +10 ICPC WF spoiler (do not open unless completely sure)Div1 Hard is very similar to ICPC WF 2013 problem K (and, I think, both problems are solved in a very similar way).
 » 2 years ago, # |   -8 Looks like the problem setters have taken this post( http://codeforces.com/blog/entry/51890 ) too seriously.