AquaMoon's blog

By AquaMoon, 14 months ago, In English

Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.

During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.

In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) Invitation to TheForces Round #22 (Interesting-Forces)

1864A-Increasing and Decreasing

Idea : wuhudsm

Tutorial
solution

1864B-Swap and Reverse

Idea : Amir_Parsa, chromate00

Tutorial
solution
bonus

1864C-Divisor Chain

Idea : wuhudsm

Tutorial
solution

1864D-Matrix Cascade

Idea : AquaMoon

Tutorial
solution

1864E-Guess Game

Idea : wuhudsm

Tutorial
solution

1864F-Exotic Queries

Idea : ODT, AquaMoon

Hint
Tutorial
solution

1864G-Magic Square

Idea : AquaMoon

Hint1
Hint2
Hint3
Tutorial
solution

1864H-Asterism Stream

Idea : adventofcode Solution: Psychotic_D, amenotiomoi

Tutorial
solution

1864I-Future Dominators

Idea : Psychotic_D, amenotiomoi

Tutorial
solution

Feel free to ask if you have any questions! (*╹▽╹*)

  • Vote: I like it
  • +201
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any mathematical solution for A ?

For example : I tried to figure out whether the gap=y-x-1 is >= required_gap. Where required_gap = ((n-2)*(n-1))/2 ( n-2 because nth and 1st element are already set ) I tried this way but failed pretest 2.

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

I have no idea what the editorial is talking about for H. I thought it was a "berlekamp massey go brrrr" problem.

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

    Can you elaborate on your solution?

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

      Short version:

      By linearity of expected value, we can sum up the probability of reaching each state with value < N and that's the answer

      dp[i][j] = probability of reaching a state that sum operations summed up to at most j and there were exactly i operations of multiply by 2. In other words, exactly i multiply by 2 operations and the number is <= 2^i + j.

      dp[i][j] = (dp[i][j-2^i] + dp[i-1][j]) / 2

      The answer is sum dp[i][N-2^i] for every i.

      Define F_i[n] = dp[i][N % (2^i) + n * 2^i]. F_0 is a recurrence (F_0[n] = F_0[n-1] / 2 + 1).

      F_i[n] = (F_i[n-1] + dp[i-1][N % (2^i) + n * 2^i]) / 2 = (F_i[n-1] + F_(i-1)[a_i + 2 * n]) / 2 for some a_i that is 1 or 0, because N % 2^i is either N % 2^(i-1) or N % 2^(i-1) + 2^(i-1).

      Hope that the following works:

      R'[n] = R[a + b * n] for constant a, b. If R is a recurrence of degree D, R' is also a recurrence of degree D.

      R'[n] = R'[n-1] + R[n]. If R is a recurrence of degree D, R' is a recurrence of degree D+1.

      it shouldn't be hard to prove that. I think I'm able to prove it using generating functions.

      then the solution is: compute the first 2*i values of F_i using the first 4*i values of F_(i-1) then interpolate the recurrence using berlekamp massey.

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

Video tutorial for problems A&B&C explained: https://youtu.be/y5QoCUF7hpQ IN ENGLISH Thought would be useful

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

fast editorial. very thank you.

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

Another way to understand problem C :

If we are faced with number $$$2n$$$, take a sequence of operations that takes $$$n$$$ to $$$1$$$, multiply every factor by $$$2$$$ so that you get a sequence that takes $$$2n$$$ to $$$2$$$, then decrease by $$$1$$$. If we have number $$$2n + 1$$$, just decrease by $$$1$$$.

We can see that no divisor will appear more than twice because of the multiplications by $$$2$$$ that make them bigger as it goes.

It in fact creates the same sequence as the one in the editorial, but that's how I found it anyway

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

In problem B, is there a proof that after some series of these 2 transformations any two adjacent elements will be swapped?

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

    Notice that every element with the same indices modulo $$$2$$$ are already "congruent" (i.e. can be swapped over freely). Now, lets say the original string was $$$abcdefghij$$$. If we apply the same operations with the editorial, the string becomes $$$fedcbaghij$$$, and then $$$fgabcdehij$$$. See how $$$f$$$ originally had an even index, but now an odd index. Now after we swap things over, we can make $$$abcdegfhij$$$, only leaving this pair of $$$f$$$ and $$$g$$$ swapped. We can generalize this to swap any two adjacent indices. The rest of the proof is left for the reader.

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

Really cool round, enjoyed every problem C-F! Thank you very much authors!

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

Why TLE for problem D?

Submission

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

    It gets AC in 64-bit C++, or if you add the fast-IO line which is unfortunate :/. See 220609340, you should keep that line in pretty much all submissions. (ios_base::sync_with_stdio(false); cin.tie(NULL);)

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

Anyone solving problem D with $$$O(n^2logn)$$$ segtree solution? Got TLE but it should pass n = 3000... Perhaps my segtree template sucks.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Bro i got tle during contest . I realises that i can drop the log factor in my code now.
    Now i get accepted.
    MY approach is playing with diagonals.
      x-i > abs(y-j)
      let do what if we have (x,y) as point and we see points that can update his value
      solving this inequality in reverse order
      x+y < i+j
      x-y > i-j     As we see these are some diagonals
    
      Interesting fact: if we get the sum of elements on which we apply opertion before
                        (by some how) we can check if its value is 1 or 0. if 1 we apply here
     Curr = (x,y)
    : to get the sum, I see that Total = sum [ val(i+j) >= (x+y) ] - sum [ val(i-j+n-1) < (x-y+n-1)]
      Its like range update with point query
      n^2 logn  (TLE)
      we know that the thing that The Total above want doesn't depend upon current row
      we can use difference array type things and get the answer
      n^2 Accepted :)
    
  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can check my sumbission 220585884 It passed all the tests however very close to TLE. At first, I thought it should work without any problems, but now I understand I'm lucky it didn't fail

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

    Removing the lazy part of this template is enough to make it work 220620036 (this works because you are only adding to ranges of length 1, so no actual lazy propagation takes place).

    It is also storing / updating node lengths everywhere, which is also not needed, and removing it would probably speed it up even further.

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

It's was a great round! Thanks for editorial. Problem C was pretty nice

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

I got TLE on test 49 in F(220571360), I can pass in less than 1000ms by using fread(220608103). But test 48 need to read more things than test 49. What's the reason?

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

    So do I. Should I stop using cin/cout from now on?

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

    I got the same TLE due to using std::sort. It might be the first time I'm seeing a NlogN intended solution not allowing std::sort.

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

      I don't think your TLE is due to std::sort. Your code passes with a small change (seems to be the same thing as here).

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

        using GNU C++14 can pass in 1560ms(220632696), using GNU C++20 (64) got TLE in 4 seconds(220632734)?

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

          bruh sounds so weird

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

          When im upsolving problems i think that cpp20 is much faster that cpp14? See my submissions on 1265E ^^

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

    Hay, I also met the same issue. And I also tested different IO methods and different implementations of segment tree. The result is on this blog. I don't know the reason, but you could have a look if you are interested.

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

Can someone share their O(sqrt(x)) solution for problem C? I had no clue that bit manipulation was to be used here.

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

Why does this submission for B fails,i was doin, exactly same as of tutorial,

https://codeforces.net/contest/1864/submission/220591195

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

    if(n & 1) u print new line

    but u don't print new line in other case, where next query solution merges with that query

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

    If $$$k$$$ is odd and $$$n$$$ is even, you don't print a newline character at the end:

    Input:
    2
    2 1
    aa
    2 1
    aa
    
    Correct Output:
    aa
    aa
    
    Your Output:
    aaaa
    
»
14 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Does anything change in problem B with n=k? I couldn't think of a difference

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    Yes, it changes a bit
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, you're right. I should've tried to observe with a small example.

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

Maybe my solution for D using bitsets would be easier to understand for some people

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

I'm not really getting the solution to D. I don't understand why prefix sums are mentioned and how they are used. The code did not clarify anything, it just confused me more. It would be very helpful if someone could give a more detailed explanation.

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

A more understandable solution to H, and didn't require too much knowledge or math.

First, we can consider subtracting $$$1$$$ from $$$n$$$ or dividing $$$n$$$ by $$$2$$$, and compute the expected step to make $$$n$$$ be $$$0$$$. We can build a recurrence $$$f(n) = 1 + \frac{1}{2} (f(n - 1) + f(\lfloor n/ 2 \rfloor))$$$. And the answer to the original problem is $$$f(n - 1)$$$.

It seems it's hard to compute $$$f(n)$$$ by some matrix or the linear recurrence trick. But here is the magic, you can maintain $$$b_{n} = [f(n), f(\lfloor n/2 \rfloor), f(\lfloor n/4 \rfloor), \dots, 1]^T$$$. So we can build the transition from $$$b_{n-1}$$$ to $$$b_n$$$. And it's not hard to see, that the transition matrix only depends on the number of trailing zeros of $$$n$$$ in its binary representation. The answer is $$$\prod_{i=1}^n M_{ctz(i)}$$$.

We can precompute $$$\prod_{i=1}^{2^k} M_{ctz(i)}$$$ in $$$O(\log^4 n)$$$, and solve each query in $$$O(\log^3 n)$$$.

Submission: 220569504

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

    Wow, very cool! Thank you for sharing.

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

    I think my solution is very similar to yours, though I do not 100% understand your sol. My solution represents the dp like this: $$$f(x + 1) = 1 + \frac{1}{2}(f(x) + f(\left \lceil{\frac{x}{2}}\right \rceil)$$$ (exactly the same as yours essentially) with a restriction of I will assume that $$$x \equiv 0 \;(\bmod\; 2)$$$. Then I calculate a new function $$$f(x + 2) = 1 + \frac{1}{2}(f(x + 1) + f(\left \lceil{\frac{x + 1}{2}}\right \rceil).$$$ Then I will assume that $$$x \equiv 0 \;(\bmod\; 4)$$$ and rewrite the formula like this: $$$f(x + 2) = 1 + \frac{1}{2}(f(x + 1) + f(\left \lceil{\frac{x}{2}}\right \rceil + 1).$$$ Note that now both of the recurrences can be substituted with the first function, and when all simplified it leads to $$$f(x + 2) = 2 + \frac{1}{4}(f(\left \lceil{\frac{x}{4}}\right \rceil) + 2f(\left \lceil{\frac{x}{2}}\right \rceil) + f(x))$$$. Then again I will assume that $$$x \equiv 0 \;(\bmod\; 8)$$$ and re-expand the formula and repeat. This leads to log n different functions that can jump from $$$f(x) \rightarrow f(x + 2^{k})$$$ when $$$x \equiv 0 \;(\bmod\; 2^{k})$$$ (given that you know $$$f(\left \lceil{\frac{x}{2^{i}}}\right \rceil)$$$ for all i <= k).
    Submission: 220629661
    It really took me a long time to wrap my head around the pattern between expansion and how to code it up but I think it is quite beautiful how apply somewhat arbitrary modulo restrictions onto the equation allows for kind of a "binary exponentiation" trick.

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

    why your f(n) = 1 + (1/2) * (f(n — 1) + f(n / 2)) ? why do not you consider the case which n is a add number ?

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

      He shifted all the numbers down by one, so the floor division actually becomes ceil diving.

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

    The method of undetermined coefficients (待定系数法) also works: https://codeforces.net/blog/entry/119850

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

    And answer to the original problem is $$$f(n-1)$$$

    Why is $$$f(n-1)$$$ equal to the answer? I still can't prove this after few months :(

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

Problem C is Preety Good. I didn't get any approach during contest I solved A, not able to B , C then i got D :) Though rank is very bad but solved D :)

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

I have another solution to E

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

How do we sort ACBDE TO ABCDE with k as 4?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • ACBDE -> AEDBC reverse CBDE to EDBC
    • AEDBC -> AECBD swap C and D
    • AECBD -> BCEAD reverse AECB to BCEA
    • BCEAD -> DCBAE swap D and E, and swap B and D
    • DCBAE -> ABCDE reverse DCBA to ABCD
»
14 months ago, # |
Rev. 13   Vote: I like it +6 Vote: I do not like it

An alternative solution of 1864E - Guess Game

From the very beginning let us sort our sequence $$$s$$$.

For two integers $$$a$$$ and $$$b$$$ denote by $$$f(a, b)$$$ the number of $$$1$$$-s in the largest common prefix of $$$a$$$ and $$$b$$$. Then the answer is

$$$ans = \sum_{i, j} \bigl(f(s_i, s_j) + [s_i < s_j]\bigr).$$$

Denote

$$$a_i = f(s_i, s_{i+1}).$$$

The key step is to note that since $s$ is sorted, then for $$$i < j$$$ we have

$$$f(s_i, s_j) = \min_{i\leq k<j}f(s_k, s_{k+1}) = \min_{i\leq k < j} a_k.$$$

Therefore, we obtain

$$$ans = \sum_{i, j} \bigl(f(s_i, s_j) + [s_i < s_j]\bigr) = 2 \sum_{i < j} f(s_i, s_j) + \sum_i f(s_i, s_i) + \sum_{i < j} [s_i \neq s_j] = $$$
$$$ = 2 \sum_{i < j} (\min_{i\leq k < j} a_k) + \sum_i f(s_i, s_i) + \sum_{i < j} [s_i \neq s_j].$$$

We can compute the sum of minimums of all subsegments of $a$ with $$$O(n)$$$ time complexity (for each element $$$a_i$$$ we should just find the nearest elements from left and right that are less then $$$a_i$$$). The both remaining terms are obviously also linear.

Code: 220611319

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

I solved D using the data structures. Let's consider that we have already found all the cells that will have the value $$$1$$$ and will have row index smaller than $$$x$$$. Let's denote the number of that cells as $$$currentCount$$$. Now, we want to find all the cells equal to $$$1$$$ in the row $$$x$$$.

Let's consider the cell $$$(x, y)$$$, and understand which cells can force the cell $$$(x, y)$$$ to flip its value. The value in the cell $$$(x, y)$$$ will be equal to the initial value in the cell $$$(x, y)$$$ plus the number of cells $$$(i, j)$$$ (mod 2) satisfying the following condition:

  1. $$$i < x$$$
  2. $$$x - i \geq |y - j|$$$

For the second condition, we can note that the equation is met either for $$$x - i \geq y - j$$$ or for $$$x - i \geq j - y$$$, since we know that $$$x - i > 0$$$ and $$$min(y - j, j - y) \leq 0$$$. So we need to find the number of cells, for which both equations are met:

  1. $$$x - i \geq y - j$$$, we can transform into this $$$x - y \geq i - j$$$
  2. $$$x - i \geq j - y$$$, we can transform into this $$$x + y \geq i + j$$$

So we can keep two Fenwick trees, and for each cell in the first Fenwick tree add $$$1$$$ in position $$$i - j$$$ and for the second one in position $$$i + j$$$.

Now, the new value for the position $$$(x, y)$$$ will be equal to the following:

$$$ initialValue[x][y] + get1(x - y) + get2(x + y) - currentCount (mod 2) $$$

where $$$get1(x)$$$ is equal to the sum of values in the first Fenwick tree, for which the indices are smaller than or equal to $$$x$$$. $$$get2(x)$$$ is the same for the second Fenwick tree.

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

    Yaa I do the same. You can still improve it like instead of 4 values in the expression use diagonals to get the value.I do it this way. By seeing as diagonal we remain with just 2 values

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

    Why should we subtract currentCount?

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

      Because for each cell we may count it twice, and we guarantee know that we count each cell at least once. Our goal is to calculate only the cells for which both equations are met, because of it we subtract $$$currentCount$$$.

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

        Shouldn't currentCount count the answer so far above the current row, which may contain flipped cells not affecting cell (x, y)? Why remove cells not even flipping current one?

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

          Because for each cell we know that at least one of these equations is true:

          • $$$x - i \geq y - j$$$
          • $$$x - i \geq j - y$$$

          $$$x - i$$$ is always greater than 0, while the minimum of $$$y - j$$$ and $$$j - y$$$ is always smaller than or equal to 0.

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

            Oh, got it now, that's smart, thanks for the explanation

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

Tutorial of F: Consider all adjacent equal pairs $$$(l, r)$$$, and $$$m$$$ is the minimum element between $$$(l, r)$$$.

$$$m$$$ should be the maximum element between $$$(l, r)$$$ satisfying $$$m < a_l$$$

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

    That confused me as well

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

    Sorry for the mistake! Fixed. Thank you (〃'▽'〃)o

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

      It seems like you didn't fully fix it. Now the tutorial says:

      ... and $$$m$$$ is the maximum element between $$$(l, r)$$$

      You changed minimum to maximum, but didn't add the constraint $$$m < a_l$$$

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

        Oh thank you! Fixed (〃•ω‹〃)

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

An O(nlog(max(ai)) solution for E, without tries.

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

shouldn't 30*N*log(N) pass the time limit? can someone check the solution

for prefixes i am converting them to number and storing in map

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

    I didn't read the code too carefully but you can try to check whether mp[x] exists before doing operations like += mp[x]. This prevents the map from creating extra elements. I also had TLE with map and this helped.

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

The word "graph" appears only once in this tutorial, for 9 problem

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

How can I "Reduce $$$x$$$ to $$$2L$$$." in problem C?

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

    for some x, say 19 whose binary representation is 10011 = 2^4 + 2^1 + 2^0. You can see that 2^1 divide 2^4, 2^0 divide 2^4, 2^0 divide 2^4. So the answer is you just minus the rightmost bit to x, in this case, is 2^0 and 2^1 until x has only one bit in binary representation.

    P/S: Sorry for my bad English. Hope you understand this explanation

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

In F,

which can be easily calculated with a segment tree and sweeping lines.

Can someone explain how sweeping lines are used here? A link would also be appreciated.

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

    I think my solution implements that 220623962. sweepline used for dectime.

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

    The first part of the solution is finding $$$m$$$ (the maximum value in $$$(l, r)$$$ that is less than $$$a_l = a_r$$$) for all adjacent equal pairs $$$(a_l, a_r)$$$. I did this using a segment tree and stored the pairs $$$(m, a_l)$$$. Now, you need to count the number of pairs that satisfy $$$m < L \leq a_l = a_r \leq R$$$ for each query.

    Sort the queries by increasing the left endpoint and also sort the pairs found earlier. Now, you can do sweepline and add the values of $$$a_l = a_r$$$ to an ordered set once $$$m$$$ is less than the current query's $$$l$$$. The answer for each query is the position of the upper bound of $$$r$$$ in the set.

    220616946 sorry if the code is a bit messy.

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

      I think I see it, thank you.

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

Another implement for D whose time complexity is O(n^2) but only O(n) space 220627524. The logic in this code may cause you confused, in this case, ask me(and vote)

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

    O(n) space? It takes O(n^2) memory just to store the matrix lol.

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

      Sorry for my mistake. I had to fix it and now this code uses only 156KB of memory 220627524

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

    Why we need to store the minus and the add in different arrays. Should that not be possible using a single prefix sum array like what I have done in this solution. It is giving WA but I am not able to understand why it is wrong. Can you please help me?

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

      I don't know how to explain this clearly. But the key is the minus and the add extend in a different direction

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

    Hey, can you explain your solution? It really would be helpful. Thanks

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

Problem F is somewhat similar to this: http://www.usaco.org/index.php?page=viewproblem2&cpid=1116 (It is the same problem but [l, r] matters on position rather than value. The basic idea (incrementing R and maintaining L in a fenwick tree / segment tree) persists in this problem too which I find to be pretty cool (The only addition is that you need to use a min segment tree to determine the ranges to add).

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

problem i should not exist

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

Feedback on the problems:

A and B: Fine easy problems. Not especially interesting, but not too bad (and quick enough that I was able to move on to the more exciting problems without too much delay).

C: Good easy problem. In some sense, the observation to use powers of two wasn't especially motivated, but for problems like this I often find it helpful to try to reduce the problem to some special case I know how to handle easily, so in that sense reducing $$$n$$$ to the next lower power of two felt like a reasonable thing to do.

D: Not terrible, but not my favorite problem ever. The idea to go top to bottom and flip cells that needed to be flipped along the way was fairly intuitive, and so it felt like most of the task was just working out details.

E: Good problem. I always enjoy this kind of logic puzzle, and I found both solving the problem and implementing the solution to be fairly satisfying.

F: Nice DS problem. The idea is both well-motivated and elegant, and all in all the implementation isn't too bad.

G: I enjoyed this problem very much, with the reservation that I think the statement was very contrived. It felt like the conditions in the problem basically came from having the solution in mind and trying to stretch the setting of the problem to fit it. Once I parsed the task, though, I really enjoyed the process of working on it (even though I wasted time in contest implementing a completely incorrect idea, then failed to debug my correct solution before the end of the round :p). It was very satisfying to gradually understand the setup of the problem better until I was finally able to make the observations necessary to solve the problem.

H: Decent problem. The setup is nice, but I wasn't a huge fan of the main observation (realizing that the relevant sequence can be expressed as sums of geometric sequences) because it didn't feel like I was unlocking some deep structure of the problem--instead, it felt as though I was doing the bare minimum to get the problem to fit into some high-powered technology (e.g. Berlekamp-Massey as other commenters have noticed; I was able to use Gauss-Jordan elimination to achieve essentially equivalent effect).

I haven't paid close attention to the preparation (e.g. I didn't check to see how many FSTs there were), and there was obviously an issue with the original test data in D, but overall I enjoyed the problems (especially EFG) and the round as a whole (despite performing below my standards and taking a substantial rating loss). Thanks to the authors!

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

If only the constraint for k in C was 64, I would've done it faster. Anyways, nice problems!

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

Can someone explain me D?

How are we achieving the required conditions? And it is my request to authors to please be consistent. It is easier to understand the code when it is based on tutorial.

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

    Let me explain a bit informally.

    We greedily look from above, inverting every cell with $$$1$$$ by using the operation right on that cell. This is because, if we do not use the operation on this cell, we cannot affect this cell at all afterwards, therefore we must use the operation on this cell.

    Now for how we will simulate the operations. Try rotating the matrix by $$$45$$$ degrees, and now the range of the operations will be a rectangle (though clipped out due to the borders), which is a very good situation to use a 2D prefix sum on. This should help you to understand the rest of the solution.

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

Great contest!~ qwq i love the problem D and i think the expectation problem E is also great. by the way congratulate to le0n for getting to grandmaster~

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

I have a different solution for D. Suppose I am at (x,y) and I want to check the parity of the number of cells before it which have affected this cell. Observe that, if a cell "covers" (x-1, y) (a cell covers a cell (a,b) if the diagonal lines coming out of it enclose (a,b)), then it also covers (x,y). Now, what are those points which cover only (x,y) but do not cover (x-1,y)? They are precisely those whose right diagonal (line with slope -1) passes through (x-1,y-1) and (x,y), and those whose left diagonal (line with slope 1) passes through (x-1, y+1) and (x,y). So, we need to store and do the following updates: For the previous row, store how many times (x-1, y) was operated upon, add its parity, and also add the parity of the number of operated cells which are diagonal to (x,y), which can be stored in a map using the fact that the sum/difference of the indices on the diagonals remains constant. https://codeforces.net/contest/1864/submission/220595343

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

I loved problem D proposed by AquaMoon and obviously the problem H proposed by you buddy amenotiomoi, and the Editorial justifies it <3

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

    I am so delighted that you love my problem!~o(〃'▽'〃)o

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

      Its obvious for me to like ヽ(´▽`)ノ <3

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

can anyone tell me this why https://codeforces.net/contest/1864/submission/220617780 solution of b is giving time complexity?

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

I was having fun solving those problems. Enjoyable round.

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

I thought about B's bonus and came out with a solution:

Solve the problem with $$$k=3$$$. Then flip the string. Solve the problem again. Then find the minimum among the two.

If $$$n\le 2$$$, then you can just sort the string.

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

how tf can people have negative rating when in this contest i didn't solve a single problem but got +112 and got to +875 ?

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

By mistake, I solved F for index range queries, instead of value range. Does anyone have link to that kind of a problem ?

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

i know how D works but i dont understand the prefix sum part, i have been tried for many hours and i couldn't figure it out, please give me some help :(

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

    A 1 in the current line can result in 111 in the next line, and 11111 in the line after next. Since these number of 1s are O(n), we can try to reduce it to O(1) by using prefix sums.

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

      i understood the 11111 part, but struggling with O(1) prefix sum update :(, ill try my best to figure it out, thanks for paying attention

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

F Why the maximum element between (l,r) and max<L (I guess it's value L) can counted

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

in problem B what is the proof that with even K it is always possible to sort the elements in order? can any one help me with that...

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

    Swap $$$(s_{i}, s_{i+2})$$$ means we can sort all the chars in odd and even positions. If $$$k$$$ is even we can change the parity of any char we want (i.e. from odd to even and from even to odd) thus we can sort all string.

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

      but why does size of k does not matter suppose if n=6 and k=4 then how can we sort them

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

        I was trying explaining it by myself, but editorial is better. In the first pic the red is what have changed, blue is what remaining the same. So we can just swap the modulo 2 of two adj. indexes we want, and with swap $$$(s_{i}, s_{i+2})$$$ we can place any chars we want. For you i made the same with $$$n = 6$$$ and $$$k = 4$$$.

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

I understand how to prepare and utilize 2D prefix sums for range queries, as well as how to prepare and utilize 1D difference arrays for range updates. However, Problem D here seems to require 2D difference arrays, which I haven't quite figured out yet, and the editorial seems to be rather vague. Can anyone please provide any resources to learn about 2D difference arrays and/or elaborate on the details for it?

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

    Well, 2D prefix sums and 2D difference arrays are essentially the exact same. Let's say you add 1 to p[x][y]. When computing the prefix sum of p, you would have added 1 to all a[i][j] where i >= x and j >= y. Using this in a similar method to how 2d prefix sums allows you to do rectangular updates.
    Example:
    p[0][0]++;
    p[2][0]--;
    p[2][2]++;
    p[0][2]--;
    if you compute the prefix sum of p, you will end up with
    1 1 0
    1 1 0
    0 0 0
    (top-left is (0, 0))

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

Bonus for F: try to solve it as if it were an interactive problem, i.e. you must answer a query in order to read the next one.

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

Can someone suggest some more problems like E. I found the use of Trie to calculate the total number of turns very unintuitive.

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

I have another solution for problem E without tries:

Consider p/q — expected value. Let's sort an array. Taking s[i] as one of the element in the game we can calculate value added to p. We know that in sorted array going from the beginning the end-game bit (XOR == 1) is moving right. So, let's brute force a position of end-game bit from the most significant one. Consider _b as bit value of s[i]. We can easily precompute how many steps we have to do before reaching this bit or even do it greedily because common prefix of two numbers is getting bigger. As we don't want to have collisions and our left bound is going right we want to know how many numbers in [l,i) have (_b^1) value in the bit. Let's make prefix sums! pref[val][bit][i] (val — {0, 1}, bit — {0...31}) And after calculating update left bound using binary search (just make pos[val][bit] and push all required numbers positions). Time complexity — O(32*NlogN)

Submission 221065798

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

Can anyone help me in getting error in this submission for Problem E, it is failing on testcase 6.

I solved it using tries..

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

Hi, I submitted my solution to D in Java 8, it's giving TLE on testcase 8. But, when I submit the code in C++ using the same logic which I used in my Java solution, it's giving AC. Any insights on how can I pass it in Java ?

Java Solution

C++ solution

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

For D, Similar problem in 1D array Restaurant Customers

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

Problem C fails for the n=15 according to editorial the answer is 7 - 15 14 12 8 4 2 1

but the min answer is 6 ie 6 — 15 10 5 4 2 1

Then what about this??

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

    In this problem you don't need to minimize the number of operations.

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

the most simple solution to C: https://codeforces.net/contest/1864/submission/244224068

Just think backwards: go from 1 to n, add 2^k every iteration until n is reached, 2^k is such that 2^k + cur < n and 2^k <= cur. In words, reach closest 2^l < n, then go to n from this 2^l.

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

include

include<bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp> // Common file

include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;

typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

//#define int long long

using ll = long long; int MOD = 1e9+7, INF = 1e9+1;

//---------------------------------------------------------------------------------------------------------------------------// ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;} ll mminvprime(ll a, ll b) {return expo(a, b — 2, b);} ll mod_add(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} ll mod_mul(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} ll mod_sub(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;} ll mod_div(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} //only for prime m //--------------------------------------------------------------------------------------------------------------------------//

int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } vector findFactors(int n) { vector factors; for (int i = 1; i <= n; ++i) { if (n % i == 0) { factors.push_back(i); } } return factors; } int ceil_f(int b,int a) {return(b+a-1)/a;} void solve() { int n;

cin>>n;

vector<string>v(n);

for(int i=0;i<n;i++) cin>>v[i];

vector<vector<int>>l(n+1,vector<int>(n+1,0));
vector<vector<int>>r(n+1,vector<int>(n+1,0));
int cnt=0;
for(int i=0;i<n;i++)
{  
    vector<int>p(n+1);
    p[0]=l[i][0];
    for(int j=1;j<n;j++)
    {
        p[j]=p[j-1]^l[i][j]^r[i][j-1];
    }
    for(int j=0;j<n;j++) cout<<p[j]<<" ";
    cout<<endl;
    for(int j=0;j<n;j++)
    {
        cnt+=p[j]^(v[i][j]-'0');
        if(p[j]^(v[i][j]-'0')) {l[i][j]=1;r[i][j]=1;}
    }
    //updating l
    for(int j=0;j<n;j++) if(l[i][j]==1) l[i+1][max(j-1,0)]=1;
    //Updating r
    for(int j=0;j<n;j++) if(r[i][j]==1) r[i+1][min(n-1,j+1)]=1; 
}
cout<<cnt<<endl;

} int32_t main() { int tt; cin>>tt; while(tt--) { solve(); } } please someone help in my solution Problem D please please please please please

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

I have a solution of problem $$$D$$$ which exploites the properties of connection between pascal triangle and diagonal in the matrix ( sounds like you need to have heavy knowledge but no just simple observations) submission

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

    could u please explain your approach

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

      consider a row as an array and if I give you data on which subarrays inversion happen how do you calculate whether inversion happens in particular index / column using prefix sum?

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

        yes I think I get that part.

        The idea is to to first create markings(+1 at start of subarray and -1 after it ends) and then create a prefix array based on the marking of subarrays.

        But In this problem, how do you get the markings on ith row

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

          in a cell of a row has a count of marking +1 = the count of inverted cells in the diagonal to the right from it

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

My solution for problem D

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

Was there any trick for question B i was not able to find the pattern by myself or any suggestions??