Keshi's blog

By Keshi, 2 years 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

| Write comment?
»
2 years 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

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

Great, thoughtful problems. Good job.

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

Great job! Loved the problems, thank you!

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

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

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

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

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

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

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

              Thanks a lot ! That's super clear :D

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

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

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

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

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

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

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

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

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

woah! thanks for super-fast tutorial!

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

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

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

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

      Can you give some problems that uses this eating concept

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

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

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

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

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

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

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

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

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

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

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

»
2 years 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.]

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

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

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

Great job! Loved the problems, thank you!

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

Is this contest unrated?

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

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

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

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

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

Great problems! Credits to authors

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

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

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

      I see. Thanks!

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

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

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

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

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

        Yes, it's better to add.

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

        It seems the construction is also the final solution

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

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

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

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

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

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

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

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

Can I get more explanation about find_3412?

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

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

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

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

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

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

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

Interesting 1C and 1D,tks.

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

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

Div2E is kinda awesome. I really liked this problem.

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

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

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

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

»
2 years 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)

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

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

This is problem C.Can anyone tell me which test case is failing

include<bits/stdc++.h>

define ll long long

define ld long double

using namespace std; /* " I AM VENGEANCE , I AM THE NIGHT , I AM THE BATMAN ! " ____ __ __ __ __ __ ___ _ __ __ __ __ __ ____ -._: .:'::: .:\ |__/| /:: .:' ::: .:.-' \ : \ |: | / : / \ :: .-_____/ :: _______-' . :: . / | : :: ::' : :: ::' : :: ::' :: ::' : :: :| | ;:: ;:: ;:: ;:: ;:: | | .:' ::: .:'::: .:' ::: .:'::: .:' :| / : : : : : \ /______::_____ :: . :: . :: _____._::____\ ----._:: ::' : :: ::' _.----' --. ;:: .--' -. .:' .-' \ / \ / \/ */ //Number to string-->string s=to_string(a); //String to number-->ll a=atoi(s.c_str());

//3D vector of dimension 2*2*3 with all elements as 1 // vector<vector<vector > > vect3d(2, vector<vector > (2,vector(3,1)));

//Binary Search for desired position

// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k){ // return mid; // } // else if(arr[mid]>k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }

//Binary Search for index of first occurance of k

// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k && (mid==0||arr[mid-1]!=k)){ // return mid; // } // else if(arr[mid]>=k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }

//Binary Search for index of last occurance of k

// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k && (mid==n-1||arr[mid+1]!=k)){ // return mid; // } // else if(arr[mid]>=k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }

// bool comp(pair<ll,ll>p1,pair<ll,ll>p2){ // if(p1.first<p2.first){ // return true; // } // if(p1.first==p2.first){ // if(p1.second<p2.second){ // return true; // } // } // return false; // }

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll t; cin>>t; while(t--){ ll n; cin>>n; ll sum=0; ll arr[200003]; for(int i=0;i<n;i++){ cin>>arr[i]; sum=sum+arr[i]; } if(sum!=0){ cout<<"No"<<endl; continue; } if(arr[0]<0){ cout<<"No"<<endl; continue; } ll point=n; //Do check if all are zeros or not(Boundry Condition) bool snake=false; for(int i=0;i<n;i++){ if(arr[i]!=0){ snake=true; } } if(!snake){ cout<<"Yes"<<endl; continue; } for(ll i=n-1;i>=0;i--){ if(arr[i]!=0){ point=i; break; } } for(ll i=1;i<=point;i++ ){ arr[i]=arr[i]+1; } bool poke=true; ll c=-arr[0]+2;

for(ll i=1;i<point;i++){ if(arr[i]<c){ poke=false;

} else{ c=-(arr[i]-c)+1;

} }

if(poke){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } }

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't read this. Can you post it better in the form of a donut?

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

In 1694B-Paranoid string why should we add i when s[i]!=s[i-1]?