Tlatoani's blog

By Tlatoani, 4 years 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: MagentaCobra and qlf9

Preparation: MagentaCobra

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

Idea: MagentaCobra

Preparation: MagentaCobra

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

| Write comment?
»
4 years 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).

»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Thanks for the fast editorial! The contest was awesome!

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What a fast editorial!

»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

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

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

»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

tourist : 5 problem — 12 minutes...

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

Has anyone printed this for 1392E - Омкар и утка? (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

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

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problems were awesome, thanks for the fast editorial

»
4 years 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.net/topic/82091/en2

Thanks in Advance!!!!!

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

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

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

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

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

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

Thanks for a good round and fast editorial!

»
4 years 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!

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

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

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Fast editorials are always great ! :) Thanks Tlatoani

»
4 years 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$$$.

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

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

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

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

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

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

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

      • »
        »
        »
        »
        4 years 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)?

        • »
          »
          »
          »
          »
          4 years 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)$$$

      • »
        »
        »
        »
        4 years 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)$$$?

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

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

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

            • »
              »
              »
              »
              »
              »
              »
              4 years 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}$$$.

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

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

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

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

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

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

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

    Hi! Can you please give the submission link to you solution? I am trying to find it , but unable to do so right now. Thanks.

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

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

  • »
    »
    4 years 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]$$$.

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

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

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

    Read the problem statement carefully before commenting.

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

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

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

»
4 years 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?

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

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

    The deck is replaced for a joker

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

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

    Do it for fun not for rating then you will be relaxed and automatically think simple.

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

»
4 years 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.net/contest/1392/submission/90165976

I got it don't bother.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

              Can you briefly explain your solution, please?

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

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

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

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

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

    If biggest number comes in first position.

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

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

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

»
4 years 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?

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

CONTEST WAS EXCELLENT! gg.

»
4 years 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.net/contest/1392/submission/90138778

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

    I did something similar. DP with 4 cases.

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

    • »
      »
      »
      4 years 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);
      
      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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.net/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();
          }
          
      • »
        »
        »
        »
        4 years 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.net/contest/1392/submission/90165043

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

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

          LLLRR

          Here it is obviously better to change the second L.

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

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

    Can You Explain Why Are You Shifting the String ?

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

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

    Your code is very clean...Thanks!

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

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

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

why tle in test case 9 in problem B? code

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

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

How did everyone get hacked on B?

Mine failed system tests btw.

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

»
4 years 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.net/contest/1392/submission/90159907

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

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

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

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

»
4 years 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 - Омкар и утка. Is it wrong ?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

what

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

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

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

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

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

Problem C should have dp tag.

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

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

»
4 years 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 - Омкар и утка

My solution

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

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

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

»
4 years 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?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
4 years 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?

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

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

      Can you please elaborate your inductive proof?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
4 years 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?

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

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

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

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

»
4 years 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?

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

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

What is the idea behind this solution of F

90126141

»
4 years 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. =)

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

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

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

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

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

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

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

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

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

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

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

»
4 years 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 ?

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

Tlatoani

who is getting the random t-shirts ?
»
4 years 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?

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

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

1 6 RLLLRR

why does this give 1

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

»
4 years 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?

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

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

can anyone explain reason behind the working of logic in problem c(https://codeforces.net/contest/1392/problem/C) in more detail by taking an example,im not understanding the editorial?

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

    Notice that the last element of the array will be the maximum element in the end of all operaions, so increment the array elements from right to left of array.

    for example in this test case:

    4
    5 3 2 5

    1- a[3]<a[4] do nothing.
    2- a[2]>a[3] increment the segment[3:n] by(a[2]-a[3]) ,now array =[5,3,3,6]
    3-a[1]>a[2] increment the segment[2:n] by(a[1]-a[2]) ,now array =[5,5,5,8]

    now total operations =3.

    Here is my code ,it's very easy to understand it.

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