# | User | Rating |
---|---|---|

1 | Benq | 3797 |

2 | tourist | 3723 |

3 | Radewoosh | 3720 |

4 | ecnerwala | 3579 |

5 | ksun48 | 3463 |

6 | Um_nik | 3457 |

7 | maroonrk | 3446 |

8 | jiangly | 3432 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 209 |

2 | awoo | 184 |

3 | rng_58 | 183 |

4 | Errichto | 181 |

5 | maroonrk | 176 |

5 | Radewoosh | 176 |

5 | SecondThread | 176 |

8 | -is-this-fft- | 175 |

9 | Um_nik | 171 |

10 | antontrygubO_o | 167 |

I hope everyone enjoyed the contest!

UPD: Added implementations for all problems.

Author: antontrygubO_o

Tutorial is loading...

Author: hugopm

Tutorial is loading...

Author: Kuroni

Tutorial is loading...

Author: Maripium

Tutorial is loading...

Author: hugopm

Tutorial is loading...

Author: Ari

Tutorial is loading...

Author: 1-gon

Tutorial is loading...

Tutorial of Codeforces Round #668 (Div. 1)

Tutorial of Codeforces Round #668 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2021 07:58:37 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Thanks for a good round and fast editorial!

Thanks for a good round and fast editorial!

I had to google how during the contest and actual real-life trees kept popping up lol

smh this guy didn't do the tree basics set, what a cyan...

Can't do the tree basics set if it isn't open for virtualing yet :/

The problems should all be publicly available, but how do I open it for VP?

This should come up in the "Edit" tab of the contest (I think)

Here's what I see:

On the same page, there's also this, which should do the trick

What do you mean by "on the same page"? I literally just posted what the page looks like for me and that isn't there.

Doesn't it already say that, in case the visibility isn't private, the following will be set to defaults, where "virtual allowed: yes" is in the list

UPD: Btw, I am able to click on "virtual participation" under the contest, and it asks me to register. So, I'd say it's some issue on ScarletS's side.

I'm just a cyan with a good keyboard tbh, will watch your vids later tho :)

I only got AC because I saw your video and reused the code that I submitted for your contest. You are a prophet orz

I got the diameter idea just because I did those gym questions. Thanks!

Hi, I believe that it is not necessary to use binary lifting for problem d1C. We could use a segment tree of pairs (v, -index), and do a range minimum value on this.

This will automatically tiebreak for the larger-indexed nodes to come first.

Edit: Thanks for the round, the problems were interesting!

Yup it's true, a lot (including me) solved it like this. However, the tutorial's solution can be implemented using only Fenwick tree, and we feel like it's more beautiful to include such a solution.

can u explain more how can we do that? i seen your submission when u take query why u have change your b to N-b

I’ll assume you mean why I insert the value

`v=mp(s-A[s],-s)`

as your question.The reason why the first value of the pair is

`s-A[s]`

is as stated in the editorial. When we query, to prevent numbers from going below zero, we would like to find the maximum index that is zero. Since c++ compares values by the first digit, then second digit, and that we have a minimum value segment tree, we acquire the maximum index by inserting -s as the tiebreaker. This means the largest index is reflected as the minimum value.Hope this helps!

STRONG PRETESTS

nice problems

agree

ty

deleted

Good problems! Congrats on great round!

In the tutorial of tree tag in case 1 why are we saying that alice tags bob in the first move? Did the question mean that even if alice and bob share a vertex once ..alice wins??But i don't think it was mentioned as such??Can u please answer[user:Monogon]

The statement said in at most 10^100 moves, meaning Alice can win before that many moves are done. I hoped the explanation of sample 1 would make this clear. Sorry that the statement wasn't more clear about it.

I got confused by the last line saying that if after 10^100 moves they occupy the same place. Thanks for the clarification. Great round.

My Code using Vectors gave Runtime on Test 4 while the

Samecode using Array Passed!Someone please help?

Edit: Got it

You call

`v.clear()`

after every test, which means your`f(i,0,k+1) v[i]=""`

and so forth only work for the first test. After that it's UB / crash. See 92079157.Oh! Got it Thanks!

Now I'm wondering how it

worked on my local compiler (Sublime Text 3)

passed the first 3 pretests lol

Undefined Behaviour means that anything is possible. Unlike some more programmer-friendly languages, C++ is rather harsh and won't check for things like "out of bounds access" because that would be a waste of time for a correctly-written program (unless you enable the debug mode!).

The first two tests seem to have small sizes of $$$n$$$, and the third one only had one sub-test.

Data in a

`vector`

lives in some block of memory allocated to you by the OS, and it will be at least a couple of kB. It just so happens that this block was large enough to fit the small tests (you were still going out of bounds, but it kinda worked because there was accessible memory there). But when your program tried to reuse over 1 MB of memory that had no longer belonged to it, you were out of luck.OH. I didn't know. Thanks ! :)

That's the best explanation of UB that I have ever seen!

<rant> Ahhhh I got the first 2 cases for D1B / D2D, but didn't expect such as simple algo for 3rd and 4th cases. I guess I need to work on proofs for next time. </rant>

Great contest, hope to see more like it :)

Can someone explain me the meaning of problem Div2.D (Tree Tag). I read it again and again for about one hour and yet could not relate the meaning of the problem.The problem statement is so unclear.

I'll try to explain in graph theory terms.

Alice and Bob are each located at some node in a tree (undirected fully connected graph without cycle). Each edge has length 1.

On Alice's turn, she starts at her current node and can take any walk any path with length

`<=da`

to end up at her next node. On Bob's turn, he does the same (with path length`<=db`

instead of`da`

). Alice wants to end up in the same node as Bob at some finite time. Bob doesn't want to be in the same node as Alice.Print whether Alice reaches same node as Bob or not.

Thanks, I got it now. I thought that for alice to win,alice and bob had to be in thier same respective initial nodes .

The variables used for notation were unclear to me at first as well.

We have a tree T on n vertices. Alice is initially at vertex 'a' of T, and Bob is initially at vertex 'b' of T. Now, Alice has a jump-power of "da" (this da is unrelated to the vertex a, nor is it d*a). da (better written as d_{Alice}) is the maximum distance Alice can jump in one move. Similarly, db (better written as d_{Bob}) is the maximum distance Bob can jump in one move.

Now they take turns jumping from vertex to vertex. In each move, Alice can move from her current vertex (say u) to a vertex v such that

dist(u,v) <= d_{Alice}.

The legal moves for Bob are similar, but with d_{Bob} instead of d_{Alice}

If within 10^{100} moves, Alice can force herself and Bob to be on the same node, then she wins, else Bob wins.

somehow i feel prob B is the hardest :v

Me too :(

No! Easy O(n) Solution

Dude I can read the tutorial now. I didn't ask for your code.

But In a community, no one asks someone(particular person mostly), They gets suggestions or answers from anyone. :)

Can someone explain the editorial of problem B

Explantion Video

thank you

Check out mine 92120083

True :(

Very cool problems! Thank you!

STRONG PRETESTS..

Thanks for a nice round with cool problems.

Please attach codes also

For Div2D, my code mysteriously fails on pretest 9... : https://codeforces.com/contest/1405/submission/92071460. I have the same logic/cases as the editorial, and I calculate the diameter of the tree with two runs of bfs. Any help would be greatly appreciated.

I'm a little bummed because I was so close to solving 4 questions which was my goal for this contest.

I think you forgot to reset

`maxDist`

to 0 between test cases D:EDIT: Oh wait I see you did. I think you might have forgot to reset something, not sure.

Hack case:

I think it should be

`if(2*da+1 >= maxPath) cout << "Alice\n"`

instead of just`if(2*da >= maxPath) cout << "Alice\n";`

My code returns Alice for that test though, which I am pretty sure is correct (she can stand on node 3 and then catch Bob on the next move). Also in the editorial it is 2*da >= diameter (and diameter = maxPath in my code).

I think in

Especially at

`vector<bool> vist(n);`

it should be`vector<bool> vist(n+1);`

instead due to your node was 1 base index.Omg, thank you so much, it got AC. Haha, one missing "+1" derailed my whole solution. Next time I should probably just decrement all the nodes by 1, lol.

Can You please explain to me your bfs2 function?? The diameter of a tree implies the longest common path from one leaf node to another. So how are you calculating that longest path?? Thanks in advance.

https://youtu.be/FQLPNQppBNs

Thanks,it helped me a lot

In addition to the video from AdnanShamsi I think this website has a good explanation: https://medium.com/dev-genius/find-the-largest-distance-between-two-nodes-in-a-tree-a-k-a-diameter-of-the-tree-620e33d7b0d8. You can also replace bfs with dfs (but you have to visit every node regardless, so it doesn't really matter).

Thank you.

The real question is how did your checker for problem D work if they choose to play as the first player? It sounds way easier to solve than to verify...

Ari's comment on the matter.

TLDR: We used bitset dp for small $$$n$$$ and heuristics for larger $$$n$$$.

https://codeforces.com/blog/entry/82288?#comment-691987

idk about all of you.... but I used two pointers and it somehow worked lol

In problem

DIV2(D) Tree Tag, nowhere in the problem statement it is mentioned that if Alice catches Bob then Alice wins or vice versa. I think that the problem statement should be updated! Correct me if I am wrong :)Edit:Finally understood what "If after at most 10^100 moves, Alice and Bob occupy the same vertex, then Alice is declared the winner. Otherwise, Bob wins." means :)Same mistake i also did bro.

It was quite obvious from the above line that Alice will try to catch Bob (occupy the same vertex) and Bob will try to avoid.

Can Anyone tell me Why Did Codeforces compiler gave Run Time Error in my Solution to

Problem B Div 2.My Submission:92070449 while other compilers like https://www.onlinegdb.com/ gave correct answers?I wasted the whole 1 and a half hours to debug this still can't. Can anyone tell me why did it happen?

I just Used Lower Bound to find the position of the lowest index greater than my present positive index and after operation erases it.

Please Help !!!I think itr = -1 causes a problem; what do you do when neg becomes empty?

neg will never become empty because the sum of all elements of array is 0.. So vector pos and neg will become 0 at the same time.

Actually, I printed itr immediately after

auto itr=lower_bound(all(neg),pos[0])-neg.begin(); if(itr>=sl(neg)) itr=sl(neg)-1;

and I did see itr = -1.

Ok, you're right.. When I added if(itr<0) break, the code worked, Thanks for Help !! b/w how did you debugged the code.. When I was trying to print it was giving run time error and I don't know how to use debugger..

You said your code worked on onlinegdb, so I tried it there. It did not give a runtime error there because of how it handles neg[-1], perhaps.

My submission for Div2 D Tree Tag gives

WA on pretest 2.I checked the cases in below order:

If db < 2*a + b. Alice Wins

If distance of Bob from Alice <=

da. Alice Wins.If diameter >= db. Bob wins, otherwise Alice Wins.

Is there anything I'm missing(as per editorial I think not) or my implementation has a bug?

submission : 92063203

In case 3,even if diameter is smaller than db, Bob can win because min(diameter, db) needs to be greater than 2*da.

Got it. Thanks :)

I confused why this solution fails for Div2 D in the pretest 2

The Algo, I am using to get diameter is

Find a leaf node

Do DFS to get the farthest node to it

This node will be one endpoint of diameter

Find second diameter endpoint by doing a DFS again

My Submission

Can someone please help me find the type of input my solution is failing in Div2C. It shows wrong answer on 2343rd case in test case 2.My Solution

would you explain what you are doing in your code?

I'm grouping the characters in the string with respect to their position modulo k. If in any of these groups both O and 1 is present output NO. If only 0 is present add the size of this group to a variable called zero. If only 1 is present then add the size of the group to variable called one. Finally if n is even check and if either one or zero is greater than n/2 answer is NO or if n is odd and either one or zero is greater than n/2 + 1 answer is NO. Else the answer is always YES.

I think your code fails the following case

1 6 4 110011

Your code gives No whereas the answer is Yes. Hope this helps!!!

Oh yeah got it. Thanks a lot.

In problem D is was stated "Note that when performing a move, a player only occupies the starting and ending vertices of their move". Then shouldn't Alice win on his second move when 2 * da >= dist(a, b)?

I think it means that the players 'teleport' instead of walking along the tree

If after at most inf moves, Alice and Bob "occupy" the same vertex, then Alice is declared the winner.

I assumed I have to consider both starting and ending node of one's last move :facepalm:

I think I have superpower, no matter how much time do I have, I can still solve a problem in a minute AFTER the contest ends))

Why didn't this work in div2 D 92059623?

You should use

`2*da >= db`

instead of`2*da > db`

in line no 71.Test case:

Sorry, wrong submission 92060277

`if(*min_element(dp.begin(), dp.end()) <= da)`

I think, this is the bug in your code.Test case:

I confused why this solution fails for Div2 D in the pretest 2

The Algo, I am using to get diameter is

Find a leaf node

Do DFS to get the farthest node to it

This node will be one endpoint of diameter

Find second diameter endpoint by doing a DFS again

My Submission

Really good contest!

Div2 C has appear in earlier Contest on Codeforces itself(k periodic string)

Can yo share the link to that question?

I just don't get it. Why cant I solve problems like today's Div2-B? I mean Mathy questions like these. What should I do to solve such questions? What tags should I solve, or what question types? In fact, what is even this category — Greedy + math, Math, Problem solving?

Any one who was weaker on such problems and now comfortable in them, can you share what you practiced for these?

I am not so bad at CP that I should not even be able to solve it in 2 hours. Its just the approach doesn't strike me. I look at the test cases, develop some method to at least have a functional code for the visible test case then try some cases of my own. Finally when I cant think of any test case that might fail for my code, I submit just to see Wrong answer on Pretest 2. I know this is not the best of the methods but that is just how it happens with me. :(

Some insight please!

Dude, you need to relax. If you try to rush things during the contest you will not solve the problem!!! When you read a problem, 99% of the time you will have no idea how to solve it. But don't panic!!! First thing you should do is to read statement very slowly, identify all details that look important. Then stay away from the computer and take a sheet of paper to try some test cases. Always solve a problem on paper first!!!

You need to be organised with your notes, otherwise you will get confused. Use as much paper as necessary, don't restrict yourself to tiny margins.

You need to look for patterns you have seen before. This requires PERSISTENCE, leave no stone unturned. If making an assumption helps, do it! Breaking the problem in cases just gives you powerful assumptions to work with.

I agree this is nothing to panic. Thanks there! It just gets a bit frustrating when you know you are capable enough to solve it but still fail. I agree with the persistence thing and I also agree that practice is the only key but I also want to practice smartly!

If something is above my level, I read the editorial and try to upsolve it but for such problems, I think there has to be something cleverer that you can do rather than just practicing a lot.

In div2D Tree Tag

initially, we have to check case 1 that is fine as Alice has the first move

why do we need case 2 as for every test case will fall in

either case 3 or case 4?If $$$2da \geq \text{tree diameter}$$$, the answer is Alice even if $$$db > 2da$$$

Thanks! I got it, db will not matter as bob is limited by the diameter of the tree so he can't use his db to full extent to escape.

s=[f(1,r),f(2,r),…,f(n,r)] ?

For problem Div2 D my logic was similar to the editorial. Yet, I got WA on 274th case in the second test case.

I would be much obliged if someone could go through my code or give me some test case where my code fails.

CodeAlso adding the link to my submission Link

The contest was well balanced. Thank you for organizing it.

92082520 I’m very confused about this wrong submission. Anyone can help me? Thanks!

Does anyone have an intuitive solution for Div2 B?

The solution I wrote in editorial is not very intuitive, but I chose it because it is easier to prove. Here is another way to view things:

You can visualize $$$a_i > 0$$$ as a pile of $$$a_i$$$ tokens, and $$$a_i < 0$$$ as a "gap" that need to be filled with $$$|a_i|$$$ tokens. You want to make everything flat.

Free operations move tokens to the right. Imagine walking on the array from left to right, having a "bag" of tokens. When you encounter a pile ($$$a_i > 0$$$), put all these tokens in your bag. When you encounter a gap ($$$a_i < 0$$$), empty your bag here as must as you can.

This is equivalent to doing $$$\text{sizeBag} := \max(\text{sizeBag} + a_i, 0)$$$.

It is "intuitive" that you use free operations as best as you can. The final answer will be the final size of your bag (the number of tokens you couldn't put into gaps).

yes, this is a very intuitive solution 1-gon please add this to the editorial

Thanks, makes sense now.

For free operation ->

i<j and you are to increment aj and decrement ai, so by decrement if you have to make ai zero then it should be positive number right. so a negative number can make positive numbers of past towards zero in free.

Thanks. I find the backward version also fairly intuitive :

Backward version can be a bit clearer.

Walk through

`a`

, if last (current) element is negative then accumulate it to`accum`

— there will be "free of charge" turns to make it zero. If it positive and`accum + last`

is positive then we need "paid" turns.My submission 92031517 (I use Kotlin). Note

`reversed()`

method in the read data part.Can't we do 'C' using the Sliding window technique?

92089156 but it's very messy. You can probably write it in a better way I guess.

Nice problems and thanks for fast result and fast editorial!!

Why I was getting TLE plz can anyone help in test case 9 Code:https://codeforces.com/contest/1405/submission/92085005

prob B

the complexity of the algorithm is n squared and do not write such shit code because no one will ever help you look for errors in such code

OK bro thanks for helping

How to make a code simple? Is my way of writing code shit or my logic is shit???

u code style is shit :), check example my code or code of a famous coder (red mb)

Bro can u explain your approach to me how you managed to solve this question in O(n)

This round made me blue, so can't complain. Nice and fast editorial :)

Authors solution for E is pretty cool, but there were a similar (but much harder) problem in ptz winter 2020 which inspired me for this solution:

Let's decide for each cell will we cover it by a vertical (V) line or a horizontal (H) line. For test form the statement it will be like this:

We can see that we pay for horizontal line once in its beginning. So we pay for ".H" or "VH". Similarly for vertical lines. So we have to choose one of two options for each cell, and we pay something for choosing different options for some pairs of cells and also something fixed for each choice. That's standard min-cut problem.

Why this solution fails My submission I am trying to debug it from the last 1.5 hours, Fully exhausted now, Any help will be highly appreciated! UPD: I got it!

i am getting WA on 829th token of second test case in Div 2C https://codeforces.com/contest/1405/submission/92087888 please assist me

Can someone please help me understand what is the error in my code?

The submission id is: 92058038 .

Any help would be appreciated.

what if we have to tell "weather Alice can capture Bob in almost k turn" or "what is the guaranteed min turn in which Alice can capture Bob", in question D

Tag Tree.the following will be the ans, right ? or Am I missing something

case 1 : 1 turn.

case 2 : 2 turn .

case 3 : -1 (never)

case 4 : ceil(dis(a, b) / da).

In div2A if I reverse the array of odd length then the middle element remains in the same position, can anyone explain how reversing gets the correct answer, I know I am sounding dumb but I got this doubt. I actually didn't get a thought about it when I submitted my code.

The permutations are considered different if they disagree at

someindex, notallindices. $$$[1,2,3]$$$ and $$$[3,2,1]$$$ are different permutations.I am happy for this round. I became Pupil from Newbie :)

Can someone provide a DP based solution for Div2/C

please help me with this. Div2 D. it's showing runtime error on test-2. https://codeforces.com/contest/1405/submission/92077516 variables meaning- ans=initial dist from alice to bob. path=dia of tree.

Any one please!!

I found the problem with your code.

In cases where Bob comes out to be the winner you are not resetting the values of mx, node and path.

My god! Thank you so much bro.

Happy to help !!

What to do if I can't understand the proof of div2-b task? How do you upsolve if you can't understand the editorial?

https://codeforces.com/contest/1405/submission/92095673 You can check my submission if you want...

Read this

Thanks. I understood that one well.

In problem 2E, what exactly is the BIT you want to maintain? Because s is already weakly decreasing, binary search on s for the lmax will be log(n), but the tutorial said naive binary search needed log^2. Very confused. Can someone help me

An operation on BIT takes $$$\mathcal{O}(\log n)$$$ time, and binary search do $$$\mathcal{O}(\log n)$$$ operations on the BIT. Hence, finding $$$l_{\max}$$$ with this method $$$\mathcal{O}((\log n) \cdot (\log n)) = \mathcal{O}(\log^2 n)$$$ time.

I mean, wouldn't BS on s just be fine? Or is s just the bit?

Do you mean s[i] = f(1, r)+f(2, r)+....+f(i, r)?

s is a BIT, not just an array. We need to both "increment on prefix" and "get an element" in $$$\mathcal{O}(\log n)$$$.

oh OK, thanks a lot.

My current understanding:

For each step, (if necessary) use binary search on s to find max, and use a BIT which is the prefix sum of s to increment [1, l] by 1?

So I don't know why binary search is on the BIT? Is something wrong?

A nice trick of divC!

https://www.youtube.com/channel/UCBStHvqSDEF751f0CWd3-Pg?view_as=subscriber

Video Editorials of all latest contests , all questios . Even courses for various coding techniques will be taught . Do share , subscribe and like

sorry hugopm for bothering again:

In tutorial: Note f(l, r) the maximum number of elements we can remove in the subarray a[l...r] (zero if l>r). During our iteration over r, we're going to maintain the answers for each l: s=[f(1, r),f(2, r),...,f(n,r)] <-------- here do you mean f(l, r)? Also, do you mean for each l we maintain s_l=sum of everything in the bracket?

I don't really understand why solution for Div2. B is working.

me too.. can someone explain intuitively

This comment explains it well.

Explanation Video Just a suggestion :)

thank you so much. helped a lot.

Would it be possible to solve Div1C using Mo's algorithm ? I misread the ai = i condition and thought that ai = i should hold for the sub-array [L, R] (with indexes from the sub-array).

For Mo's algorithm, addition/deletion from the end point should be pretty simple while addition/deletion from the beginning should be doable by using a deque(I'm still a bit confused about this part)

The TL of 4s seemed pretty generous so I got stuck on thinking about Mo's Algorithm ;-;

Mo's Algorithm doesn't work there.Because when deleting/adding from the begining , the effect will be quite complex!Though deleting/adding from the end is easy!

yeah i just realized that while trying to code the solution ;-;

i'm still not able to understand the tree tag question and then it is obvious not get the tutorial to can someone please suggest me what are the prerequisite in need to know or if someone is uploading it's video tutorial then please share the link ... thank you in advance

Some points to note in this question are-

->If Alice can catch Bob in first move then she wins.

->Bob wont try to move unless Alice comes to catch him.

->If the length of longest path on the tree (i.e. the diameter of tree) is <= twice the length of range of a (i.e. da) i.e. Alice can reach the midpoint of the diameter and if then Alice has her range such that she can reach both the endpoints of the diameter in one jump then she will definitely catch Bob because Bob must be in her range (as diameter is already the longest path).

->If Bob can in a single jump go from a vertex u to vertex v such that Alice can only have a single vertex (either u or v) in her range then Bob can keep jumping from u to v (when vertex u is in range of Alice) and v to u (when vertex v is in range of Alice).

->If Alice can have both the vertices u and v in her range in a single jump then she will catch Bob in the end.

->Alice will try to stay (da-1) distance away from Bob in order to maximise the distance that Bob needs to escape her.

One more hack case for D: 1 7 3 6 2 3 1 2 2 3 3 4 4 5 5 6 5 7

https://codeforces.com/contest/1405/submission/92122526 My submission for Div2, C problem is giving wrong answer on Test set 2 (156 case). I am counting number of ones, zeros and question marks, in substring of length k and assigning value of 1 or 0 to a question mark only when a substring contains just one question mark.

Could someone please explain in brief how the diameter of tree has been calculated with only one dfs in the above implementation in Div 1-B / Div 2-D problem Tree tag. Thanks in advance.

For each node, you basically calculate the sum of the two longest paths from it (or one if it's a leaf) except for the path to it from the initial vertex. If the initial vertex is a part of a diameter-length path, it's obvious this will return the right result.

If the initial vertex is not a parth of such path, consider the first vertex you encounter during the DFS that is indeed a part of such path. Let us denote that first vertex by u. The counter intuitive part is that you don't consider the path from the initial vertex to u — BUT, since all the vertices on the path to u were, by definition, not a part of any diameter-length path, they do not need to be considered. You will then take the sum of the two longest paths from the current vertex, not including the path to it, and that will be the diameter.

Understod now, Thanks

is it rated? my change has gone away..why?

Same here :(

I have a problem for Div1 B: if $$$tree\ diameter\leq 2*da$$$ then Bob can't win.But why if $$$tree\ diameter > 2*da$$$ and other cases are all satisfied ,Bob is sure to win?

If diameter > 2*da then bob every time go to that long diameter place and if distance between them <=da then bob goto to the other side of that diameter..so alice can not touch him anyway.

But can you make sure that Bob can walk to the diameter?

Bob will run to the leaf node away from Alice(it can be proved that there will always be one), from there he will make a jump,if alice cant catch him in first move,he can't catch till he reaches leaf node as db>da and he is running in opposite direction.

But if Bob reach a leaf ,he can't find a node which he can reach but Alice can't?

sorry I didn't get it, bob reaches the leaf node and which node should he find?

The node that Bob can reach but Alice can’t reach

I am not sure if I get your question properly, but once bob reaches the leaf, Alice should be at a distance of atmost a(if greater than 'a' we will wait for him to come nearer), then we make a jump, since we are at the leaf node we can jump at a distance of min(db,diameter) and this distance should be greater than 2*da, as it should cross Alice and he should not catch us in the next move also. Root the tree at bob's initial position, it will be easier to visualize

Ok thank you very much

Or can you prove it can't happen?

It's a bit late, but I have a solution for Div2E/Div1C that isn't that practical, but I find rather cute (it was also the first thing I thought of).

Instead of doing what is in the editorial, consider solving the problem without constraint of $$$x$$$ or $$$y$$$. The following greedy algorithm works: At every step, choose the highest $$$i$$$ to remove if possible. The reason is obvious: if there are multiple with $$$i=A[i]$$$, the only one that won't force the others to become $$$i<A[i]$$$ is the largest. Therefore define a prototypical sequence of removals $$$R$$$, from the greedy algorithm. (To actually find $$$R$$$, I used a lazy propagation segtree with pairs — there may be an easier method.)

When there is the constraint of $$$x$$$, notice that after the first element $$$R[i] \leq x$$$, the rest of $$$R$$$ after it cannot be removed. We can have prefix min on $$$R$$$ and binary search for this element, let's call it $$$k$$$. Also, for the constraint of $$$y$$$, all elements where $$$R[i] \geq y, i<k$$$ cannot be removed as well by definition (but our inability to remove them doesn't affect our ability to remove other elements). To get this count we can answer queries offline in increasing order of $$$y$$$ using BIT.

Write-up is long, but the idea is really simple. However, implementation is some mess.

Yeah, I actually came up with this simulation solution before the official BIT-only one.

You may want to check my implementation, which is short and fast. The trick is that, in order to decrement a suffix beginning at $$$i$$$, we can decrement the whole array, and when we go down the path leading to the leaf $$$i$$$, each time we go to the right child, we add $$$+1$$$ on the left child. Hence, we can do "descent in the tree" (finding rightmost zero) and "decrement on suffix" in a single function "pop".

Instead of using Fenwick tree to get around the constraint on $$$y$$$, one can instead build the segment tree of $$$R$$$ (as defined in parent comment by astoria). Each node (covering the range of indices $$$[l, r]$$$) stores the array $$$[R[l], R[l+1], R[l+2], ..., R[r]]$$$, but sorted in ascending order.

Then, for each query, one can use the segment tree of $$$R$$$ to query the number of array indices $$$i$$$ of $$$R$$$ in the interval $$$[1, k-1]$$$ such that $$$R[i] \leq n-y$$$, where $$$k$$$ is the smallest index $$$k$$$ such that $$$R[k] \leq x$$$. Of course, we need to be careful of the edge case when $$$k = 1$$$.

Now, the solution works with online querying (without any persistent data structures contrary to what is mentioned in the official editorial), but in a slightly worse overall time complexity of $$$O(n log n + q log^2 n)$$$.

My code is rather messy, and it can be found here.

Please correct me if I made a mistake.

Is this algorithm to find the Diameter of a tree is correct

Find a leaf node, say N

Do DFS to get the farthest node to it

This node will be one endpoint of diameter, say p

Find second diameter endpoint by doing a DFS again from this endpoint p

But for me it fails, I don't know why My Submission

Your code is long, so I couldn’t totally tell, but did you make sure that the first dfs and second dfs don’t overlap? If they do, the actual diameter is shorter than it would output.

Actually both DFS are copies of each other, one(DFS1) returning "one end of diameter" and the other(DFS2) computing the Diameter by doing a DFS traversal from this endpoint

I'm sure my BFS code is correct..there aren't any issues in it

Actually I'm keen whether this algo/method will work...finding one endpoint then computing diameter from it

There are two bugs in your code:

1) BFS is wrong. Line no 26 should be

`x.d = 0;`

Testcase2) DFS2 is wrong. Line no 103 should be

`x.d = 0;`

TestcaseBonus: In DFS1 also, line no 64 should be

`x.d = 0;`

but it won't affect the final solution because`x.d`

is increased by 1 for all nodes and here you only concern about the node number with max`x.d`

.AC Submission : 92202644

Thank You so so Much Bro

Can someone please tell where did I go wrong in this solution for div2C?

In the tutorial of 1405D — Tree Tag, the inequality in Case 3:

`dist(b,a)+dist(a,v)≤da+(da+1)`

confuses me. We already know that`dist(a,v)=da+1`

, so the above inequality is saying that`dist(b,a) <= da`

, but how can this be true? If`dist(b,a) <= da`

holds, then we are already done in Case 1 and won't go to Case 3, can someone help me to understand that? Thanks in advance..

D1C can be solved with K-query :) https://codeforces.com/contest/1404/submission/92066332

Nice Editorial

Fast Editorial & Ver Concise....!

Imagine Alice and Bob actually playing Tree Tag game for 10^100 moves.

https://codeforces.com/contest/1405/submission/92515764 why it is giving TLE? i checked for hours for potential infinite loop in my while loop. but both positive_index and negative index are always decreased no matter what the condition is. or am i wrong??

Can someone please give me hack cases for Problem C Div2. My solution is not working at a point and I can't figure out why...I'm a complete beginner so if someone is looking at my code then I'm sorry about the quality of code. Any help will be much appreciated. 92764694

The tutorial for B is so messed up.

I don't know have anyone here now , but i got TLE for pro D.

This is my code :https://ideone.com/hwulqr

i can't fix my code although my solution is very simple . I thinhk i wrong somewhere in my code . If you see this comment , you can help me ? -- Sorry for my poor English .

Can anyone tell me what is 0ll(used in div 2 B)??

can someone explain sample 3 of div2D

I didn't understood why the suffix max sum is the answer of problem b? can anyone help