Thanks for a good round and fast editorial!

Thanks for a good round and fast editorial!

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!

STRONG PRETESTS

nice problems

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]

My Code using Vectors gave Runtime on Test 4 while the Same code using Array Passed!

Someone please help?

Edit: Got it

<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.

somehow i feel prob B is the hardest :v

Very cool problems! Thank you!

STRONG PRETESTS..

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.

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...

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 :)

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 !!!

My submission for Div2 D Tree Tag gives WA on pretest 2.

I checked the cases in below order:

1. If db < 2*a + b. Alice Wins

2. If distance of Bob from Alice <= da. Alice Wins.

3. 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

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

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 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?

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

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!

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?

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.

#include<bits/stdc++.h>
#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<lli>
#define pll pair<lli,lli>
#define vpi vector<pair <lli,lli> >
#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<<a[i]<<" ";}
#define ppt(i, l, r, a) for (i = l; i < r; ++i){cout<<a[i].ff<<"-"<<a[i].ss<<" ";}
#define form(i, l, r) for (i = l; i > r; --i)
#define forl(i, l, r) for (i = l; i < r; ++i)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
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<dt)
	{
		dm=dt;
		ndm=p;
	}
	lli ans=1;
	for(auto x: v[p] )
	{
		if(!vis[x]) 
		{
			ans+=dfs(dt+1,x);
		}
	}
	return ans;
}


void dfs1(lli dt,lli p=0)
{

	vis1[p]=dt;
	//cout<<p<<" ";
	// if(dm<dt)
	// {
	// 	dm=dt;
	// 	ndm=p;
	// }
	//lli ans=1;
	for(auto x: v[p] )
	{
		if(!vis1[x]) 
		{
			if(x==b-1)
			{
				dist=dt+1;
				return;
			}
			else dfs1(dt+1,x);
		}
	}
}


int main() 
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	lli t,c,d,q,h,i,j,k,n1,n2,n3,st,mid,end,pos,ind,min1,min2,max1,max2,lsb,sum,tot,rem,ans,prod,diff,count,flag,flag1,temp,temp1,temp2;
	lli mod=1000000007, inf=LLONG_MAX , pr=998244353;

	
	for(cin>>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<<dist;
		if(flag) cout<<"Bob";
		else cout<<"Alice";
		forl(i,0,n)
		{
			vis1[i]=0;
			vis[i]=0;
			dm=0;dist=0;
			v[i].clear();
		}
	}
}
	

Also 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?

Can't we do 'C' using the Sliding window technique?

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

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:

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.

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!

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.

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.

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?

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

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?

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

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

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

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.

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

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?

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.

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

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

.

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

Fast Editorial & Ver Concise....!

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

Since we are not in case 2, there is at least one vertex with distance at least da from Alice. If Bob is at such a vertex at the start of his turn, he should simply stay there.

I think it should be "at least greater than da from Alice". Because, if distance is equal to da, then Alice can reach it.