gaurav172's blog

By gaurav172, history, 5 years ago, In English

1316A - Grade Allocation

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
Development: gaurav172, shaanknight, coder_h, madlad

Tutorial
Solution

1316F - Battalion Strength

Author: gaurav172
Development: gaurav172, shaanknight

Tutorial
Solution
Tutorial of CodeCraft-20 (Div. 2)
  • Vote: I like it
  • +141
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +241 Vote: I do not like it

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

  1. The $$$p$$$ among the top audience members with maximum $$$s_{i, j} - a_{i}$$$
  2. The $$$p$$$ among the top $$$p + k$$$ audience members, not in the top $$$k$$$ audience members
  3. 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$$$.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

what is &mdash in b solution ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
5 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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)?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like 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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why condition involving variable a is included in solution of problem c code ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To take the first idx that a[idx] is not divisible by p.

    You can use (break) after you find such idx.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another mathforces round

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    watch this video after 7 minutes: https://www.youtube.com/watch?v=wi14d0zcjCw

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Detail Explanation For C (pardon my mistakes)

As Gcd of (a1,a2,a3,a4.......) =1

so p cant divide all of them if p divides all of them then gcd would be p

same goes for (b1,b2,b3,.......)

So there is atleast one ai and bi such that p does not divides them

Now if you see closely

x0 's coefficient = a0*b0

x1 's coefficient = a0*b1 +a1*b0

x2 's coefficient = a0*b2 + a1*b1 + a2*b0

and 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*b0

All the number before a2*b2 is divisible by p as a0,a1 are divisible by p then there multiple

will also be divisible

All the number after a2*b2 is divisible by p as b0,b1 are divisible

Now if a%m==0 and b%m==0 then (a+b)%m==0

So sum of all the numbers before a2*b2 and after a2*b2 is divisible by p

Now 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 p

So total sum of X4's coefficient is not divisible by p

Hence this is one of the answer

So what you need to do is Loop through set A and Set B find the least number which is not divisible by p

from above example its a2 and b2

So your answer will be 2+2 == 4 (which your coefficient's power)

Sample Code in C++

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 == 0

    I know p is a prime but how to prove there doesn't exit any p like 8?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          p is prime that's y this condition is satisfied otherwise not .

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Really Helpfull.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why the least one should be taken?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just to proof There maybe other co primes with p , hence other ai*bj that satisfies the condition

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by gaurav172 (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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 !!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's here. Submission of rank 1 :>

      1316C

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is correct because the problem description claimed that if more than one solutions exist, you can put any of them.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :>

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            For intuition, you can reverse both polynomials, and it's the same as the editorial said.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 answer

    The 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.

    :)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow! I got it now :>. Thank u ^_^ !

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible".Why this?Can you please explain?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hack:

        5 5 5

        0 1 0 3 0

        0 2 0 4 0

        a[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

»
5 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

In task C:

Why if we give similar, we wont get coefficients, which become divisible by p?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone plz explain how in coefficient of pow(x,i+j)

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

can plz somebody explain me that how other tems in coefficient of pow(x,i+j) other than ai*bi are divisible by p??

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$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.

»
5 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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!!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B why the condition (n%2==k%2) is used? Can someone please explain it?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one please elaborate in detail how to solve E. I am unable to understant it :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which part do you want ? The sorting part or Dp part?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes please... I got the dp part but still didnt get why we sort.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dp part

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the suffix part(about the parity of n and k) in problem B?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any FFT solution or tutorial for the C problem

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think total time complexity should be O(n^3) considering testcases and that might cause you TLE

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for this prob isn't as nice as the editorial's, but I thought I'd share it. An observation is that if we sort array A in increasing order, then we will have to select the last k people plus p extra people in the prefix. The way we choose which ones will be part of the team and the audience is up to us however. Let's let dp1[i][j] be the best answer considering the first i people and filling up all the positions in the team denoted in bitmask j. We'll ignore the audience for now. Now let's let dp2[i][j] consider the people from the last person to the ith person. If we choose to add a person to the team, we will add their position strength but subtract their audience strength. Finally, we'll iterate over the size of the suffix as it can range from len = k to k+p. For each size, we'll iterate over all bitmasks who have len-k bits on, and then compute the sum of dp2[start of suffix][some bitmask] + dp1[start of suffix-1][complement bitmask] + sum of all audience values in the suffix.

239550098