Keshi's blog

By Keshi, 7 weeks ago, In English

1694A - Creep

Idea: AmShZ

Solution
Implementation

1694B - Paranoid String

Idea: AmShZ

Solution
Implementation

1693A - Directional Increase

Idea: alireza_kaviani

Solution
Implementation

1693B - Fake Plastic Trees

Idea: AmShZ, alireza_kaviani

Solution
Implementation

1693C - Keshi in Search of AmShZ

Idea: AmShZ

Solution
Implementation

1693D - Decinc Dividing

Idea: AmShZ

Solution 1

Thanks to Koosha_Mv

Solution 2
Implementation 1
Implementation 2

1693E - Outermost Maximums

Idea: Keshi

Solution
Implementation

Check out this solution by ecnerwala

1693F - I Might Be Wrong

Idea: AmShZ

Thanks to antontrygubO_o for proof

Solution
Implementation by Um_nik

Thanks to Um_nik

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

»
7 weeks ago, # |
Rev. 3   Vote: I like it +99 Vote: I do not like it

fastest editorial, epiq round, ORZ

I'm a simple man, I upvote this post

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

    In the consequence, you get upvotes too. Hee...hee ..You're amazing and smart both :-)

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

      You commented right under my comment. Hee...hee...you're amazing and smart both :-)

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

        I'm simple man, I will just upvote you're comment right under my comment. :-D

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

          You commented right under his comment again. Hee...hee...you're really smart :-)

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

Great, thoughtful problems. Good job.

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

Great job! Loved the problems, thank you!

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

Is there a proof for Div1C / Div2Е that all edges with min dis are equally beneficial ? I think it is not. In some case it's better to block a way with dis = min if we have another way with the same dis and less count of elements to block in future.

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

    Note that, in the definition of "dis[u]", we are already including the cost of the edges we have to block to get from u to N. So all edges with the same minimum dis are equally beneficial.

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

      why to decrease the degree of a node after visiting it. And why every one doing it in backwards. In the contest i did it from the front and didn't have any intuition on decreasing the degree and ended up getting wrong answer on pretest 16.

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

        Maybe you can think the DAG solution first(aka invent subtask), then it is quite intutive to do it backward.

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

          I agree with this but I don't get why dijkstra works.

          What I wanted to do was to compute the SCC, compress the graph as a DAG and then iterate over the compressed top-sort to do the dp and in each SCC I should propagate the dp value all over the cycles by running the dp n times in each SCC. This will give some $$$O(n^2)$$$ algorithm.

          I think the fact that makes dijkstra work is that each cycle will become "directed", like if we add an edge from each node to the node it gets the answer, there will be no cycles so propagating from the smallest value first should work I guess ?

          Can anyone tell me if I'm correct or provide some better intuition of why it works please ?

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

            First define $$$distance[v]$$$ be the minimum number of operation need to be done to reach vertex $$$n$$$, then every vertex have some non-negative distance.

            Let consider for a vertex $$$v$$$, how do we find the $$$distance[v]$$$?

            assume vertex $$$v$$$ can reach $$$v_1, v_2, v_3, ..., v_k$$$(sorted by distance in increasing order), then it is obvious that if you want to reach $$$v_i$$$, you need to block all vertex whose distance is greater than $$$v_i$$$, so you need to block $$$k - i$$$ edges to guarantee reaching $$$v_i$$$.

            So you can think this as there has an edge whose weight is $$$k - i + 1$$$ from $$$v$$$ to $$$v_i$$$, then the problem can be reduced as a well-known problem: "Given a directed graph, all edge have some positive weight, find the minimum distance from $$$n$$$ to $$$1$$$", but with a little twist: "you won't know the weight of edges until you calculate it."

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

              Thanks a lot ! That's super clear :D

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

              But I saw this problem as follows "when ever u want to move forward in original graph(not in rev_graph) let's say from u-v , then you need to remove all the edges that are going from 'u' to some other node except all the multiple edges that are between u-v because we can use a random operation once to get there and I did it untill I reach node n without removing any edge. It seems intuitive to me but I saw this is not optimal why it is happening.here is the link to my solutionYour text to link here... . Here dp[i] stores min op to reach I from 0 and dp[n-1] is the ans.

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

                you don't need to block edges that make you reach some vertex whose distance to $$$n$$$ is shorter than $$$v$$$, because reaching these vertex will only make the answer better.

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

                  Ohh, while moving forward if we know any forward edge has less dp val we use it first so while moving forward let's say if we go from u-v we have to know dp values of all 'v' nodes and their order based on dp values. That is reason why we do it from backwards, And we use dijkstra because it gives order of nodes 'v' based on lower dp values, And the reason to remove edges was to, while moving from lesser dp values to higher of all 'v' nodes we don't consider previous edges in this operation because it gives min ans.you( __Shioko ) explained that it in very nicely with one simple observation very very thankful to you. I explained it elaborately because someone having similar idea like me and struggling to understand probably would get some help.

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

        multiple edges,and you can't use set to delete it.

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

          multiset is not working as well, i dont know why

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

          Could you please elaborate with an example. I still don't get idea of why removing edges benefits us.

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

            in the sample input 2 , if you try to expand from node 4 you will first go to node 1 with dist 3 .and you decrease the degree of node 1, then you can go to node 1 in another edge from 4 to 1 with dist 2.

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

              Thanks to your efforts, I understood my errors and explained my wrong thought process and explained how to correct it, to get it accepted in my comment above this one.

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

woah! thanks for super-fast tutorial!

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

I originally posted this under the round announcement but perhaps it's better to post it here:

Thanks for this great div2 round !

I think the difficulty curve was a bit messy BUT the problems were interesting

Here is my feedback on each of the problems because I think it can be valuable to authors to know what people thought about the problems

A
B
C
D
E
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the last statement in Div2B solution to me in simpler worda? Im unable to understand why we should add r-1 to the answer

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

    Let's introduce the "eating" idea

    01 -> 1, that means 1 can eat 0 (the 1 is kinda "eating" the 0 to its left)

    10 -> 0, that means 0 can eat 1 (the 0 is kinda "eating" the 1 to its left)

    Say you consider the blocks of consecutive same numbers

    [0...0][1...1][0...0][1...1]

    Each block can eat the block right to its left. This way, only the last block will survive at the end of the process. So we need the last block to be of size 1

    What they say in the editorial is that they fix the right border of the substring (call it $$$r$$$), now if the char is the first of its block, all the substrings having their left border to the left of $$$l$$$ will be paranoid (because of what I explained earlier) and there are $$$r - 1$$$ such left border (we do $$$-1$$$ because we don't want to consider the case $$$l = r$$$ as we handle it separately by adding $$$n$$$ to the answer).

    For example if you fix $$$r$$$ to be 3, the left border can be $$$1$$$ or $$$2$$$ so you have $$$3 - 1 = 2$$$ ways of choosing it.

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

      I tried this 'eating' approach (160867965). While I don't understand it completely, it seemed to work with the testcases in the problem and few others that I made. It failed the longest testcase so I'm assuming it's overflowing? I tried to find small counterexamples on cfstress but it didn't help. Could you kindly tell me if my approach is correct or not?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        $$$ long \ long = int \times int$$$

        does not prevent overflows.

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

          and I learn a new thing. Gosh, I wasted so much time over this. It passed (160900152) Thanks!

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

        it gets AC by using long long everywhere 160900072

        If you have any question about things that aren't clear don't mind to ask me

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

      Can you give some problems that uses this eating concept

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

        Hey! I think that's not some general concept, the key idea is just to try to get familiar with the operations described and to see them in some intuitive way.

        I suggest you to read this amazing blog by Everule. I solved the 2nd problem of the blog using that kind of intuition.

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

      Really nice explanation. I was not able to understand the solution when I read the editorial but after reading your comment I completely understood the approach. Thanks

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

    If it ends on different numbers, then it works. So, all substrings starting from $$$i=1$$$ to $$$r-1$$$ and ending in $$$r$$$ need to be counted, and we add the $$$r-1$$$ options to $$$ans$$$.

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

Loved this round!

Here's my solution for div1E (could be the same, but the interpretation seems different). Consider numbers by increasing, suppose we have considered all numbers up to $$$x$$$ (all the rest are $$$0$$$ for now). Suppose we now place $$$a_i = x + 1$$$ at an empty position. We define $$$L_i$$$ and $$$R_i$$$ as the smallest number of operations to get $$$a_i$$$ to zero if we start with the left/right relaxation respectively. At this stage we can consider all $$$i$$$ such that $$$a_i$$$ is actually $$$x + 1$$$, and add $$$\min(L_i, R_i)$$$ to the answer. Note that initially $$$L_i = R_i = 1$$$.

How do $$$L_i$$$ and $$$R_i$$$ change when going $$$x \to x + 1$$$? If there are no $$$x + 1$$$'s, we do nothing. Otherwise, for a position $$$i$$$:

  • if there are $$$x + 1$$$'s only to the left of $$$i$$$, then $$$R_i$$$ doesn't change, and new $$$L_i = \min(L_i, R_i) + 1$$$, as we will change $$$a_i = x + 2$$$ to $$$x + 1$$$, and reduce to the previous stage,
  • if there are $$$x + 1$$$'s only to the right of $$$i$$$, then $$$L_i$$$ doesn't change, and new $$$R_i = \min(L_i, R_i) + 1$$$ similar to the above,
  • if there are $$$x + 1$$$'s on both sides, then both new $$$L_i = R_i = \min(L_i, R_i) + 1$$$.

These updates can be done via a segment tree with lazy $$$(\min, +)$$$ matrix multiplication.

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

I couldn't prove the complexity of my accepted solution for div 1D, which seems to be quite different from the official implementations. (Editorial for the task still not out as i write this)

What I did:

First, note that if $$$(x,y)$$$ is a valid pair, then all $$$(a,b)$$$ such that $$$x \le a \le b \le y$$$ are valid, as you can simply remove prefixes and suffixes from the increasing/decreasing subsequences.

Next, we can find the largest $$$y$$$ such that $$$(x,y)$$$ is valid for some $$$x$$$ in $$$\mathcal O(n)$$$ using this. We also note that we can do the same in reverse (i.e. find the smallest $$$x$$$ such that $$$(x,y)$$$ is valid for some $$$y$$$, by simply flipping increasing and decreasing).

Now, we first let $$$x_0 = 1$$$, and find the corresponding maximum $$$y_0$$$. Then we do the reverse starting on $$$y_0+1$$$ and find the least $$$x_1$$$ such that $$$(x_1,y_0+1)$$$ is a valid pair. Note that here $$$x_1 > x_0$$$ must hold as $$$(x_0, y_0+1)$$$ is not valid. Then we just repeat this process, each time finding maximum $$$y_i$$$ for $$$x_i$$$, then finding minimum $$$x_{i+1}$$$ for $$$y_i+1$$$. Do this until $$$y_k=n$$$ eventually and we can simply add up the answer using a loop.

This solution looks like $$$\mathcal O(n^2)$$$ and I could neither prove a better complexity nor come up with any construction that leads to TLE, I wonder if anyone can help think of one (proof or counterexample), thanks a lot :D

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

    I can't prove it very formally.But I have an idea. Assume every time the y become to y + 1, the average mount of x you should calculate is p, such that the answer would be about p*(n-p)*(p+1)*p/2, and this number is less than the situation which all of the array is a Dicinc array, that would have n * (n + 1)/ 2 subarrays. Then it is very easy to find that p would not bigger than n^(1/3), and your algorithm's complexity would be like O(n^(4/3)).I think it is very fast.

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

      Could you explain more on “the answer would be about p*(n-p)*p*(p+1)/2”? Thanks a lot.

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

        What I had wrote is wrong here, and I should removed it but I can't. Sorry for that. The value I shoudl write is (n — p) *(p (p + 1)) / 2, which means you should calculate a p length array for (n — p) times ,and the mount of subarrays of every array is p * (p + 1) / 2.

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

    When we try to generate the Decinc decomposition of an array going left-to-right (or backwards), it is enough to store the following values from the previous position: the minimum possible last value of the $$$inc$$$ if the previous element was placed in the $$$dec$$$, and the maximum possible last value of the $$$dec$$$ if the previous element was placed in the $$$inc$$$ ($$$0$$$/$$$\inf$$$ in cases where the other sequence wasn't started yet, $$$\inf$$$/$$$0$$$ if the previous element couldn't be placed in that sequence). my implementation of this approach

    Let's look at some three consecutive elements such that $$$a < b > c$$$ and at the state of calculating the decomposition left-to-right after $$$c$$$. If $$$c$$$ is in the $$$dec$$$, then the minimum possible last value of the $$$inc$$$ is either $$$a$$$ or $$$b$$$ or $$$\inf$$$ (since it's impossible to place both of them in the $$$dec$$$ and have $$$inc$$$ ending in some different value). If $$$c$$$ is in the $$$inc$$$, then the maximum possible last value of the $$$dec$$$ is either $$$b$$$ or $$$0$$$. So there is a limited number of possible states giving full information on the decomposition up to $$$c$$$ — $$$6$$$, actually less. So there are $$$O(1)$$$ possible right ends for the maximal Decinc segments enclosing $$$a$$$, $$$b$$$, $$$c$$$. Similarly for $$$a > b < c$$$. But when we extend a maximal segment to the right by $$$1$$$, the new maximal segment gets a new such chainsaw point (otherwise it's trivial to show that the previous segment wasn't maximal to the right), which will be traversed $$$O(1)$$$ times before going out of scope of another maximal segment. Hence the solution works in $$$O(n)$$$.

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

1693A — Directional Increase

I think in the second condition bj==0 should be there instead of bj!=0.

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

Thanks for the superfast editorial

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

I ACed problem D at $$$01:59:45$$$ . The adrenaline rush was real, I have never felt the the flow of time like today, I could feel every second ticking inside my mind near the end. Thank you for this round.

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

Alternate (I think) solution for 1D briefly:

An array is decinc if there is some $$$(k, x)$$$ such that when you split the array into quadrants based on whether $$$j \leq k$$$ and on whether $$$p_j \leq x$$$, then the quadrant with $$$j \leq k$$$ and $$$p_j \leq x$$$ and the quadrant with $$$j > k$$$ and $$$p_j > x$$$ is increasing, and the other two quadrants are decreasing.

For a fixed $$$k$$$, we can see that there are basically three choices of $$$x$$$ we need to consider: two where $$$p_k$$$ and $$$p_{k + 1}$$$ are on the same side of $$$\leq x$$$, and one where they're on the different side.

The value from this approach is that for a certain $$$(k, x)$$$, the furthest to the left of $$$k$$$ you can go is independent from the furthest to the right of $$$k$$$ you can go. So for each $$$(k, x)$$$, we want to calculate these furthest left and right endpoints based on the increasing/decreasing constraints.

I did this by maintaining binary search trees containing points where the increasing/decreasing constraints are violated for each of the halves $$$\leq x$$$ and $$$> x$$$, moving $$$x$$$ from $$$0$$$ to $$$n$$$. Unfortunately this part had very high constant factor and TLEd in Kotlin. My C++ solution ran in about 1 second.

After finding the furthest to the left and right you can get from each $$$(k, x)$$$, we can simply calculate for each left endpoint what the farthest right endpoint we can get is using a linear scan. The overall complexity is $$$O(n\lg n)$$$ (with high constant factor).

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

Div 1 A ~ D are good problems compared to some previous rounds, really satisfied with solving them!

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

Can you explain Div2E in a bit more detail? I don't understand why always choosing the maximum dis_n is correct. It seems possible that dis_n can be updated later by dis_{n'}, where dis_{n'} < dis_{n}.

Is it crucial that all edges are length 1? If the edges are not length 1, would a dijstra-like solution still work?

[update: For the first part I misunderstood the use of priority_queue. For the second part I think the answer is yes, but am interested in solving this variation.]

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

    There seems to be a simple solution: split each edge (u,v,w) (where w is the length) into two segments by introducing an extra vertex y, so that (u,v,w) -> (u,y,0) and (y,v,w). We can run the same dijkstra on this new graph. But since each y has out degree 1, the update for these are trivial. By doing this, it is guaranteed that y will be considered in increasing order of dis_y.

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

In problem 2 & 3, the constraints for n < 10^9, still it gave me wrong answer for using int for input, while it worked with long? Any idea why this happens? TIA P.s i used Java

»
7 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

There were some weak test cases for problem Div2 C, 160878758 this solution fails for the test case

1
2
1 -1

yet is still AC.

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

Great job! Loved the problems, thank you!

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

Div2 problem B was wild...I think the insight to recognize that even if there is one difference, that propagates all the way up the string and "eats" everything before it was a pretty amazing thing to hide.

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

the problems were really well thought!

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

Is this contest unrated?

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

    Just wait. If it was, they would announce it.

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

Can anyone explain div2D / div1B ? I am not able to understand the editorial for this one.

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

    Hey!..Just think in bottom up fashion that if you update the current vertex to max range value(that is r) then every vertex from this to root will have values in decreasing order(going from bottom to up).

    Also we can change our decreasing sequence with any values.So when we reach current vertex and founded all sum of child and If that sum is greater than equal to l means we need no updation because we can somehow bring their value within range.otherwise we need to add the current vertex max range with +1 in counter(as we updated!).

    Thus answer is just counter.

    Submission 160993101

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

Can anyone explain div2D/div1B?

I solved it but I couldn't get Lemma 1 in editorial...

Let's look at example:

3
1 1
2 2
1 1
1 1

I.e. we have a root with two children. Children are required to be in range (1, 1) and the root in range (2, 2).

The minimum number of operations is 2:

  1. Increase by 1 values at vertexes 1 and 2

  2. Increase by 1 values at vertexes 1 and 3

It looks to me that for optimum solution value at root should be increased twice. So it seems to me the Lemma 1 is not hold.

It would be great to get clarification.

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

    I think it means that each node will only be the end of a single path (but may be in the middle of multiple paths)

    The way I solved it was to realise that every leaf node will have a single path back to the root and each of those paths would start by returning leafenode.r. Any nodes in the middle of the path will return as much as possible (node.v = min(node.r, sum(node.children.v))) towards the root. If sum(node.children.v) is less than node.l then we need to add an extra path from the root to that node and return node.r towards the root.

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

Great problems! Credits to authors

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

In div1 C I don't get why you can't do dijkstra starting from node 1? I am getting WA on testcase 16 when doing it. It seems also that most people have solved it staring from n..

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

    Consider the following test:

    4 4
    1 2
    2 4
    1 3
    3 4
    

    The answer is 2, by using the move operation two times, but your code outputs 3.

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

      I see. Thanks!

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

      Could you plz explain why starting from 1 will get WA, while starting from n can find out the correct answer? I didn't get that :(

      Actually, I made some testcases that can hack my program(starting from 1). But I don't know why it can be correct to start from n.

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

    can u explain significance of array d used in editorial in div1 c. I am not able to understand.

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

Can someone explain the proof of the claim "It's trivial that we only sort with segments with balance 0" in the editorial of Div1 F? This does not seem trivial to me. Apologies if I am missing something very simple.

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

    proof of this: suppose that 0s are more than 1s. if the first character of the interval is 0, delete it, otherwise we have a prefix with equal 0s and 1s, and after performing a operation on it, the first character will be 0, and we can delete it. so we can reach our goal by operations with equal numbers 0 and 1.

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

      I understand now, thank you! By the way, I think this is definitely a nontrivial (and interesting) proof. Maybe you should consider adding this to the editorial?

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

        Yes, it's better to add.

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

        It seems the construction is also the final solution

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

I believe you mean 2143-avoiding permutations for D problem, not 2134

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

nice

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

In div1 C $$$\newline$$$ Why bottom up dp on dfs doesn't work 160881231

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

    Take a look at Ticket 12523 or Ticket 12520 from CF Stress for a counter example.

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

      Thanks found my mistake. $$$\newline$$$ What i was doing was applying dp on dfs of directed graphs which is nothing more than dp on the topological sort of the directed graphs. Since topological sort does not exist on directed graphs with cycles hence we can't apply this. Dijkstra is the only option left.

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

        Could you please explain why dijkstra works here ? I don't clearly see why it would work and the editorial doesn't seem to explain it.

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

          At each step keshi would choose worst possible road, so optimal solution should be keeping minimum distance roads and blocking the rest, as stated in the editorial. $$$\newline$$$ So let's look from the perspective of the cities to which keshi will reach, any particular cities will be chosen only if it's distance is minimum compared to other cities. $$$\newline$$$ So we essentially want to sort them according to their distance, which is exactly what dijsktra does. $$$\newline$$$ Instead of 1 as source node, n can be taken as source node and dijsktra can be used to search for shortest path to 1st node.

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

Can I get more explanation about find_3412?

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

    an $$$O(n\log n)$$$ approach:

    for each $$$l$$$ , find maximum $$$r$$$ within $$$[l, r]$$$ is decinc using two-pointers

    for 3412 case, if $$$[l, r - 1]$$$ is already decinc, then the situation of $$$[l, r]$$$ only depends on whether it's possible to find a 3412-tuple which the 2-element corresponds to $$$a_r$$$

    suppose $$$f_r$$$ represents the largest index $$$i < r$$$ which $$$a_i < a_r$$$ ,it's optimal to choose $$$a_{f_r}$$$ as the 1-element

    suppose the 3-element is fixed with some element $$$a_k$$$, then it's optimal to choose $$$a_{g_k}$$$ as the 4-element where $$$g_k$$$ represents the smallest index $$$i > k$$$ which $$$a_i > a_k$$$

    if in the range $$$[l, r]$$$ there exists some element $$$a_k > a_r$$$ and $$$g_k < f_r$$$ ,then $$$[l, r]$$$ is not decinc since $$$a_k, a_{g_k}, a_{f_r}, a_r$$$ form a 3412-tuple

    to check the existence of $$$a_k$$$ ,for each $$$a_k$$$ we put a pair $$$(a_k, g_k)$$$ into a sequence , sort all the pairs by $$$a_k$$$ increasing and check whether the minimum $$$g_k$$$ among a suffix of the pair sequence is smaller than $$$f_r$$$

    arrays $$$f$$$ and $$$g$$$ could be pre-computed

    during the tow-pointers process , using some data structures like segment trees to maintain the sorted sequence to support insertion/deletion of elements while moving pointer $$$[l, r]$$$

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

Here is a solution to E that only involves binary indexed tree/order statistic set (insert-value and range-count).

As the editorial states, we can greedily move each maximum to the smaller of the max on the left and the max on the right. Let's simulate this process efficiently. We'll go from highest values downwards. Note that, at a single current max value, there may be several different values that our maxes get set to, so we can't naively simulate this process. Instead, we'll instead just mark all current values as "to set to smaller of left-max or right-max".

Then, as we continue processing, when we process a current value which occurs to the right of something marked as "to set to smaller of left-max or right-max", we change the mark to "to set to left-max" (and likewise on the left side). If we process a current value which occurs to the left of something marked as "to set to left-max", then, we must set it to exactly the current value; then, we can add it to the cost and treat it as "to set to smaller of left-max or right-max".

At any point in this process, the "active" elements (ones with marks) are just all elements bigger than the current value. Also, we can verify that the elements marked "to set to left-max" are a prefix, and the elements marked "to set to right-max" are a suffix. Thus, we can just maintain the cutoff indices between our three types of marked elements, and use a BIT/order statistic set to count how many "active" nodes need to move.

This solves the whole problem in $$$O(n \log n)$$$ with very little code. 160890042

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

Got Stuck in 'B' after a long time. The problems were great!✔️

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

Fastest editorial with the fastest rating tags.

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

I tried to solve the problem B with DP but it went to memory limit exceeded T_T

All my efforts were put to waste but nvm ill try my best next time again

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

For B, I literally guessed the solution, and I have no idea why it works. Can anyone here explain it?

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

Are there any problems similar to Div2B and Div2C? I think i need to practice more those kind of problems. Thank you.

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

guys, please help me understand the problem A. i didnt understand problem A properly because im weak in english. 'Define the creepiness of some binary string S as the maximum score among all of its prefixes' is this mean [i...n] or [1...i] or are both wrong?

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

    Prefixes in Problem-A refer to S substring starting from 1 that is [1...i] where 1<=i<=n.

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

Can someone explain why in div2 C if we carry out the operation of continuously increasing A(i) with decreasing A(i+1) instead of any other index will ensure a correct answer.

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

can you please explain how to solve the problem by taking an example with intution/proof ?https://codeforces.com/contest/1221/problem/C (not of this contest)

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

Why are we using dijkstra in Div2E. can anyone please give point by point explanation for div2E.

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

The proof idea of div1D/div2F solution2:

It's trivial that if an array is Decinc, it must be $$$3412$$$-avoiding and $$$2143$$$-avoiding.

To prove the other side, we can use strong induction on the number that the array has by considering the biggest element in the array.

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

Interesting 1C and 1D,tks.

»
7 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

For 1963C,I try to use an algorithm we called SPFA to solve it.SPFA can be so slow and what i have written cound be much slower.But unexpectedly,it was accepted.MAybe the data should be much stronger.Looking forward to a hack or a proof of its correctness.

See my submission here! 160873008

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

Div2E is kinda awesome. I really liked this problem.

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

    Why are we using dijkstra in Div2E. can u please give point by point explanation for div2E.

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

      Let $$$dist(u)$$$ be the minimum operations needed to reach node $$$n$$$. Obviously, $$$dist(n)=0$$$ (As in editional). Now consider we want to go node $$$n$$$ from $$$u$$$ via some adjacent node $$$v$$$, then we have to block every edge which leads to the node $$$w$$$ whose distance value is larger than that of $$$v$$$, i.e. $$$dist(w)>dist(v)$$$. In this case, the number of operations needed to reach node $$$n$$$ from $$$u$$$ is $$$dist(v)+f_u(v)+1$$$ where $$$f_u(v)$$$ is the number of adjacent edges which leads to nodes whose distance value larger than that of $$$v$$$. Additional plus one is the cost of going through the edge. Considering every adjacent node of $$$u$$$, we can derive the formula:

      $$$dist(u)=\min_{v \in_{N(u)}}(dist(v)+f_u(v)+1)$$$

      If we think the term $f_u(v)$ as weight of edge passing through $$$u$$$ to $$$v$$$, we can reduce the problem to find single source shortest path in the weighted reversed digraph $$$G$$$ but the weights are unknown (but fixed). So we can use the dijkstra algorithm. But how do we know the shortest path length when we don't know the weight of edges until we actually investigate them? Actually, we know in the action of the algorithm. Suppose we are at the $$$i$$$th iteration of the dijkstra algorithm and we already know the distance values of marked nodes. Suppose we picked some unmarked node $$$v$$$. Of course we know that $$$dist(v)$$$ is minimum among unmarked nodes. Now we want to efficiently calculate contributions of $$$dist(v)$$$ to the nodes adjacent to $$$v$$$ (Note that we are considering reversed digraph). But how do we know the value of $$$f_u(v)$$$ for each adjacent nodes of $$$v$$$? If we maintain for each node $$$u$$$ how many edges are there which leads to the unmarked node so far (let us call them $$$d_{+}(u)$$$), we can easily calculate the value of $$$f_u(v)$$$ because it is just equal to $$$d_{+}(u)$$$. Why this is true is that every node we marked so far obviously has smaller distance value than $$$dist(v)$$$ and every unmarked node we will mark in next iterations can never have distance value less than $$$dist(v)$$$. Thus, all we have to do is maintain $$$d_{+}(u)$$$ and decrease by one if we investigate it in relaxation step. (Sorry my English is poor so it can be very hard to read 0_0)

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

Hi, can someone explain to me for C, why does the sum of all elements have to be equal to zero?

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

    The number at index i is increase when moving away to the right. The number at index i is decreased when moving away to the left. Let A represent the number of times the pointer moves right. Let B represent the number of times the pointer moves left. For the pointer to end up at index 1, this must be true: A==B because moving to the right A times requires moving to the left B times. Every right move is +1. Every left move is -1. So A-B=0, the sum of elements is 0.

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

Keshi in Search of AmShz

Please someone simplify the idea of solving above problem. I can't figure out- how we are avoiding cycles? how we are updating the answer with min_distance but at the end we still got the largest path from 1 to N?

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

Can someone please suggest a simpler solution to div1B or the solution in the editorial is the simplest one? I didn't get why a 1k7-rated problem could be such hard, or maybe it requires using some popular ideas that I haven't known yet. Tysm

»
7 weeks ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it
Let i be the smallest such that numbers from a_i to an increase.

shouldn't be ...?

Let $$$i$$$ be the smallest such that numbers from a_i to $$$a_n$$$ increase.

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

Is there any way to solve Div2 E with SCC, (after compressing graph with strongly connected component)

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

In Div2 E, why to decrease the degree of a node after visiting it??

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

Nice contest, loved the problems. Also, it seems like the authors are die hard Radiohead fans.:)