Codeforces Round #668 Editorial

1405B - Array Cancellation

Author: hugopm

Tutorial

1405C - Balanced Bitstring

Author: Kuroni

Tutorial

1405D - Tree Tag

Author: JettyOller

Tutorial

1405E - Fixed Point Removal

Author: hugopm

Tutorial

1404D - Game of Pairs

Author: Ari

Tutorial

1404E - Bricks

Author: Monogon

Tutorial

Tutorial of Codeforces Round 668 (Div. 1)

Tutorial of Codeforces Round 668 (Div. 2)

+421

Monogon
4 years ago
205

Comments (164)

Show archived | Write comment?

alegsandyr

4 years ago, # |

+36

Thanks for a good round and fast editorial!

→ Reply

2018LZY

4 years ago, # |

+12

Thanks for a good round and fast editorial!

→ Reply

Norrius

4 years ago, # |

+430

→ Reply

askd

4 years ago, # ^ |

+73

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

→ Reply

4 years ago, # ^ |

+162

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

→ Reply

ScarletS

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

ScarletS

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Here's what I see:

→ Reply

ScarletS

4 years ago, # ^ |

-13

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

→ Reply

4 years ago, # ^ |

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.

→ Reply

gupta_samarth

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

askd

4 years ago, # ^ |

+37

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

→ Reply

Dragonado

4 years 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

→ Reply

piyush14298

4 years ago, # ^ |

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

→ Reply

dvdg6566

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

→ Reply

Kuroni

4 years ago, # ^ |

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.

→ Reply

MehulJ21

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

dvdg6566

4 years ago, # ^ |

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!

→ Reply

bhavsar

4 years ago, # |

+11

STRONG PRETESTS

→ Reply

onetaps

4 years ago, # |

nice problems

→ Reply

Hz_

4 years ago, # ^ |

← Rev. 2 →

-15

agree

→ Reply

onetaps

4 years ago, # ^ |

→ Reply

Temirulan

4 years ago, # |

+16

Good problems! Congrats on great round!

→ Reply

Dr_Disrespect

4 years ago, # |

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]

→ Reply

Monogon

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

→ Reply

Dr_Disrespect

4 years ago, # ^ |

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.

→ Reply

SarthakBansal

4 years ago, # |

← Rev. 3 →

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

Someone please help?

Edit: Got it

→ Reply

Norrius

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

→ Reply

SarthakBansal

4 years 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

→ Reply

Norrius

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

→ Reply

SarthakBansal

4 years ago, # ^ |

OH. I didn't know. Thanks ! :)

→ Reply

aneee

4 years ago, # ^ |

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

→ Reply

arthurg

4 years ago, # |

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

→ Reply

code_warrior

4 years ago, # |

← Rev. 2 →

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.

→ Reply

arthurg

4 years ago, # ^ |

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.

→ Reply

code_warrior

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

GiangBang

4 years ago, # |

somehow i feel prob B is the hardest :v

→ Reply

anjanik012

4 years ago, # ^ |

Me too :(

→ Reply

ThinkTwice

4 years ago, # ^ |

← Rev. 4 →

-6

No! Easy O(n) Solution

→ Reply

anjanik012

4 years ago, # ^ |

-26

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

→ Reply

ThinkTwice

4 years ago, # ^ |

+14

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

→ Reply

Timur_Sitdikov

4 years ago, # |

+53

Very cool problems! Thank you!

→ Reply

Anushk-24

4 years ago, # |

STRONG PRETESTS..

→ Reply

abhaypatil2000

4 years ago, # |

Please attach codes also

→ Reply

4 years ago, # |

For Div2D, my code mysteriously fails on pretest 9... : https://mirror.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.

→ Reply

smax

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

leloy

4 years ago, # ^ |

Hack case:

→ Reply

leloy

4 years ago, # ^ |

I think it should be if(2*da+1 >= maxPath) cout << "Alice\n" instead of just if(2*da >= maxPath) cout << "Alice\n";

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Reiva5

4 years ago, # ^ |

I think in


int bfs2(){
  int m = 0;
  queue<int> vis;
  vector<bool> vist(n);

Especially at vector<bool> vist(n); it should be vector<bool> vist(n+1); instead due to your node was 1 base index.

→ Reply

https://youtu.be/FQLPNQppBNs

4 years ago, # ^ |

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.

→ Reply

puspaul.halder

4 years ago, # ^ |

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.

→ Reply

AdnanShamsi

4 years ago, # ^ |

→ Reply

puspaul.halder

4 years ago, # ^ |

← Rev. 3 →

Thanks,it helped me a lot

→ Reply

4 years ago, # ^ |

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

→ Reply

puspaul.halder

4 years ago, # ^ |

Thank you.

→ Reply

Ari's comment on the matter.

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

→ Reply

Kuroni

4 years ago, # ^ |

+10

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

→ Reply

dorijanlendvaj

4 years ago, # ^ |

+10

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

→ Reply

ankurkayal

4 years ago, # |

← Rev. 3 →

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

→ Reply

awasthishubh

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

→ Reply

pranshukas

4 years ago, # |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

pranshukas

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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.

→ Reply

pranshukas

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

4 years ago, # |

← Rev. 3 →

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

→ Reply

its_me_bitch

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Got it. Thanks :)

→ Reply

zass

4 years ago, # |

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

→ Reply

sirearsh

4 years ago, # ^ |

would you explain what you are doing in your code?

→ Reply

zass

4 years ago, # ^ |

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.

→ Reply

Uchiha_Itachi_21

4 years ago, # ^ |

I think your code fails the following case

1 6 4 110011

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

→ Reply

zass

4 years ago, # ^ |

Oh yeah got it. Thanks a lot.

→ Reply

mahade31

4 years ago, # |

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

→ Reply

leloy

4 years ago, # ^ |

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

→ Reply

mahade31

4 years ago, # ^ |

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:

→ Reply

oleh1421

4 years 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))

→ Reply

Vladosiya

4 years ago, # |

Why didn't this work in div2 D 92059623?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

You should use 2*da >= db instead of 2*da > db in line no 71.

Test case:

→ Reply

Vladosiya

4 years ago, # ^ |

Sorry, wrong submission 92060277

→ Reply

4 years ago, # ^ |

← Rev. 3 →

if(*min_element(dp.begin(), dp.end()) <= da) I think, this is the bug in your code.

Test case:

→ Reply

Trgt_2021_explosion

4 years ago, # |

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

→ Reply

decoder__

4 years ago, # ^ |

Can yo share the link to that question?

→ Reply

sapphire

4 years ago, # |

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!

→ Reply

Arkham_Knight

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

idontknowthesestuff

4 years ago, # |

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?

→ Reply

mphillotry

4 years ago, # ^ |

If $$$2da \geq \text{tree diameter}$$$, the answer is Alice even if $$$db > 2da$$$

→ Reply

idontknowthesestuff

4 years ago, # ^ |

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.

→ Reply

I_Love_LeNguyenTrucQuynh

4 years ago, # |

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

→ Reply

munditva

4 years ago, # |

← Rev. 2 →

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

→ Reply

Sawlaniji

4 years ago, # |

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

→ Reply

mmmmmiao

4 years ago, # |

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

→ Reply

ustaritz

4 years ago, # |

Does anyone have an intuitive solution for Div2 B?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

idontknowthesestuff

4 years ago, # ^ |

yes, this is a very intuitive solution Monogon please add this to the editorial

→ Reply

tushar_b18030

4 years ago, # ^ |

← Rev. 2 →

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.

	int positive = 0;
	for (auto i : a) {
		if (i > 0)positive += i;
		else positive -= min(positive, abs(i));
	}
	cout << positive << endl;

→ Reply

ustaritz

4 years ago, # ^ |

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<long long>(a[i], -sum_neg);
       sum_neg += free;
       sum_pos += (a[i] - free);
    }
}
cout << sum_pos << endl;

→ Reply

speshuric

4 years ago, # ^ |

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)

→ Reply

amanjainnn

4 years ago, # |

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

→ Reply

Mugiwara_ya

4 years ago, # ^ |

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

→ Reply

TleTerror

4 years ago, # |

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

→ Reply

Khalnayak

4 years ago, # |

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

→ Reply

Khalnayak

4 years ago, # ^ |

prob B

→ Reply

Stimsly

4 years 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

→ Reply

Khalnayak

4 years ago, # ^ |

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

→ Reply

Stimsly

4 years ago, # ^ |

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

→ Reply

epsilon_573

4 years ago, # |

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

→ Reply

Um_nik

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

→ Reply

roshan_mehta

4 years ago, # |

← Rev. 2 →

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!

→ Reply

Lepps

4 years ago, # |

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

The submission id is: 92058038 .

Any help would be appreciated.

→ Reply

niti_n_n_itin

4 years ago, # |

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

→ Reply

tusshar

4 years ago, # |

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.

→ Reply

Monogon

4 years ago, # ^ |

The permutations are considered different if they disagree at some index, not all indices. $$$[1,2,3]$$$ and $$$[3,2,1]$$$ are different permutations.

→ Reply

ad_47

4 years ago, # |

← Rev. 2 →

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

→ Reply

Uchiha_Itachi_21

4 years ago, # ^ |

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.

→ Reply

ad_47

4 years ago, # ^ |

My god! Thank you so much bro.

→ Reply

Uchiha_Itachi_21

4 years ago, # ^ |

Happy to help !!

→ Reply

dottomato

4 years ago, # |

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?

→ Reply

4 years ago, # ^ |

Read this

→ Reply

4 years ago, # |

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

→ Reply

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

oh OK, thanks a lot.

→ Reply

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

4 years ago, # ^ |

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?

→ Reply

yy_makemelove

4 years ago, # |

A nice trick of divC!

→ Reply

sanchitgupta456

4 years ago, # |

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

→ Reply

4 years ago, # |

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?

→ Reply

isdvhb

4 years ago, # |

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

→ Reply

4 years ago, # ^ |

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!

→ Reply

isdvhb

4 years ago, # ^ |

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

→ Reply

roshan84ya

4 years ago, # |

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

→ Reply

jnarutoj

4 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

RabbitPower

4 years ago, # |

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

→ Reply

Why_am_i_here_

4 years ago, # |

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.

→ Reply

Aloncf

4 years ago, # ^ |

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

→ Reply

QuitAfterPurple

4 years ago, # |

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

→ Reply

4 years ago, # |

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?

→ Reply

RD_TheCoder

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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

→ Reply

AjaySabarish

4 years ago, # ^ |

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.

→ Reply

4 years ago, # ^ |

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

→ Reply

AjaySabarish

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

AjaySabarish

4 years ago, # ^ |

← Rev. 3 →

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

→ Reply

4 years ago, # ^ |

Ok thank you very much

→ Reply

4 years ago, # ^ |

Or can you prove it can't happen?

→ Reply

astoria

4 years ago, # |

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.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

user14767553

4 years ago, # ^ |

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.

→ Reply

harshitsoora

4 years ago, # |

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

→ Reply

connorwang38

4 years ago, # ^ |

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.

→ Reply