pikmike's blog

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

1327A - Sum of Odd Integers

Idea: vovuh

Tutorial
Solution (vovuh)

1327B - Princesses and Princes

Idea: BledDest

Tutorial
Solution (pikmike)

1327C - Game with Chips

Idea: Ne0n25

Tutorial
Solution (Ne0n25)

1327D - Infinite Path

Idea: adedalic

Tutorial
Solution (adedalic)

1327E - Count The Blocks

Idea: adedalic

Tutorial
Solution (Roms)

1327F - AND Segments

Idea: Ne0n25

Tutorial
Solution (Ne0n25)

1327G - Letters and Question Marks

Idea: BledDest

Tutorial
Solution (BledDest)
Tutorial of Psycho Thriller Cap
 
 
 
 
  • Vote: I like it
  • +84
  • Vote: I do not like it

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

D and E should have been swapped !

»
7 months ago, # |
Rev. 5   Vote: I like it -11 Vote: I do not like it

Great Contest! Congratulations!

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

In this contest Problem A is also very tricky.

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

    Yes! C++ solution for A had to handle int overflow with k*k.

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

    can someone please explain this in A : It is obviously greater than 2(k−1)−1 because k2≤n and it is obviously odd because the parity of n and k is the same.

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

For E i used a more dp like solution.

The number of blocks of size n is allways 10. Let

$$$bl(n)=10$$$

$$$bl(n-1) = 2*10^2 - 10*2 = 180$$$

$$$bl(n-2) = 3*10^3 - 180*2 - 10*3$$$

$$$bl(n-3) = 4*10^4 - bl(n-2)*2 - 180*3 - 10*4$$$

$$$bl(n-4) = 5*10^5 - bl(n-3)*2 - bl(n-2)*3 - bl(n-1)*4 - bl(n)*5$$$

...

This can be implemented in $$$O(n)$$$ with simple additions and multiplications. 74112302 (I use pow there, but that could be a multiplication, too)

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

    What's the logic behind this? I found this pattern but it didn't make sense to me.

    Thanks in advance.

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

      For say n=3 there are $$$3*10^3$$$ single digits. But some of those digits have neighbours which are same digit, we call them blocks.

      So, every digit not belonging to a block is a single digit. For n=3 this is $$$3000 - 2*180 - 3*10$$$ The 2 and 3 are the size of the blocks, 180 and 10 are the number of blocks.

      And that pattern repeats, since for any blocksize, if n is increased by one, the number of blocksize+1 is the same as before. Every block can be extended by one member.

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

      The reason for the pattern is that the total number of digits is always going to be n * 10^n, so you're just weighting each block count by its size and finding the value for the next n that makes it add up to the right value.

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

        Why total number of digits is always n*(10^n)? Shouldn't it be 10^n only? Thanks.

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

          It is $$$10^n$$$ numbers, $$$n$$$ digits each.

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

    RHS of bl(n-i) contains n-i terms hence a total computation of summation i over n which is quadratic. Is this what you mean?

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

      I solved this problem in the same way. You can maintain the value that you are subtracting off, and update as you go. if value[] is the value you want, psum[] is the partial sum of value[], and subs[] is the amount you are subtracting off, then the transitions are:

      subs[i] = subs[i+1] + psum[i+2] + 2*value[i+1]
      value[i] = (n-i+1) * 10^(n-i+1) — subs[i]
      psum[i] = psum[i+1] + value[i]

      There are other ways to do it, but this is how I did it in my code. 74286577

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

    wow wow wow wow wow.....thanks man....#thankusomuch.

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

    How can you implement this in o(n)?

    Wont it take o(n^2)?

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

      I'm leaving the power part, just for to demonstrate how to do it in O(N)

      1. $$$bl(n - x) = bl(n - x + 1)*2 + bl(n - x + 2)*3 + ... + bl(n + x - x)*(x+1)$$$

      2. $$$bl(n - (x + 1)) = bl(n - (x + 1) + 1)*2 + bl(n - (x + 1) + 2)*3 + ... + bl(n - (x + 1) + (x + 1)) *((x + 1)+1)$$$

      The second equation can be written as.

      2.$$$bl(n - (x + 1)) = bl(n - x)*2 + \left[bl(n - x + 1)*3 + ... + bl(n) *(x+2)\right]$$$

      And the first.

      1. $$$bl(n - x) = \left[bl(n - x + 1)*2 + bl(n - x + 2)*3 + ... + bl(n)*(x+1)\right]$$$

      The difference is:

      $$$sum = bl(n - x + 1) + bl(n - x + 2) + ... + bl(n) $$$

      $$$bl(n - (x + 1)) = bl(n - x)*2 + sum + bl(n - x)$$$

      So we just have to update $$$sum$$$ each step.

      For me, this is bit annoying than the solution described in the tutorial

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

    Nice observation, since top-down is always easy to observe. Good job !

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

Can anyone explain the solution of D with examples and the topic I must know before solving it?

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

Can someone explain solution of E? The language in the editorial is very hard to follow for me.

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

    especially "blocks which first element is a first element of integer"

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

    For E , consider we are finding answer for length k , let x be the number within block ( 0 <= x <=9) for say k=3 and n=7; then two cases are : 1. xxx++++ , ++++xxx 2. +xxx+++ , ++xxx++ , +++xxx+ these are ( n — k -1 ) For case a: u choose x in 10 ways , now immediate next to x has to be different because we are doing this for length k ,so it will be chosen in 9 ways , remaining we have ( n-k-1)positions left which can be filled with 10 numbers . For case b : u can understand similarly .

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

      Ya this makes it clear what the editorial meant, thanks!

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

      How can we be guaranteed that there are no collisions, like For n==5 and k==2 Case:1 00___ -> last two dashes have 10 chances each so 00_00 is possible. ___00 -> first two dashes have 10 chances each so 00_00 is possible. We are counting that twice write.but we are not supposed to be.

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

        yeah , i thought about that and this is the reason i could not solve in the contest , i too thought that there will be collision . But this is not a collision , we actually need to add these two . Just take some time , u will see . ( we need block count , focus on this ). See , for 00x** , counting the right x** gives u numbers which contains it and it implies this block was present in them . for , **x00 we do the same and this block was present in them . When we add these two values , we are adding blocks 00___ and ___00 and 2 different block because of their position . For eg , 00900 u need to do +2 and not +1 .

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

          thanks man its nice to observe this thing For eg , 00900 u need to do +2 and not +1(block count). thanks

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

    Take the example of n=5, k=2 where n is the total size, and k is the block size. So .33.. and ...99 would fall under this.

    Observations

    • All Placements: xx... | .xx.. | ..xx. | ...xx — (n-k+1) ways
    • All placements can be broken down into corner placements and middle placements
    • Corner placements (where xx is either suffix or prefix): xx... or ...xx — 2 ways
    • Middle placements (where xx is neither suffix nor prefix): (total number of ways) — (corner placements) = (n-k+1) — (2) = (n-k-1) ways
    • There's 10 ways of picking x in the block 'xx' (0..9) and 9 ways of picking the digit adjacent to x (0..9 minus x)
    • Each corner placement has only 1 digit adjacent to it that needs to be different from x, while middle placements have 2 such digits
    • Number of remaining/unfilled positions = (total length) — (size of block) — (number of adjacent digits that need to be different)
    • Number of remaining/unfilled positions = (n — k — 1 for corner) and (n — k — 2 for middle)
    • Number of filling these unfilled positions = 10^(positions) — since each unfilled position can be 0..9

    Calculations

    • If n==k, then you can only fill it in 10 ways. Return that as answer.
    • Total count of all corner placements for all x = (# of corner placements) * (# of ways of picking x in the block xx) * (# of ways of picking the digits adjacent to xx) * (number of ways to fill up every remaining position with digits 0..9)
    • Total count of all corner placements for all x = 2 * 10 * 9 * 10^(n-k-1)
    • Similarly, total count of all middle placements for all x = (n-k-1) * 10 * 9 * 9 * 10^(n-k-2)
    • Answer = (Total count of all corner placements) + (Total count of all middle placements)
    • Answer = (2 * 10 * 9 * 10^(n-k-1)) + ((n-k-1) * 10 * 9 * 9 * 10^(n-k-2))
    • Answer = (180 * 10^(n-k-1)) + ((n-k-1)*81*(10^(n-k-1))
    • Answer = (180 + (n-k-1)*81) * 10^(n-k-1)

    (Edit: Just realized that the editorial pretty also goes into detail — I had not read that for E. So may be worth referencing that as well.)

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

      Cool, Thanks! I understand the solution however it feels that at my current level it is very unlikely that i ll be able to come up with a solution like this :(

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

        Not at all. I'm sure you can do it with practice. I didn't get this during the contest either. But I had an improvement over the last few times when I had similar problems (when I was completely clueless). This time at least I was approximately right as I was close to a solution. The only difference between then and now has been doing some practice on paper.

        It will look a lot simpler when you do it on paper, than by reading and trying to comprehend. Use this text as reference and don't get overwhelmed by it.

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

      How can we be guaranteed that there are no collisions, like For n==5 and k==2 Case:1 00___ -> last two dashes have 10 chances each so 00_00 is possible. ___00 -> first two dashes have 10 chances each so 00_00 is possible. We are counting that twice write.but we are not supposed to be.

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

        The problem asks for blocks, not how many unique numbers match the criteria. A hint in that direction is the second example: when n = 2, and k = 1, you'd expect 90 numbers, but the answer is 180, since it is blocks. A block is simply the same digit repeated to a certain length. So the number 23 would have 2 blocks of size 1 in it, even though it is only one number.

        Note that if you were to calculate the count of unique numbers, instead of blocks, then you'd divide this by a certain factor (your example correctly identifies the overcounting that needs to be accounted for).

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

          thanks dude , little bit confused with blocks and numbers,finally understood.

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

    Here check out my video solution https://www.youtube.com/watch?v=gmis4iWP_pY

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

Could someone explain the time complexity for problem D?

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

    $$$O(n^{1/3})$$$ is a "rule of thumb" approximation for $$$\max _{x=1} ^{n} d(x)$$$, the maximum number of divisors of $$$x \in [1,n]$$$. For exact values, you may consult this list.

    Theoretically, this formula is $$$O(n^\epsilon)$$$ for any $$$\epsilon > 0$$$, but it takes very large values of $$$n$$$ to converge, so this fact's not useful in typical competitive programming contexts.

    You can get a close approximation at typical CP-relevant ranges ($$$n \lesssim 10^{18}$$$) via the formula $$$\max _{x=1} ^{n} d(x) \approx \min (3.5273 n^{1/3}, n^{1.066 / \ln \ln n})$$$ (source)

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

      can you explain the 3rd test case of problem D. i`m getting ans with p5 but how for p2

      Q

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

      solution In the third test case, p2=[3,6,1,8,7,2,5,4] and the sequence starting from 4: 4,p2[4]=8,p2[8]=4,… is an infinite path since c4=c8=4.

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

        For each index, you need to build the cycle for that index (and mark the other members of the cycle in an auxiliary array so you don't build any cycle more than once). Then for each divisor $$$d$$$ of the cycle size $$$s$$$, you want to find a position $$$i$$$ where all indices $$$cycle[i + kd]$$$ for $$$k \in [0, \frac s d)$$$ have the same color. A success means you have found a path in $$$p^d$$$, so the smallest $$$d$$$ of all successes is the answer.

        Sample: 74200072

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

          Thanks really a great explanation, it was very hard for me understand this without a perfect explanation.

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

For D, example 2 of the problem statement states:

In the second test case, p5=[1,2,3,4,5] and it obviously contains several infinite paths.

However, if you take the original array p1 = [2 3 4 5 1], and run through the iterations, then:

p1 = [2 3 4 5 1]
p2 = [3 4 5 1 2]
p3 = [5 1 2 3 4]
p4 = [4 5 1 2 3]
p5 = [2 3 4 5 1]

So is there an issue with the statement, or in the way p5 has been calculated?

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

    $$$p^k[i]$$$ isn't calculated from $$$p^{k-1} [p^{k-1} [i]]$$$

    It is $$$p^k[i] =p[p^{k-1}[i]]$$$

    It was mentioned in the problem that multiplications like c=a*b turns out to be like c[i] = b[a[i]]

    So $$$p^k=p^{k-1}*p$$$ turns out to be $$$p[p^{k-1}[i]]$$$

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

      Clear now. Thank you very much.

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

      In Problem D, if t=1 , n=3 , p[]=[ 2, 3, 3 ] , c[]=[ 2, 1, 3 ]. As we already have an infinite cycle at p[3] of length 2. So output must be 1. But above code of pikmike is giving 3. So, please point out my mistake, if any.

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

        elements of the permutation are unique. It's mentioned in the problem "The second line contains n integers p1,p2,…,pn (1≤pi≤n, pi≠pj for i≠j) — the permutation p."

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

        the array p[] is a permutation of 1 to n , it can't have 2 3 3

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

I think this contest was prepared very well. Especially solutions of C and E were satisfying. Thanks to authors.

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

Can this editorial be linked to the contest? Thanks!

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

Why is the time complexity for problem B O(n + m), what is m as mentioned in the editorial? Shouldn't it be O(n^2), because k can be any value up to n.

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

    Yes, k can be any value up to N but. You didn't read the guaranteed carefully as there is a line told that.

    It's also guaranteed that the total number of kingdoms in lists over all test cases does not exceed 10^5.

    So if you run through all K. it's only up to 10^5 for all test cases. You can think M as the total number of kingdoms in lists.

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

      Oh! my mistake thank you for correcting me

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

PROBLEM A can someone explain the condition : if(n%2!=k%2) then "NO"

thanks

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

    Odd+Odd=Even.

    Even+Odd=Odd.

    Therefore you can only make N from sums of K odd number if and only if they have the same parity.

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

      Clear now. Thank you very much.

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

      As you said they should have same parity. But the condition says that the remainder must be equal to be YES this means n and k must have the same remainder by 2?

      Please can you explain it to me?

      Thanks in advance

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

For the problem G, there needs little effort to reduce the complexity from $$$O(L |S|)$$$ to $$$O(m L^2 + |S|)$$$. Who is interested can compare my two submissions 74205780 and 74200846.

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

    stO 叉姐 Orz, can you explain the details? thanks a lot!

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

      Divide the string $$$s$$$ with questions marks into $$$(m + 1)$$$ parts $$$p_0, p_1, \dots, p_m$$$. Essentially, we need $$$\mathrm{go}(u, p_i)$$$ for each node $$$u$$$ in the Aho-Corasick Automaton and its corresponding contribution. Direct computation leads to $$$O(L |S|)$$$ as the editorial says. However, if $$$p_i > L$$$, all $$$\mathrm{go}(u, p_i)$$$ agree on the value. Thus, we need only compute $$$\mathrm{go}(u, p_i)$$$ for one $$$u$$$.

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

        wow, thank you! I just realized I used the same technique on a contest I prepared last year(

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

        if $$$|p_i|>L$$$, all $$$\mathsf{go}(u,p_i)$$$ agree on the value.

        You mean if $$$|p_i| > L$$$ then the value gained by traversing the substring $$$p_i$$$ in the A-C automaton is the same regardless of the initial state? I cannot see why this is true. Please elaborate on this. Thanks!

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

          Let's elaborate a bit. Suppose that $$$p_i > L$$$ and $$$p_i = ab$$$ where $$$|a| = L$$$. We will see that $$$\mathrm{go}(u, a) = v$$$ is a constant regardless of the $$$u$$$. Thus, the contribution can be separated into two pieces: the one from $$$u$$$ to $$$v$$$, which can be computed in time $$$O(|L|^2)$$$, and the one starting from $$$v$$$, which can be done in time $$$O(|b|)$$$.

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

            Thank you every much, I think I understand it now. The idea is that if we think of a node $$$u$$$ of the AC automaton as the corresponding string, then $$$\mathsf{go}(u, p_i)$$$ will arrive at some suffix of the string $$$up_i$$$ and when $$$p_i$$$ is long enough, that suffix will be solely part of $$$p_i$$$. Correct me if I'm wrong.

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

The use of c both as a permutation and the colour function makes it confusing at times.

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

can anyone explain me how does we can simply apply down , up, left ,right, as normal. because in problem C they have different notatation if we want to change the position.

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

In Problem D, if t=1 , n=3 , p[]=[ 2, 3, 3 ] , c[]=[ 2, 1, 3 ]. As we already have an infinite cycle at p[3] of length 2. So output must be 1. But above code of pikmike is giving 3. So, please point out my mistake, if any.

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

    The p[] array must consist of disinct elements .
    But in your test case 2nd and 3rd elements are both 3 .

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

Who can help me explain F clearly! Thanks!

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

Can someone help me in the solution for problem D. I got the question but the editorial is hard to follow. Thanks in advance!

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

    The D question demands lot of observations and tricks . Read The editorial line by line just as hints and try them yourself . I assure that may help a lot

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

      I did it over and over, still not able to catch up. Can you help me by providing some relevant prerequisites or a dry run of the solution?

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

        Hi, not sure if you are still stuck, but comments like this and this are very helpful. I went from not even understanding the question to completely understanding and implementing D. Hope it helps!

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

I can't understand the DP defination of problem F. Would anyone explain for it clearly? Thanks.

  • »
    »
    7 months ago, # ^ |
    Rev. 11   Vote: I like it +27 Vote: I do not like it

    First note that we can calculate a result for each bit separately and multiply them all for the final answer. Iterate $$$s$$$ over $$$[0, k)$$$, and let $$$b_i$$$ represent the bit in position $$$s$$$ of $$$x_i$$$.

    We can now divide the conditions into what we'll call $$$1$$$-segments and $$$0$$$-segments in accordance to its $$$b_i$$$ for the current $$$s$$$.

    Note that most of our arrays and data structures we use should be indexed over $$$[0, n+1]$$$ (we'll see why in a moment). The $$$[l, r]$$$ in the conditions should remain 1-indexed.

    Now we do the precalculation step. We want two things from the precalculation:

    1. For each index, we want to know whether it is covered by a $$$1$$$-segment. This is a classic "union of segments" problem and can be done in many ways: pre-sorting and two pointers, removal from sorted sets, or even DSU

    2. For each index $$$i$$$, we want to know the maximum $$$l$$$ among all $$$0$$$-segments whose $$$r < i$$$. If you're stuck, see the spoiler for details on how to do this efficiently. We'll call these values $$$f_i$$$ in accordance with the editorial. (If no such segments exist for index $$$i$$$, $$$f_i = 0$$$.)

    Spoiler

    We can now perform the DP. $$$dp_i$$$ represents the number of arrays of length $$$i$$$ that end with a $$$0$$$, and all $$$0$$$-segments contained within it contain at least one $$$0$$$.

    $$$dp_0$$$ represents the empty array and therefore should be $$$1$$$.

    Now we iterate $$$i$$$ over $$$[1, n+1]$$$

    If $$$i$$$ is covered by a $$$1$$$-segment, $$$dp_i = 0$$$ as we can't place a $$$0$$$ in this position.

    Otherwise $$$\displaystyle dp_i = \sum_{j = f_i}^{i-1} dp_j$$$ because the last-seen zero cannot be in a position earlier than $$$f_i$$$. This can be calculated efficiently by maintaining a prefix sum over $$$dp$$$.

    The result for bit $$$s$$$ is equal to $$$dp_{n+1}$$$. This is because we can always fix a $$$0$$$ at the fictitious $$$n+1$$$-th index, and delete it to get a suitable array.

    Asymptotics $$$\tilde{O}(k(n + m))$$$ with a possible $$$\log$$$ factor somewhere depending on implementation. Bonus: Solve in strict $$$O(k(n + m))$$$.

    sample: 74254156 (uses a specialized DSU-like data structure for the union-of-segments problem)

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

      What about the segments which are neither in 0-segment nor in 1-segment?

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

        It's fine. Because you've already precalculated $$$f_i$$$, if there are no constraints on the index, $$$f$$$ would not increase and the summation will continue accumulating.

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

      Thank you so much!

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

      I'm finding it bit hard to understand why $$$dp_{i}=\sum_{j=f_{i}}^{i-1}dp_{j}$$$. Can you please explain.

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

        $$$dp_j$$$ counts the set of strings that are length $$$j$$$ and end with a zero. So for each of those strings, you are able to add ones until index $$$i-1$$$, and then add a zero to form part of $$$dp_i$$$'s set.

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

For D, I can see why it holds that on raising by power m it divides into gcd(m,L) cycles (L=lenth of original cycle) but why does it hold when m does not divide L? Can someone give intuition/mathematical reason for this? I can see that it holds but why?

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

    When we increase the power by say 2, we are traversing the original cycle by skipping 2 steps at a time. For example: for a cycle 1 -> 2 > 3 -> 4 -> 1, with k = 2, we would have 1 -> 3 -> 1 as the cycle if we take 1 as start. Now we would have gcd(k, L) unique such cycles, in this case 2 cycles (other one being 2 -> 4 -> 2).

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

    when gcd(m,L) = 1 L*x%m = 0 only when x == m,essentially you have to walk through every single element in the cycle until you return to c1 because all mutiples of L mod m should be distinct

    else assume x and y are integers < m and x>y then if Lx%m = Ly%m,then (x-y)L%m = 0 which is a contradiction since gcd(L,m) = 1 and x-y < m

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

I spent some time looking at D and wanted to improve upon the given solution with external resources.

  1. Notice that P is nothing more than a cyclic permutation. Lecture notes on Permutation Groups and Symmetric groups. Each permutation can be written in Disjoint cycle notation. Thus there exists cycles.

  2. let A = (a1 a2 a3 .. am) be a cycle. then A^k can be written in Disjoint cycle notation with gcd(k, m) cycles each of cycle length m / gcd(k, m). Proof

  3. So let us look at all cycles A = (a1 a2 ... am). We need to take a look at all subcycles of length x. This corresponds to every cycle when we raise A to k. since x = gcd(k, m) from 2, x | m. Thus we can skip a lot of values of x.

If a particular answer of x has the property that all colors in it are same then ans = min (ans, x).

Why min(ans, x) ans not min(ans, k)? 1. We don't know exact k that it would have been raised to. 2. Notice gcd(k1, m) == gcd(k2, m) => same cycle[properties of cyclic group] Thus x is the least value of k such that gcd(m, k) = x as x | m.

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

    in the editorial,it was stated that The for k1 and k2 such that GCD(k1,m)=GCD(k2,m) the produced cycles will have the same sets of vertices and differ only in the order of walking although this should seem intuitive given your second statement that let A = (a1 a2 a3 .. am) be a cycle. then A^k can be written in Disjoint cycle notation with gcd(k, m) cycles each of cycle length m / gcd(k, m) but is there a concrete way to prove it

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

      The best proof I found was from math stack exchange. But I can provide a quick intuition of why there are gcd(k, m) cycles. 1. A = (a1 a2 .. am-1 am) has |A| (order) = m. Then |A^k| = m / gcd(m, k). This is a property of cyclic groups, and the current group is <A>.

      1. when X is written as (x1 x2 ... xn) (y1, y1 .... ym), |X| is given as lcm(n, m)
      2. A = (a1 a2 .... am-1 am) can also be written as (a2 a3 .. am am-1 a1). So since we can reorder the elements like so, when we raise A to k let us look at the position of Ai and Aj. If Ai ends up in a cycle of length x and Aj ends up in a cycle y != x then we can just reorder A in a way that Aj ends up in a cycle of length x and Ai ends up in a cycle of length y. But both cycle notation should lead to same result thus x == y.
      3. 3 says that all cycles have equal length. We need lcm of all cycle lengths to be m / gcd(m, k). Thus each cycle should be m / gcd(m, k).
      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        um,i think you misunderstood my question,i understand why there should be gcd(k,m) disjoint cycles of m/gcd(m,k) length.i was asking about why for k1 and k2 such that GCD(k1,m)=GCD(k2,m) the produced cycles will have the same sets of vertices and differ only in the order of walking,why is this true and why cant there be two different cycles(different set of vertices) with the same starting point

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

          Oh sorry yeah i misunderstood you. It turns out that <A^k> = <A^gcd(m, k)>. Thus if Gcd (m, k1 == gcd(m, k2) then they result in the same subgroup. note <a> is the subgroup generated by a

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

            ah,thank you,i think i got it now

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

    Thank you soo much for these insights, I'm finally able to understand and also implemented this problem :D

»
7 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Wow,我想到这种方法了,但是把2nm当做2(n+m)了,It's a pity

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

Can anybody explain problem A.I couldn't understand the editorial.

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

    So basically , there are only 2 cases in which the output can be "No" , ones where the parity of n and k is different because odd number of odd numbers can only add upto an odd number and similarly for 2n odd numbers .

    And the second case where we get NO as a result will be when the sum of first k odd numbers exceeds n. Understand this as if the minimum of the k odd numbers (that is the first k odd numbers) add up to be more than k , then there is no way to choose k numbers such that there sum=n.

    example: 7 3 here ist 3 odd numbers , i.e 1+3+5 = 9 , so there is no way we can hava a solution for this case.

    Also it is important that the k odd numbers should be distinct.

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

Can someone please help with a detailed code for Q2.

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

can someone explain me how in A, that parity being equal and k^2<=n be the only two conditions we need to check?

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

    sum of odd numbers when their quantity is even leads to even no while when quantity is odd it leads to odd no. eg- 1+3=4(qty=2 and sum is even), 1+3+5=9(qty=3(odd) and sum is odd)

    sum of first k odd natural number is k*k. So min sum is k*k. n should always be greater than k*k

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

I am still not able to understand the implementation of problem E .Please someone explain me in a easier way.

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

In Q1327B can there be more than one ans?(for test case 2) eg- IMPROVED 1 1 or IMPROVED 2 1

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

For Problem D : Can someone explain this in statement in detail ? "Now, walking with step k we can note, that the initial cycle c split up on GCD(k,m) cycles of length m/GCD(k,m)"

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

    think an array which can be divided into x group of equal size of s. If we transition from first element in first group for s time, it will become first element of second group, similarly first element of group 2 will become first element of group 3 by transitioning it s times and so on. If all visited element have same color, it will be an infinite cycle. This is what we are doing at below line, finding one infinite cycle in editorial solution.

    for(int pos = s; pos + step < sz(cycle); pos += step)

    Now we will find all number which can divide our cycle size of equal group and traverse as above to find the answer.

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

In the editerial for problem D, "for k1 and k2 such that GCD(k1,m)=GCD(k2,m) the produced cycles will have the same sets of vertices and differ only in the order of walking", I can vaguely understand it, but who can prove it rigorously? why "the same sets of vertices"?

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

    Suppose, you have the cycle $$$c_0, c_1, \dots, c_{m-1}$$$. Since $$$p^k[c_i] = c_{(i + k) \mod m}$$$, then $$$c_i$$$ and $$$c_j$$$ will be on the same split up cycle iff $$$i + kx \equiv j \mod m$$$ or $$$i + kx - my = j$$$ or $$$j - i = kx - my$$$.

    There is a property that all solutions of $$$kx \pm my$$$ with an integer $$$x$$$ and $$$y$$$ is divisible by $$$GCD(k, m)$$$, so it means that $$$i - j$$$ is divisible by $$$GCD(k, m)$$$.

    Finally, since $$$GCD(k_1, m) = GCD(k_2, m)$$$ then it's obvious that the same pairs of indices will be on the same split up cycles.

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

Please help me with Problem E:

We choose remaining digits as 10(n-len-1)(in the first case), but if in case those remaining digits also contain a block of size len — doesn't it mean we count same blocks more than once(in 2nd case again)??

For example, if n = 7 len = 2, the numbers like 1121134 come in both 1st and 2nd case?
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    as you see, the numbers 1121134 has two blocks of length 2, which is exactly the sum of 1st and 2nd case.

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

Problem E: Why don't we count the same blocks a couple of times in the first case? When we multiply 10 * 9 * 10^(n — len — 1), there are some cases included when the right side is also a block with the same length, and then we count that twice by multiplying 2.

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

Can someone help me with a TLE on problem G? I'm struggling to determine if my time complexity is the problem or if I just need to reduce my constant factor. It looks like a lot of the other solutions are using bfs to compute the subproblems (I'm using recursion) but I'm not sure what the benefit of that approach is. Here's my submission 74512969.

edit: problem was that I was using LONG_MIN instead of LLONG_MIN...

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I am not sure if i am not understanding the question but i think for input

1

3

2 3 2

1 2 3

answer should be 2 but the solution provided gives answer 3. Plz can any one explain me where if i am wrong because i think 2 & 3 form a loop

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

can somebody tell me what's wrong with my approach for problem C? link :- https://codeforces.com/contest/1327/submission/74527919 thanks in advance!!

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

    Hi, In the solution for problem B, simply adding a prince to the princess list doesn't ensure if that prince was already in her list or not. Shouldn't we first check if the prince was actually present in her original list or not?

    Also, can you help me understand why for the 10th case in this 86899341 I am getting a wrong result? How is that answer not increasing the number of couples? @coder_pulkit_c

    Thanks a lot :)

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

can someone suggest me important topics i could read, so that i am able to solve problems like E during contest.

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

Can anyone plz explain howz the number of cycles is Size/gcd(size,k) in D

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

    Here is my analysis (had to read multiple comments and the editorial to arrive at this).

    Now ($$$p^k[c_i] = c_{(i+k)mod m}$$$) :

    this is similar to jumping k steps at a time. Now each sub-cycle will be produced by starting at i (for simplicity taking ($$$c_i$$$) as i), and then after jumping k steps for x no. of times we will reach back at i. This completes our sub-cycle i.e. ($$$i + kx \equiv i mod m$$$) where x as you can see is the no. of jumps taken to reach back at i, also is the length of this sub-cycle.

    Or, ($$$i + kx - my = i \implies kx = my$$$) for some integer y.

    Now to find the min. x such that above equation holds, you see k and m are fixed, so kx = my = lcm(k, m). And as we know lcm(k, m) = km/gcd(k, m) = km/g.

    Therefore, ($$$x = lcm(k, m)/k \implies x = km/kg \implies x = m/g$$$). Hence proved length, x of sub-cycle produced is size/gcd(size, k).

    Now to prove that no. of subcycle will be gcd(k, m):

    you can see that each sub-cycle will of equal size, starting with some i, j, ... , also each element has to be a part of exactly 1 such subcycle, thus product of no. of subcycles and size of each such subcycle must be 'm', hence the proof follows.

    For proof of second observation as per editorial, please refer adedalic comment.

    Hope this helps :)

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

      It helped me a lot to understand! Thank you!

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

[problem:[problem:1327B — Princesses and Princes]]

Timeout is coming in C++. Same code Test#6

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <algorithm> //max/min //lower_bound/upper_bound
#include <math.h> //ceil/floor

using namespace std;
///////////////////////////////////////////////////////////////////////

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    int T;
    cin >> T;
    for(int t=1;t<=T;t++) {
        int N;
        cin>>N;
        vector<vector<int>> arr;
        arr.resize(N);
        vector<int> marriedP(N);
        vector<int> marriedD(N);
        for(int i=0;i<N;i++) {
            marriedP[i] = 0;
            marriedD[i] = 0;
        }
        int k;
        int improve = 0;
        int a,b;
        for(int i=0;i<N;i++) {
            cin>>k;
            arr[i].resize(k);
            for(int j=0;j<k;j++) {
                cin>>arr[i][j];
                if(marriedD[i] == 0 && marriedP[arr[i][j]-1]==0) {
                    marriedP[arr[i][j]-1] = 1;
                    marriedD[i] = 1;
                }
            }
            if(improve == 0 && marriedD[i] == 0) {
                improve = 1;
                a = i;
            }
        }
        if(improve==1) {
            for(int j=0;j<N;j++) {
                if(marriedP[j]==0) {
                    b = j;
                    break;
                }
            }
        }
        if(improve==0) {
            cout<<"OPTIMAL"<<endl;
        } else {
            cout<<"IMPROVE"<<endl;
            cout<<a+1<<" "<<b+1<<endl;
        }
    }
    
}
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hay Ne0n25, problem C is a really nice problem. But I'm wondering what if the constrain 2*n*m would be lesser then that and it was asked to visit those positions in minimum move. Can you please tell how shall I approach or give a hint?

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

Someone help? In editorial for problem D (1327D). Let's consider one cycle $$$c_1,c_2,…,c_m$$$. Why in permutation $$$p$$$ we have $$$p[c_i] = c_{(i + 1) \mod m}$$$? Example, p={7 4 5 6 1 8 3 2} c={5 3 6 4 7 5 8 4}. Cycle: 7 5 1 3 and its colors 5 6 7 8. Now $$$p[c_1] = 1$$$, $$$c_{2 \mod 4} = 6$$$. So $$$1 \neq 6$$$.

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

    It's just an abuse of notation. The letter $$$c$$$ here is used only to refer to the elements of the cycle. Hence, $$$c_i$$$ would be the $$$i-th$$$ element of the cycle (and not the value of the $$$i-th$$$ colour).

    Moreover, I doubt that you've written the cycle correctly. It should have been $$$7 -> 3 -> 5 -> 1 -> 7 ....$$$

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

In the tutorial of problem G, could someone explain why the dp can be done in O(K*L*2^K) instead of O(L*K^2*2^K)? We need to iterate the character we take in this '?', so there is an additional K in the complexity.

UPD: maybe the amount of ? (14) is ignored as a constant. The complexity seems too high to get AC in 4secs.

UPD again: I had just got aware that the number of statu is O(L*2^K), so this works.

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

can you please explain problem C.

I didnt get it. here UP means (x-1, y) then why we shouldnt iterate the loop through column m? and whole board is(n*(m-1)) but how??

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

Also for question "Sum of Odd Integers" the answer is "YES" if (n-k)/2 can be distributed among k distinct numbers, else the answer is "NO" (not able to figure out exact formula -_-)

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

I found it difficult to understand the editorial and the solution for F. I spent a lot of time to understand it. Therefore I wrote a well commented solution. Hope it helps.

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

A should have been explained more clearly for beginners

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

Can someone please tell me what's wrong here ?
I wrote the exact same code as written in solution, But it appears to be wrong.

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

For Problem C I used this logic - For every operation (L,U,D,R) I calculated a cost function which is sum of the number of steps to reach the target for each vertex from new position(on applying a particular operation) ie abs(new position of that vertex — target position).

I greedily choose the operation who's cost value is minimum and move all vertices in that way. On applying operation if any of vertex reach their corresponding target position I mark them visited and next time I don't include their contribution in calculating cost function.

Using this approach I got WA in one of test case. Please help if there is something wrong with my logic

coder_pulkit_c 79141565

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

Nice one.

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

In Problem C- Game of chips according to the given tutorial and solution

i am not able to understand how all chips got to first cell instead only the chip in the last column and first row reached the first cell because while moving towards first cell we just took a path which is covering last column and first row

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

    It says in the problem that all the chips shift together in a single move. So when L is applied once, it shifts all chips to the left by 1. So if we apply L operation m-1 times, we shift all chips to the leftmost column. If we we apply U operation n-1 times, we shift all chips to the topmost row. So shifting all the chips to the leftmost column and then shifting all the chips to the topmost row results in all the chips being shifted to (1,1). Also if a chip is already against a wall, it stays there. Let's say a chip was initially in (4, 1). Then all the L operations will just be ignored on this chip because it is in the leftmost column.

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

In B, why this test case is Optimal?

Test Case

Can't we add 5 to the 4th daughter? (What I misunderstood?)

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

The solution to C was much simpler than whatever I was trying to do, orz