### gaurav172's blog

By gaurav172, history, 3 years 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) Comments (82)
| Write comment?
 » 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$.
•  » » 3 years ago, # ^ | ← Rev. 2 →   1316E - Team Building can be solved too running $p$ times a min-cost-max-flow algorithm where the max-flow is $p$: 72494005
•  » » Can you please explain to me how to build this graph,thanks a lot.
•  » » » I can explain how to build this graph only in chinese. You can contact me with my qq:164950760.
 » what is &mdash in b solution ?
•  » » -
•  » » Fixed
 » 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.
•  » » 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.
•  » » 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.
•  » » 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.
•  » » » Hey! Hey! Hey!
•  » » » » Hey Hey Hey to the best player in Karasuno Nishinoya
•  » » watch this video . https://www.youtube.com/watch?v=wi14d0zcjCw
•  » » » thank you! very helpful!
 » 3 years ago, # | ← Rev. 2 →   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)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 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.
•  » » » 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 .
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   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.
 » Why condition involving variable a is included in solution of problem c code ?
•  » » To take the first idx that a[idx] is not divisible by p.You can use (break) after you find such idx.
 » Another mathforces round
 » 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?
•  » » 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.
 » 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?
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » Thanks a lot! Got it :)
•  » » watch this video after 7 minutes: https://www.youtube.com/watch?v=wi14d0zcjCw
 » 3 years ago, # | ← Rev. 2 →   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++
•  » » 3 years ago, # ^ | ← Rev. 4 →   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?
•  » » » 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
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   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 ?
•  » » » » » 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
•  » » » » » p is prime that's y this condition is satisfied otherwise not .
•  » » why the least one should be taken?
•  » » » Just to proof There maybe other co primes with p , hence other ai*bj that satisfies the condition
 » Auto comment: topic has been updated by gaurav172 (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 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 !!
•  » » 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
•  » » » It's here. Submission of rank 1 :>1316C
•  » » » » It is correct because the problem description claimed that if more than one solutions exist, you can put any of them.
•  » » » » » 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 :>
•  » » » » » » For intuition, you can reverse both polynomials, and it's the same as the editorial said.
•  » » 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.：）
•  » » » Wow! I got it now :>. Thank u ^_^ !
•  » » » "Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible".Why this?Can you please explain?
•  » » » » Hack:5 5 50 1 0 3 00 2 0 4 0a and b are both undivisible. But (3+1=4) is not a correct answer. a*b+a*b+a*b+a*b+a*b=10
 » 3 years ago, # | ← Rev. 2 →   In task C:Why if we give similar, we wont get coefficients, which become divisible by p?
 » can someone plz explain how in coefficient of pow(x,i+j)
 » can plz somebody explain me that how other tems in coefficient of pow(x,i+j) other than ai*bi are divisible by p??
•  » »
•  » » » sorry.....i was unable to understand there. Now i got it. Nice solution.
•  » » $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.
•  » » » Thank You for your explanation. I got it
 » 3 years ago, # | ← Rev. 3 →   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
•  » » Fixed, Thanks a lot.
 » 3 years ago, # | ← Rev. 2 →   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!!!
 » In problem B why the condition (n%2==k%2) is used? Can someone please explain it?
•  » » 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.
 » Can some one please elaborate in detail how to solve E. I am unable to understant it :(
•  » » Which part do you want ? The sorting part or Dp part?
•  » » » Yes please... I got the dp part but still didnt get why we sort.
•  » » » » 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.
•  » » » dp part
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   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
•  » » » » » Thank you so much I get it now :)
•  » » » » » Can you tell me whats wrong in my solution gaurav172 Your text to link here...
•  » » » » » » use long long instead of int
•  » » » » » » » Thank u so much my solution got accepted! :)
 » Can someone explain the suffix part(about the parity of n and k) in problem B?
•  » » 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
 » Any FFT solution or tutorial for the C problem
•  » » 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
•  » » » Yes Mine Passed.
 » 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?
•  » » I think total time complexity should be O(n^3) considering testcases and that might cause you TLE
 » 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 ?
•  » » There is a restriction on sum of n over all test cases.
•  » » » Thanks, now i get it.. :D
 » for question B i tried to solve this in college(pretending like i am attending the lecture but i solve questions mostly time) ,i come with exact same approach but i implement it wrong i guess ,after almost 15 days i didnt got the perfect idea and now after seeing editorial i feel stupid and happy at the same time