### 1-gon's blog

By 1-gon, history, 7 months ago,

I hope everyone enjoyed the contest!

UPD: Added implementations for all problems.

1405A — Permutation Forgery

Author: antontrygubO_o

Tutorial

Implementation

1405B — Array Cancellation

Author: hugopm

Tutorial

Implementation

1405C — Balanced Bitstring

Author: Kuroni

Tutorial

Implementation

1405D — Tree Tag

Author: Maripium

Tutorial

Implementation

1405E — Fixed Point Removal

Author: hugopm

Tutorial

Implementation

1404D — Game of Pairs

Author: Ari

Tutorial

Implementation

1404E — Bricks

Author: 1-gon

Tutorial

Implementation

• +421

 » 7 months ago, # |   +36 Thanks for a good round and fast editorial!
 » 7 months ago, # |   +12 Thanks for a good round and fast editorial!
 » 7 months ago, # |   +430
•  » » 7 months ago, # ^ |   +73 I had to google how during the contest and actual real-life trees kept popping up lol
•  » » » 7 months ago, # ^ |   +162 smh this guy didn't do the tree basics set, what a cyan...
•  » » » » 7 months ago, # ^ |   0 Can't do the tree basics set if it isn't open for virtualing yet :/
•  » » » » » 7 months ago, # ^ |   0 The problems should all be publicly available, but how do I open it for VP?
•  » » » » » » 7 months ago, # ^ |   0 This should come up in the "Edit" tab of the contest (I think)
•  » » » » » » » 7 months ago, # ^ |   +1 Here's what I see:
•  » » » » » » » » 7 months ago, # ^ |   -13 On the same page, there's also this, which should do the trick
•  » » » » » » » » » 7 months ago, # ^ |   +3 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.
•  » » » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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 listUPD: 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.
•  » » » » 7 months ago, # ^ |   +37 I'm just a cyan with a good keyboard tbh, will watch your vids later tho :)
•  » » » » 7 months ago, # ^ |   +21 I only got AC because I saw your video and reused the code that I submitted for your contest. You are a prophet orz
•  » » » » 7 months ago, # ^ |   0 I got the diameter idea just because I did those gym questions. Thanks!
 » 7 months ago, # | ← Rev. 3 →   +45 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!
•  » » 7 months ago, # ^ |   +5 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 7 months ago, # ^ |   +3 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!
 » 7 months ago, # |   +11 STRONG PRETESTS
 » 7 months ago, # |   +5 nice problems
•  » » 7 months ago, # ^ | ← Rev. 2 →   -15 agree
•  » » » 7 months ago, # ^ |   0 ty
•  » » 7 months ago, # ^ | ← Rev. 2 →   -16 deleted
 » 7 months ago, # |   +16 Good problems! Congrats on great round!
 » 7 months ago, # |   +5 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]
•  » » 7 months ago, # ^ |   +23 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.
•  » » » 7 months ago, # ^ |   +7 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.
 » 7 months ago, # | ← Rev. 3 →   0 My Code using Vectors gave Runtime on Test 4 while the Same code using Array Passed!Someone please help?Edit: Got it
•  » » 7 months ago, # ^ |   +11 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.
•  » » » 7 months ago, # ^ |   +10 Oh! Got it Thanks!Now I'm wondering how it worked on my local compiler (Sublime Text 3) passed the first 3 pretests lol
•  » » » » 7 months ago, # ^ |   +19 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.
•  » » » » » 7 months ago, # ^ |   +3 OH. I didn't know. Thanks ! :)
•  » » » » » 7 months ago, # ^ |   +5 That's the best explanation of UB that I have ever seen!
 » 7 months ago, # |   +4 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. Great contest, hope to see more like it :)
 » 7 months ago, # | ← Rev. 2 →   0 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.
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   +1 Thanks, I got it now. I thought that for alice to win,alice and bob had to be in thier same respective initial nodes .
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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 thatdist(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.
 » 7 months ago, # |   +4 somehow i feel prob B is the hardest :v
•  » » 7 months ago, # ^ |   0 Me too :(
•  » » » 7 months ago, # ^ | ← Rev. 4 →   -6 No! Easy O(n) Solution
•  » » » » 7 months ago, # ^ |   -26 Dude I can read the tutorial now. I didn't ask for your code.
•  » » » » » 7 months ago, # ^ |   +14 But In a community, no one asks someone(particular person mostly), They gets suggestions or answers from anyone. :)
•  » » » » 7 months ago, # ^ |   0 Can someone explain the editorial of problem B
•  » » » » » 7 months ago, # ^ |   0
•  » » » » » » 7 months ago, # ^ |   0 thank you
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Check out mine 92120083
•  » » 7 months ago, # ^ |   0 True :(
 » 7 months ago, # |   +53 Very cool problems! Thank you!
 » 7 months ago, # |   +5 STRONG PRETESTS..
 » 7 months ago, # |   0 Thanks for a nice round with cool problems.
 » 7 months ago, # |   0 Please attach codes also
 » 7 months ago, # |   0 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 7 months ago, # ^ |   0 Hack case: 1 5 1 5 2 5 1 2 2 3 3 4 4 5 
•  » » » 7 months ago, # ^ |   0 I think it should be if(2*da+1 >= maxPath) cout << "Alice\n" instead of just if(2*da >= maxPath) cout << "Alice\n";
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » 7 months ago, # ^ |   +4 I think in int bfs2(){ int m = 0; queue vis; vector vist(n); Especially at vector vist(n); it should be vector vist(n+1); instead due to your node was 1 base index.
•  » » » » » » 7 months ago, # ^ |   0 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.
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   +1
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   0 Thanks,it helped me a lot
•  » » » 7 months ago, # ^ |   +1 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).
•  » » » » 7 months ago, # ^ |   0 Thank you.
 » 7 months ago, # | ← Rev. 2 →   +10 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...
•  » » 7 months ago, # ^ |   +10 TLDR: We used bitset dp for small $n$ and heuristics for larger $n$.
•  » » 7 months ago, # ^ |   +10
 » 7 months ago, # |   0 idk about all of you.... but I used two pointers and it somehow worked lol
 » 7 months ago, # | ← Rev. 3 →   0 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 :)
•  » » 7 months ago, # ^ |   0 Same mistake i also did bro.
•  » » 7 months ago, # ^ |   +10 Alice and Bob occupy the same vertex, then Alice is declared the winner. 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.
 » 7 months ago, # |   0 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 !!!
•  » » 7 months ago, # ^ |   +3 I think itr = -1 causes a problem; what do you do when neg becomes empty?
•  » » » 7 months ago, # ^ |   0 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.
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 7 months ago, # ^ |   0 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..
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
 » 7 months ago, # | ← Rev. 3 →   0 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
•  » » 7 months ago, # ^ |   +3 In case 3,even if diameter is smaller than db, Bob can win because min(diameter, db) needs to be greater than 2*da.
•  » » » 7 months ago, # ^ |   0 Got it. Thanks :)
•  » » » 7 months ago, # ^ |   0 I confused why this solution fails for Div2 D in the pretest 2The 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
 » 7 months ago, # |   0 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
•  » » 7 months ago, # ^ |   0 would you explain what you are doing in your code?
•  » » » 7 months ago, # ^ |   0 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.
•  » » 7 months ago, # ^ |   +1 I think your code fails the following case 1 6 4 110011Your code gives No whereas the answer is Yes. Hope this helps!!!
•  » » » 7 months ago, # ^ |   0 Oh yeah got it. Thanks a lot.
 » 7 months ago, # |   0 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)?
•  » » 7 months ago, # ^ |   +4 I think it means that the players 'teleport' instead of walking along the tree
•  » » » 7 months ago, # ^ |   0 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:
 » 7 months ago, # |   +91 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))
 » 7 months ago, # |   0 Why didn't this work in div2 D 92059623?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +7 You should use 2*da >= db instead of 2*da > db in line no 71.Test case: 1 3 1 3 1 2 1 2 2 3 
•  » » » 7 months ago, # ^ |   0 Sorry, wrong submission 92060277
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   0 if(*min_element(dp.begin(), dp.end()) <= da) I think, this is the bug in your code.Test case: 1 6 2 5 2 5 1 2 1 3 1 4 4 5 5 6 
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 I confused why this solution fails for Div2 D in the pretest 2The 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
 » 7 months ago, # |   0 Really good contest!
 » 7 months ago, # |   0 Div2 C has appear in earlier Contest on Codeforces itself(k periodic string)
•  » » 7 months ago, # ^ |   +3 Can yo share the link to that question?
 » 7 months ago, # |   +1 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!
•  » » 7 months ago, # ^ | ← Rev. 2 →   +7 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.
•  » » » 7 months ago, # ^ |   0 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.
 » 7 months ago, # |   +1 In div2D Tree Taginitially, we have to check case 1 that is fine as Alice has the first movewhy do we need case 2 as for every test case will fall in either case 3 or case 4?
•  » » 7 months ago, # ^ |   0 If $2da \geq \text{tree diameter}$, the answer is Alice even if $db > 2da$
•  » » » 7 months ago, # ^ |   +1 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.
 » 7 months ago, # |   0 s=[f(1,r),f(2,r),…,f(n,r)] ?
 » 7 months ago, # | ← Rev. 2 →   0 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. Code#include #define MOD 1000000007 #define PR 998244353 #define INF INT_MAX #define endl "\n" #define newl cout<<"\n" #define mp make_pair #define mt make_tuple #define pb push_back #define ff first #define ss second #define vi vector #define pll pair #define vpi vector > #define shot(p) sort(p.begin(),p.end()) #define ulta(ord) reverse(ord.begin(), ord.end()); #define lli long long int #define sz(a) int((a).size()) #define pat(i, l, r, a) for (i = l; i < r; ++i){cout< r; --i) #define forl(i, l, r) for (i = l; i < r; ++i) using namespace std; #include using namespace __gnu_pbds; const int N=100000; vi v[N+1]; vi subt; lli tt; lli vis[N+1]={0}; lli vis1[N+1]={0}; lli dm=0, ndm=0; lli a,b,n,da,db,dist=0; lli dfs(lli dt,lli p=0) { vis[p]=dt; if(dm>t;t--;newl) { cin>>n>>a>>b>>da>>db; forl(i,0,n-1) { cin>>c>>d; v[c-1].pb(d-1); v[d-1].pb(c-1); } flag=1; if((db+1)/2<=da) flag=0; else { dfs1(0,a-1); if(da>=dist) flag=0; else { dfs(0); forl(i,0,n) vis[i]=0; dm=0; dfs(0,ndm); // forl(i,0,n) vis[i]=0; if((dm+1)/2<=da) flag=0; } } //cout<
 » 7 months ago, # |   0 The contest was well balanced. Thank you for organizing it.
 » 7 months ago, # |   0 92082520 I’m very confused about this wrong submission. Anyone can help me? Thanks!
 » 7 months ago, # |   0 Does anyone have an intuitive solution for Div2 B?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +8 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).
•  » » » 7 months ago, # ^ |   +3 yes, this is a very intuitive solution 1-gon please add this to the editorial
•  » » » 7 months ago, # ^ |   0 Thanks, makes sense now.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 For free operation ->i 0)positive += i; else positive -= min(positive, abs(i)); } cout << positive << endl; 
•  » » » 7 months ago, # ^ |   +4 Thanks. I find the backward version also fairly intuitive : long long sum_pos = 0; long long sum_neg = 0; for (int i=n-1; i>=0; i--) { if (a[i]<0) { sum_neg += a[i]; } else if (a[i]>0) { long long free = min(a[i], -sum_neg); sum_neg += free; sum_pos += (a[i] - free); } } cout << sum_pos << endl; 
•  » » » » 7 months ago, # ^ |   0 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. val n = readInt() val a = readArr(n).reversed() var accum = 0L var ans = 0L for (ai in a) { accum += ai if (accum > 0) { ans += accum accum = 0 } } println(ans) 
 » 7 months ago, # |   0 Can't we do 'C' using the Sliding window technique?
•  » » 7 months ago, # ^ |   0 92089156 but it's very messy. You can probably write it in a better way I guess.
 » 7 months ago, # |   0 Nice problems and thanks for fast result and fast editorial!!
 » 7 months ago, # |   0 Why I was getting TLE plz can anyone help in test case 9 Code:https://codeforces.com/contest/1405/submission/92085005
•  » » 7 months ago, # ^ |   0 prob B
•  » » » 7 months ago, # ^ |   +10 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
•  » » » » 7 months ago, # ^ |   0 OK bro thanks for helping
•  » » » » 7 months ago, # ^ |   0 How to make a code simple? Is my way of writing code shit or my logic is shit???
•  » » » » » 7 months ago, # ^ |   0 u code style is shit :), check example my code or code of a famous coder (red mb)
•  » » » » » » 7 months ago, # ^ |   0 Bro can u explain your approach to me how you managed to solve this question in O(n)
 » 7 months ago, # |   0 This round made me blue, so can't complain. Nice and fast editorial :)
 » 7 months ago, # |   +79 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: V.VV VHH. VH.. 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.
 » 7 months ago, # | ← Rev. 2 →   0 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!
 » 7 months ago, # |   0 i am getting WA on 829th token of second test case in Div 2C https://codeforces.com/contest/1405/submission/92087888 please assist me
 » 7 months ago, # |   0 Can someone please help me understand what is the error in my code? The submission id is: 92058038 .Any help would be appreciated.
 » 7 months ago, # |   0 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 somethingcase 1 : 1 turn.case 2 : 2 turn .case 3 : -1 (never)case 4 : ceil(dis(a, b) / da).
 » 7 months ago, # |   0 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.
•  » » 7 months ago, # ^ |   +5 The permutations are considered different if they disagree at some index, not all indices. $[1,2,3]$ and $[3,2,1]$ are different permutations.
 » 7 months ago, # |   0 I am happy for this round. I became Pupil from Newbie :)
 » 7 months ago, # |   0 Can someone provide a DP based solution for Div2/C
 » 7 months ago, # | ← Rev. 2 →   0 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.
•  » » 7 months ago, # ^ |   0 Any one please!!
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 My god! Thank you so much bro.
•  » » » » 7 months ago, # ^ |   0 Happy to help !!
 » 7 months ago, # |   0 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?
•  » » 7 months ago, # ^ |   0 https://codeforces.com/contest/1405/submission/92095673 You can check my submission if you want...
•  » » 7 months ago, # ^ |   +3
•  » » » 7 months ago, # ^ |   0 Thanks. I understood that one well.
 » 7 months ago, # |   0 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
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 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)?
•  » » » » 7 months ago, # ^ |   0 s is a BIT, not just an array. We need to both "increment on prefix" and "get an element" in $\mathcal{O}(\log n)$.
•  » » » » » 7 months ago, # ^ |   0 oh OK, thanks a lot.
•  » » » 7 months ago, # ^ |   0 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?
 » 7 months ago, # |   0 A nice trick of divC!
 » 7 months ago, # |   0 https://www.youtube.com/channel/UCBStHvqSDEF751f0CWd3-Pg?view_as=subscriberVideo Editorials of all latest contests , all questios . Even courses for various coding techniques will be taught . Do share , subscribe and like
 » 7 months ago, # |   0 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?
 » 7 months ago, # |   0 I don't really understand why solution for Div2. B is working.
•  » » 7 months ago, # ^ |   0 me too.. can someone explain intuitively
•  » » » 7 months ago, # ^ |   0 This comment explains it well.
•  » » » 7 months ago, # ^ |   0 Explanation Video Just a suggestion :)
•  » » » » 7 months ago, # ^ |   0 thank you so much. helped a lot.
 » 7 months ago, # |   0 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 ;-;
•  » » 7 months ago, # ^ |   +8 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!
•  » » » 7 months ago, # ^ |   0 yeah i just realized that while trying to code the solution ;-;
 » 7 months ago, # |   0 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
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
 » 7 months ago, # |   0 One more hack case for D: 1 7 3 6 2 3 1 2 2 3 3 4 4 5 5 6 5 7
 » 7 months ago, # |   0 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.
 » 7 months ago, # |   0 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.
•  » » 7 months ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 7 months ago, # ^ |   0 Understod now, Thanks
 » 7 months ago, # |   +3 is it rated? my change has gone away..why?
•  » » 7 months ago, # ^ |   0 Same here :(
 » 7 months ago, # |   0 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?
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 But can you make sure that Bob can walk to the diameter?
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 7 months ago, # ^ |   0 But if Bob reach a leaf ,he can't find a node which he can reach but Alice can't?
•  » » » » » » 7 months ago, # ^ |   0 sorry I didn't get it, bob reaches the leaf node and which node should he find?
•  » » » » » » » 7 months ago, # ^ |   0 The node that Bob can reach but Alice can’t reach
•  » » » » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 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
•  » » » » » » » » » 7 months ago, # ^ |   0 Ok thank you very much
•  » » » » » 7 months ago, # ^ |   0 Or can you prove it can't happen?
 » 7 months ago, # |   +3 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 •  » » 7 months ago, # ^ | ← Rev. 2 → 0 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". •  » » 4 months ago, # ^ | 0 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.
 » 7 months ago, # |   0 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
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 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 endpointI'm sure my BFS code is correct..there aren't any issues in itActually I'm keen whether this algo/method will work...finding one endpoint then computing diameter from it
•  » » 7 months ago, # ^ | ← Rev. 4 →   0 There are two bugs in your code:1) BFS is wrong. Line no 26 should be x.d = 0; Testcase1 5 1 4 2 5 1 2 2 3 3 4 4 5 2) DFS2 is wrong. Line no 103 should be x.d = 0; Testcase1 5 1 5 2 5 1 2 1 3 3 4 4 5 Bonus: 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
•  » » » 7 months ago, # ^ |   0 Thank You so so Much Bro
 » 7 months ago, # |   0 Can someone please tell where did I go wrong in this solution for div2C?
 » 7 months ago, # |   0 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.
 » 7 months ago, # | ← Rev. 4 →   0 .
 » 7 months ago, # |   0 D1C can be solved with K-query :) https://codeforces.com/contest/1404/submission/92066332
 » 7 months ago, # |   0 Nice Editorial
 » 7 months ago, # |   +3 Fast Editorial & Ver Concise....!
 » 7 months ago, # |   0 Imagine Alice and Bob actually playing Tree Tag game for 10^100 moves.
 » 7 months ago, # |   0 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??
 » 7 months ago, # |   0 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
 » 7 months ago, # |   0 The tutorial for B is so messed up.
 » 7 months ago, # |   0 I don't know have anyone here now , but i got TLE for pro D.This is my code :https://ideone.com/hwulqri 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 .
 » 6 months ago, # |   0 Can anyone tell me what is 0ll(used in div 2 B)??
 » 6 months ago, # |   0 can someone explain sample 3 of div2D