### Keshi's blog

By Keshi, 8 months ago,

Idea: AmShZ

Solution
Implementation

Idea: AmShZ

Solution
Implementation

### 1693A - Directional Increase

Idea: alireza_kaviani

Solution
Implementation

### 1693B - Fake Plastic Trees

Idea: AmShZ, alireza_kaviani

Solution
Implementation

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

• +471

 » 8 months ago, # | ← Rev. 3 →   +99 fastest editorial, epiq round, ORZI'm a simple man, I upvote this post
•  » » 8 months ago, # ^ |   +6 In the consequence, you get upvotes too. Hee...hee ..You're amazing and smart both :-)
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +28 You commented right under my comment. Hee...hee...you're amazing and smart both :-)
•  » » » » 8 months ago, # ^ |   +6 I'm simple man, I will just upvote you're comment right under my comment. :-D
•  » » » » » 8 months ago, # ^ |   -28 You commented right under his comment again. Hee...hee...you're really smart :-)
 » 8 months ago, # |   +22 Great, thoughtful problems. Good job.
 » 8 months ago, # |   +22 Great job! Loved the problems, thank you!
 » 8 months ago, # |   +2 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.
•  » » 8 months ago, # ^ |   +13 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.
•  » » » 8 months ago, # ^ |   +5 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.
•  » » » » 8 months ago, # ^ |   0 Maybe you can think the DAG solution first(aka invent subtask), then it is quite intutive to do it backward.
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » » » » » 8 months ago, # ^ |   +28 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."
•  » » » » » » » 8 months ago, # ^ |   0 Thanks a lot ! That's super clear :D
•  » » » » » » » 8 months ago, # ^ |   0 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.
•  » » » » » » » » 8 months ago, # ^ |   +4 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.
•  » » » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » 8 months ago, # ^ |   0 multiple edges,and you can't use set to delete it.
•  » » » » » 8 months ago, # ^ |   0 multiset is not working as well, i dont know why
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Could you please elaborate with an example. I still don't get idea of why removing edges benefits us.
•  » » » » » » 8 months ago, # ^ |   +3 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.
•  » » » » » » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   +12 woah! thanks for super-fast tutorial!
 » 8 months ago, # | ← Rev. 2 →   +26 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 interestingHere 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 AGood problem A, not an a+b problem but not an impossible problem either. BI had the right observation instantly (that there is some sort of "eating" relation that is directed from right to left but I spent a lot of time to actually see that it worked. The problem was great but it could have been better as a div2 C (I think the C was better as B) ? Anyway, I liked B a lot, very cute observation CThe samples kinda spoil the problem (the explanations on how to get the 2 -1...sequence shows that you can do everything with "left/right" moves and then it's just about simulating the process). That's why I think it would have been a better problem as div2 B. Still a nice problem though (but not as good as the others). DThe problem is really interesting and educative but it's perhaps a bit too easy as a div2 D. I think it would fit nicely as div2 C or edu D (but my advice might be completely fucked up). EI didn't success in making my DP work for cycles (I had some O(N^2) by splitting in strongly connected components though). Some people said that using dijkstra to do "implicit topsort" or whatever it's called is standard but I never saw this after solving a lot of standard problems (including some more OI style problems)...In my opinion, it's a beautiful problem showing an interesting trick, congrats to the authors!!
 » 8 months ago, # |   0 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
•  » » 8 months ago, # ^ | ← Rev. 6 →   +10 Let's introduce the "eating" idea01 -> 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.
•  » » » 8 months ago, # ^ |   0 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?
•  » » » » 8 months ago, # ^ |   +6 $long \ long = int \times int$does not prevent overflows.
•  » » » » » 8 months ago, # ^ |   0 and I learn a new thing. Gosh, I wasted so much time over this. It passed (160900152) Thanks!
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   0 it gets AC by using long long everywhere 160900072If you have any question about things that aren't clear don't mind to ask me
•  » » » 8 months ago, # ^ |   0 Can you give some problems that uses this eating concept
•  » » » » 8 months ago, # ^ |   0 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.
•  » » » » » 8 months ago, # ^ |   0 okay,thanks
•  » » » 8 months ago, # ^ |   0 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
•  » » 8 months ago, # ^ |   0 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$.
 » 8 months ago, # |   +83 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.
 » 8 months ago, # |   +74 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 Code160875853 (Ignore the few lines of template)
•  » » 8 months ago, # ^ | ← Rev. 2 →   +18 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.
•  » » » 8 months ago, # ^ |   0 Could you explain more on “the answer would be about p*(n-p)*p*(p+1)/2”? Thanks a lot.
•  » » » » 8 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   +10 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 approachLet'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)$.
 » 8 months ago, # |   +20 1693A — Directional IncreaseI think in the second condition bj==0 should be there instead of bj!=0.
•  » » 8 months ago, # ^ |   +23 Thanks!
 » 8 months ago, # |   0 Thanks for the superfast editorial
 » 8 months ago, # | ← Rev. 2 →   +4 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.
 » 8 months ago, # |   +36 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).
 » 8 months ago, # |   +38 Div 1 A ~ D are good problems compared to some previous rounds, really satisfied with solving them!
•  » » 8 months ago, # ^ | ← Rev. 2 →   +8 Is your comment related to your rating changing?
 » 8 months ago, # | ← Rev. 2 →   +9 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.]
•  » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   0 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
 » 8 months ago, # | ← Rev. 2 →   -8 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.
 » 8 months ago, # | ← Rev. 2 →   +29 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).
 » 8 months ago, # |   +3 Great job! Loved the problems, thank you!
 » 8 months ago, # |   0 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.
 » 8 months ago, # |   0 the problems were really well thought!
•  » » 8 months ago, # ^ |   0 Hello, my doppelganger !!!
 » 8 months ago, # |   0 Is this contest unrated?
•  » » 8 months ago, # ^ |   0 Just wait. If it was, they would announce it.
 » 8 months ago, # |   0 Can anyone explain div2D / div1B ? I am not able to understand the editorial for this one.
•  » » 8 months ago, # ^ |   0 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
 » 8 months ago, # |   0 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: Increase by 1 values at vertexes 1 and 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.
•  » » 8 months ago, # ^ |   +2 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.
 » 8 months ago, # |   0 Great problems! Credits to authors
 » 8 months ago, # |   0 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..
•  » » 8 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 8 months ago, # ^ |   0 I see. Thanks!
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 8 months ago, # ^ |   0 can u explain significance of array d used in editorial in div1 c. I am not able to understand.
 » 8 months ago, # |   0 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.
•  » » 8 months ago, # ^ |   +8 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.
•  » » » 8 months ago, # ^ |   +18 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?
•  » » » » 8 months ago, # ^ |   +8 Yes, it's better to add.
•  » » » » 8 months ago, # ^ |   0 It seems the construction is also the final solution
 » 8 months ago, # |   0 I believe you mean 2143-avoiding permutations for D problem, not 2134
•  » » 8 months ago, # ^ |   0 You are right. Will be fixed.
 » 8 months ago, # | ← Rev. 3 →   0 nice
 » 8 months ago, # |   +3 In div1 C $\newline$ Why bottom up dp on dfs doesn't work 160881231
•  » » 8 months ago, # ^ | ← Rev. 2 →   +7 Take a look at Ticket 12523 or Ticket 12520 from CF Stress for a counter example.
•  » » » 8 months ago, # ^ |   +7 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.
•  » » » » 8 months ago, # ^ |   0 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.
•  » » » » » 8 months ago, # ^ |   +11 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.
 » 8 months ago, # |   +8 Can I get more explanation about find_3412?
•  » » 8 months ago, # ^ |   +20 an $O(n\log n)$ approach:for each $l$ , find maximum $r$ within $[l, r]$ is decinc using two-pointersfor 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-elementsuppose 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-computedduring 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 months ago, # ^ |   0 Thanks, this is my understanding: 161348650
 » 8 months ago, # |   +126 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
 » 8 months ago, # |   0 Got Stuck in 'B' after a long time. The problems were great!✔️
 » 8 months ago, # |   0 Fastest editorial with the fastest rating tags.
 » 8 months ago, # |   0 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
 » 8 months ago, # |   0 For B, I literally guessed the solution, and I have no idea why it works. Can anyone here explain it?
 » 8 months ago, # |   0 Are there any problems similar to Div2B and Div2C? I think i need to practice more those kind of problems. Thank you.
 » 8 months ago, # |   0 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?
•  » » 8 months ago, # ^ |   0 Prefixes in Problem-A refer to S substring starting from 1 that is [1...i] where 1<=i<=n.
•  » » » 8 months ago, # ^ |   0 thank you!
 » 8 months ago, # | ← Rev. 2 →   0 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.
 » 8 months ago, # | ← Rev. 2 →   0 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)
 » 8 months ago, # |   +3 Why are we using dijkstra in Div2E. can anyone please give point by point explanation for div2E.
 » 8 months ago, # | ← Rev. 2 →   +33 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.
•  » » 8 months ago, # ^ |   +21 Isn't it Div1D?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +18 Thanks, it's correct now.
 » 8 months ago, # |   +1 Interesting 1C and 1D,tks.
 » 8 months ago, # | ← Rev. 3 →   +8 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
 » 8 months ago, # |   +9 Div2E is kinda awesome. I really liked this problem.
•  » » 8 months ago, # ^ |   0 Why are we using dijkstra in Div2E. can u please give point by point explanation for div2E.
•  » » » 8 months ago, # ^ | ← Rev. 4 →   +20 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)
 » 8 months ago, # |   0 Hi, can someone explain to me for C, why does the sum of all elements have to be equal to zero?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
 » 8 months ago, # |   0 Keshi in Search of AmShzPlease 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 months ago, # |   0 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 months ago, # | ← Rev. 3 →   +10 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.
•  » » 7 months ago, # ^ |   +15 Thanks!
 » 7 months ago, # |   0 Is there any way to solve Div2 E with SCC, (after compressing graph with strongly connected component)
 » 7 months ago, # |   0 In Div2 E, why to decrease the degree of a node after visiting it??
 » 7 months ago, # |   0 Nice contest, loved the problems. Also, it seems like the authors are die hard Radiohead fans.:)
 » 4 months ago, # |   0 Div2B: Is there a way to extract test 8 input data?Having trouble understanding why 174865970 could fail.(Should not be overflow, Integer is an arbitrary-length integer type.)
»
4 months ago, # |
-8

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

# 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; } } }

 » 3 months ago, # |   0 In 1694B-Paranoid string why should we add i when s[i]!=s[i-1]?
 » 3 days ago, # |   0 why did we add r — 1 to the answer??