cgy4ever's blog

By cgy4ever, history, 15 months ago, ,

Topcoder SRM 710

•
• +59
•

 » 14 months ago, # |   +47 This round will start in 22 hours!
 » 14 months ago, # |   +29 Will start in 1 hour.
 » 14 months ago, # |   -95 We need CF round :(
 » 14 months ago, # | ← Rev. 3 →   +27 oh my god! I am feeling so Stupid! euheuheuh I have no idea about div1 A topcoder! Can anyone explain the DIV1 A solution?
•  » » 14 months ago, # ^ |   +23 Type-B is reverse of type-A. Do type-A for two sequences to get the same sequence. Example: the first slot get all stones.
•  » » 14 months ago, # ^ |   0 me too.but the contest does not end
 » 14 months ago, # |   +132 I was the author for this round. I hope you enjoyed the problems! Here are some short hints to the problems along with the code. Div2MagicSubsethint1What if there were no magic stones? hint2What should we do if we take the magic stone? solutionTake the max of the two cases above. codepublic class MagicSubset { public int findBest(int[] values) { int n = values.length; int s1 = 0; for (int i = 1; i < n; i++) s1 += Math.max(0,values[i]); int s2 = values[0]; for (int i = 1; i < n; i++) s2 += Math.min(0,values[i]); return Math.max(s1,-s2); } }  ForwardMancalahint1Choose an arbitrary pile as the "final" pile. What are some strategies to get all the stones in that pile? hint2Do we have enough moves? solutionLet's choose pile 0 as our "final" pile. Then, while there exists a non-empty pile that is not pile 0, do a move on that pile. This is guaranteed to terminate in at most (num stones) * (num piles) steps. codeimport java.util.ArrayList; import java.util.Arrays; public class ForwardMancala { public ArrayList find(int[] start) { ArrayList ret = new ArrayList<>(); int n = start.length; while (true) { boolean changed = false; for (int i = 1; i < n; i++) { if (start[i] > 0) { changed = true; int t = i; int d = start[i]; start[i] = 0; while (d-->0) { t = (t+1) % n; start[t]++; } ret.add(i); } } if (!changed) break; } return ret; } public int[] findMoves(int[] start) { ArrayList ans = find(start); int[] ret = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) ret[i] = ans.get(i); return ret; } }  MinMaxMaxThere are two different approaches. approach1Add the edges in increasing cost. hint1Fix the largest weight node that we will use. Then, we can do something like Kruskal. hint2How long does it take to update a single edge? Maybe try amortized analysis also? code#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define PB push_back #define MP make_pair #define SZ(v) ((int)(v).size()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define FORE(i,a,b) for(int i=(a);i<=(b);++i) #define REPE(i,n) FORE(i,0,n) #define FORSZ(i,a,v) FOR(i,a,SZ(v)) #define REPSZ(i,v) REP(i,SZ(v)) typedef long long ll; class MinMaxMax { public: ll findMin(vector a, vector b, vector w, vector v) { int n=SZ(v),m=SZ(w); vector > ov; REP(i,n) ov.PB(MP(v[i],i)); sort(ov.begin(),ov.end()); vector > ow; REP(i,m) ow.PB(MP(w[i],i)); sort(ow.begin(),ow.end()); vector > d(n,vector(n,LLONG_MAX)); REP(i,n) { vector alive(n,false); REPE(j,i) alive[ov[j].second]=true; vector comp(n); REP(i,n) comp[i]=i; REP(j,m) { int aa=a[ow[j].second],bb=b[ow[j].second]; if(comp[aa]==comp[bb]||!alive[aa]||!alive[bb]) continue; ll cur=(ll)ov[i].first*ow[j].first; vector va,vb; REP(k,n) if(comp[k]==comp[aa]) va.PB(k); else if(comp[k]==comp[bb]) vb.PB(k); REPSZ(ai,va) REPSZ(bi,vb) { int ca=va[ai],cb=vb[bi]; if(cur x.a)); long[][] mn = new long[n][n]; for (long[] x : mn) Arrays.fill(x, 1L << 40); for (int i = 0; i < m; i++) { mn[a[i]][b[i]] = mn[b[i]][a[i]] = w[i]; } long[][] dist = new long[n][n]; for (long[] x : dist) Arrays.fill(x, 1L << 60); for (int e = 0; e < n; e++) { int k = d[e].b; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { mn[i][j] = Math.min(mn[i][j], Math.max(mn[i][k],mn[k][j])); dist[i][j] = Math.min(dist[i][j], 1L * mn[i][j] * Math.max(v[k], Math.max(v[i], v[j]))); } } } long ret = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { ret += dist[i][j]; } } return ret; } }  Div1ReverseMancalahint1The two operations are inverses of each other. hint2We can bring both of them to any common state. solutionRead the problem statement for div2 med. Try to get all the stones into one pile. codeimport java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class ReverseMancala { public ArrayList find(int[] start, boolean rev) { ArrayList ret = new ArrayList<>(); int n = start.length; while (true) { boolean changed = false; for (int i = 1; i < n; i++) { if (start[i] > 0) { changed = true; int t = i; int d = start[i]; start[i] = 0; while (d-->0) { t = (t+1) % n; start[t]++; } if (rev) { ret.add(t+n); } else { ret.add(i); } } } if (!changed) break; } if (rev) Collections.reverse(ret); return ret; } public int[] findMoves(int[] start, int[] target) { ArrayList ans = find(start, false); ans.addAll(find(target, true)); int[] ret = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) ret[i] = ans.get(i); return ret; } }  MagicNimhint1What are some obvious winning or losing states? condition1All piles have 1 stone. Alice can always win by taking the magic stone then deciding based on parity of remaining stones. condition2XOR of all stones is equal to zero. Alice can take the magic stone and leave the victory condition alone. bad movesOtherwise, if the xor is nonzero and there exists a pile with at least 2 stones, then it is not optimal to take the magic stone. Since winning conditions of misere and normal nim are the same when there exists a pile with at least 2 stones, you are passing a winning state to the other player by taking the magic stone. hint2After checking those two cases, we can ignore the lowest bits of all the numbers, as well as the magic stone. solutionThis then becomes a game where a[i] is replaced by a[i]>>1, and the last player who takes a stone loses. This is misere nim. codepublic class MagicNim { public String findWinner(int[] a) { return (Arrays.stream(a).max().getAsInt() <= 3 ? 2 : 1) != Arrays.stream(a).reduce(0, (x,y) -> x^y) ? "Alice" : "Bob"; } }  Hyperboxeshint1Solve the problem when k = 1. hint2Solve a more general version of the problem when k=1, but we also want certain pairs of hyperboxes to be intersecting (described by a bit-mask with (m choose 2) bits). To restate, for every 2^(m choose 2) choices of bitmasks, compute the number of ways to solve this problem in 1 dimension. solutionTwo hyperboxes intersect if and only they intersect in every single dimension. Thus, they are disjoint if we take the bitwise and of all intersections of each dimension and it equals zero. This can be done efficiently with a Fast Walsh Hadamard transform. codepublic class Hyperboxes { public static int mod = 998244353; public static long[] inv; static { inv = new long[20]; inv[1] = 1; for (int i = 2; i < inv.length; i++) { inv[i] = (mod - mod / i) * inv[mod % i] % mod; } } public long choose(long n, int k) { if (k < 0 || k > n) return 0; long ret = 1; for (int i = 0; i < k; i++) { ret = ret * (n-i) % mod; ret = ret * inv[i+1] % mod; } return ret; } public int[] t = {0,1,3,6,10,15}; public int getBit(int i, int j) { if (j > i) { int w = i; i = j; j = w; } return t[i-1] + j; } public boolean nextPermutation(int[] p) { for (int a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.length - 1; ; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } public long mod_exp(long b, long e, long mod) { long res = 1; while (e > 0) { if ((e & 1) == 1) res = (res * b) % mod; b = (b * b) % mod; e >>= 1; } return res; } public int n,m,k; public int[] f1; public int[] f2; public void dfs(int next, int closed, int groupopen, int pclosed, int intersections, int groups, long mult) { if (next == m && closed == (1 << m) - 1) { f1[intersections] += choose(n, groups) * mult % mod; if (f1[intersections] >= mod) { f1[intersections] -= mod; } return; } if (next < m) { dfs(next + 1, closed, (1 << next), -1, intersections, groups + 1, mult); if (pclosed == -1) { dfs(next + 1, closed, groupopen | (1 << next), -1, intersections, groups, mult * inv[Integer.bitCount(groupopen) + 1] % mod); } } // choose to close, continue same group for (int x = pclosed+1; x < next; x++) { if (((closed>>x) & 1) == 1) continue; if (((groupopen>>x) & 1) == 1) continue; int ninter = intersections; for (int w = 0; w < next; w++) { if (w != x && ((closed>>w) & 1) == 0) { ninter |= 1 << getBit(x, w); } } dfs(next, closed|(1<>x) & 1) == 1) continue; int ninter = intersections; for (int w = 0; w < next; w++) { if (w != x && ((closed>>w) & 1) == 0) { ninter |= 1 << getBit(x, w); } } dfs(next, closed|(1<>c)&1) == 1) nmask |= 1 << target; c++; } } f2[nmask] += f1[mask]; if (f2[nmask] >= mod) f2[nmask] -= mod; } while (nextPermutation(perm)); } while (nextPermutation(perm)); } public int findCount(int _n, int _m, int _k) { n = _n; m = _m; k = _k; f1 = new int[1<= 0; i--) { for (int j = 0; j < len; j++) { if (((j>>i)&1) == 0) { f2[j] = (f2[j] + f2[j|(1<>i)&1) == 0) { f2[j] = (f2[j] - f2[j|(1<
•  » » 14 months ago, # ^ |   +31 Nice problems, thank you!
•  » » 14 months ago, # ^ | ← Rev. 2 →   +80 I still don't understand one thing in MagicNim problem solution. Why can we use nim modification with a[i] >> 1? In this case, for example, test with signle pile with 2 stones must have the same answer as test with single pile with 3 stones, but I think it's not true (single pile with 2 stones is loosing, while single pile with 3 stones is winning as we can remove one stone from it and reduce the problem to a pile with 2 stones).
•  » » » 14 months ago, # ^ |   +38 I had a hard time understanding the solution too, and in my opinion the setter hints and solution above lack one specific detail, the last bit of numbers can't simply be 'ignored'. Although the official (and neat) java code is correct :). Hope the following code explains a bit more. codeint xxor = 0; int mx = 0, mx_misere = 0; for(auto i:arr){ xxor ^= i; mx = max(mx, i); mx_misere = max(mx_misere, i >> 1); } if(xxor == 0 || mx == 1) return "Alice"; else{ int xor1 = xxor >> 1; int low = xxor & 1; // misere nim subgame result is lose for current player // reason: some pile with more than one stone // xor of all numbers is 0 if(mx_misere >= 2 && xor1 == 0){ if(low == 1)return "Bob"; else return "Alice"; } // misere nim subgame result is lose for current player // reason: no pile with more than one stone // number of piles odd if(mx_misere <= 1 && xor1 == 1){ if(low == 1)return "Alice"; else return "Bob"; } // misere nim subgame result is win for current player return "Alice"; } 
•  » » » » 14 months ago, # ^ | ← Rev. 6 →   +5 In your code: "if (mx_misere >= 2 && xor1 == 0)"why does Bob wins only when low == 1?I think Bob always wins in this case(regardless of the value of low) because the only hope for Alice to win is to keep xor1 value equal to zero using an odd number and decreasing it by one, but if she does that the original xor value becomes zero and Bob uses the magic stone and wins.UPD: Actually the expression(xor1 == 0 && low == 0) will never be true so there is no problem code-wise(it will get AC).
•  » » » 14 months ago, # ^ |   +13 Yes, sorry, I missed one step. In particular, if the misere nim is a losing case for the current player, the current player can only win if there are an odd number of piles with an odd number of stones. They can win by taking a single stone from some pile with an odd number of moves (i.e. a "pass" move). Only the parity of the number of pass moves matters, since our opponent can copy our passes.
•  » » » » 14 months ago, # ^ |   +28 :) thank you for the problems anyway. This problem really made me feel the 'Misere' part of game theory :)
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +5 Can someone explain how that playing a misere nim game after dividing pile sizes by 2 came up in MagicNim problem? Sorry didn't understood that.
•  » » » » 14 months ago, # ^ |   +16 We know that in MagicNim, two positions are for sure winning:1- all piles with less than two elements: we take the magic stone, and choose the nim if the number of remaining piles is even, otherwise choose misere nim.2- the xor of all numbers is 0: we take the magic stone and choose to play normal nim. Moreover, in any other case you cannot take the magic stone, as in both cases, nim or misere nim, you would leave the adversary in a winning position.Then we can somehow try to simplify the game, and get rid of the magic stone. The first player that after his move leaves the game in one of the two positions above loses (and that's the only way one can lose), so we can define a new game, where there is no magic stone, and the losing positions are the two above. In that new game, we can forget about the last bit in each number, the only thing we need to remember about those bits is the parity. So our new game is a misere nim + (odd-even game with the last bit). And then you get the messy analysis above :)
•  » » » » » 14 months ago, # ^ |   +30 Why we can ignore last bit in each number? I can't understand it(There could be an even->odd move). Anyway, Nim game probs are too hard :(
•  » » » » » » 14 months ago, # ^ |   +3 I couldn't understand it either, maybe someone has to make some graphics, at least I cant :(.To answer your question, the last bit can't be ignored. Imagine we are playing the game where losing positions are those whose xor is 0, or all piles have at most 1 stone, and there is no magic stone (the original game reduces to this one, the last one to move loses, so this is by itself misere).Now the trick for the solution is that in these new game we can define 8 states, following this: each time:there will be some piles with more than one elements, lets say those piles are represented as its half in the misere nim subgame (observe here we are ignoring the last bit), in this subgame we have at most 4 states (as in misere nim), and every time we make a move we can change the parity of the last bits.also there are some piles with one stone: we represent all the last bits on all numbers as one, its xor or parity, whatever, so in this subgame we have two states.in general we have 8 states.now the possible moves are: take a stone from a pile with one stone: this corresponds to changing the parity of the last bit. take some stones from another pile, this corresponds to a move in the misere subgame, and can always change the parity of the last bit.The trick and surprise and solution is that with those 8 states is enough for defining winning and losing positions for the whole game, and that can be proven by analyzing all cases, and all possible transitions...and I can say a lot of problems are too hard :( but wouldn't choose nim games between them :) although this one more than being hard is messy, mostly to explain...
•  » » » » » 14 months ago, # ^ | ← Rev. 3 →   0 Still can't understand why after dividing all number by 2 it becomes a misere nim. I mean the losing state becomes the xor sum of all number is 0 or all number is less than 2. Why we can still use the same way solving the misere nim to solve this by just forgetting about the last bit?
•  » » 14 months ago, # ^ |   +10 Talking about hard problem: The last part could be also easily done with Inclusion–exclusion principle. The hardest part is k = 1. What is your asymptotic? Could you please clarify it? I wrote this part also in a different way: I generate number of way to put segments with compressed coordinates. After that, if I know that there are 100 ways of putting segments (6 segments) onto 11 points with some intersection_mask, then I just add to dp[intersection_mask] += 100 * C(n, 11).I didn't like medium problem: I guess it could only be solved (and very fast, i got ac after writing stupid solution with this approach in a couple of minutes) by looking at a table of numbers.Easy is a cool problem. But I made a bug, so without a small pretest I spent a lot of time trying to find the mistake in the code.
•  » » » 14 months ago, # ^ |   +10 I can give you some loose bounds; there may be better ways to make it tighter. You can also add counters to code to see exact number of operations.I fix the order that the intervals open. Since the intervals can be represented by balanced parenthesis, a very loose bound is catalan(6) * 6! * 2^12 ~ 10^7. More specifically, catalan(6) comes from number of ways to form a balanced parenthesis sequence, 6! comes from number of ways to close parenthesis, and 2^12 comes from number of ways to split the elements into groups where they take the same value. In practice, this is smaller, since I don't expand impossible states. Afterwards, I can do a post-processing step where I can permute the labels. This step takes 2^(m choose 2) * m! * m^2, but actually, if I prune out zero entries (i.e. masks with zero ways), it's actually 2^(m choose 2) + (m!)^2 * m^2. I'm not sure why there are exactly m! nonzero masks before permuting labels.This approach takes 0.5s for everything for my solution in Java.
 » 14 months ago, # |   +11 I don't want to participate in div1 at all but topcoder pushed me too fast, I do not belong there :(
 » 14 months ago, # |   +15 How silly is it to not be able to see that the two operations in Div1 300 are inverses of each other? In retrospect these things always seem so obvious ... :(
•  » » 14 months ago, # ^ |   +25 I tried to make that clear with the first two samples. But, I'm not sure how many people read the samples carefully.
 » 14 months ago, # |   +5 Did anyone try div2 600 using dfs with each vector state as a node ?
 » 14 months ago, # | ← Rev. 2 →   0 .
•  » » 14 months ago, # ^ |   0 Challenges to write editorials are up, though I didn't note when exactly they appeared.
•  » » » 14 months ago, # ^ |   0 yes challenge is now up and that is why I just edited my comment but still they mentioned it like this "just after the srm" challenge will be open.