### gaurav172's blog

By gaurav172, history, 19 months ago,

Author: gaurav172
Development: gaurav172, firebolt, night_fury208

Tutorial
Solution

### 1316B - String Modification

Author: preet_t
Development: preet_t, shaanknight, night_fury208

Tutorial
Solution

### 1316C - Primitive Primes

Author: lazyneuron
Development: lazyneuron, shaanknight,firebolt

Tutorial
Solution

### 1316D - Nash Matrix

Author: shaanknight
Development: shaanknight, riz_1_, coder_h,Altitude

Tutorial
Solution

### 1316E - Team Building

Author: gaurav172

Tutorial
Solution

### 1316F - Battalion Strength

Author: gaurav172
Development: gaurav172, shaanknight

Tutorial
Solution
Tutorial of CodeCraft-20 (Div. 2)

• +141

 » 19 months ago, # |   +241 E can be solved in $\mathcal{O}(np + \text{poly}(p))$ with min-cost flow: 72472865.We for sure will have the $k$ most valuable audience members fill some positions. Initially have them fill the audience-positions, then move to fill the other positions in the team. The candidates for position $j$ in the team are The $p$ among the top audience members with maximum $s_{i, j} - a_{i}$ The $p$ among the top $p + k$ audience members, not in the top $k$ audience members The $p$ not among the top $p + k$ audience members with maximum $s_{i, j}$ Breaking ties arbitrarily. If the player for position $j$ comes from the top $k$ audience members, they can, without loss of optimality, come from 1 by a swapping argument. If the player comes from the top $p + k$, not top $k$, they obviously come 2. Otherwise, they come from 3. Thus considering these $3p$ options is sufficient.We have $\mathcal{O}(p)$ options for each position, of which there are $p$, so with some consideration we can build a min-cost flow graph on $\mathcal{O}(p^{2})$ vertices, with $\mathcal{O}(p^{2})$ edges. This min-cost flow problem may then be solved in time polynomial in $p$.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 1316E - Team Building can be solved too running $p$ times a min-cost-max-flow algorithm where the max-flow is $p$: 72494005
•  » » 18 months ago, # ^ |   +1 Can you please explain to me how to build this graph,thanks a lot.
•  » » » 18 months ago, # ^ |   0 I can explain how to build this graph only in chinese. You can contact me with my qq:164950760.
 » 19 months ago, # |   +5 what is &mdash in b solution ?
•  » » 19 months ago, # ^ |   +11 -
•  » » 19 months ago, # ^ |   +5 Fixed
 » 19 months ago, # |   0 We know that cumulative gcd of coefficients is one in both cases. Hence no prime divides all the coefficients of the polynomial.can someone please explin me the meaning of line and from where it comes from.
•  » » 19 months ago, # ^ |   0 if we assume that all the coefficients are divisible by p then the gcd of all the coefficients will not be 1.So we will have atleast one coefficient which is not divisible by p.
•  » » 19 months ago, # ^ |   -13 GCD of all coefficients is 0 means the only common factor all of them have is 1 and 1 cannot be broken down into any product of primes. So basically there is no common prime factor for all coefficients. Eg. If the GCD would have been say 10(2*5), then all the coefficients would have had 2 and 5 as common prime factors.
•  » » 19 months ago, # ^ |   +2 It means that if a prime p had divided all the coefficients then the gcd would have been some multiple of that prime and not 1.
•  » » » 18 months ago, # ^ |   +1 Hey! Hey! Hey!
•  » » » » 18 months ago, # ^ |   0 Hey Hey Hey to the best player in Karasuno Nishinoya
•  » » 19 months ago, # ^ |   +1 watch this video . https://www.youtube.com/watch?v=wi14d0zcjCw
•  » » » 18 months ago, # ^ |   0 thank you! very helpful!
 » 19 months ago, # | ← Rev. 2 →   +6 In problem B, if only those values of $k \equiv n \pmod{2}$ are allowed, we can solve it in $\mathcal{O}(n\log(n))$, since it can be reduced to finding the minimum lexicographic rotation of the modified string $\star, s_1,s_2,\star,s_3,s_4,\star, \dots,\star, s_{n-1},s_n$ if $n$ is even, where $\star$ is an auxiliary character lexicographically smaller than any lowercase latin letter. This case can be handled similarly if $n$ is odd.Is there a way to solve the problem in $\mathcal{O}(n\log(n))$ when the suffix is reversed ($k$ and $n$ of different parity)?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +7 The problem turns into: split the string into XY, then it turns into YX or Y(X') depending on parity. Try to do a comparison as fast as you can. Then you can solve in O(N * comparison cost). First, you can do O(nlogn) easily using hash + binary search. You can push that even further, computing the suffix tree of STRING + '#' + REVERSEDSTRING and using lcp (in the tree's case the lcp of two suffixes is the lca of them in the tree). You can do LCA in O(1) using O(N) preprocessing so you can actually solve the whole thing in O(N).This is something crazy I though after the contest, just proving a bound. There's probably a way to do it that's way simpler tho, I'd be interested in that if someone knows it.
•  » » » 19 months ago, # ^ |   +8 Thank you so much. The solution where you do the same naïve algorithm, but compare 2 strings with binary+hashing using segments of $s_1 \dots s_n$ or $s_n \dots s_1$ is exactly what I was looking for.
•  » » » 19 months ago, # ^ |   0 While preparing the problem we tried solving the problem in O(N) , but we could think of the solution for a particular parity and not for the other parity . We tried solving using suffix array and not suffix tree , is there a way we can solve for both parities using suffix array only .
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +4 You can do the same but calculating the suffix array in O(N), there's a divide and conquer way to do it in O(N). The lcp query is just a min query in range and that can be done in O(N) preprocessing too.
 » 19 months ago, # |   0 Why condition involving variable a is included in solution of problem c code ?
•  » » 19 months ago, # ^ |   0 To take the first idx that a[idx] is not divisible by p.You can use (break) after you find such idx.
 » 19 months ago, # |   0 Another mathforces round
 » 19 months ago, # |   0 Editorial of problem C is a little bit blurry. How can we say the terms inside parenthesis is divisible by prime p? Can anyone please explain?
•  » » 19 months ago, # ^ |   +5 Given i is the smallest index where ai is not divisible not divisible p which means a0 to ai-1 are all divisible by p.So the terms in left paranthesis are divisible by p. Similarly for terms in right paranthesis also b0 to bj-1 are all divisible by p.
 » 19 months ago, # |   +7 In problem C, I understand till the part where we can guarantee a[i]*b[j] will not be divisible by p. How did they arrive at the summation result, where they take all bracketed terms to be divisible by p and only a[i]*b[j] to be not divisible? Can't there be two elements in the summation each individually not divisible by p, but their summation is divisible?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +8 The solution is you find the first i in first polynomial ( i can be from 0 to n-1 ) such that it's coefficient is not divisible by p. Since all other ak's from k = 0 to i — 1 are divisible by p , the entire thing that you put in initial paranthesis is divisible by p. The paranthesis having sum of (i-1) products of two coefficients, out of which one is surely divisible by p, results in entire paranthesis sum being divisible by p.Now we want a find a j in 2nd polynomial, similar to how we found i in first polynomial. Since now all other bk's from k = 0 to j — 1 are divisible by p , the entire thing that you put in second paranthesis is divisible by p .The remaining thing left in expression as you have understood is not divisible by p.
•  » » » 19 months ago, # ^ |   +3 Thanks a lot! Got it :)
•  » » 19 months ago, # ^ |   +3 watch this video after 7 minutes: https://www.youtube.com/watch?v=wi14d0zcjCw
 » 19 months ago, # | ← Rev. 2 →   +3 Detail Explanation For C (pardon my mistakes)As Gcd of (a1,a2,a3,a4.......) =1so p cant divide all of them if p divides all of them then gcd would be psame goes for (b1,b2,b3,.......)So there is atleast one ai and bi such that p does not divides themNow if you see closely x0 's coefficient = a0*b0x1 's coefficient = a0*b1 +a1*b0x2 's coefficient = a0*b2 + a1*b1 + a2*b0and so on...Now suppose a2 is one of the number which is not divisible by p (all previous number are divisible ex. a0,a1) and b2 is one of the number from b set which is not divisible by p ( all previous one are divisible b0,b1)now x4' s coefficient = a0*b4 +..... +a2*b2+........a4*b0All the number before a2*b2 is divisible by p as a0,a1 are divisible by p then there multiple will also be divisibleAll the number after a2*b2 is divisible by p as b0,b1 are divisibleNow if a%m==0 and b%m==0 then (a+b)%m==0So sum of all the numbers before a2*b2 and after a2*b2 is divisible by pNow if a%m==0 and b%m!=0 then (a+b)%m!=0(a2*b2)%p!=0 As a2 and b2 are not so there product will also be not divisible by pSo total sum of X4's coefficient is not divisible by pHence this is one of the answerSo what you need to do is Loop through set A and Set B find the least number which is not divisible by pfrom above example its a2 and b2 So your answer will be 2+2 == 4 (which your coefficient's power)Sample Code in C++
•  » » 19 months ago, # ^ | ← Rev. 4 →   0 How a2%p!=0 and b2%p!=0 implies (a2*b2)%p!=0 ?like 4%8==4 and 12%8==4 but (12*4)%8 == 0I know p is a prime but how to prove there doesn't exit any p like 8?
•  » » » 19 months ago, # ^ |   +6 Sorry i did not totally get your question This may help I used if a3%p==0 and b3%p==0 then (a3*b3)%p==0 You are saying opposite of it And there was some typo mistake Fixed now
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 In Your explanation, Line no 20. (a2*b2)%p!=0 As a2 and b2 are not so there product will also be not divisible by p. How ( a2 * b2) % p! = 0 ?
•  » » » » » 19 months ago, # ^ |   +6 Suppose a2 has prime factor like p1,p2,p3 and b2 has prime factor(Different from a2) p4,p5 And p is not one of them because p is one of a2 and b2 's prime factor then a2 ,b2 will be divisible by p Now a2*b2 has prime factor like p1,p2,p3,p4,p5 and p is not one of them So a2*b2 is not divisible by p
•  » » » » » 18 months ago, # ^ |   +1 p is prime that's y this condition is satisfied otherwise not .
•  » » 18 months ago, # ^ |   +1 Really Helpfull.
•  » » 18 months ago, # ^ |   0 why the least one should be taken?
•  » » » 18 months ago, # ^ |   0 Just to proof There maybe other co primes with p , hence other ai*bj that satisfies the condition
 » 19 months ago, # |   +3 Auto comment: topic has been updated by gaurav172 (previous revision, new revision, compare).
 » 19 months ago, # | ← Rev. 3 →   +3 In problem C: I read some submission seem choose any a[i] and b[j] which are not divisible by p :>. Is it indeed a violation ?? Because it does not satisfy the formula in solution !!
•  » » 19 months ago, # ^ |   +3 Try to hack it if you think it's wrong. From the description given by you it seemed that it is in fact wrong. (Or post the submission link please
•  » » » 18 months ago, # ^ |   0 It's here. Submission of rank 1 :>1316C
•  » » » » 18 months ago, # ^ |   0 It is correct because the problem description claimed that if more than one solutions exist, you can put any of them.
•  » » » » » 18 months ago, # ^ |   0 I got it but if (i,j) is not the first then the terms inside parentheses are not all divisible by p. So i think it is wrong although i can not hack it :>
•  » » » » » » 18 months ago, # ^ |   0 For intuition, you can reverse both polynomials, and it's the same as the editorial said.
•  » » 18 months ago, # ^ |   +8 Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible. Here is a hack 5 5 5 0 1 0 3 0 0 2 0 4 0 (3,1) is not divisible but 3+1=4 is not a correct answerThe reason why the submission you mentioned below passed is that he actually choose the last undivisible a[i] and b[j]. It can be proved that last and first are both correct.：）
•  » » » 18 months ago, # ^ |   0 Wow! I got it now :>. Thank u ^_^ !
•  » » » 18 months ago, # ^ |   0 "Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible".Why this?Can you please explain?
•  » » » » 18 months ago, # ^ |   0 Hack:5 5 50 1 0 3 00 2 0 4 0a[3] and b[1] are both undivisible. But (3+1=4) is not a correct answer. a[0]*b[4]+a[1]*b[3]+a[2]*b[2]+a[3]*b[1]+a[4]*b[0]=10
 » 19 months ago, # | ← Rev. 2 →   -6 In task C:Why if we give similar, we wont get coefficients, which become divisible by p?
 » 18 months ago, # |   0 can someone plz explain how in coefficient of pow(x,i+j)
 » 18 months ago, # |   -6 can plz somebody explain me that how other tems in coefficient of pow(x,i+j) other than ai*bi are divisible by p??
•  » » 18 months ago, # ^ |   +9
•  » » » 18 months ago, # ^ |   0 sorry.....i was unable to understand there. Now i got it. Nice solution.
•  » » 18 months ago, # ^ |   0 $x^{i + j}=(a_0 * b_{i + j} + a_1 * b_{i + j - 1} + ...) + a_i * b_j + (a_{i + 1} * b_{j - 1} + a_{i + 2} * b_{j - 2} +...)$.if $x_i$ and $x_j$ are the first coefficient that can not divisible by p, than $a_0$,$a_1$,$a_2$...,$a_i-1$ and $b_0$,$b_1$,$b_2$...,$b_j-1$ can divisible by p, so $(a_0 * b_{i + j} + a_1 * b_{i + j - 1} + ...)$ and $(a_{i + 1} * b_{j - 1} + a_{i + 2} * b_{j - 2} +...)$ can also divisible by p, and also $a_i * b_j$ can not.
•  » » » 18 months ago, # ^ |   0 Thank You for your explanation. I got it
 » 18 months ago, # | ← Rev. 3 →   +5 In problem F , the value 「val」 in the segment tree sould be $\sum_{i=1}^{n} \sum_{j=i+1}^{n} prob_{i,j} \cdot p_i \cdot p_j$ but not $\sum_{i=1}^{k} \sum_{j=i+1}^{k} p_i \cdot p_j$ @gaurav172
•  » » 18 months ago, # ^ |   0 Fixed, Thanks a lot.
 » 18 months ago, # | ← Rev. 2 →   0 In B problem, won't suffix of the answer string be S1S2....Sk-1 when n and k have opposite parity since total operations is n-k+1 and even operations will result in same order of the substring. Plz help!!!
 » 18 months ago, # |   0 In problem B why the condition (n%2==k%2) is used? Can someone please explain it?
•  » » 18 months ago, # ^ |   0 To check if $n$ and $k$ have the same parity. Depending on this condition, the modified string's suffix will be $s_1s_2..s_{k-1}$ or its reverse.
•  » » » 18 months ago, # ^ |   0 Why can't we reverse the strings when n & k don't have same parity?
 » 18 months ago, # |   0 Can some one please elaborate in detail how to solve E. I am unable to understant it :(
•  » » 18 months ago, # ^ |   0 Which part do you want ? The sorting part or Dp part?
•  » » » 18 months ago, # ^ |   0 Yes please... I got the dp part but still didnt get why we sort.
•  » » » » 18 months ago, # ^ |   +1 So, you can't keep another dimension to the dp (the number of people selected as audience till now), we need to find another way to add audience contribuition to our DP. Initially, just forget about the audience and try to find just skills. suppose you keep a track of people whom you have selected for players among the $N$ people, to then select audience, we just need to select the best $k$ among the remaining as. As we have sorted in decreasing order of $a_i$, these will be the first $k$ among the remaing (non-selected people). So, we just need to add this in our DP solution, we either selected $i$ as a player or, for the current state $(i,mask)$ — we can find how many people we have not selected as players for this state, if they are less than $k$ we need to include $i$ as audience , else we have already selected $k$ audience.
•  » » » » » 18 months ago, # ^ |   0 Thank you..! that's exactly what i was looking for.
•  » » » 18 months ago, # ^ |   0 dp part
•  » » » » 18 months ago, # ^ | ← Rev. 4 →   +1 DP part is pretty straight forward. consider that you need to select only players, so to get optimal value at state $(i,mask)$ — you can either select $i$ as one of the players or $not$.So you can just iterate over all the positions $j$ in the mask, and try to set $i$-th person to the $j$-th position. — $dp[i][mask] = max(dp[i][mask],dp[i-1][mask \oplus 2^{j}]+s_{i,j}$. if we don't want to select $i$ as a player — $dp[i][mask] = dp[i-1][mask]$.This is the standard bitmask dp, I have explained the audience part in the above comment
•  » » » » » 18 months ago, # ^ |   0 Thank you so much I get it now :)
•  » » » » » 18 months ago, # ^ |   0 Can you tell me whats wrong in my solution gaurav172 Your text to link here...
•  » » » » » » 18 months ago, # ^ |   +1 use long long instead of int
•  » » » » » » » 18 months ago, # ^ |   0 Thank u so much my solution got accepted! :)
•  » » » » » 18 months ago, # ^ |   0 how can i be less than number of set bits in mask. I don't get that part. Because of that the number of players selected that is (i — 1 — setbits) would even become negative. Can u elaboarate how does this vaild.
 » 18 months ago, # |   0 Can someone explain the suffix part(about the parity of n and k) in problem B?
•  » » 18 months ago, # ^ |   0 You just have to see the numbers of characters (n — k) i.e for eg - bbcdabcd here value of k will be k = 5 and n = 8. So numbers of characters from k are abcd i.e. equal to 4. Since 4 is even you will append the suffix part just like this i.e. your answer will be abcd + bbcd = (abcdbbcd) If string would be bbcdabcdd here the value of k will also be 5 and numbers of character from k are 5 (abcdd) which is odd. So we will first reverse the suffix part and then append it to our answer i.e. abcdd + reverse(bbcd) = abcdd + dcbb = abcdddcbb
 » 18 months ago, # |   0 Any FFT solution or tutorial for the C problem
•  » » 18 months ago, # ^ |   0 We tried not to make the FFT solution pass. The constraints are really tight for normal FFT to pass, probably only those whose codes are really optimized might have passed
 » 18 months ago, # |   0 have anyone done E with memoization instead of DP? Mine is getting TLE. https://codeforces.com/contest/1316/submission/73085301Is there anything that I am missing?
 » 16 months ago, # |   0 yo, B is messed up for java or something? I'm using stringbuilders and everything, I did EXACTLY what the editorial said, and still TLEing. Is it because Java is a slow language or what?
•  » » 15 months ago, # ^ |   0 I think total time complexity should be O(n^3) considering testcases and that might cause you TLE
 » 15 months ago, # |   0 Problem B : Can someone explain how the O(n^2) per testcase(total 5000 testcases, n <=5000) is okay? Isn't total time complexity should be O(n^3) considering testcases and that might cause TLE ?
•  » » 15 months ago, # ^ |   +3 There is a restriction on sum of n over all test cases.
•  » » » 14 months ago, # ^ |   0 Thanks, now i get it.. :D