Tlatoani's blog

By Tlatoani, 13 months ago, In English

We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)

We have to apologize to antontrygubO_o a bit here -- the rejection count mentioned in the editorial for Codeforces Round #655 (Div. 2) actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:

Rejection Counts

Without further ado, here are the tutorials for each of the problems:

Tutorial is loading...
Solution (Kotlin) by golions
Solution (Java) by MagentaCobra
Solution (C++) by hugopm

Idea: hu_tao and qlf9

Preparation: hu_tao

Tutorial is loading...
Solution (Kotlin) by Tlatoani
Solution (Java) by MagentaCobra
Solution (C++) by tfg

Idea: hu_tao

Preparation: hu_tao

Tutorial is loading...
Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by tfg

Idea: qlf9

Preparation: qlf9

Tutorial is loading...
Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Ari

Idea: Tlatoani

Preparation: Tlatoani

Tutorial is loading...
Solution (Kotlin) by Tlatoani
Solution (Java) by golions
Solution (C++) by hugopm

Idea: Tlatoani

Preparation: Tlatoani and golions

Tutorial is loading...

EDIT: The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:

If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.

If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $$$\alpha$$$ that can be immediately applied on the vector.

Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).

Therefore, applying other (different) operations cannot prevent operation $$$\alpha$$$ from being able to be applied, so operation $$$\alpha$$$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $$$\alpha$$$ does not occur initially, then operation $$$\alpha$$$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.

Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Devil

Idea: Tlatoani

Preparation: Tlatoani and qlf9

Tutorial is loading...
Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by mohammedehab2002

Idea: Tlatoani

Preparation: Tlatoani

Tutorial is loading...
Solution (C++) by zscoder
Solution (Java) by qlf9
Solution (Kotlin) by Tlatoani

Idea: zscoder

Preparation: zscoder

Tutorial is loading...
Solution (C++) by KLPP

Idea: KLPP

Preparation: KLPP

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

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

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

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

    Can you please elaborate the logic given in tutorial for Problem E. I have given this question a good amount of time. thanks IN ADVANCE.

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

Thanks for the fast editorial! The contest was awesome!

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

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

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

What a fast editorial!

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

To everyone who got hacked on problem 2 (me included)

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it -22 Vote: I do not like it

    wait how did everyone get hacked? like what was the test case?

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

      Many people initialized max as 0 instead of -INF or -1e10 and therefore got hacked with any negative test case for e.g. 1 1 -10

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    i also got hacked, but most hacked solutions won't pass system tests anyway so yeah.

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

tourist : 5 problem — 12 minutes...

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

Has anyone printed this for 1392E - Omkar and Duck? (example with n = 10)

1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 1 
3 4 5 6 7 8 9 10 10 1 
5 8 12 17 23 30 38 46 46 1 
9 16 27 43 65 94 130 166 166 1 
17 32 58 100 164 256 376 496 496 1 
33 64 121 220 382 628 958 1288 1288 1 
65 128 248 466 838 1420 2212 3004 3004 1 
129 256 502 958 1750 3004 4720 6436 6436 1 
257 511 1003 1915 3499 6007 9439 12871 12871 1

Submission: 90149344

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

    I used the same logic that you did except that I used the last element of each row equal to the second last element instead of using 1s.

    My submission — 90156646

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

    I solved it as in the editorial
    Can you explain your solution?

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

      The matrix satisfies two properties -

      First, for any cell (i,j) the path which gives the smallest sum is always RRR...DDD... and the path which gives the largest sum is DDD...RRR...

      Secondly, for any cell (i,j) not lying in the topmost row or leftmost column, the maximum sum obtained in any path to the cell (i-1, j) is always 1 less than the minimum sum obtained in any path to the cell (i,j-1).

      After constructing such a grid, for each query we backtrack from (n,n) to (1,1) using these maximum and minimum sums.

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

      Let $$$S_{i, j}$$$ be the set of weights of all paths from (1, 1) to (i, j).
      The idea is that $$$S_{i, j}$$$ and $$$S_{i - 1, j + 1}$$$ should be disjoint. Also, $$$S_{i, j}$$$ can be obtained by merging $$$S_{i - 1, j}$$$ and $$$S_{i, j - 1}$$$ and adding a[i][j] to all weights.
      So, for each cell, you can greedily choose a[i][j] such that $$$min(S_{i, j}) = max(S_{i - 1, j + 1}) + 1$$$. It turns out that, for each cell, $$$S_{i, j}$$$ contains consecutive elements, so you can store efficiently these sets by storing only the minimum and the maximum.

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

    Almost the same principle, but a little differences:

    • zeroes in border path
    • every number is just more than maximal path in upper part
    0 0 0 0 0 0 0 0 0 0
    1 1 1 1 1 1 1 1 1 0
    2 3 4 5 6 7 8 9 10 0
    4 7 11 16 22 29 37 46 56 0
    8 15 26 42 64 93 130 176 232 0
    16 31 57 99 163 256 386 562 794 0
    32 63 120 219 382 638 1024 1586 2380 0
    64 127 247 466 848 1486 2510 4096 6476 0
    128 255 502 968 1816 3302 5812 9908 16384 0
    256 511 1013 1981 3797 7099 12911 22819 39203 0
    

    so my numbers bigger but still acceptable (max is 39_301_087_452_632 for 25x25)

    90174692

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

Problems were awesome, thanks for the fast editorial

»
13 months ago, # |
  Vote: I like it -113 Vote: I do not like it

can Anyone help me with some doubts I have. i attended a interview today and it has two question. can someone could say solution for it.

https://codeforces.com/topic/82091/en2

Thanks in Advance!!!!!

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

    anyone please!!!! just giving idea to solve will be a great help

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

      First at least post it so people can comment on it. It is currently just a revision

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

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

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

An easier solution for $$$H$$$.

First, the answer is the expected number of jokers times (the expected number of cards you draw before a joker + the joker).

The expected number of jokers can be expressed as $$$\sum_{k\geq 0}$$$ Pr[S is not full after $$$k$$$ jokers].

By PIE, Pr[S is not full after $$$k$$$ jokers]= $$$\sum_{i=1}^n {n \choose i} (-1)^{i-1} (\frac{m}{m+i})^k$$$.

So we get the answer.

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

Thanks for a good round and fast editorial!

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

In Problem A,

According to editorial [7,4,3,7] gives '1'. But it should be 3 right! [7,4,3,7] => [7,7(4+3),7] gives 3 right! Please help!

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

    it is 1. in the array [7,4,3,7], you can do these steps: step 1: [7+4,3,7] step 2: [11+3,7] step 3: [21] Answer = 1

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

    Hi Akhil, How about [7,4,3,7] => [11,3,7] => [14,7] => [21]?

    You can take any two consecutive and have to minimize.

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

    No, it is just an example. Not an optimal solution. It reduces to one eventually. 7+4=11, 11+3=14 , 14+7=21

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

Fast editorials are always great ! :) Thanks Tlatoani

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

The answer for H can even be simplified to $$$\left(\frac{n}{m+1}+1\right)\cdot\left(m\cdot H_n+1\right)$$$ where $$$H_n = \frac11+\frac12+\dots+\frac1n$$$.

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

    Is there any combinatorics proof for this? (I assume not but) or just algebra

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

      My solution did not involve any algebra.

      Call an iteration of the process to be drawing cards until we reshuffle. In each iteration, we draw each of the $$$n$$$ normal cards with probability $$$\frac1{m+1}$$$ and 1 joker. Thus in expectation every iteration takes $$$\left(\frac{n}{m+1}+1\right)$$$ seconds.

      We now need to calculate the expected number of iterations (and we can ignore how many cards we draw during each iteration). Let's say there are $$$k$$$ remaining useful cards we need when we start an iteration. With probability $$$\frac{m}{m+k}$$$ the first {useful card or joker} is a joker, and we start a new iteration. The rest of the time, the situation has converted to the start of an iteration where there are $$$k-1$$$ useful cards we need. If we let $$$I_k$$$ be the number of iterations we need when there are $$$k$$$ things not in our set, so we note that if each iteration has probability $$$\frac{m}{m+k}$$$ of ending uselessly, and probability $$$\frac{k}{m+k}$$$ of converting down, then the recursive formula is $$$I_k = \frac{m}{k} + I_{k-1}$$$. Noting $$$I_1 = m + 1$$$ gives us $$$I_k = m \cdot H_k + 1$$$.

      Multiplying these two numbers together gives us the answer.

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

        Thank you so much for the explanation, amazing and clean answer.

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

        Can you just multiply these two expected values together? These two values don't seem to be independent (1 iteration implies that you must have drawn n+1 cards).

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

          Let $$$E$$$ denote expected value and $$$P$$$ denote probability.

          $$$\begin{align*} E[\text{# of seconds until game ends}]&=\sum_{i=1}^{\infty}E[\text{contribution of }i\text{-th iteration}]\\ &=\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\cdot E[\text{length of }i\text{-th iteration}|\text{game did not end after }i-1\text{ iterations}]\\ &=\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\cdot E[\text{length of any iteration}]\\ &=\left(\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\right)\cdot E[\text{length of any iteration}]\\ &=E[\text{# of iterations}]\cdot E[\text{length of any iteration}]\\ \end{align*} $$$

          We used the fact that the length of the $$$i$$$-th iteration given that the game didn't end after $$$i-1$$$ iterations is still $$$\frac{n}{m+1}+1$$$. However, this does not imply that

          $$$E[\text{# of seconds until game ends}|\text{game ends after }i\text{ iterations}]=i\cdot E[\text{length of any iteration}],$$$

          which is what you wrote above.

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

          It's worth pointing out that having the type of independence you correctly note is absent would likely not even be useful. (Not that its absence is a poor reason to take caution!) Sure, if $$$N$$$, $$$X$$$ are two independent non-negative random variables, then $$$\operatorname{E}[\,N \cdot X\,] = \operatorname{E}[\,N\,] \cdot \operatorname{E}[\,X\,]$$$, but if $$$N$$$ is the number of iterations and $$$T = N \cdot X$$$ is the total time elapsed, then the necessary value $$$X = T / N$$$ is probably tricky to say anything useful about, and there is no better hope of multiplying the duration of any single iteration by something convenient and getting the total duration of all iterations.

          Of course, thinking about when (and how often) each iteration duration $$$X_i$$$ in the infinite i.i.d. sequence $$$ \{X_i\}_{i=1}^\infty $$$ will contribute to the overall time leads directly to the argument Benq describes above, but may have the downside that it "doesn't feel like" multiplication as much as a kind of factorization.

          Another way of approaching this, which uses more advanced concepts, but which might be more intuitive, is to note that $$$Y_k = \sum_{i=1}^k X_i - \left(\frac{n}{m+1}+1\right)$$$ defines a martingale, that $$$N$$$ is a stopping time with respect to its natural filtration, and that

          $$$ T = Y_N + N \cdot \left(\frac{n}{m+1}+1\right). $$$

          It's then easy to verify that $$$ Y_N $$$ satisfies the conditions of the optional stopping theorem, so that

          $$$\operatorname{E}[\, T \,] = \operatorname{E}\left[\, Y_N + N \cdot \left(\frac{n}{m+1}+1\right) \,\right] = 0 + \operatorname{E}[\, N \,] \cdot \left(\frac{n}{m+1}+1\right).$$$

          These abstractions might seem intimidating, but they really aren't doing much more here than capturing why Benq's argument works.

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

        Why is I_k = m/k + I_(k-1)?When there are k useful cards,the probability of converting down is k/(m+k).Why the expected number of iterations to k-1 useful cards is not the reciprocal of k/(m+k),and I_k = m/k + 1 + I_(k-1)?

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

          $$$I_k=\frac{k}{m+k}\cdot I_{k-1}+\frac{m}{m+k}\cdot (I_k+1)$$$

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

        Why is the expectation for the first part $$$\ (\frac{n}{m+1} + 1)$$$?

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

          If you choose any card (aside from the jokers), the probability that it comes before all $$$m$$$ jokers is $$$\frac{1}{m+1}$$$. Sum this over all $$$n$$$ cards (by linearity of expectation).

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

            why the probability is 1/(m+1)?

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

              For any set of $$$x$$$ cards, each card comes first with probability $$$\frac{1}{x}$$$.

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

    Hello sir conqueror_of_tourist, Why don't you open a YouTube channel, like you are one of the red coder which codes in python. It will be helpful for many of us. Please think about it. Thanks

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

I hacked tfg's solution for B.by test 1 1 1 -1.Its answer is actually 0 but tfg's solution got 1.

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

Don't you think that tfg code for problem B is incorrect. mx should be start from -1e9 because array value can be negative also

UPDATE: Now, it has been corrected.

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

    Yes,actually it is.I hack 4 solutions with this test.THIS SOLUTION IS WRONG!!!

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

For D I would like to share my approach

You can split the array into segments which do not interact with each other. Each segment must either be - "RRLL" - "RL" - "RRL" - "RLL"

dp[i] records the minimum number of changes needed such that arr[:i] is made up of the above segments.

We can assume that the first element in the array do not interact with the last element of the array, by shifting the array four times and calculating the optimal changes required for each.

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

    I did this too! I think you only need to shift it three times because the requirement is that the solution starts with R, and there are at most two Ls in a row, but I also happened to shift it four times just to be safe.

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

In the problem B tutorial (c++ one) max taken here is 0 and should be taken -INT_MAX most people got hacked for that only. (edit : its been corrected).

»
13 months ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.

1

16

17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17

Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25.

Could you help qlf9

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

    This is my solution for C https://codeforces.com/contest/1392/submission/90111238

    For bi≤bi+1 to be valid you can think it like bi — bi+1 ≤0. and minimizing condition will be equal to zero. So what I did was I checked if a[i] — a[i+1] was greater than zero then we just have to add 1 height that number of times.

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

      But yours also return 26(5+13+8) for the case I provided. Which is wrong. The 5th element is 25 and in order to make this a non-decreasing array all the subsequent elements have to increased to 25 too. In that case the answer would be 32

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

    You don't know how to get 26 for this example? For every $$$a[i - 1] - a[i] > 0$$$ in decreasing order of $$$i$$$, perform $$$a[i - 1] - a[i]$$$ operations over the range $$$[i, n]$$$.

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

      I know Nson. I get where that logic is coming from. But all I am saying is that this logic is wrong. I am even providing you with a counter example. Try the counter example and see it for yourself. If my counter example is wrong then please tell me. 26 is wrong for this example. As I said earlier, the 5th element is 2(which is also the maximum), meaning all the subsequent elements have to increased at least to 25 to make it a non-decreasing array. If i am misunderstanding something tell me

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

        I just provide you the algorithm to build the correct answer.

        I ran locally and got these

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

        The first four elements can be smaller than 25. And I don’t really know what you want to prove.

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

    Read the problem statement carefully before commenting.

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

      Dear saquib2508 I have read the problem statement many times, but cannot find where am I wrong. It might be helpful if you could help me. Which part of my question is wrong? If you could point it out.

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

    it is right that all subsequent elements have to be at least 25 but it does not mean that to make them at least 25 we have to perform 25 or more operations.[12,13,25,12,20] here we need only 13 operations. Hope I got you right!!!

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

    Thanks for helping me out. You guys are the best!!

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

Why doesn't the following work for H?

f(0) = 0 f(i) = 1 + i/(m+i) * f(i-1) + m/(m+i) * f(n)

My logic was that, at f(i), we must use a move and then there is a i/(m+i) chance the problem is reduced to f(i-1) and an m/(m+i) chance that we must restart (hence f(n)). Could someone help me understand the flaw in this approach?

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

    You most likely misread the problem. There is replacement when a joker is drawn, and you should get a 2D recurrence of this form instead.

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

    The deck is replaced for a joker

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

How to deal with overthinking, sometimes I end up making very complex logic even for easier problems like A and B ..

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

Thanks for the great round and the fast editorial. I really loved the interactive problem.

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

can someone help me I am getting TLE on test 16 in E....

https://codeforces.com/contest/1392/submission/90165976

I got it don't bother.

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

    You are using left shift to calculate power of (i+j).When (i+j)==31 it will give a negative number because if the number is shifted more than the size of integer, the behaviour is undefined. Try to calculate power of (i+j) with the help of dp and your solution will get accepted!

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

      replacing 1 with 1LL worked.... thanks though.

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

    leave it

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

For F, if you look at the list of height differences, then the problem is identical to Juggling Troupe from NWERC 2017, except jugglers are allowed to start with more than 2 balls.

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

    It's probably easier to solve F if you haven't seen this problem ...

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

      Actually there was also an old GCJ problem. It helped me a lot but yet another insight is needed for today's F, that's nice.

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

      Ah, yes. F is easier because the heights start out strictly increasing (meaning each juggler starts with at least one ball in the transformed problem)... didn't notice this.

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

Explain D plz....i just changed LLL to LRL and RRR to RLR....couldnt find any other observations.

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

    Probably, you forgot that beds are arranged in a circle and got wrong calculations on prefix/suffix

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

      i checked on circles too. I still can't figure out where that observation fails.

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

        Well, if you changed LLL to LRL too, but by just searching LLL and replacing them — this will fail at RLLLLLR (You will get RLRLRLR instead of RLLRLLR), so it is better to replace LLL to LLR.

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

          Thanks. But, what will be the resultant string for LLLRRRLLL?

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

            You're right, this replacement fails at this example :) But my solution counts answer without any replacements, so I just supposed this was your problem.

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

              Can you briefly explain your solution, please?

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

                Firstly, if there are both L and R in string I move the prefix that contain only L or only R to the end, if the last symbol is the same (like in your example LLLRRRLLL -> RRRLLLLLL). Then, I look at substrings containing only one symbol — if length of this substring is L, you need to add (L + 1) / 3 to answer — it is not hard to prove. And if the whole string is "LL...LL" or "RR...RR" answer is (n + 2) / 3, it is easy to prove, too.

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

            Just understand that we are fine as long as no 3 L's or R's come together. For every 3 consecutive Ls or Rs one correction is needed. So ans will be sum of all (num/3) where num is number of consecutive Ls and Rs as we look at array. Another special case is if entire array is just Ls or Rs, then ans = ceil(n/3). U can check for any arbitrary example, atleast these much corrections needed to do everything right.

            MAIN MISSION: No 3 consecutive Ls or Rs (works in a circular fashion)

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

Could the tutorial be any faster ? :D Amazing contest. Thanks a lot.

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

Maybe the fastest editorial on CF...

Thanks

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

Can anyone please provide test case where my code would't give correct answer for problem A? 90106564

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

    If biggest number comes in first position.

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

    It looks like any decreasing sequence (e.g. 6 5 4) should fail your solution, because this check: long.Parse(s)>firstMax will be false and you'll never assign anything to secondMax.

»
13 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.

1

16

17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17

Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25.

Could you help qlf9 Tlatoani

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

    17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17

    after 4 moves

    17 15 12 16 25 15 12 18 19 16 15 15 18 20 21 21

    after 1 more move

    17 15 12 16 25 15 12 18 19 16 16 16 19 21 22 22

    after 3 more moves

    17 15 12 16 25 15 12 18 19 19 19 19 22 24 25 25

    Do the rest on your own.

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

one of the best rounds ever

great round

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

Thanks for the fast editorial!

Request: Can the written explanations be hidden inside spoilers?

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

CONTEST WAS EXCELLENT! gg.

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

Can Anyone explain 1392D - Omkar and Bed Wars in easy language? i can't able to understand editorial.

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

I solved 'D' with dynamic programming by changing the string so it is comprised of four available good options:

string good[] = {
    "RL",
    "RRL",
    "RLL",
    "RRLL"
};

I then tried 4 (the longest good sequence) different string shifts to account for circular nature of the problem.

Submission: https://codeforces.com/contest/1392/submission/90138778

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

    I did something similar. DP with 4 cases.

    https://codeforces.com/contest/1392/submission/90124447

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

      Cool!
      It would probably be enough to only call solve() once, but initialize dp for all four cases:

      dp[1][0b00]=!(a[0]==0) + !(a[1]==0);
      dp[1][0b10]=!(a[0]==1) + !(a[1]==0);
      dp[1][0b01]=!(a[0]==0) + !(a[1]==1);
      dp[1][0b11]=!(a[0]==1) + !(a[1]==1);
      
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey, do you know some easy equivalent problem without circular arrays? The code is very difficult to understand with circular arrays. I was unable to find a problem like given a 1D boolean array, find the minimum number of operations so that there are no 'k' consecutive characters... or any other, which can be solved using dp. TIA

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

          I don't know non-circular equivalent, but although you need to put some thinking into circular nature of the problem, the code to account for it is quite short. In my submission (https://codeforces.com/contest/1392/submission/90138778) it's just shifting the string 4 times. In the editorial it's these lines:

          while(s.size() && s[0] == s.back()) {
              cnt++;
              s.pop_back();
          }
          
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I solved D in different way. I used a deque and a 3 element window. When I am getting LLL or RRR in the window I changed the 3rd element of that window to tht opposite one. But it failed on TC2.

        Link for submission. https://codeforces.com/contest/1392/submission/90165043

        I want to know is the approach totally wrong or something corner is missing.

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

          LLLRR

          Here it is obviously better to change the second L.

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

            On my first attempt I changed the middle one ..it failed Then changed the last one...still failing

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

    Can You Explain Why Are You Shifting the String ?

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

      Good "group" may start at the end of the string.
      Example: LLRRLR — it can't be separated into four seqeunces above,
      but if you shift it: RLLRRL = RLL+RRL
      Because the longest group length is 4 (RRLL), I need to try 4 different shifts

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

    Your code is very clean...Thanks!

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

    I was thinking the same logic but dp[1]=0 stands always or not? I am getting an error in it;

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

      dp[0] = 0
      How many characters do you need to change in first 0 characters to get a correct string? Because empty string is correct (in this problem) then it's 0

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

why tle in test case 9 in problem B? code

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

    Because:

        for(i=0;i<n;i++)
      {
        b[i]=*max_element(a, a + n)-a[i];
      }
         for(i=0;i<n;i++)
      {
        c[i]=*max_element(b, b + n)-b[i];
      }
    

    You search max element 'n' times. So it will need n*n operations.

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

How did everyone get hacked on B?

Mine failed system tests btw.

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

Thanks for the round! I liked H. Kudos to simple solutions in the comments...

I came to the similar recurrence as in the editorial, while I simplified the computation part. When we have $$$\lvert S \rvert = x$$$, we can remove the cards with a number in $$$S$$$ and set the operation time to $$$1 + \frac{x}{m+(n-x)+1}$$$ seconds instead of $$$1$$$ second.

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

Not tying to complain at all but C was worded so poorly. that question was easier than A and B for most that right to left thing had me badly

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

I am unable to understand why my solution for problem C does not work, what is the possible error. Someone's help with an example test case in which my solution gives wrong answer is highly appreciated.

Code link https://codeforces.com/contest/1392/submission/90159907

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

Clearly C wasn't rejected enough. Explains why it's the weakest problem of the contest.

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

    I didn't understand the Editorial of C clearly.Can you explain C?

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

    Can you please explain C?

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

I had a different fucked up idea for task E using meet in the middle. Give random numbers to the array and find the path by using meet in the middle. Still don't know why I thought that the complexity would be O(T*2^n/2) when it was O(T*2^n). So yeah it failed on test 18. The probability to get a unique path is very high. I thought about the correct approach but this seemed way easier and I still can't understand why

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

    Bear in mind that if the sum on your path is k, but your path is different from the actual hidden path, then your solution is still wrong!

    • in task E
    • what is the point in making this bold , what is 'actual hidden path'?? somebody pls explain, I think I don't get it........
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There can be different paths with same K. Thus if the system selects one of the paths and output other, then its basically wrong. It just meant all path weights should be unique.

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

1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n ...

I did this for 1392E - Omkar and Duck. Is it wrong ?

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

what

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

any idea of the interactor of problem E. i mean , to prove my solution wrong you have to find at least 2 path with same sum. My question is how can i check this ? cz the sum might be very large.

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

Looks like I overcomplicated C a little bit using RMQ.
Used a well-known approach though.

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

    How did you do it? I tried to do it during contest, but kept getting TLE. I tried updating all the elements from $$$i$$$ to $$$n - 1$$$ but kept getting TLE. Help please. Thanks! I tried using the approach from this.

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

      let $$$b_i$$$ be the minimum number we have to add to $$$a_i$$$ to make the array $$$a$$$ sorted. Now the answer is the minimum number of operations to make all $$$b_i$$$ equal to $$$0$$$.

      We can find the answer using this recursive function:

      long long f(int l, int r, long long mn)
      {
          int p=qry(l,r); // p = position of the minimum value in the subarray b[l...r]
          long long x=b[p]-mn;
          if(p>l) x+=f(l,p-1,b[p]);
          if(p<r) x+=f(p+1,r,b[p]);
          return x;
      }
      

      Initial call is $$$f(1,n,0)$$$.
      My submission

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

Problem C should have dp tag.

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

Sheldon approves the rejection count 73.
Big Bang Theory fans will get this.

Also, press F to display your condolences for the problem setters.

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

Is there anyway i can see all the test cases (higher), cf doesn't show if the test cases are too large to see

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

Can any one help me figure a counter test case that fails my solution for D? in this code, I look for sub-strings of length 3 that are either LLL or RRR and if found, I increase the answer by 1 and moves the i to the next triplet of characters.

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

Here's my approach for problem E (Much less intuitive: I dont know how one thinks of a solution like given in the editorial).

Idea is same: All paths should have different sums.

Set row_1 and col_n to 0. Now we fill elements starting from col_n-1 to col_1 and row_2 to row_n

Current max sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,j+1)->(n,j+1)->(n,n)]

Minimum sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,n)->(n,n)]

Value(i,j) should be such that minimum sum through (i,j) should be greater than current maximum sum through (i-1,j). Subtract the sum in 2 paths and add 1 to get Value(i,j)

Now processing queries is easy. From (x,y) you go down if sum from [(x,y+1)..(n,n)] < required sum else you go right.

For example n=6

0 0 0 0 0 0 
70 35 15 5 1 0 
70 35 15 5 1 0 
50 25 11 4 1 0 
30 15 7 3 1 0 
16 8 4 2 1 0 

1392E - Omkar and Duck

My solution

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it
    I dont know how one thinks of a solution like given in the editorial
    

    A possible approach to come with that solution:
    - it could be useful to use powers of 2 (since different sums of distinct powers of 2 correspond to different numbers)
    - distinct powers of 2: this means that you could put a different power of 2 on each diagonal (since we visit each diagonal only once, the powers are distinct)
    - but this doesn't work because, if you are on some cell, at the next move you can go to 2 cells with an equal value, so you obtain 2 equal sums (i. e. the cells $$$(i + 1, j)$$$ and $$$(i, j + 1)$$$ have equal sums)
    - so, you need to "turn off" one of these two cells for each $$$i, j$$$
    - after drawing some cases it's easy to realize that you can "turn off" cells with odd $$$x$$$

    I came out with your solution (link to comment) because I thought that $$$2^{50} > 10^{16}$$$, so I tried to put prefix sums of Pascal's triangle in the grid instead, then I optimized that approach.

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

      Completely forgot that distinct 2-power sums are unique. Thanks

      Yeah your is exactly the same solution, extra 1 added. xd

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

    leave it..

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

Kudos for providing solutions in other languages than C++!!

PS. But please don't write C++ in Java xD

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

Can somebody help and explain why my recursive solution for C is failing the second test? 90168524

What I'm doing is finding all nonincreasing subarrays, and then recursively finding the most effective way to make a nonincreasing subarray a nondecreasing one. What the recursive function does is splitting subarrays in index of their max element and doing it recursively until it finds a subarray with equal values, then making all values of this subarray equal to max element in previously called function. I understood the solution in editorial, but I'm sure my approach should also be correct.

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

My solution for B was hacked. How to view which test case failed?

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

    Resubmit your code, you will get to know about the WA Testcases...

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

On E, I wrote a WA program but returned TLE. Why? TLE on test 1(WA) AC

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

    You output the wrong answer, but your program doesn't stop.

    I think the problem description should remind participants of this.

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

SIMPLEST SOLUTION FOR B submission:90119461

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

I'm just curious about how the tests for problem E were made. I'm thinking of finding two paths with equal sum then asking for this sum. Is this how the tests were made or it's just random? I don't think it's random so if the testers can satisfy my curiosity I'd be glad.

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

    I'm not the tester but I did write something like interacotor( which can generate data and test a program ) locally. It turns out that the data generated randomly is already strong enough for every wrong approach I know.

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

Can anyone tell me, why I was getting MLE in problem A when I was using array ?

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

    No bothering please I have understood this myself.

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

I had another approach for C:

code

This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.

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

    NICE!

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

    Please explain why this idea will work?? thanks in advance!!

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

      i explained it:

      This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone tell me what is &mdash in solution of problem C ?
»
13 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I couldn't understand the solution of F, before I read the problem statement once again and realized that the constraint was not $$$h_1\leq h_2\leq\cdots\leq h_n$$$ but $$$h_1<h_2<\cdots <h_n$$$. What the heck. I was solving the harder version.

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

https://codeforces.com/contest/1392/submission/90188584 why this code giving memory limit exceeded

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

Hello, can someone help me with alternate explanation for C ?? I am not able to keep up with the explanation given in editorial

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

About the proof of F, why is it clear that the order does not matter?

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

    I was also curious about that — it is plausible (a priori) there could be a way to get stuck depending on your order (or at least, it's not immediately clear why that's false).

    I proved that there can only be one difference of 0 in the end in a different way — I showed by induction that any two points with a difference of 0 must have a point in between with a difference of 2 or more.

    It took a long time though — if I knew that order didn't matter, the conclusion would be much faster.

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

      Can you please elaborate your inductive proof?

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

        Consider the sequence of differences a[i+1]-a[i]. Let's call that sequence b[i].

        The claim is that if at any point i<j and b[i]=b[j]=0 then there must be a k, i<k<j, where b[k]>=2.

        Suppose this claim is false, and consider the first moment where this property fails — that means that b[i]=b[j]=0, and for all k, i<k<j => b[k] <= 1.

        That means that the last move must have been somewhere on the interval [i,j]. Recall that a move at k reduces b[k] by 2 and increases b[k-1] and b[k+1] by 1. Since b[k-1] and b[k+1] are <=1, b[k-1] and b[k+1] must have been 0 before the move, and b[k] was 2 or more. But that means that the property was false on the previous turn too! A contradiction.

        With the claim, since the last moment has only 1s and 0s, we know there can't be 2 0s.

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

    viewing those operations as operator(function on vector), we only need to prove that operators are communicative, that is to say we only need to verify that for all index $$$i,j$$$, the operating order on $$$(h_i,h_{i+1})$$$ and $$$(h_j, h_{j+1})$$$ does not matter, which can be seen clearly for both $$$|i-j|=1$$$ and $$$|i-j| \neq 1$$$ cases.

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

      If h=[1,3,4], then the only order is [1,3,4]->[2,2,4]->[2,3,3]. The other order [1,3,4]->[1,4,3]->[2,3,3] contains an invalid operation.

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

        It does not matter much as we only care the output after these operations, and do not care the validness of those operations (just do them formally).

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

          Why do we not care the validness? If we swap two adjacent operations, one of them may become invalid and force the process to end. Tlatoani would you help explain why is it clear that the order does not matter? It is definitely true but i think it requires a (nontrivial) proof.

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

            If I get it correct, what the editorial does is just rearranging those operations, and what we need to make sure is that the output after rearranged operations is identical to the one after operations mentioned in the statement. Therefore, we may formally define operations $$$op_i$$$ on all states instead of valid states and check the communicative property. Once we get that property, we can claim that rearrangement does not affect the final result, and the valid rearrangement is just a special case of this.

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

            This turned out to be harder to prove than I thought, but I think you can do something like this:

            If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.

            If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $$$\alpha$$$ that can be immediately applied on the vector.

            Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).

            Therefore, applying other (different) operations cannot prevent operation $$$\alpha$$$ from being able to be applied, so operation $$$\alpha$$$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $$$\alpha$$$ does not occur initially, then operation $$$\alpha$$$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.

            Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).

            Thank you for pointing out how this is nontrivial, I will probably update the editorial with this proof.

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

              Can you please explain what does "maximal operations" mean?

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

                A sequence of operations such that you cannoy perform any additional operations at the end.

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

In problem D. Omkar and Bed Wars. Can someone tell me how they come with this formula floor(n/3) or ceil(n/3). During contest i was very confused about this. Do we have to come up with this formula directly with intuition or their is some simple thinking strategy which can be used for other problems also.

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

    I assume you agree that the illogical strategy happens when there is $$$LLL$$$ or $$$RRR$$$.

    So if the given string has all characters same, then you split it into, say, buckets of length 3 and flip the 3rd character, i.e. $$$RRR$$$ -> $$$RRL$$$. This way, if n is not divisible by 3, then there's at least one character left, and it wraps around to beginning where there are two same of them. In other words, the last, then first and second characters are the same so we need to deal with this. So it becomes $$$ceil(n/3)$$$ or $$$(n + 2) / 3$$$. This is the case when the string has all same characters.

    If the string doesn't have all characters same, and has a maximal segment of length k of same characters. Then we do the same operation as we did above, however, this time, since both sides of the segment has different character and there'd be at most two characters at the end (and in the beginning), we don't have to deal with what's left at the end. Thus, the answer for this segment is $$$k / 3$$$.

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

      okk !! now i understood how to think in a more better way. Thank you !

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

can someone tell me why did i get a TLE here? https://codeforces.com/contest/1392/submission/90105088

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

For F, I didn't realize the heights were strictly increasing, I just thought they were non-decreasing. I believe my solution works for those cases too, if anyone is curious (or can find a counterexample).

Slightly cleaned up submission: 90191364

(I break the array into subarrays and solve each subarray. When the heights are strictly increasing, as in the actual problem, it just ends up doing a single subarray, haha.)

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

Can anyone spare some time to figure out why my solution is not working in C. My solution can be easily understood. Here is my code. Thanks in advance to that great soul who helps me.

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

    It is asked to find the minimum number of operations to make the sequnce non decreasing. You do not calculate that. Instead, you calculate the number of operations to make all elements equal.

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

Can someone explain why in D we are rounding up instead of down?

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

Can anyone help me find error in my code for C problem thanks in advance here is the link https://ide.geeksforgeeks.org/M9zO7OyT2Z

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

    Please validate the output for following test case: 13 1 2 3 5 6 3 2 1 3 4 5 0 6

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

      guys, I was solving question C with the help of editorial and want to come up with my solution but I got stuck. help me out.90195244 thanks

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

      the answer to your test case is 13 right???

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

      I got 6 as the answer which i think is the correct ans

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it
        1 2 3 5 6 3 2 1 3 4 5 0 6 <- Input array
        1 2 3 5 6 3 2 1 3 4 5 5 6 <- add 5 (at index 11)
        1 2 3 5 6 3 2 2 3 4 5 5 6 <- add 1 (7)
        1 2 3 5 6 3 3 3 3 4 5 5 6 <- add 1 (6-7) 
        1 2 3 5 6 4 4 4 4 4 5 5 6 <- add 1 (5-9)
        1 2 3 5 6 5 5 5 5 5 5 5 6 <- add 1 (5-10)
        1 2 3 5 6 6 6 6 6 6 6 6 6 <- add 1 (5-11)
        
        So, Ans = (5+1+1+1+1+1) = 10
        
»
13 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Thanks for fast Editorial,Explanation for problem F is too good.

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

In F, if we go by the pattern that $$$h_i = 1000001*(i-1)$$$, then it looks like in the output, $$$h_1$$$ should be $$$499999500000$$$ and not $$$499999500001$$$. But the judged answer is $$$499999500001$$$. Why is that so? Edit: I was talking about Test 9, forgot to mention.

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

can anyone tell easy test case for pretest 8 90152118 here is my submission thanks in advance

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

In problem 1392 C , the water slide one, my approach was that each support should be greater than maximum element to the left of it. So what i did was to find a subarray that had all its elements less than the max element in the left. Then find minimum in that subarray and add max-min to answer. Example: 19 21 12 3 24 22 ans=18+2=20 right??? What is wrong with my approach i fail in pretest 2

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

    See this test case t = 1 n = 8 array => 19 21 12 9 3 7 10 2 actual answer is 26 but your answer will be 19.

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

      understood. I am having trouble understanding the solution for this problem. Could u give me an explanation or an intution. Thanx :D

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

I feel so stupid after looking at the solution of problem A. Damn what should i do to think like that fast??? LOL

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

I have tried E after reading the editorial. But I am getting TLE on 17th test case

Please look a the function solve()

can somebody help me here?

My Solution

Thanks in advance

UPDATE

I have tried without storing the matrix My Solution without matrix storing

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

Problem E when I tried to generate 2^50 with bit shift i.e. 1<<50, I got a negative value. Then I had to use the pow() fn.

I wanted to ask : 1) Can I do the same with bitshift? If yes, How? 2) Is there any limit of pow() fn also?

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

Somehow in the problem B I though that the maximum element in the array minus 0 equal 0 :T

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

What is the idea behind this solution of F

90126141

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

For Problem E, the matrix can also be

$$$ \begin{array}{ccc} 2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 \\ 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 \\ 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 \\ 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 \\ 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 \\ 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} & 2^{11} \\

\end{array} $$$

when $$$n=6$$$, since the duck is at $$$(x,y)$$$ $$$\forall x,y\in [1,n]$$$, we can know the direction the duck walk to next step from the lowest bit of the sum of left problems.(Submission:90156663)

It's a really interesting constructive problem, thanks for preparing this awesome round. =)

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

    Upsolved it this way:

    $$$2^1$$$ $$$2^2$$$ $$$2^3$$$ $$$2^4$$$ $$$2^5$$$
    $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$
    $$$2^3$$$ $$$2^4$$$ $$$2^5$$$ $$$2^6$$$ $$$2^7$$$
    $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$
    $$$2^5$$$ $$$2^6$$$ $$$2^7$$$ $$$2^8$$$ $$$2^9$$$

    Just follow the bits of the path sum to find the path. It was a really interesting problem and I regret not spending enough time on it during the contest.

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

      I solved it this way for lets say 4*4 matrix the matrix is

      1 2 4 8

      0 0 0 16

      4 8 0 32

      0 16 0 64

      See paths diagonally!

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

For I, KLPP could you please explain furthuer what does However, some faces are not interesting, namely the 2×2 square of adjacent cells. mean? Sorry for my bluntness, but I'm just sort of threw out the track right here QAQ. Thanks in advance.

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

    2x2 squares of cells that either all have temperature >=x or temperature <x are faces of the graph, however, they do not correspond to any connected component, so we have to subtract them from the number of faces.

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

      Thanks, I think I'm kind of gettig it right :)

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

        Consider a face in, for example, the graph with vertices with temperatures >=x. You can see that this face is an area enclosed by vertices, which means that inside it there is a bad connected component or nothing(in the case of the 2x2 square). Let, for example, H represent cells with temperatures >=x and C otherwise:

        HHHHH

        HCCCH

        HC CH

        HCCCH

        HHHHH

        Here you can see that the face enclosed by the 'H' correspond to a bad connected component in the 'C'. However, in this particular case:

        HH

        HH

        There is nothing inside, and thus it is not an interesting face. Sorry for my poor editing skills.

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

          Oh, I think I've just realized what you mean the moment before you started to provide further explanation. So sorry for my stupid problem on understanding that formula. Anyway, thanks a million for your help, and it is a really educational and inspiring problem!

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

what should be the answer for question d in the case 1 6 RRRRRR

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

    I think it should be 3 but most accepted codes print the answer 2

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

"Fun fact: This problem was originally proposed as B"

It might have had 5k+ ACs then....lol

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

Can someone tell me why this solution 90172327 is wrong in problem C ? I loop on the numbers from the smallest and merge the equal numbers using DSU, so that they can be increased at the same time, and for each number I see the number to the left (after merging equal elements) if it was larger, then I need to increase that number, if the difference between the current number and the number on the right is smaller that between it and the number to the left, so I increase it to be equal to the number to the right

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

why the below solution is giving a wrong answer on pretest 8 i cannot see the test cases(it is showing ......) below is the code

Your code here...
ll c=0;
	for(int i=0;i<n-1;i++)
	{
		ll mx=INT_MAX;
		ll cur=i;
///cur is current maxixum index from left till where we have iterated
	if(a[i]>a[i+1])
	{
		while(a[i]>a[i+1])
		{
			mx=min(mx,a[i+1]);
			i++;
		}
		c+=a[cur]-mx;
	}
	}
	cout<<c<<"\n";
»
13 months ago, # |
  Vote: I like it +13 Vote: I do not like it

"Clearly, the order in which we perform the slides (transfers of one square meter of dirt from $$$a_j+1$$$ to $$$a_j$$$ for some $$$j$$$) does not matter." Why ? Can someone explain ?

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

Tlatoani

who is getting the random t-shirts ?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain what's wrong in my logic?

whenever I find a[i+1]>a[i],then I insert each of the elements from i+1 on wards which are smaller than a[i] and then take the lowest element present in the set to calculate the number of operations required. And then repeat the process several times

http://codeforces.com/contest/1392/submission/90294667

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

    16 17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17

    notice this case when you take temp as 25 all values after it are less than it. So operations are 25-11=14. but you are not allowed to make these operations since this subarray after 25 is not non decreasing and for an operation subarray must be non decreasing.

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

90300727 Here is a greedy solution for Problem D , I had a few mistakes on the contest.

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

Could anybody tell me what's wrong with this DP code for D? It is getting TLE on test 6. Thanks!

CODE
»
13 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

In Problem C Editorial "Now let's look at the pair $$$a_j,a_{j+1}$$$. If $$$a_j≤a_{j+1}$$$ (or if j=n), applying an operation would not change ans". Does the equality $$${a_j}=a_{j+1}$$$ holds here?

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

could anybody tell me what wrong in this code of plroblem D ...click

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

My blog discusses the solution to 1392F - Omkar and Landslide if the original heights are non-decreasing instead of strictly increasing.

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

1 6 RLLLRR

why does this give 1

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

I problem

However, some faces are not interesting, namely the 2×2 square of adjacent cells. Let Q1 be the number of such squares

  1. not interesting = bad?
  2. What's 2x2 square meaning?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The inequality written for problem C. The part that considers the right border of a subarray, shouldn't it be if A_{j+1} > A_{j} then doing an operation wouldn't change ans; whereas if A_{j+1} <= A_{j}, then doing an operation will increase answer by 1?

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

V1+F1=E1+C1, where V1 is the number of vertices in graph 1, F1 is the number of faces in graph 1, ….

However, some faces are not interesting, namely the 2×2 square of adjacent cells. Let Q1 be the number of such squares.

Similarly, V2+F2=E2+1+C2. Why V1+F1=E1+C1, but V2+F2=E2+1+C2, whats meaning of C1 and C2?

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Your code here...
    F + V - E = 1 + C
    
    F1 + V1 - E1 = 1 + C1
    F2 + V2 - E2 = 1 + C2
    
    F1 = 1 + C1 + E1 - V1
    F2 = 1 + C2 + E2 - V2
    
    Q = 2 * 2 sq
    
    F1 - Q1 = bad(C2)
    F2 - Q2 = bad(C1)
    
    1 + C1 + E1 - V1 - Q1 - bad(C2) = 0;
    1 + C2 + E2 - V2 - Q2 - bad(C1) = 0;
    C1 + bad(C1) - (C2 + bad(C2))  + E1 - E2 - V1 + V2 - Q1 + Q2 = 0
    ans = E2 - E1 + V1 - V2 + Q1 - Q2
    = -E1 + V1 + Q1 + (E2 - V2 - Q2)
    
»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There are many type mistakes in problem I. Could you fix it? Thank you very much. QAQ

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

I am suffering a lot in understanding the logic of problem E can any one please help me... i cant understand what is the reason behind constructing array like that

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

I solved H by brute-forcing for small $$$n,m$$$ and I found this formula

$$$f(n,m)=\frac{(m A_n + n!)(m+n+1)}{n!(m+1)}$$$,

where $$$A_n$$$ is A000254

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

For problem I,whats meaning of C1 and C2?Can anyone help me?

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

For the proof of Problem F, the editorial details an argument which requires the fact that "the order of operations does not matter". It is actually hard to prove this, and even with this lemma, it is a long and convoluted way to prove.

I have a much simpler and intuitive proof!

First, a lemma:

If position $$$i$$$ and position $$$i+1$$$ have the same value (say $$$q$$$) in iteration number $$$j$$$, then in iteration number $$$j-1$$$: it is necessary that position $$$i$$$ has value $$$q-1$$$ and position $$$i+1$$$ has value $$$q+1$$$.

The proof of this lemma is simplicity itself and is left as an exercise to the reader (it is really easy, I am not tricking you).

Now, for the sake of contradiction, let's say that we have as the final array a situation with more than one pair of equal elements. Because of the lemma, we can't have more than two consecutive equal elements. Now if the equal elements are as such

$$$a$$$ | $$$a$$$ | $$$a+1$$$ | $$$a+2$$$ | $$$a+3$$$ | $$$a+4$$$ | $$$a+4$$$

then we by going backwards, we can reach an impossible state (where the array is not non-decreasing), hence the contradiction.

And yeah, I use the fact that the array is always non-decreasing. It is also very easy to prove. (just use induction on iteration number).