awoo's blog

Educational Codeforces Round 86 Editorial
By awoo, history, 5 years 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: Neon

Tutorial
Solution (Ne0n25)
  • Vote: I like it
  • +149
  • Vote: I do not like it

Comments Comments (155)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks! It answered my questions!

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

thanks for the editorial. C was bit tricky.

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

Can anyone please elaborate inclusion-exclusion part for E?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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?

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

          Exactly

          → Reply
        • »
          »
          »
          »
          »
          5 years 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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.

              → Reply
    • »
      »
      »
      5 years 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.

      → Reply
    • »
      »
      »
      5 years 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??

      → Reply
      • »
        »
        »
        »
        5 years 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 . .
        → Reply
    • »
      »
      »
      5 years 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?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation.

      → Reply
    • »
      »
      »
      5 years 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!

      → Reply
    • »
      »
      »
      5 years 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 :)

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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.

              → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
    • »
      »
      »
      5 years 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 ?

      → Reply
    • »
      »
      »
      5 years 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} ?

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

      In the 3rd and 4th paragraph you mean COLUMNS, not rows??

      → Reply
  • »
    »
    5 years 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.

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

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

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

Please someone tell me faster approaches for Problem C.

→ Reply
  • »
    »
    5 years 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.

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

      would you please explain this proof ?

      → Reply
    • »
      »
      »
      5 years 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://mirror.codeforces.com/contest/1342/submission/78349599)?

      Thanks a ton in advance!

      → Reply
    • »
      »
      »
      5 years 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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hi, please can you give an idea of why taking the range between l and r is incorrect in comparison to your solution, taking first 1 to l-1, and 1 to r. I can not find a counterexample.

      Here is my submission: 112327238

      UPD: AC 112369657

      → Reply
»
5 years 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 ?

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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; } ***

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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 !

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

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

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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 ?

    → Reply
    • »
      »
      »
      5 years 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$$$.

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

    That's exactly what I did

    → Reply
  • »
    »
    5 years 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!

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

      please tell me if you found the answer

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

    Really amazing solution and explanation. Thanks

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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$$$

    → Reply
»
5 years 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!.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.)

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, made a small error in the previous version.

    → Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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 ?

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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).

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

How to solve E with FFT?

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1342/submission/78247111 is correct while https://mirror.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

→ Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

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

    1 4 15 1 59 73

    your output : 0 correct output : 1

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

How does https://mirror.codeforces.com/contest/1342/submission/78244632 pass but https://mirror.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.

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

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years 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?

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

    Both work fine

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years 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 ?

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

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

Video solution for C.

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

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

My submissions to F
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years 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?

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1342/submission/78195420

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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?

    → Reply
  • »
    »
    4 years 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

    → Reply
»
5 years 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 :)

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

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

    → Reply
    • »
      »
      »
      5 years 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??

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years 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???

→ Reply
  • »
    »
    5 years 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..

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years ago, # |
← Rev. 3   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 \operatorname{lcm}(a,b), k\cdot \operatorname{lcm}(a,b)+\operatorname{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 $$$\mathcal O(1)$$$ time. Thus, the time complexity can be reduced down to $$$\mathcal O(q)$$$ per test case.

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1342/submission/78388627 Thank you.

→ Reply
  • »
    »
    5 years 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.

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

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

→ Reply
»
5 years 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.

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

    1 4 15 1 63 79

    your output: 17 correct output: 5

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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)]$$$.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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..

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

      Ah Sorry , I didn't notice that. Thank You.

      → Reply
  • »
    »
    5 years 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).

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

      Got it..! :) Thanks. (Corrected the typo).

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

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

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

→ Reply
»
5 years 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.

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

    Can you please explain why that inequality holds?

    → Reply
»
5 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

@Neon: 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.

→ Reply
»
5 years 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");
	}
}
→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Another solution for D using priority queue

Code
→ Reply
»
5 years 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).

→ Reply
»
5 years 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

→ Reply
»
5 years 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?

→ Reply
»
5 years 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. (Neon BledDest adedalic awoo)

Here is my solution: 80590063

→ Reply
»
4 years 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)

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Good contest

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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]++; }

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in C a*b can be replaced by lcm of a and b also.

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Whats wrong with my solution for problem E?

Let c = n-k. Number of ways such that c columns are filled = (Number of ways such that <= c columns are filled) — (Number of ways such that <= c-1 columns are filled)

So formula is $$$ \binom{n}{c}c^n - \binom{n}{c-1}(c-1)^n $$$

→ Reply