Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### memset0's blog

By memset0, history, 3 years ago, ,

Hi All,

Topcoder Single Round Match 701 will be held 26 October 05:00 PM BDT

Wish you all good luck. Let's discuss the problems after the contest .

EDIT : This match is sponsored by booz allen hamilton. winners will get t-shirts from Booz Allen Hamilton .

• +68

 » 3 years ago, # |   +3 The match announcement promises t-shirts from Booz Allen Hamilton again (and this should really be included in the blog announcement, not in the comments). Not sure whether this is a copy-paste error, I guess we'll just have to wait and see :-)
•  » » 3 years ago, # ^ |   0 I apologize. I was not sure about the prizes. EDITED and thanks
•  » » 3 years ago, # ^ |   0 I could not find the t-shirt announcement in the web arena. ( It only mentions sponsored by BAH). I guess its there in the applet. To popularise it better, the announcement should also be put in Web arena.
•  » » 3 years ago, # ^ |   +19 What's the criteria for getting t-shirts?
 » 3 years ago, # |   +64 I would prefer srm announcements from one person and I think that cgy4ever is the best option. Finding an old discussion would be so much easier then, just scrolling through his blogs. Searching the blog in google or in codeforces-search doesn't give instant results sometimes.
•  » » 3 years ago, # ^ |   +25 then I will cordially request cgy4ever for posting srm announcements from next SRMs
•  » » 3 years ago, # ^ |   +31 I think a special account made for Topcoder admins is an even better option.
•  » » 3 years ago, # ^ |   +83 Okay, I will add a blog for each SRM once I know it — so you can view my blog to see the schedule of upcoming SRMs.And I will update it about 24 hours before the contest so that it will be in the "recent actions" list.
•  » » » 3 years ago, # ^ |   0 Thank you so much. :)
 » 3 years ago, # | ← Rev. 2 →   +17 Has anyone used the Web Arena recently? Has it improved? (e.g. stable to use, can challenge normally, etc.)Also is there any way to generate class definition, test codes... for the web arena?
•  » » 3 years ago, # ^ |   +15 It is definitely a lot more stable than it was before. Not faced any issue in the past few srms i participated. I have not yet found any method to generate these.
 » 3 years ago, # |   0 The competition just finished. Can someone please tell me how to solve Div2. 1000 pointer ? I partially computed the state (win/lose) for numbers upto 1,000,000. For numbers greater than that I used recursion to reach numbers <= 1,000,000. But It didn't work, I was getting seg fault. Anyone who solved the problem, Kindly share the approach and if possible, a link for the code. Much Thanks.
 » 3 years ago, # |   +18 Any hint for Div1.600 ? There seems to be a crucial insight ?
•  » » 3 years ago, # ^ |   +13 The first character of the string can either be at the first position or the last (since only reversal m affects it).Then, of the remaining positions of the final string that aren't fixed, the second character of the original string can either be at the first position or the last, and so on...Now use this observation to make a DP function that counts how many of the resulting strings have a prefix p. My DP state was (how many characters in front, how many characters in back).
 » 3 years ago, # |   0 How to solve div2 900 problem ?? Any hints
 » 3 years ago, # |   0 How to solve Div2 900?I saw only one person who passed all tests.
•  » » 3 years ago, # ^ |   0 How to view the global leaderboard ?? I could only find the room summary leaderboard. I am new to topcoder .
•  » » » 3 years ago, # ^ |   +1 Active contests -->>> SRM 701 --->>> Division summary
•  » » » » 3 years ago, # ^ |   +1 got it. thanks..
 » 3 years ago, # |   +8 How to solve div1 300 ?
•  » » 3 years ago, # ^ |   +14 What I did was this, the boolean value DP[0][n] denotes whether it is a winning position for Alice or not, and DP[1][n] denotes the same for Bob. I calculated these values till 1e5. Consider any 5 consecutive values of DP[0] array. There are at most 2^5 = 32 such sequences. So if you precompute till 1e5, one is bound to repeat. Using that I found the length of the cycle (let it be len). Then answer is DP[0][n % len].
•  » » » 3 years ago, # ^ |   0 Consider any 5 consecutive values of DP[0] array.  Why 5 elements is enough, but not 1+2+3+4+5=16?
•  » » » » 3 years ago, # ^ |   +8 Because you take either 1,2,3,4 and/or 5 elements from the pile. So, DP[0][i] depends on DP[1][i-1], DP[1][i-2], DP[1][i-3], DP[1][i-4] and/or DP[1][i-5]. :)
•  » » » » » 3 years ago, # ^ |   0 Hey satyaki3794, I was looking at your code for this problem. I couldn't understand one thing. Why don't you break off the loop once you have the cycle value for the first time.I mean shouldn't the cycle value remain constant? I tried this but this gives a WA? Can you please explain what is wrong with this idea?
•  » » » » » » 3 years ago, # ^ |   0 Yes, cycle value should remain constant. Breaking off the loop when you get cycle value for the first time shouldn't change the answer. There must be some other bug in your code.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 Hi satyaki3794, even i tried by the same approach but breaking off when i get the cycle for first time fetched WA. Gives AC when submitted without the break statement. Code#include using namespace std;int dp[2][200]; int mask[100];class PartisanGame { public: string getWinner(int n, vector a, vector b) { memset(mask, 0, sizeof(mask)); dp[0][0] = dp[1][0] = false; for(int i=1; i<200; i++) { dp[0][i] = dp[1][i] = false; for(int j=0; j=i; j--, k++) { if(dp[0][j]) { nw+=(1<
•  » » » 3 years ago, # ^ |   0 I'm trying to understand why you picked 1e5. If each group has 5 things and there are 32 possible groups, then after 5*32=160, the next group should be a repeat. So is checking 165 enough, or was 1e5 significant for some other reason? Thanks.(I just noticed that 165 and 1e5 are similar, with e being upside down 6 :-)
•  » » » » 3 years ago, # ^ |   +1 165 is enough. No special reason for 1e5.
•  » » » » » 3 years ago, # ^ |   0 Awesome. Thank you!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Is this correct? Code#include using namespace std; class PartisanGame { public: string getWinner(int N, vector a, vector b); }; string PartisanGame::getWinner(int N, vector a, vector b) { string ret1 = "Alice"; string ret2 = "Bob"; vector < int > f(1<<21,0) , g(1<<21,0) , fail(1<<21,0); int j = 0 , i ; for(i=1;i=v) f[i] = f[i] || !g[i-v]; for(auto &v:b) if(i>=v) g[i] = g[i] || !f[i-v]; if(i!=1){ while(j && f[j+1]!=f[i])j = fail[j]; if(f[i]==f[j+1])++j; fail[i]=j; } } int period = f.size()-1-j; --N; N%=period; return f[N+1]?ret1:ret2; } 
 » 3 years ago, # |   -39 I need some Help :D Here's my solution for 250 Div2 #include #define pb(x) push_back(x) #define bug cout<<"HERE"<( \ ( std::ostringstream() << std::dec << x ) ).str() #define clr(x,y) memset(x,y,sizeof(x)) #define all(v) v.begin(),v.end() #define FOR(i,l) for(int i=0;i=0;--i) #define fast ios_base::sync_with_stdio(0); cin.tie(0); #define inp freopen("input.txt", "r", stdin); #define out freopen("output.txt", "w", stdout); using namespace std; typedef long long ll; typedef vector vi; inline int toInt(string s){int v; istringstream sin(s);sin>>v;return v;} inline ll toll(string s){ll v; istringstream sin(s);sin>>v;return v;} class SquareFreeString{ public : string isSquareFree(string s){ int n = (int)s.length(); bool f = 0; FOR(i,n){ FOR1(j,i+1,n){ string cur = ""; for(int k=i;k<=j;++k)cur+=s[k]; if(cur.length()%2==0){ if(cur.substr(0,cur.length()/2)==cur.substr(cur.length()/2,cur.length())) f = 1; } } } return f ?"not square-free\n":"square-free\n"; } }; //int main (){ // SquareFreeString x ; // // cout <
 » 3 years ago, # |   +37 I was a writer this time. That's my 4th Single Round Match at TopCoder) Sorry for inconvinience in PartisanGame, I forget to add constraint that a and b are non-empty, so this case was not present at samples. Hope you liked the tasks anyway) Short editorials: div2-easy SquareFreeString:Just check each substring. codeclass SquareFreeString(): def isSquareFree(self,s): return any((lambda w: len(w)%2 == 0 and w[:len(w)/2] == w[len(w)/2:])(s[i:i+j]) for j in range(1,len(s)+1) for i in range(len(s)-j+1)) * "No" or "Yes" div2-medium SortingSubsets:Which elements will remain on its own positions after sorting? Precisely this elements we will not take to our set. code public static int getMinimalSize(int[] a) { int n = a.length; int[] b = new int[n]; for (int i = 0; i < n; ++i) b[i] = a[i]; Arrays.sort(b); int ans = n; for (int i = 0; i < n; ++i) if (a[i] == b[i]) --ans; return ans; } div-2 hard ThueMorseGame:O(n) solution using bitmasks. code public static String get(int n, int m) { long full = (1l << m) - 1; long mask = full; for (int i = 0; i <= n; ++i) { int win; if (Integer.bitCount(i) % 2 == 1 || mask != full) win = 1; else win = 0; mask = ((mask << 1) | win) & full; } return (mask & 1) == 1 ? "Alice" : "Bob"; } div1-easy PartisanGame:One can see that we win/lose on next position for Alice and Bob depends only on last five positions, so period will be not greater than 1024 (in fact, maximal period is around 20). codeclass PartisanGame(): def getWinner(self,n,a,b): a = list(a) b = list(b) if n == 0: return "Bob" MAXK = 5 lw = (1<<(MAXK<<1)) def getNext(mask): amask = mask >> MAXK bmask = mask & ((1<>1) | (winA << (MAXK-1)) bmask = (bmask>>1) | (winB << (MAXK-1)) return (amask << MAXK) | bmask def mult(p,q): return [p[q[i]] for i in xrange(lw)] perm = [getNext(i) for i in xrange(lw)] ret = [i for i in xrange(lw)] n += 1 while n > 0: if n % 2 == 1: ret = mult(ret, perm) perm = mult(perm, perm) n >>= 1 return (ret[lw-1] >> (2*MAXK-1)) * "Alice" or "Bob" div1-medium KthStringAgain:One can notice that strings in the collection can be obtained using following pseudocode: L = 0, R = |s|-1, res[0...(|s|-1)] (resulting string) from c = s[0] to s[|s| - 1] we can choose one of: 1. res[L++] = c 2. res[R--] = c add res to collection Using this, we can easily calculate number of strings with given prefix. codepublic static long count(String s, String p) { int n = s.length(); int m = p.length(); long[][] d = new long[n + 1][n + 1]; d[0][0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { int l = j; int r = n - 1 - (i - j); if (l >= m || s.charAt(i) == p.charAt(l)) d[i + 1][j + 1] += d[i][j]; if (r >= m || s.charAt(i) == p.charAt(r)) d[i + 1][j] += d[i][j]; } } long ans = 0; for (int j = 0; j <= n; ++j) ans += d[n][j]; return ans; } public static String getKth(String s, long k) { --k; int n = s.length(); String ans = ""; for (int i = 0; i < n; ++i) { for (char c = 'a'; c <= 'z'; ++c) { String p = ans + Character.toString(c); long cnt = count(s, p); if (cnt <= k) { k -= cnt; } else { ans = ans + Character.toString(c); break; } } } return ans; } div1-hard FibonacciStringSum:This hard intended to be easier than usual.One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) ... f(n-2 * (a + b + 1), a, b).Coefficients of linear reccurence can be found using gauss elimination or directly (say, using generating functions or other reasoning). code public static int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; } public static int sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; } public static int mul(int x, int y) { long p = (long) x * (long) y % mod; return (int) p; } public static int binpow(int x, int to) { int y = 1; while (to > 0) { if ((to & 1) == 1) y = mul(x, y); x = mul(x, x); to >>= 1; } return y; } public static int inv(int x) { assert(x != 0); return binpow(x, mod - 2); } private static class Matrix { int n; int[][] a; public Matrix(int size) { n = size; a = new int[n][n]; } public Matrix one() { Matrix ans = new Matrix(n); for (int i = 0; i < n; ++i) ans.a[i][i] = 1; return ans; } public Matrix mul(Matrix other) { Matrix ans = new Matrix(n); for (int i = 0; i < n; ++i) for (int k = 0; k < n; ++k) for (int j = 0; j < n; ++j) ans.a[i][j] = add(ans.a[i][j], FibonacciStringSum.mul(a[i][k], other.a[k][j])); return ans; } } public static Matrix binpow(Matrix x, int to) { Matrix y = x.one(); while (to > 0) { if ((to & 1) == 1) y = y.mul(x); x = x.mul(x); to >>= 1; } return y; } public static int[] getCoefficients(int n) { int[] a = new int [2 * n + 1]; a[0] = 1; for (int i = 0; i < n; ++i) { for (int j = 2 * n; j >= 0; --j) { int nw = sub(0, a[j]); if (j >= 1) nw = sub(nw, a[j - 1]); if (j >= 2) nw = add(nw, a[j - 2]); a[j] = nw; } } return a; } public static int[] getSequence(int cnt, int a, int b) { int[] fact = new int[cnt + 1]; int[] ans = new int[cnt]; fact[0] = 1; for (int i = 1; i < fact.length; ++i) fact[i] = mul(i, fact[i - 1]); BiFunction binom = (Integer n, Integer k) -> { if (n < 0 || k < 0 || n < k) return 0; int res = fact[n]; res = mul(res, inv(fact[k])); res = mul(res, inv(fact[n - k])); return res; }; for (int n = 0; n < cnt; ++n) { for (int k = 0; 2 * k - 1 <= n; ++k) { int bon = binom.apply(n - k + 1, k); bon = mul(bon, binpow(k, b)); bon = mul(bon, binpow(n - k, a)); ans[n] = add(ans[n], bon); } } return ans; } public static int get(int n, int a, int b) { int m = a + b + 1; int[] c = getCoefficients(m); int depth = c.length - 1; Matrix A = new Matrix(depth); for (int i = 0; i < depth; ++i) A.a[0][i] = sub(0, c[depth - i - 1]); for (int i = 1; i < depth; ++i) A.a[i][i - 1] = 1; A = binpow(A, n); int[] seq = getSequence(depth, a, b); int ans = 0; for (int i = 0; i < depth; ++i) ans = add(ans, mul(A.a[depth - 1][i], seq[depth - i - 1])); return ans; } 
•  » » 3 years ago, # ^ |   -10 One can see that we win/lose on next position for Alice and Bob depends only on last five positionsHow to prove this formally?
•  » » 3 years ago, # ^ |   0 Could someone explain the solution for Div2. 900 ? Thanks.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 You store the answers for last 50 states (one can use queue, but the writer has done using bit masks). I understood it. It is quite elegant. The idea is to reduce memory while the time complexity stays the same.
•  » » 3 years ago, # ^ |   +1 I can't understand your code for Div2 900...Could you please give some hints?Thank you very much for that.
•  » » » 3 years ago, # ^ |   +10 Finally I understand it. Very nice problem. Thank you~
•  » » 3 years ago, # ^ |   +11 Why do i get tle with the following O(N) solution for div2-hard ? Codestring get(int n,int m) { int currl = 0; while(currl + m + 1 <= n) { currl+= m + 1; while(currl<=n && (__builtin_popcount(currl) & 1))++currl; } if(currl == n)return "Bob"; return "Alice"; } 
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +5 __builtin_popcount is slow. This takes 0.4 seconds in the worst case (I didn't check to see if it actually passes system test, so it may have some bug): Codeint popc[66000]; int popcount(int x) { return popc[x & 0xffff] + popc[(x>>16) & 0xffff]; } string ThueMorseGame::get(int n,int m) { popc[0] = 0; for (int i = 1; i < (1<<16); i++) popc[i] = popc[i & (i-1)] + 1; int currl = 0; while(currl + m + 1 <= n) { currl+= m + 1; while(currl<=n && (popcount(currl) & 1))++currl; } if(currl == n)return "Bob"; return "Alice"; } 
•  » » » » 3 years ago, # ^ |   0 Yeah , it passes now :(
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 i cant understand your(fauzdar65) solution. would you mind explaining?
•  » » » » 3 years ago, # ^ |   +3 I move from one losing position to the next losing position. If at the end i stop at n, then its a losing position, otherwise i skip n, that means it is a winning position.0 is the first losing position. If X is a losing position, then surely X+1,X+2....X+m are winning positions as we can move to X. So, from X we move to X+m+1. If this number has even number of set bits, then this is the next losing position, otherwise this becomes a winning position, and next candidate for losing position is the next number i.e (X+m+1)+1 . So, we keep adding 1 till we find next losing position.
•  » » » » » 3 years ago, # ^ |   0 Why If this number has even number of set bits, then this is the next losing position ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +10 One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) ... f(n-2 * (a + b + 1), a, b). How to notice and/or prove this? I'm just trying to understand what's the intuitive way of noticing this fact and believing in it during the contest as for me the only way of thinking was to try to derive f(n, a, b) from f(n - 1,  * ,  * ) and f(n - 2,  * ,  * ) (which can be done but it requires raising 702x702 matrix to 109-th power and is most likely too slow).
•  » » » 3 years ago, # ^ |   +5 If you write y=(n-x), then you can expand (n-x)^b, so you can notice you only need the powers x^0, x^1, ..., x^(a+b).
•  » » » » 3 years ago, # ^ |   0 This would be an intuitive reason to change the a, b parameters, but why does this give a recurrence on n?
•  » » » » » 3 years ago, # ^ |   +16 Hmm, I guess I don't know the answer to that. This was more if you're looking to solve it by exponentiating a matrix, this is the most intuitive way I think.Is there a way to translate the matrix to a recurrence? I'm not sure if this is even possible in general.
•  » » » » » » 3 years ago, # ^ |   +34 Yes there is. f(n) = Anij (that is any coefficient in fixed position in matrix powers) obey recurrence relation, which coefficients are coefficents of χA (characteristic polynomial). That is follows from Cayley-Hamilton formula χA(A) = 0.Take for example. χA(λ) = λ2 - λ - 1.So, obey reccurence
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 And what is that matrix A you're talking about? It should be of size a + b. I know only the matrix of size (a+1)*(b+1)*2 (number of taken zeros, ones and the last bit). Upd: Well, I got the solution described above: just understand, that f(n,a,b) = sum {one^a*(n-one)^b}. So you can take the matrix of size (a+b+1)*2 (powers of taken 1s and the last bit) and the answer is weighted sum of coefficients of this vector: (A^n * v0).But the weights in this sum depend on n, so how do you get a recurrent?P.s. I solved the problem from the different angle: I need to find sum(x_i) ^ a * sum(!x_i)^b, so need to count number of ways to choose not intersecting multisets of sizes a and b, so I just counted the answer for n,a,b with the first and the last bits fixed. After that I split n in two parts and check that both middle bits are not equal to 1. I got accepted with n -> [n/2], [(n+1)/2], and so I needed map, but actually if you divide n into (2^r) > (n — 2^r), than you don't need any map, and it works in log(10^9) * a^2*b^2.
•  » » 3 years ago, # ^ |   +5 I have a question about div1 300 ptr. I failed that problem because I did not cover the special case when the vector was empty. Was not mentioning that fact explicitly and not add it to examples done on purpose?Also the wording in the constraints was confusing for me and I did not think about empty vector at all.
•  » » » 3 years ago, # ^ |   +15 That is kind of accident and totally not on purpose, I'm sorry for that.There was one more constraints like "a will contain between 1 and 5 elements, inclusive." Then I guess Arterm notice "all number in a will be distinct" + "all number in a will be between 1 and 5" can imply this, so he removed that constraint.It can be confusing but we think empty set is valid based on this: https://en.wikipedia.org/wiki/Vacuous_truth
•  » » » » 3 years ago, # ^ |   0 Thanks for the answer. I just want to make sure that I do understand correctly: You wanted to make the vectors non empty explicitly. You thought that the other 2 constraints assure that, so you removed that constraint. You did not add a checker for empty vectors test cases. Author's solution was working correctly on empty vectors. Somebody created challenges with empty vectors and you decided that in fact these 2 constraints allow empty vectors. So you left results as is?
•  » » » » » 3 years ago, # ^ |   0 Yes, your understanding is right.
•  » » » » » 3 years ago, # ^ |   0 Yeah, that's my fault. I commented two constraints to remove "redundancy". When cgy4ever noticed that it was too late to do anything.
•  » » 3 years ago, # ^ |   0 Hello, could you please explain the DP used in KthStringAgain? What is the content of d[i][j] and how do you go from a lower state to the next?
•  » » 3 years ago, # ^ |   0 Can you explain me solution of div 2 hard by bitmask?
•  » » 23 months ago, # ^ |   0 Can someone please explain how the period is calculated for the problem div1-easy PartisanGame?
 » 3 years ago, # |   +44 I added a quick editorial on the site: https://apps.topcoder.com/wiki/display/tc/SRM+701Just wondering, do people find these useful? (i.e. on the actual site as opposed to a comment on CF) I just happened to do this one and 700 because I was involved in preparing the rounds. It seems the view counts are relatively low.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +11 Yes, they are valuable. But it's hard to find them.Thank you for giving an explicit link!And if it is possible, could you add a few more sentences after the sentence: Namely, a number is winning if and only there exists a losing number.` ? :)I don't understand what that means exactly.
•  » » » 3 years ago, # ^ |   +5 Sorry, I missed some words. I added a few more.In general, all editorials can be found here: https://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+AnalysisThey haven't been kept up to date in the past few months, so that's probably why you can't find some.
•  » » » » 3 years ago, # ^ |   0 Thanks!
•  » » » 3 years ago, # ^ |   0 Winning number=the 1st player (p1) that finds it on the stack wins. Losing number=the 1st player (p1) that finds it on the stack loses, the other (p2) wins. N.B: p1 is not Alice and p2 is not Bob. "0" is a losing number because if p1 finds it, it means that p2 has won. A number with odd 1s is a winning number because if p1 finds it, it means that p2 has made a losing move. A number is winning if it can reach a losing number-> it means that p1 can force the losing number on p2. i.e. p1 finds a number x and moves to the losing number y. p2 finds y (i.e is p1 with respect to y) -> loses -> x is a winning number for the original p1.
•  » » 3 years ago, # ^ |   0 Hello, could you please explain the DP used in KthStringAgain? What is the content of d[i][j] and how do you go from a lower state to the next?
 » 3 years ago, # |   +24
 » 3 years ago, # |   0 Div2 hard is a kind of Bash Game.But when I used TC test,I found that data 499... 1 run 2.4s~2.7s,so I just bruteforce when m==1.When m==2,it runs 1.7s :)