pikmike's blog

By pikmike, history, 6 months ago, translation, In English

1342A - Road To Zero

Idea: BledDest and adedalic

Tutorial
Solution (Roms)

1342B - Binary Period

Idea: adedalic

Tutorial
Solution (adedalic)

1342C - Yet Another Counting Problem

Idea: BledDest and adedalic

Tutorial
Solution (BledDest)

1342D - Multiple Testcases

Idea: BledDest

Tutorial
Solution (pikmike)

1342E - Placing Rooks

Idea: BledDest

Tutorial
Solution (BledDest)

1342F - Make It Ascending

Idea: Ne0n25

Tutorial
Solution (Ne0n25)
Tutorial of div2 B-C #1
 
 
 
 
  • Vote: I like it
  • +149
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks! It answered my questions!

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

thanks for the editorial. C was bit tricky.

»
6 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Can anyone please elaborate inclusion-exclusion part for E?

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it +120 Vote: I do not like it

    Suppose we just try to place the rooks in the $$$c$$$ columns we've chosen. There are $$$c^n$$$ possibilities, because we can place each rook in any of $$$c$$$ columns and there are $$$n$$$ rooks. (We will see this is when $$$i=0$$$.)

    However, we've accidentally counted some arrangements where some columns aren't used. Let's subtract all arrangements where one column is empty. We choose the empty column ($$$c \choose 1$$$), and the rooks go in the remaining columns ($$$(c-1)^n$$$). Like in the first case, some other columns might be empty; we just know for sure the column we've chosen is. So, there are $$${c \choose 1} (c-1)^n$$$ combinations we want to subtract. (This is $$$i=1$$$.)

    Now, consider combinations where two rows are empty. For each pair of rows $$$a$$$ and $$$b$$$, we've already subtracted those combinations in the case $$$i=1$$$. Actually, we've subtracted them once for the case where $$$a$$$ is for certain empty, and once for the case where $$$b$$$ is for certain empty. We've overcompensated, so we will add back in the combinations where two rows are empty, so add $$${c \choose 2}(c-2)^n$$$. ($$$i=2$$$)

    I think we need another iteration to clarify why we can just alternate. For $$$i=3$$$, consider rows $$$p$$$, $$$q$$$, and $$$r$$$. (__r i p n a m e s p a c e s lol__) We've accidentally added it once at $$$i=0$$$, subtracted it for $$$p$$$, then $$$q$$$, then $$$r$$$ for $$$i=1$$$, added it for $$$p, q$$$, then $$$p, r$$$, then $$$q, r$$$ for $$$i=2$$$. So, we need to unadd it back.

    And just keep going.

    So, it turns out it works because of that weird alternating binomial property. But we don't really need to know that, as long as we can find the pattern.

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

      The "alternating binomial property" can be proven easily enough. The number of combinations we've already counted so far for some $$$i$$$ is $$$\displaystyle\sum_{j=0}^{i-1} {(-1)^j {i \choose j}}$$$. (See case $$$i=3$$$ in my other post for the reasoning.) This is just $$$\displaystyle\sum_{j=0}^{i} {(-1)^j {i \choose j}} - (-1)^i {i \choose i}$$$. The summation is just a binomial expansion, so this simplifies to $$$(1-1)^i - (-1)^i {i \choose i} = 0^i - (-1)^i = -(-1)^i$$$, This means we have overcounted by that much, so we add $$$(-1)^i$$$ to the answer to correct it.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can E's solution be also written as S(n,n-k)*(n-k)! .where S(i,j) is stirling number?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Exactly

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How did you conclude that?

          I mean it's true from the mathematical perspective, but is there any intuition for it?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            In our case, $$$S(n, n-k)$$$ represents number of ways to distribute $$$n$$$ rooks into $$$n - k$$$ nonempty columns. This number doesn't consider the order of columns (e.g. distribution $$$[[1,2],[3]]$$$ is the same as $$$[[3], [1,2]]$$$). However, these are two different distributions for us. That is why we multiply the number by $$$(n - k)!$$$, the number of permutations of $$$(n - k)$$$ columns.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              Wait what does $$$n-k$$$ mean, $$$n-k$$$ may be negative here! Although I also was thinking about stirlings. First some background on what I understand:

              In particular if $$$k \neq 0$$$ (for $$$k = 0$$$ answer is $$$n!$$$) then we calculate all ways for $$$n$$$ rooks to span all $$$n$$$ rows, call it $$$W$$$. Our answer will be $$$2W$$$ (replace row with column)

              Now as you say, since $$$k\neq 0$$$ some columns will be repeated. So we group them by columns. Stirling number $$$S(n,p)$$$ will give set of all partitions of $$$n$$$ into $$$p$$$ groups. Now pairings in this question depends on the size of groups right, say $$$p = 2$$$ and $$$n = 4$$$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $$$\binom{3}{2}$$$ and in second case it will be $$$\binom{2}{2}\cdot\binom{2}{2}$$$ so how stirling will help here

              Please tell me if I misunderstood it, Thanks a lot.

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

      Nice, detailed explanation. It was too hard for me to get this inclusive-exclusive approach by myself.
      Just one note about this part: " We've accidentally counted it once at i=0, subtracted it for p, then q, then r for i=1, added it for p,q, then p,r, then q,r for i=2. So, we need to add it back. " Isn't it supposed to be subtraction for i = 3, not add it back ? If it is so , than I got it.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      We want k pairs so lets group first (k+1) elements, they will have n options, next rook will have n-1, next will have n-2 and so on.

      So the answer is n*(n-1)*(n-2)*...*(k+1)

      What is wrong with this answer??

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know if I understand your answer, but I think you don't account for arrangements where two different attacking pairs are in different columns.

        For example, I don't think your way counts the following arrangement for $$$n = 4$$$, $$$k = 2$$$.

        R . . .
        R . . .
        . R . .
        . R . .
        
    • »
      »
      »
      6 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hey this is a very clear explanation thank you. I was wondering if you came up with a to define sets that fulfill this expression. For example if you let S(i) be the set of configurations where at least i columns have no rooks, we have

      $$$S(i) = {c \choose i} \cdot (c - i)^n$$$

      And $$$S(n) \subset S(n - 1) \subset ... \subset S(1) \subset S(0)$$$ which implies $$$S(0) / S(1)$$$ is the answer. This is incorrect because $$$S(i)$$$ double counts some configurations and throws them away. I was wondering if you had a set definition that worked?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider n=3, k=1

      |r| | |

      |r| | |

      | |r| |

      |r| | |

      | |r| |

      |r| | |

      here, in both the arrangements column 1 has 2 rooks, column 2 has 1 rook and column 3 has no rook.

      How have we considered the above two cases different? It seems we just distributed n rooks in c columns each being non-empty. I cannot understand. Please explain!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey Russell_Emerine so as you said to place $$$n$$$ rooks in $$$c$$$ columns initially we get $$$c^n$$$ arrangements, what I think this is is that for every rook we have $$$c$$$ options to place to but why don't we consider the permutation among the rows? Say, for example, a column contains $$$k$$$ rooks then these $$$k$$$ rooks can be spread throughout $$$n$$$ rows so arranging $$$k$$$ rooks in that column(which has $$$n$$$ rows) hence $$$C_{k}^{n}$$$ possibilities for that column similarly why are we not considering the arrangement of those rooks among the rows for each column? I hope you understand my question, Thanks in advance.
      I might sound like a novice but am not good at combinatorics so I'd be grateful for any help :)

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is because the rooks are not distinct, it dosen't matter if first rook goes to first row, or last row both cases are same configurations. Only thing that matters is all rows should be filled. So we won't consider nCk

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But the thing is there might be less than $$$n$$$ rooks in a row in the arrangement, so in that case, the arrangement does matter, consider it like we know every row is gonna be filled but which row must be filled with which column varies hence my question.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There can be no case where there is less than n rooks, this is the first assumption we are taking that, all rooks must be in all different rows so that they attack all non empty cells(columns as well as rows). After that assumption we are just playing around with the column positions. If that was the case the question would be much harder to solve.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I don't think you understood my query, I know all $$$n$$$ rows are filled but which rows is filled in which column will differ, every $$$(n-k)$$$ column will have at least $$$1$$$ rook, but rest rooks are distributed arbitrarily among them, hence a column will have less than $$$n$$$ rooks for sure so I was wondering about arranging them in $$$n$$$ rows, but nevermind I understood my flaw, thanks for your time.

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

        Even I had the same doubt but got cleared somehow.

        Just consider assigning numbers to each rook (virtually) R1, R2, R3, ...Rn denoting the row number to which this rook will belong.

        Note: since all rooks are similar, it does not matter which rook is assigned which row number.

        So, consider n-3, k=1

        |r1| | |

        | |r2| |

        |r3| | |

        and

        |r1| | |

        |r2| | |

        | |r3| |

        In this way we consider them different. Since we were assigning column to each rook independent of the other. we have already counted this. I hope this was useful.Give a thumps up if you agree.

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

          Ohh now I understood thanks buddy, rraj0510 so we assign each rook an id corresponding to its row that rook is to be placed in that row only that way all possibilities are covered with $$$c^n$$$, Now I got the intended intuition.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am still confused , after we consider all c^n possibilities and then subtract the possibility that one of the columns is completely empty using cC1 , how are we overcounting that exactly 2 columns are empty ? Edit: got it , thanks for good explanation.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about the arrangements of rooks within each of these columns, how is that accounted for ?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wish This could also be included in the editorial for additional explanation

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, I just wanted to ask if the rooks are numbered ?

      For example, if there are 3 rooks and 3 columns,

      Does it make any difference if the rooks go to columns {1, 2, 3} respectively instead of {2, 1, 3} ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Russell does a good job of explaining IE if you're not familiar. If you are familiar, if we take the IE formula from wikipedia:

    $$$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$$$

    Let $$$A_i = $$$(arrangements such that column i is empty), then

    $$$\left|\bigcup _{i=1}^{c}A_{i}\right|$$$

    represents the number of ways to arrange the rooks among $$$c$$$ columns with an empty column among those $$$c$$$ columns. Therefore, the number of ways such that there is no empty column is

    $$$\binom{c}{0} c^n - \left|\bigcup _{i=1}^{c}A_{i}\right|$$$

    , which when simplified will give you the formula.

    A cleaner way for me to think about this entire problem, that doesn't directly use IE (but uses IE under hood) is that first I choose the k empty columns, then I have to group the rows together which have rooks that attack each other, then I have choose a column for each group of rows. The first choice is $$$\binom{n}{k}$$$, the second choice can be calculated with a Sterling number of the second kind $$$S(n, n - k)$$$, and the third is $$$(n - k)!$$$. Alternatively, $$$S(n, n - k) * (n - k)!$$$ is the number of ways we can assign $$$n$$$ rows to $$$(n - k)$$$ non-empty columns.

    Then $$$ans = 2 * \binom{n}{k} * S(n, n - k) * (n - k)!$$$ which gives the same formula.

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

    My solution with explanation in comments, https://codeforces.com/contest/1342/submission/78619750

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

Please someone tell me faster approaches for Problem C.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    if $$$a \leq b$$$, and lcm(a,b) is L. Then from b to L-1 every number satisfies. Therefore we don't even need to check which numbers are good between 0 and L-1 individually and it will always be (L-b). Then just answer each query in O(1) time. Here is my code for reference.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      would you please explain this proof ?

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

        I tried to prove it Here See if that makes sense!

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          instead of lcm(a,b) can we have a+b?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't think that'll work.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              but why? I have spent enough time disproving, could you please help. Thanks

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      hey! I also tried a very similar approach to the questions, so basically I exclude the numbers in which the condition ((x%a)%b == (x%b)%a) is satisfied from the range [l,r]. These numbers would be of type in (N*lcm(a,b)+max(a,b)-1) for N in {0,1,2,3...}. Now I just need to calculate numbers like these which lie in [l,r] and subtract it from the total (l-r+1).

      Is this approach right? If so could you please help me with why this solution is getting a wrong answer (https://codeforces.com/contest/1342/submission/78349599)?

      Thanks a ton in advance!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://codeforces.com/contest/1342/submission/78237660 My code is failing for test case 3 . can you please tell me for which test case it is failing.I can"t find any test case doubleux

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

      that's what i thought too but my implementation kept on not working :( do u know where i went wrong code

»
6 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

Can we build the array required in C with LCM(a,b) instead of building it for a*b ?

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

    Yes, that is exactly what I did. Although worst-case complexity will be same, since $$$LCM(a,b)=a*b$$$ if $$$a$$$ and $$$b$$$ are co-prime.

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

    Yes, C can also be solved using LCM(a, b). Here's my solution with no pre-processing and O(1) space: 78178389

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey @aditya.vallabh , nice solution. Can you explain these two lines *** if(l%lcm < a) { res += a — l%lcm; } if(r%lcm < a) { res -= a — r%lcm — 1; } ***

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Basically all the numbers which fall in the range of [k*lcm, k*lcm + max(a,b)] (k is any integer) have equal moduli. If l or r falls in the middle of such a range, the numbers either have to be included or excluded which is handled in these two statements.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it. Thanks.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please provide the proof for your statement dedsec7

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

          Can you please check what is wrong with my code? HERE

          I have used the same logic but cannot figure out the mistake.

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

How ((ab + x) mod a) mod b = (x mod a) mod b . Can anyone please explain !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ab % a == 0 so we have ( (0 + x ) mod a ) mod b

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

    just take any two a and b and print 1 to 100 numbers satisfying the property and you will see a pattern.

    And I guess it will give you a good intution towards the problem.

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

The problem F can be passed by $$$\mathrm O(n^24^n)$$$ algorithm. Enumerate a set $$$s$$$ to be removed, then denote $$$f(i,\,S)\;(0\leq i\leq n-|s|,\,S\in s)$$$ as the minimum $$$a_i$$$ when the set of elements which is used is $$$S$$$. The transfer is very simple.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't quite understand how your algorithm is different from the reference solution. Do you have code? I'm also quite surprised that $$$O(n^2 4^n)$$$ works because I had quite a lot of trouble not getting TLE for my $$$O(n^2 3^n)$$$ solution (I had to use a profiler to shave constant factors).

»
6 months ago, # |
  Vote: I like it +41 Vote: I do not like it

There's another approach to solve C (in fact it solves a harder version of it). Let's suppose we are given $$$a,b$$$ and the interval $$$[l,r]$$$ in each test case. It suffices to solve the problem for the interval $$$[0,r]$$$ and the interval $$$[0,l-1]$$$ and substract.

Notice that if we fix that $$$a\leq b$$$ then $$$(x \text{ mod } a) \text{ mod } b$$$ is just $$$x\text{ mod } a$$$. Therefore, if one wants that $$$(x\text{ mod } a)\text{ mod } b = (x\text{ mod } b)\text{ mod } a$$$, this amounts to verify that $$$x\text{ mod } a = (x\text{ mod } b)\text{ mod } a$$$ or equivalently, that:

$$$ x \equiv x\% b\pmod{a}.$$$

So, we want to know how many $$$x\in [0,r]$$$ are such that the above congruence is true.

From the division algorithm, we have that there is a $$$q$$$ and $$$r'$$$ such that $$$ x = qb + r'$$$ and $$$0\leq r'<b$$$. The congruence above translates into $$$x\equiv r' \mod{a}$$$, and then what we want is $$$x-r'=qb$$$ to be a multiple of $$$a$$$. This amounts to have $$$q$$$ a multiple of $$$\frac{a}{\gcd(a,b)}$$$, let's say $$$q= n\frac{a}{\gcd(a,b)}$$$ where $$$n\in \mathbb{Z}_{\geq 0}$$$.

So now we want to know how many $$$x\in [0,r]$$$ are such that there is an $$$n\geq 0$$$ satisfying $$$x = n\frac{ab}{\gcd(a,b)} + r'$$$ where $$$0\leq r'<b$$$.

This can be solved in many ways: a naive $$$O(b)$$$ algorithm would be to notice first that $$$\frac{ab}{\gcd(a,b)}=\text{lcm}(a,b)$$$, and then observing that clearly for all $$$n\in \left[0,\left\lfloor\frac{r}{\text{lcm}(a,b)}\right\rfloor-1\right]$$$ and all $$$r'\in [0,b)$$$ those $$$x$$$ work. Then for $$$n=\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor$$$ iterate in $$$O(b)$$$ to take into account those $$$r'\in [0,b)$$$ that work.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how to deduced then what we want is x−r′=qb to be a multiple of a from x≡r′moda ?

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

      Because $$$x \equiv qb + r'$$$ so $$$x - r' \equiv qb$$$. Also $$$x \equiv r' \mod a$$$, so $$$x - r' = qb$$$ must be a multiple of $$$a$$$.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's exactly what I did

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excellent explanation! Can someone further explain: This amounts to have q a multiple of a / gcd(a, b)? Thanks!

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

    Really amazing solution and explanation. Thanks

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

"The property given in the statement holds for x if and only if it holds for x mod ab." , couldn't get this line. Can anyone explain?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's say $$$X = x + kab$$$

    If $$$(X\%a)\%b = (X\%b)\%a$$$ then $$$((x+kab)\%a)\%b = ((x+kab)\%b)\%a$$$ that means $$$(x\%a)\%b =(x\%b)\%a$$$

    (Recall that $$$p + tq \mod q = p\mod q$$$)

    So if $$$X$$$ satisfies the condition, so does $$$X \mod ab$$$

»
6 months ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

The equality to the solution of problem E is actually Stirling Number of the second kind(How many possible ways can we put n different things into k indifferent boxes such that the order of things in each box doesn't matter and each box must have atleast one thing?) multiplying it with k!.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I replied on a similar comment above concerning with stirlings. I am unable to solve this question for some time now. Here is what I understand:

    --- If $$$k \neq 0$$$ (for $$$k = 0$$$ answer is $$$n!$$$) then we calculate all ways for $$$n$$$ rooks to span all $$$n$$$ rows, call it $$$W$$$. Our answer will be $$$2W$$$ (replace row with column)

    Since $$$k\neq 0$$$ some columns will be repeated. So we group them by columns. Stirling number $$$S(n,p)$$$ will give set of all partitions of $$$n$$$ into $$$p$$$ groups. Now pairings in this question depends on the size of groups right, say $$$p = 2$$$ and $$$n = 4$$$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $$$\binom{3}{2}$$$ and in second case it will be $$$\binom{2}{2}\cdot\binom{2}{2}$$$ so how stirling will help here

    Please tell me if I misunderstood it, Thanks a lot.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 12   Vote: I like it +3 Vote: I do not like it

      EDIT : You need to find number of arrays that has n−k distinct numbers, not k. My bad ;_;

      Let's consider only the case some columns are repeated (we can multiply the answer with 2 to make up for the other case.)

      We will place the rook of row $$$i$$$ at column $$$A[i]$$$.

      For example, if $$$n = 4$$$ and $$$k = 2$$$, we will have something like this $$$A = (1,1,2,2)$$$ or $$$A = (4,4,4,1)$$$ or $$$A = (3,1,1,1)$$$

      Now, you can see that in case $$$k = 2$$$, there are 2 distinct numbers.

      Which means if we want k pairs of rooks fighting, we need to build an array that has k distinct numbers.

      That means if you want to find how many ways we can place the rook for $$$(n,k)$$$, Just find how many ways we can build an array that has $$$k$$$ distinct numbers instead.

      Combinatorics time! :

      How many ways can we choose k distinct numbers? $$$C_{n,k}$$$

      How many way can we arrange n different index into k distinct numbers?

      That is when our stirling number comes to a play.

      $$$Stirling(n,k)$$$ = How many ways can we arrange n different index into k indifferent boxes

      To make k indifferent boxes into k different boxes is just to multiply it with k!

      So, $$$Stirling(n,k) *(k!)$$$ = How many ways can we arrange n different index into k distinct numbers

      Therefore, the number of arrays that has $$$k$$$ distinct numbers is $$$C_{n,k}*Stirling(n,k) *(k!)$$$

      And the final answer is $$$2*C_{n,k}*Stirling(n,k) *(k!)$$$

      (The $$$Stirling(n,k)$$$ can be calculated in $$$O(k*log(n))$$$ time using the formula in the wikipedia.)

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for reply, I think my confusion was because of given constraint in question that $$$k \le \binom{n}{2}$$$ whereas in reality $$$k \le n-1$$$. I was thinking that if $$$3$$$ rooks appear in a col then pairings is taken as $$$\binom{3}{2}$$$. But it is only $$$2$$$. In general if there are $$$m$$$ rooks in a col then pairings is $$$m-1$$$ right!

        This confusion got cleared when I read your second line with sample $$$A$$$. Now everything makes perfect sense. So reflecting my understanding, I now see if we have all $$$n$$$ in a col then we always get $$$n-1$$$ attack pairs. If we split it in 2 col then we have $$$n-2$$$ pairs of attacks no matter what the distribution.

        In general we need $$$k$$$ pair attack so we have $$$S(n,n-k)$$$ ways to make partition into $$$n-k$$$ group. Now multiplied by $$$\binom{n}{k}$$$ to signify which col those group denotes. Upto this is ok. Why multiply by $$$(n-k)!$$$ also

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Don't worry dude now I got it, We use $$$(n-k)!$$$ to shuffle between which group from partition corresponds to which selected col.

»
6 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

I have used the following greedy approach for problem D. Start iterating from the smallest element and assign all the frequencies of it in one array till the time the capacity of array allows or we have exhausted all the frequencies. If we have exhausted the frequency of that particular element, move on to the next element, if the capacity of the array is allowed.

It fails on test case 11. Can anyone please help me figure out what's wrong with the approach?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, made a small error in the previous version.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you figure out what's wrong with the approach?

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

    Try the example, $$$M = [1, 1, 2, 2]$$$ and $$$C = [2, 1]$$$

    The correct answer is we can group like $$$[1, 2], [1, 2]$$$ but your greedy leads to the groups $$$[1, 1], [2], [2]$$$.

    If you go from largest element to smallest element, I believe the greedy works but you have to worry about TLE on a case with $$$\sqrt{n}$$$ distinct values with $$$\sqrt{n}$$$ each (I used some similar greedy with optimization).

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

I have a weird solution for D that's more complicated but also simpler than the editorial's. Instead of precalculating the bounds, I construct the answer directly.

I have a vector<vector<int>> $$$t$$$ that will represent my testcases, and a position $$$p$$$ that will represent the testcase I'm adding to. $$$p$$$ will always go from the back of $$$t$$$ to the front. Also, I will add in each array in order of decreasing length.

Suppose I want to add in an array of length $$$m$$$. $$$t[p]$$$ consists only of arrays of length greater than or equal to $$$m$$$, so they all contribute to $$$c[m]$$$. If there's still room for $$$m$$$ there, go ahead and add it. If there isn't (i.e. $$$|t[p]|=c[m]$$$), we can for the sake of argument consider $$$t[p]$$$ "filled up" and decrement $$$p$$$, or set $$$p$$$ to the back of $$$t$$$ if $$$p=0$$$. Note that we can only move on from a $$$t[p]$$$ when it is filled up.

Now, $$$p$$$ is one less. The last time $$$t[p]$$$ was filled up was when $$$p$$$ cycled through $$$t$$$ earlier. The $$$c$$$ at that time was either less or equal to now. If it was less, great! there's more room for our $$$m$$$. If not, we know the whole $$$t$$$ has been travelled through with the same value of $$$c=c[m]$$$. This means we can't place $$$m$$$ anywhere in $$$t$$$ because all the testcases are filled to the same $$$c$$$! Our only option is to add a new testcase and place $$$m$$$ there. Set $$$p$$$ there too.

Make sure to account for when $$$t$$$ is completely empty as well.

Since we only add testcases when it's impossible to place $$$m$$$ anywhere else, the solution must be optimal. Furthermore, for every $$$m$$$ we only use append and size operations on at most two distinct locations $$$p$$$, so every $$$m$$$ is $$$O(1)$$$. This means the runtime of the main process is $$$O(n)$$$, and total runtume with sorts and everything is $$$O(nlog(n)+k)$$$, just like in the official solution.

Find it here: 78200438

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    for (int i = 0; i < n; i++) {
            if (t.empty())
                t.push_back({m[i]});
            else if (t[p].size() < c[m[i]])
                t[p].push_back(m[i]);
            else {
                if (p == 0) p = t.size();
                p--;
                if (t[p].size() < c[m[i]])
                    t[p].push_back(m[i]);
                else {
                    t.push_back({m[i]});
                    p = t.size() - 1;
                }
            }
        }
    

    If an element doesn't fit into current t[p] , you do a p-- . So how do we know that current i will either belong to p-1 or p+1(new testcase). Don't we have check over entire p = 0 to p-1 and then add it into new testcase ?

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

      I think solution is working once from top to bottom and then goes bottom to top...
      Here is my thinking why does an element either belong to p or p-1 or p+1 (i.e, creating new testcase)...If we observe first larger elements of sizes of array are fixed from top to bottom.
      Like this, arr_sizes = [3,3,3,2,2,2,2,1,1,1] and arr_k = [3,2,1]
      So after first top to bottom session, ans = [[3],[3],[3]] and p=2
      Now array size changes to 2, here we have three choices, p,p+1,p-1
      So we added 2 to p So now ans = [[3],[3],[3,2]]
      Again we have to add 2, we can add new testcase i,e. p+1 and ans = [[3],[3],[3,2],[2]] (Wrong answer) but it would not generate minimum answer. We cannot add 2 to p and make ans = [[3],[3],[3,2,2]] (Wrong answer) since there should only 2 array>=2
      We have all arrays filled up with exact size except last one, so now we will look for upper half, now it's time to move bottom to up
      ans = [[3],[],[]] p=0 (Go top to bottom)
      ans = [[3],[3],[]] p=1
      ans = [[3],[3],[3]] p=2
      ans = [[3],[3],[3,2]] p=2
      ans = [[3],[3,2],[3,2]] p=1 (Go bottom to up)
      ans = [[3,2],[3,2],[3,2]] p=0
      ans = [[3,2],[3,2],[3,2],[2]] p=3 (We hit p==0 condition pf code)
      ans = [[3,2],[3,2],[3,2],[2,1]] p=3
      ans = [[3,2],[3,2],[3,2],[2,1,1]] p=3
      ans = [[3,2],[3,2],[3,2,1],[2,1,1]] p=3 (Go bottom to up)

      This shows when we move from top to bottom we are make all inner vectors of same sizes. When we hit to the end we make the last vector size greater then all vectors and when that vector is filled we go bottom to up for making such vectors of same size as last one....
      It was a great observation by Russell_Emerine. I wish if would have done that..
      Hope you get the intuition

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh yeah, I see now, it goes to the top and drops directly to bottom I see I see. Thanks buddy!

        I guess this question WAS tough for me after all.

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

Can anyone explain the editorial of 1342D — Multiple Testcases.

Specifically how it is proven Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ over all i from 1 to k. You can prove that you can't fit gi arrays in less than ⌈gi/ci⌉ testcases with the pigeonhole principle

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The upper bound is because we can distribute all the numbers $$$\geq k$$$, then all the numbers $$$\geq k - 1$$$, etc. For the lower bound, assume by way of contradiction that we use $$$ans$$$ testcases and there is some $$$i$$$ such that $$$\lceil g_i / c_i \rceil > ans$$$. Then by the extended pigeonhole principle, one of the testcases must have more than $$$c_i$$$ arrays of size $$$\geq i$$$, which is a contradiction (alternatively, you can think of it like trying to distribute the g_i cases among $$$ans$$$ testcases is impossible).

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E with FFT?

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

for the problem D I am not able to understand why my solution https://codeforces.com/contest/1342/submission/78247111 is correct while https://codeforces.com/contest/1342/submission/78247043 is wrong. the only difference is the 2 solution is that I have used 1e10 as a multiplier in the first and 1e11 in the second . since the constraints were 2*1e5 I don't think replacing 1e10 with 1e11 should be an issue , but it turns out it is . It will be really helpful if anyone can explain reason behind failure of later second submission

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

    I don't understand your solution method at all, but could it be floating point rounding error?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your help, Yes it was floating point rounding error. Thanks again.

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

In the Editorial for Problem D. I am not able to understand this thing, "Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ overall i from 1 to k". Can somebody explain how is this working? I am able to form some intuition about it after reading the Editorial but it is still not completely clear to me. If somebody can explain it in a little more detail it will be highly appreciated.

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

    I mean there's really no more detail to that. You want to place these $$$g_i$$$ arrays somewhere. What's the minimum number of testcases required to do that if you can't put more than $$$c_i$$$ in each of them? So you put $$$c_i$$$ into the first one, $$$c_i$$$ into the second one and so on until you have no more arrays left. You will use exactly $$$\lceil \frac{g_i}{c_i} \rceil$$$ testcases with that.

    That idea by itself does not really account for the placement of individual arrays of these sizes exactly, so the actual construction is more complicated than the proof for the minimum bound.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi I understood most part of the solution by this line is confusing me.

      forn(i, n) res[i % ans].push_back(a[i]);
      

      I understand you are assigning the elements into ans arrays and in a sort of cyclic order. But how do you guarantee that the element in the array will follow the constraint. I tried some test cases and it does!!

      Is there some sort of proof or something. Even some intuition might do as well. Thankyou very much

      PS: it was nice editorial

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

problem A stated that our task is to get x and y equal to 0 simultaneously. This costed me 2 incorrect submissions until that was clarified. Anyway this was one of the few div 2 contest where D problem felt easier and within the range.

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

I tried problem C, although wasn't able to get it correct and looked up the tutorial. But I have my code for the same which is not so efficient and correct (but should run). What bugs me is when I try and run it (I use sublime text 3), it gives me "'filename' is not recognized as an internal or external command, operable program or batch file. [Finished in 3.7s with exit code 1] " message without showing any errors in code, and I'm not able to quite pin point what's causing it. Please help me with this. Code: https://pastebin.com/f87wxz80

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

I am unable to find what is wrong in my code. I have calculated all values from l to r for which (x%a)%b == (x%b)%a using lcm(a,b) and simple multiplication and then subtracting it from (r-l+1). But my code is stuck at 2nd test case. Here is my code code.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same. I don't understand why. The restricted range should be [nl, nl+b) where l is the lcm and nl is a multiple of lcm and b is the larger of (a,b). Mine also fails at 2nd test case.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 4 15 1 59 73

    your output : 0 correct output : 1

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

How does https://codeforces.com/contest/1342/submission/78244632 pass but https://codeforces.com/contest/1342/submission/78244302 fails? There is only one line change, and that line never gets executed. The 'cout << "???"' line never gets executed, since the test passes.

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

Can anyone help with TL on problem F?) https://codeforces.com/contest/1342/submission/78328093

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

    You probably need to remove the first innermost loop, which can be replaced with something like

    int lower_than_j = s & ((1 << j) - 1);
    if (lower_than_j == 0) continue;
    msb = 31 - __builtin_clz(lower_than_j);
    

    This also replaces the if statement.

    Other micro-optimizations you could try is if you iterate over j from high to low, I think you can break instead of continue when msb == -1. Also, I think k's maximum value is __builtin_popcount(s) + 1 since you can't have more groups than on-bits.

    It took me a while to not get TLE, though I had a slightly different setup. Hope this helps.

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

      Thank you) But, unfortunately, it doesn't help. I have one of the submissions, where I precalculate msb for all masks and bits. The thing that helped was to change backward DP behavior (where I subtract submask) to forward DP (where I add submask of superset). It also changed some of the if statements

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

for D problem: why do we need to assign indexes by sorting in decreasing order..will doing same in increasing order work?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Both work fine

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the exactly same logic as in tutorial..used both increasing and decreasing but its not working.. what wrong with the code 78370972

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

For D, why does inserting the (i mod ans)th testcase always optimally construct the testcase array? Like is there any proof or intuition to understand/come up with it ?

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

    The intuition is basically something along the lines of "add stuff in such a way that it's packed as tightly as possible". Like given the fixed number of testcases, put arrays of all big sizes so that each testcase has as few of them as possible. And the modulo does exactly this. It puts arrays like $$$1,2,\dots,k,1,2,\dots,k,\dots$$$, which only has $$$\lceil \frac{n}{k} \rceil$$$ arrays put in the worst testcase if there are $$$k$$$ testcases and $$$n$$$ arrays.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    I think we can come up with the solution by thinking in this way. Taking just a single constraint, if suppose the count of arrays with size = k is 11 and constraint on k = 3, then we would need at least ceil(11/3) = 4 testcases. We would then distribute them as follows: tc0 = k k k ; tc1 = k k k ; tc2 = k k k ; tc3 = k k ; If we fill it in a circular manner, then we can fill the testcases in the most efficient manner satisfying the single constraint. Expanding to more than one constraint, if we take maximum of all such ceil(count/constraint), "ans" , we can distribute all arrays with whatever be the sizes among 0 to ans-1 testcases in a circular manner satisfying all the constraints.

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

Video solution for C.

»
6 months ago, # |
  Vote: I like it +24 Vote: I do not like it

War. War never changes. Can you do something about it Ne0n25?

My submissions to F
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't even understand now, how do my optimizations work.

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

C- Yet Another counting problem

An alternate O(1) for each query solution. Let's denote a as the smaller one of (a,b) and b as larger one of (a,b). Any number lying in the range [0, b) would satisfy ((xmoda)modb)=((xmodb)moda). Let's denote LCM of a and b as l. The range [0,b) would imitate itself for the range [l, l+b), [2l, 2l+b), [3l,3l+b).... So we can count the multiples of l in the given range and also find the restricted range by adding b to it. It is also possible that a multiple of l might fall outside the given range but yet some numbers fall in the range [nl, nl+b), so we need to take extra care for that.

My code doesn't work. Maybe somebody could help me figure out the mistake in the logic?

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

    I believe this submission 78156490 will show you a clearer view of your idea

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

You can do C in $$$O(1)$$$ per query and $$$O(q)$$$ per test case with no precomputation required. I believe in the small problems like A,B,C the intended solution should be the fastest one. Even if the explanation is a bit longer and not that beautiful. Here is my solution. https://codeforces.com/contest/1342/submission/78195420

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Here's a terrible overkill solution for E, as an alternative to inclusion-exclusion. We want to count the number of ways to distribute $$$n$$$ rooks into $$$m = n - k$$$ fixed columns, such that all of them remain non-empty and there's one in every row. Assume that we fix the ordered tuple $$$a_1, a_2, \dots, a_m$$$ of how many rooks we place in each column. Then the number of ways to place the rooks is

$$$\frac{n!}{a_1!a_2! \dots a_m!}$$$

This formula counts the number of ways to arrange the $$$n$$$ rooks if they're labeled and then eliminate the order from all rooks in the same column. Thus the problem is reduced to calculating

$$$\displaystyle\sum_{a_1 + \dots + a_m = n} \frac{1}{a_1!a_2! \dots a_m!}$$$

Which we can interpret as the coefficient of $$$x^n$$$ in $$$\left(x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}\right)^m$$$. We can calculate this in $$$O(n \log^2 n)$$$ with binary exponentiation and NTT, which is enough to pass with a few constant factor optimizations.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I am not very familiar with NTT. Can you please share some resources to learn about it.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey I am not understanding some comments in this regard: Why are we choosing $$$n-k$$$ columns? I mean there may be case where $$$k > n$$$ in that case how can we select $$$n-k$$$ columns. Also am I correct in saying that your answer will be multiplied by $$$2$$$ because same thing be done by replacing row with column?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wanted to see if there was a simpler closed form for the PIE summation in the editorial, and looked to this comment for inspiration.

    Your polynomial set off my $$$e^x$$$ detector, so I thought it would work out pretty simply and proceeded as follows: we want the coefficient of $$$x^n$$$ in $$$n! (e^x - 1)^m$$$, which we can find by differentiating $$$n$$$ times and dividing by $$$n!$$$.

    I expanded this to $$$\sum_{k=0}^m \binom{m}{k} e^{kx}x^k (-1)^{m-k}$$$, and differentiating $$$n$$$ times gives us $$$\sum_{k=0}^m \binom{m}{k} k^n e^{kx} (-1)^{m-k}$$$, which looks awfully familiar. So that didn't work, but gave a different route to the same destination. xD

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

Can anyone explain me why ((ab+x) mod a) mod b == (x mod a) mod b
I am a beginner and don't know much about modular arithmetic... If there are some proofs of modular arithmetic that I should know as a competitive programmer can you please mention such resources
Thanks in advance :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is because (ab%a)%b==0

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain why this property creates cycle from 0 to ab-1 then ab to 2ab-1 and so on??

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, because the cycle has length ab. Because if we add ab to x, the result of the formular is the same.

        This is more or less the definition of the length of the cycle. Which number do we have to add to allways get the same result? Answer is: That one which allways creates result 0, because 0 is the neutral element of addition.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, since both a and b divide ab, ab % a = ab % b = 0. Thus (ab % a) % b = 0 % b = 0 = 0 % a = (ab % b) % a. Note that the above holds if we replace ab with lcm(a, b).

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

In problem D what's wrong for test case 1 if I give the answer as 4 1 2 2 3 as c1 can have 4 elements greater than 1???

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because if you chose array of size 1 then you have no. of arrays of size>=1 is 1. just next if you choose 2 then you have no. of arrays of size>=2 is 1. and then if you choose 2 again then no. of arrays of size>=2 is 2 now. but it is mentioned that no. of arrays of size>=2 can't exceed 1 ( as c[2]=1 ).

    I hope you get it now..

»
6 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

For problem F. Why did you decide to put such bounds on your max test? I calculate the following lower bound on your max test number of operations -- $$$4500 \cdot f(5) + 400 \cdot f(8) + 50 \cdot f(10) + 25 \cdot f(11) + 15 \cdot f(12) + 7 \cdot f(13) + 2 \cdot f(14) + f(15)$$$, where $$$f(n) = n^2 3^n$$$. That is, according to my python $$$9 ~163 ~838 ~367$$$. Why did you put 7 seconds on that?

Cause my solution jumps between TL and AC just when I change backward DP to forward DP and change a couple of if statements correspondingly.

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

    We usually set the limits in harder problems depending on the behaviour of the model solution. In this problem, the model solution runs in $$$1.4$$$ seconds on the worst case (and it may be even faster on $$$64$$$-bit compiler, which cannot be used in Polygon), so we thought that it was fine that the time limit is $$$5$$$ times larger than the runtime of our solution.

    $$$f(n) = n^2 3^n$$$ is just a close estimate of the number of required operations, since some states may be unreachable (for example, a state where $$$cnt$$$ is greater than the number of $$$1$$$-bits in the mask is impossible).

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

Can anyone told me what's wrong with my code for problem div2 C. My Source code is here. I have found the pattern that after LCM of a and b say LCM all b numbers will follow the equality x%a%b==x%b%a these numbers would be [0,b) [LCM,LCM+b),[2*LCM,2*LCM+b) I have tried to remove all these numbers. Here b refers to the big number. Somehow I am getting the wrong answer. If anyone could help, it would be a great pleasure.

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

Can anyone correct me if I'm wrong or say that I'm right? In Ques C, we may notice that all numbers $$$x\in[k\cdot lcm(a,b), k\cdot lcm(a,b)+max(a,b)-1]$$$ where $$$k\in \mathbb{Z}$$$ follow $$$(x \mod a)\mod b = (x \mod b)\mod a$$$. We can count all other numbers in the range $$$[l,r]$$$ in $$$O(1)$$$ time. Thus, the time complexity can be reduced down to $$$O(q)$$$ per test case.

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

I have an issue about ceil. Can anyone tell me why the submit is incorrect? https://codeforces.com/contest/1342/submission/78388627 Thank you.

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

    Don't use ceil, It's always better to not mess with floating points as much as possible. If you wanna find the ceil(p/q) use (p+q-1)/q instead.

    Also you're ceil doesn't work because your cnt[i+1]/cnt[i] is converted into an integer(int/int) before it is ceiled. Use ceil((float)cnt[i+1]/cnt[i]) and your code will work.

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

Problem E has fft tag, how to solve it using fft?

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

can someone plz help me in problem D?? how to approach to solve this problem?? didnt understand the editorial

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

Can somebody Please Explain Why I am getting WA on Problem C Submission.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 4 15 1 63 79

    your output: 17 correct output: 5

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

Thanks for editorial! It helped me a lot

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

Problem E

How to calculate the number of ways to distribute the rooks into $$$c$$$ columns? One of the options is to choose the columns we use (the number of ways to do this is $$$C_n^c$$$), and then use inclusion-exclusion to ensure that we are counting only the ways where each column contains at least one rook.

Why "each column contains at least one rook" not equal to $$$C_{n-1}^{c-1}$$$ — number of distributions of $$$n$$$ not different items into $$$c$$$ not empty groups?

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

    This would work if we treated all rooks as equal. But they are not — each row contains exactly one rook, so each rook is uniquely represented by its row index (so they are different).

    This formula does not distinguish, for example, between these sets of positions: $$$[(2, 1), (1, 2), (3, 2)]$$$ and $$$[(1, 1), (2, 1), (3, 2)]$$$.

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

I tried a different approach but it is failing on testcase 11. The checker says that jury has better answer, but I don't think that is possible. Please help

My Approach: I have sorted the m array(size of array of original input) in decreasing order. I have taken frequency of every element entered in m and stored in a hashmap.

Now, I also maintain a variable alpha which keeps track of number of element in the new array. when c[m[left]-1]- alpha<=0 I start a new array. This means that when the allowed limit of the element found at left index - no of element already in the list <=0 I start a new array

for example if the input array is 1 2 2 3
then after sorting it will be m=[3 2 2 1]
So in the first iteration, the ```left=0``` the frequency of ```m[left]=1``` so I put it in the array and decrease its frequency by 1 and increase left by 1

now in the second iteration of inner loop, ```left=1``` and the frequency of ```m[left]=1``` Also, alpha is 1 now. so c[m[left]-1]-alpha is equal to zero and I terminate.

Now in the the second iteration, ```left=2``` and the freq of ```m[left]=2``` Alpha=0 as new iteration started. so now I add it again to the new array 

now in the second iteration of inner loop, ```left=3``` and the frequency of ```m[left]=1``` Also, alpha is 1 now. so c[m[left]-1]-alpha is equal to zero and I terminate.

And for the third iteration, ```left=3``` and the freq is 1. alpha=0 so I add it to the new array and left=4. now since the limit is more than 1... I do not terminate and the new array has [2, 1] inside.


Thus, the final list is [3], [2], [2,1]

Now what I think is that this way leads to the optimal solution. Please explain why does it fail for test 11

The link to the code is as follows: https://codeforces.com/contest/1342/submission/78422553 @pikmike

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ok I understood it. Cannot delete it now. sad.

    fails for test case [1 1 2 2] [2 1]

    correct ans= [1 2][1 2] my ans= [1 2] [2] [1]

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

In Problem D

Input

7 7
1 2 3 4 5 6 7
2 3 2 1 2 1 1

In the above input, the editorials output is:

4
2 7 3
2 6 2
2 5 1
1 4

which says we need min 4 testcases, i think the min number would be 3 using the following distribution of arrays:

3
2 5 7
3 2 3 6
2 1 4

PLEASE, correct me if I am wrong.

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

    "The third line contains k integers c1,c2,…,ck (n≥c1≥c2≥⋯≥ck≥1); ci is the maximum number of arrays of size greater than or equal to i you can have in a single testcase."

    in input you are not following constraints... it is mentioned that n>=c1>=c2>=c3...>=ck>=1..

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

    In your second array $$$[2, 2, 3, 6]$$$, there are three elements that are $$$\geq1$$$, which violates the input (there's also a typo as the size is three, not two).

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

Can anyone explain the E part second test case as for 3x3 chessboard and exactly 3 pairs why
|R|R|.|
|R|.|.|
|R|.|.|
is not one of the valid solution? I think in this 3 pairs are attacking each other.

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

    you need to place n rooks only, in your case rooks are 4.

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

In case anyone need div2 D explanation,code and example Here

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

does anyone know how to use int64_t main() as i always get error for it even though if i use #define int unsigned long long int before??

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

((ab+x)mod a)mod b == ((x)mod b)mod a for problem C

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

I was surprised that $$$O(n^23^n)$$$ solution passed in F. I have $$$O(n^22^n+n3^n)$$$ solution.

Notice, that if $$$cnt_1 > cnt_2$$$, then $$$dp_{cnt_1,mask,pos} < dp_{cnt_2,mask,pos}$$$ for any $$$mask, pos$$$ in valid state. Thus, there is no need to recount from all dynamics states. For each $$$mask$$$ and $$$pos$$$ find the largest $$$cnt$$$, that $$$dp_{cnt,mask,pos}$$$ valid, and update $$$dp_{cnt,smask,pos}$$$ for all $$$smask$$$ that don't intersect with $$$mask$$$.

We need $$$O(n^22^n)$$$ for find largest $$$cnt$$$ for each $$$mask$$$ and $$$pos$$$ and $$$O(n3^n)$$$ for update dynamic.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain why that inequality holds?

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

For Div2D, I converted given array into a map sorted with descending order keys, and then I traverse the map from largest key to smallest, trying to make a set of testcases,while decreasing the frequency of which I am using and deleting those whose freq becomes 0.
I keep on doing this until, map becomes completely empty.
I am getting runtime error on tc 1, which is working fine locally.
Can anyone suggest how to carefully iterate over a maps keys from desc to asc order while deleting some keys based on some condition ?
I think the logic is correct, becoz if I use array instead of maps, while increasing the time complexity since I loop from max no to 1 everytime, I am getting TLE on tc16.

Solution with map

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

    I might be wrong but something similar has happened to me before, when you check for a value in the map, even if it's not an entry in the map, an entry for it gets created against the value 0/NULL, so when you're traversing the map, you also go through the new entries.

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

In problem F i fail to understand what is dpcnt,mask. what is meant by mask in editorial?

I cant understand the state of DP

Please help

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

@Ne0n25: For problem F, what does order stand for in the statement "Suppose we don't have any constraints on the order of elements," Is it for the number of elements?

Also in the statement "This runs in O(n*(3^n)), if we use an efficient way to iterate on all masks that don't intersect with the given mask.",how did you derive the O(n*(3^n))

I am pretty new to competitive programming and your reply would be of great help to me.

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

For the forth problem, can somebody explain and help me figure out whats wrong in my code. I am getting WA for the test case 11. Though i am correctly determining the minimum number of testcases required, but maybe doing some mistake in filling the arrays for the test cases.

int main(){
	BOOST();
	int n,k;
	cin>>n>>k;
	vector<int>mi(n);
	vector<int>ci(k+1);
	for(int i=0;i<n;i++)cin>>mi[i];
	for(int i=1;i<=k;i++)cin>>ci[i];

	sort(mi.begin(),mi.end());	
	int size=INT_MIN;
	int cnt;
	for(int i=1;i<=k;i++){
		cnt=n-(lower_bound(mi.begin(),mi.end(),i)-mi.begin());
		size=max(size,(cnt+ci[i]-1)/ci[i]);
	}
	
	vector<int>final[size+1];
	int flag=1;
	int cntr=0;
	while(flag<=size){

		final[flag].pb(mi[cntr]);
		int left=ci[mi[cntr]]-1; // left denotes how many more numbers i can still fill after filling mi[cntr]
		for(int i=cntr+1;i<n;i++){
			if(left==0){     // if left==0, then break;
				cntr=i;
				break;
			}
			final[flag].pb(mi[i]);
			left=min(left-1,ci[mi[i]]-1);  // every time we take minimum of the numbers we can fill after filling mi[i]
		}
		flag++;
	}

	printf("%d\n",size);
	for(int i=0;i<size;i++){
		printf("%d ",(int)final[i].size());
		for(auto &x:final[i])
			printf("%d ",x);
		printf("\n");
	}
}
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you can't debug your code , How can we ??

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I will be explaining how I attempted question D but was not able to get it accepted because of reasons unknown to me; if you realise what's wrong in my code please let me know.

  1. Firstly, I sorted m and began traversing from the last position. I checked how many arrays can be greater than this array's size using array c and incremented my counter which was initially 0 and appended it to my ans array.

  2. now I went to the second last element of m and subtracted count from the value of c at this position since I have already used an array of size greater than this arrays i.e I did c[m[i]-1]-=count.

  3. now if still the c[m[i]-1] was greater than 0 I appended this array size into my answer array and kept on traversing backwards.

  4. if my c[m[i]-1] would have been less than 0 I would have finished the process of making this test case and start making the process of the new test case from this position onwards. Also, I again initialised count to 0 and made a new copy of c.

this is the basic idea. I submitted my code and got WA at TC11. Let me know what's wrong in my idea for the question.

link to my solution: https://codeforces.com/contest/1342/submission/78349009

link to question: https://codeforces.com/contest/1342/problem/D

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: It took me a day to realise that I was only appending elements in descending order and broke the loop whenever I encountered an array size which cannot be appended. Therefore I started traversing the whole array and appending the possible array size but in doing so I ended up with the worst-case complexity of O(n^2) when each array can have only one element.

    This time I got a TLE on TC16. Please help me out; I wanted to edit in the previous comment itself but I felt that it's better this way since this would make you realise the persistent approach building process I went through.

    link to the updated solution: https://codeforces.com/contest/1342/submission/79016398

    link to the question: https://codeforces.com/contest/1342/problem/D

    Again, I know a lot of you have solved the question so please help me find out where I am going wrong and how to reduce time complexity.

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Another solution for D using priority queue

Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain the approach using priority queue?

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

From the editorial for F (first paragraph): "To model transitions, we simply iterate on the mask of elements that will be merged into a new one, and check if its sum is greater than the last element we created."

I'm kind of lost here. Is there any mathematical formulation of the DP transition that could potentially clarify this? (trying to upsolve this since this is the only problem in the contest idk how to do).

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

if you don't know the formula for ceil function it is given in D

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

i'm confused about the prefixes. in some cases, you'll have ends hanging from both the left and right, and because the mod is not uniformly distributed, if you calculate it by "the amount of mods that worked previous to this index" then what will happen if you have like 5 integers hanging from the left and 7 from the right? the 7 can be calculated easily true but what about the 5 on the right? if you calculate it using prefixes, then instead of getting the correct index you'll get prefix[a*b-5]. or do additive shifts not affect mods at all, and therefore there's no hanging left integers?

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

Hello!!

I was attempting Problem D and my approach was as follows:- I first sorted the array a in increasing order and then started traversing in the reverse direction. If for some a[i] I could find a test case whose size is less than a[i]'s capacity then I will add that element to that test case and if no such test case exists then I will make a new test case.

It is getting wrong answer at Testcase 17. I would appreciate if someone could help with the bug in my logic. (Ne0n25 BledDest adedalic pikmike)

Here is my solution: 80590063

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

Hey for problem C, can we use this logic?

let max be the greater number of a and b. So. the numbers from (multiple of lcm(a,b),multiple of lcm(a,b)+max) are to be subtracted from the given range.

Here's the code

include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b) { int max=0; for(int i=2;i<sqrt(a*b);i++) { if(a%i==0 && b%i==0 && i>max) max = i; } if(max==0) max=1; return max; }

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin>>t;

while(t--)
{
    int a,b,q;
    cin>>a>>b>>q;
    int lcm = a*b/gcd(a,b);
    //cout<<lcm<<endl;

    if(a>b)
    {
        int temp = a;
        a=b;
        b=temp;
    }                                                   // a<b always now

    long long ans[q]={0};
    for(int i=0;i<q;i++)
    {
        long long l,r;
        cin>>l>>r;

        if(lcm==b)
            cout<<0<<" ";

        else
        {
            long long count = r/lcm - (l-1)/lcm;
            //cout<<count<<endl;

            ans[i] = r-l+1 - b*count;
            //cout<<ans[i]<<endl;

            if((l/lcm)*lcm <l && (l/lcm)*lcm + b >= l)
            {
                ans[i] = ans[i] - ((l/lcm)*lcm + b - l);
            }
            //cout<<ans[i]<<endl;

            if((r/lcm)*lcm + b > r)
            {
                ans[i] = ans[i] + ((r/lcm)*lcm + b - r -1);
            }
            cout<<ans[i]<<" ";
        }
    }cout<<endl;
}

}

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

What is wrong in this Submission for Problem C??Submission

Thanks a ton in advance!!!!

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

https://ideone.com/VTSzgt alternative solution for problem C with time complexity O(log(a)) for query(because of gcd)

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Good contest

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

In problem C, I figured out that if lcm(a, b) = l, then first b(Assuming b > a) numbers from l * k (k = 0,1...) will not satisfy the conditions. So, now I just need to exclude them from my queries. I'm still getting a wrong solution. Can somebody figure out the problem pls ? Thanks. My Submission : 84942234

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

In problem B:

Why printing out the string twice is not a correct answer?

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

" Otherwise, it's also quite obvious that any string t is a subsequence of 0101...01 (1010...10) of 2|t| length."

for problem B, I dont find this sentence obvious at all. Could someone please explain it to me (and others)?

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

Can someone help me with C. My idea for this problem was the value of (x%a)%b and (x%b)%a repeats itself for every lcm(a,b) distance. So i thought i could iterate through the first lcm(a,b) numbers(from l) and add all the multiples till r to the answer. But it TLEs... can someone help on improving the complexity of my solution. Thanks in advance!!
Link to My Submission

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

    A better understanding of this C problem is in the editorial. its ,this way

    instead of a*b , just take upto lcm(a,b)

    explaination:: take t=lcm(a,b) for numbers :: 1,2,3,4.....t,t+1,t+2,t+3.....2*t,2*t+1,2*t+2......3*t,3*t+1.....4*t,...

    NOTE:: t=lcm(a,b);

    the question is why lcm(a,b)? soln:: is right in the editorial. lcm(a,b)%a%b==0 same for lcm(a,b)%b%a. this is the 2nd leat value after 0 for which it becomes 0. but 0 is not there in the range the value of l and r is from 1 to 1e18.

    so, use a prefix array for which this holds true;

    len = a * b;// here just do lcm(a,b)-->tym will be less p[0] = 0; for(int i = 1; i <= len; i++) { p[i] = p[i — 1]; if((i % a) % b != (i % b) % a) p[i]++; }