Hi everyone!

I would like to invite you to my fourth Codeforces Round, which I have made with my friends FastestFinger and TheOneYouWant. In terms of problems, it is my favorite among all my rounds.

With that said, I bring to your attention our new Codeforces Round 646 (Div. 2) that will take place on May/31/2020 17:35 (Moscow time). If your rating is less than **2100**, this round will be rated for you; otherwise, you can participate out of competition.

I would really like to thank:

- FastestFinger and TheOneYouWant for helping with preparing problems and giving new ideas.
- antontrygubO_o for coordinating our round
- 300iq, Jeel_Vaishnav, Ari, aryanc403, mahmoudbadawy, Vivek1998299, Uzumaki_Narutoo, Bakry, smartnj and Nikhil_Medam for testing the problems.
- MikeMirzayanov for Codeforces and Polygon platforms.

You will be given **6 problems** and **2 hours** to solve them. Scoring distribution will be announced later.

Good luck! :D

**UPD:** Scoring Distribution: $$$500-1000-1500-2000-2250-3000$$$

**UPD2:** Editorial (with memes, and detailed explanation) — Hope you guys enjoyed the contest! :D

I really like your problemsets. Hope this round is interesting too. Good luck :)

Thank you. The statements are concise and hopefully you'll enjoy solving them.

Are the pretests strong

Stronger is better.

You need to understand that setters always try to make pretests as strong as possible. It's just that they miss trivial/edge cases sometimes and that is completely unintentional. Sometimes, these are suggested by other people involved in setting the contest and sometimes, it just misses everyone's head. Well, there are very very rare exceptions to what I just said.

concise... nice!

Wouldn't be a surprise it you said that you will not enjoy solving them.

[Deleted]

I remember this comment.

[Deleted]

Damn True

[Deleted]

Suppose i have n accounts. I login of one and upvote all except that account's comment. I down vote you comment. So up votes=n-1 Down votes=n From my side. But unfortunately n=1;

[Deleted]

Neither it was intended to be. As i said earlier go fuck yourself.

Problem D concise. Hmm...

If you look at the statement barring input and interaction section, it looks concise to me. Interaction section of such problems has to be a bit descriptive. Some contestants found the description a bit confusing, so I'd like to know if this is what most people felt.

I personally feel the statement is simple enough to grasp after reading it once or probably twice.

Agree with you. I also don't see much scope in reduction of statement. I liked the problem though. For a while, I thought a better example could have brought more clarity but then realized that it could lead giving out unnecessary hints. Hence, I do think it was a decent enough statement. Anyway, in general, interactive problems tend to go lengthy.

Sir , itna tough , one of the toughest A problems i have seen

Problem C man! Problem C. Wrote a huge code which took 20 minutes of debugging and even after that just missed the deadline and then you present a solution like that. Felt so dumb after that.

Indian Round :)

Thanks for this round.

Can we expect Hindi version of the contest?

no

Then what about problems having characters like — Shaktimaan and Chacha Chaudary ??

Can we expect them??

I wonder what Shaktiman is doing in this quarantine. Let's hope some problem answers this question. :D

Thanks for the downvotes. I want more!!

Thank you Ashish bhai... :)

Ashishgup fanclub; Can't wait for contest :3

+1

Me Too !! Eagerly waiting :p

the_hyp0cr1t3 are you not the prez of the fanclub anymore? xD

I've realized I'm but a humble servant

+infinity

As a tester, I found the problems interesting and the contest to be well balanced in terms of topics/difficulty. Highly recommend taking part in the contest

I see this becoming tradition since 4-5 rounds, I mean a confirmation by tester. Good one!

Uh-oh. Soon we will see loads of comments like

tEStErs yOu fORgoT tO coNFirM tHe pROBlEMsET wAS gOoD

below every round announcement without these comments

Just tell me that contest doesn't have geometry problems ..XD

No Ashish Gupta dont like geometry problems and ya he said its his favorite among all.. So hopefully hopefully

Yes please, at least not some trigonometry problems.. I hate them

Were you paid to said this?

Faith in these types of comments restored.

It's my first time participating in a live Ashishgup contest and I feel so proud!( there aren't many Indian rounds :') )

Big fan here !

[Deleted]

villazer i think u should shut the f*** up

[Deleted]

u asked "what should i do?" at least its better then dying

hope,setter provides short statements.

[Deleted]

it's not funny anymore!

Wow, Indian Round.

I have already started liking the contest.

It's kinda proud feeling for me to participate in Indian rounds..So excited...Jai Hind !!!

After seeing this name Ashishgup it gives me goosebumps

Ik feeling proud Indian Army in background..

Bhai bhai bhai

How do so many people know him.. just wondering, no offense.

He is on the first page of codechef, among Indians top rated participants, and is also consistent on codeforces.

And most of his solutions are clear and self-explanatory as well.

Even his code is very readable.

'''

A graph prob for sure.

Feels like an Adrenaline Rush .... Can't wait XD

Great to see you back after more than a year. Looking forward to an educative and interesting round :)

I am proud of my country India. Thank you very much Ashishgup..

Please make sure the problem difficulties are balanced and don't go from 1000 in B to 1700 in C...!

C is supposed to be in the range of 1500-1800

What I meant was, don't have a huge gap in the difficulties of problems, space it out properly.

It was a pleasant surprise waking up this morning seeing a contest blog and a contest scheduled just after a day too.

So excited to see Indian Round in Codeforces

Really excited to participate for the very first time in an Indian round. :')

First time, i will get a chance to part in competition by Ashishgup .

Big Fan Ashishgup :)

Man, it has been a long time that comments go in such a very positive way. And it’s really cheerful to see these support and confidence to a problemsetter. I hope the round goes well and thanks for the great efforts!

Wow, An Indian Round and that too of Ashish Gupta. Can't wait to participate in it !!!

Thanks a lot codeforces for these contests !

Excited!

After all many of us are seeing an Indian problemsetter for the first time.

Why are people downvoting it??

[Deleted]

they also downvoted you.

Woah! An Indian CF Contest, after a long time! It will be fun! ;)

Thanks!

Can someone please explain, why so many downvotes, on my above comment?

I didn't make a wrong statement! I haven't made any wrong claim! I didn't say anything wrong about anyone!

I just thanked the authors! What's so downvoting in that?

Good to see aryanc403 as one of the testers.

Thanks :P

Woah, Indian round! That's so nice

I promise one Indian round every day for a week if Mike makes me Coordinator.

So I request to Mike to make you Coordinator.

MikeMirzayanov please make aryanc403 coordinator, people who agree with me, sign this petition, let's have a round every day for a week :)

Inb4 Mike makes me cf coordinator for 1 second. :)

I make you Coordinator.

I don't think so.. Let me ask round coordinator :)

Et tu, Brute?

Ashishgup orz.

https://codeforces.com/contests/writer/Ashishgup

Thanks for the round and the link. Upvoted.

Hope strong pretest and clear statement!

After a long time Ashishgup wouldn't participate in a contest XD.

$$$I \,\,am\,\, from\,\, India\,\, and \,\,Participating \,\,for \,\,the \,\,1st\,\, time\,\, in \,\,Indian \,\,authored \,\,contest.\,\, Quite \,\,excited!!$$$

Who cares!!

There are many red coders from India. I request Mike to give the opportunity to make one contest by an Indian in a month.

It is not about Mike giving an opportunity to them, everyone has an opportunity to make a contest. Just that they need to submit a nice problem set and apply to set a contest.

So do you want to say that Ashishgup and Aryan can't make one contest every month? Check the comment: https://codeforces.com/blog/entry/78132?#comment-632628

I am saying they have the opportunity to make a contest every week if they have a nice problemset (Not something like Mike has to give them a permission to do so).

It's good to see Indian Problem Setters ! Expecting :) Great Problemset :)

I don't know why I got so many down votes for this comment But Yeah atleast I know they werent Indians who disliked this ! :) :)

Categorizing people by nationality obviously does not make you feel uncomfortable. I wonder which categorization would.

spookywooky idk why it bothers you That an Indian is happy about Indian setting problems on Cf :) :) , It is not categorizing but a sort a patriotic sentiment :) Am not uncomfortable with having such a sentiment

The people are downvoting such comments, because every comment is the same, It is almost like a spam.

Arcane Oh I agree to that :) :) ! It's really looking a kind of spam with many People commenting the same thing :( Sry for that

grow up kiddo

LOL: Am never gonna grow up to where I will be matching your interests ! -27 contribution LOL!

i have to upvote for that!!! XD

Buzz Off !

gonna attempt my first indian round .. #excited

DELETED

After long time Indian setters...hoping for a great contest

WOW!! Extremely excited for a contest by GRANDMASTER FastestFinger

Eagerly waited for this trio to set problems. :D :D

Good luck! Hoping for an interesting round

It is my first Indian Codeforces Round. XD Overexited to participate in it. Hope that this contest goes very well :D

I hope one day problemsetters will be hyped caused by quality of problems instead of nationality.

I agree. The reason behind the hype is only the fact that there aren't many Indian problem setters and the last round by Indian setters was quite a while ago, so this round comes as a pleasant surprise to many.

I agree. The setter is not hyped here. You can see the past contest prepared by him. The quality of problems prepared by him are always good. Indian contests are rare on Codeforces which is the very reason of the excitement.

Problem-setters are hyped for their problem quality indeed, McDic, Monogon, FieryPhoenix to name a few! And Ashishgup does make good contests!

I think that PrinceOfPersia's problems are really nice. But he did not offer problems for a while...

I saw too much hate speech in his last round. Sadly.

I don't know what kind of drug(s) you're on, but I suggest you change your dealer man.

めんどくさい

Maybe I am mistaken. I thought there was something happened around #406 and later two guys who claimed to be your student.

I thought the community wasn't kind to you that time and I felt bad for you. Now I know, I were in drug then maybe.

Anyway, good to know that wasn't the case.

Btw, your logic has fallency, if my drug works so well, I shouldn't change the dealer, right?

Greatly depends on what kind of drugs you use ;)

Congrats to our indian problemsetters, I'm really excited about this round!

And talking about excitement, we will upsolve the problems 5 mins after the round:

https://youtu.be/yDdzbZhSYD0

See you on Algopedia!

It's a Div. 2 round. So why there is no Expert or Specialist testing the round?

Can't wait to compete in another round after a yearr! >.< so excited. cc LalisaManoban

Ikr it is going to be sooo fun!!

(-公- ;) I lost my cp skill

We are expecting short background story. I hope there will nothing like this

I liked the editorial very much. It's the first time I've seen something like that and it's cool ig.

family is giving love(downvote :P)

wow Indian round :) . Hope for good problemset. First time participation in a south Asian problem setter contest in codeforces...

I'm an Indian and also admire Ashishgup but I swear majority Indians get proud even if the word "India" is mentioned lol.

Yes, its just so cringe.

Ashishgup orz

We will remember this round!Another contest in May!

This is going to be the

11rated round hosted in the month of May. Though, out of the previous 10, one got declared unrated due to long queues, but still it's an effort worth appreciating. Kudos!^{th}Yet Another

HateForcesandFollowTheHerdForcesProblem!Dude that meme has been posted thousand times in codeforces comments section.Stop crying for downvotes everytime. The community knows better.

How 'bout reflectin' on your comment's content first bub.

Ashishgup, see the number of your fan followers XD

I really had enjoyed testing it ,and highly recommend it for every one

Happy to see Indian problem setters!!

How can i miss my favourite coder's contest !! Very excited :)

I hope current long queue won't effect this contest :(

As the Round number is a palindrome!(646) . Thinking that some tasks will be pal

INDromicHow many problems FastestFinger set? I am afraid that my typing speed is not so good.

Well my handle could have a very different meaning altogether ಠ ͜ʖ ಠ

That's what she said !

What kind of username is that?

it's been a while since i have participated in contest, keenly looking forward for this round

me also, will target pruple this time

I think both you are same person !! Why did both of you not give the contest ?

oh yeah, sorry i am same, actually i was about to give from the above account and i was really excited about it, but unfortunately my internet connection messed up, it took a long time to load the question so i skipped

Dont worry about it. I too have multiple accounts . Now I just feel like Sherlock :P

hahaha xD

Yeah I understand mobile data problems especially these when the traffic is so heavy on the website. I hope you get a broadband installed soon :D.

you are indeed sherlock, my honour sir i have talked to service provider today only :0

Woah !! That was not expected. But be careful, dont start downloading movies and stop coding, because thats the only way you can get red with all of your ids :)...

ab to sach bolde bsdk.jpeg xD

?

___ / \ o o

Ashishgup

::"TheOneYouWant for helping with preparing problems and giving new ideas"Me

::You are really good friends. :-DIndian Round :D

Hopefully, there will have no ugly geometry.hope to solve problem C ..

why people are so negative these days ..

This round is so much more famous than other codeforces rounds so far . Seriously, just have a look at the number of upvotes it has so far.

https://codeforces.com/blog/entry/76777

Also, by famous do you mean famous in one place or just really famous worldwide? Because the second one can't be accurately deduced by codeforces upvotes (see the number of participants from each country).

Though the number of participants are almost same but the number of upvotes says about the popularity of these guys in India and the number of Indian participants taking part regularly in CF contests.

Even the contest is Made In India by the "Make In India" initiative!!! Aur kitne ache din chaiye Mitron!

enjoy this round

Good contest!!

[Deleted]

They like indian contests unlike your comment.

Hoping to see short and concise problem statements!

Problem setters from other countries write contests every week: Nothing happened Problem setters from Indian: "wow, Indian round" Indian, Indian everywhere Plz stop yelling Indiots!

What's the problem saying an Indian round, Indian round.

It will be my first Indian round. Hope to have a good contest!

amnesiac_dusk Waiting for your round

Why is every Indian comment getting so many Downvotes?

Its really cringy to associate codeforces contest with patriotism lol, which many are doing here. Thats why they are getting downvotes

But I have seen similar comments during the Chinese contest's but none of them got any downvotes. Can you give the reason for that as well

https://codeforces.com/blog/entry/76895

This right here is the blog for the previous chinese round. I have scrolled through the entire comment section and found very few, probably less than five comments that are being "patriotic" about the chinese round. (Of course, I counted two, but I'm willing to admit I may have lost a few because of the sea of comments complaining that it interferes with breaking fast on the Indian subcontinent).

I haven't counted the number of "patriotic" comments on this blog, but I'm willing to bet that it's a bit more than five. Reading that kind of thing gets annoying very quickly.

every comment on this round

Wow, even I'm Indian, but this comment section is next level cringe.

just imagine tourist on this scale

Thoda time jane do. CF pe indian rounds hi dikhenge.

When do you guys have dinner since the contest runs from 8pm to 10pm in India?

You guys are having dinner?

Seh lenge thoda..

before 8 pm or after 10 PM

Although final sem exams from tomorrow, how can I miss this contest set by great Ashishgup!

Here's the problem statement:

Please explain the logic of this Problem??

Don't touch/think if code works.

Itne excited hai sab kahi chutiya na kat jaye.

Docking Complete !!

Good luck, have fun, guys!

Now I am seriously doubting myself why I started CP in the first place.

Short statement and Nice Problem Thanks :)

Thanks for the contest! IMO the problems are really interesting!

Man I made stupid mistakes ugh... I could have done better

problem C -> Test case 3, please reveal yourself :( :( :(

There's only one node in the graph...

that's 6 tc i think

Could be something like this- 1 4 1 1 2 2 3 3 4 A skewed tree considering the special element as root. Answer is always 'Ayush' in such cases

EDIT -> I am stupid to have read the problem incorrectly. Ignore below

I tried a few approaches, but one approach which looked really correct was -> If x is leaf then -> Ayush, else if K = N — 1 — degree[x] (number of nodes not counting level 0, 1 when tree is rooted at x) is odd then player 1 else player 2.

if x isn't a leaf, x will become a leaf only after N-2 removals, so change your K to N-2 and it will work.

Either D or E alone would have made this contest worth all two hours of it. Nice problems. :)

Video Tutorial for C

How do you do problem E? I tried constructing an euler tree and sorting by values and doing some stuff with that using sqrt decomposition but it failed pretest #9... I didn't use segment tree because I'm bad and don't know how to update ranges from [l,r] to 0 and find sum from [l,r]. Is that the correct method?

Problem E is just a greedy observation. First, you observe that you should replace each value of A with the root-to-leaf minimum (since if you can swap here you can swap at any ancestor). Then, within each node, you just swap as much as possible (such that as many 0s and 1s are in the right positions as possible). This can be implemented with a depth-first search to find how many swaps you perform on each node.

At least, I assume that's the correct greedy observation. Systests could end up proving me wrong.

Edit: passed systest. Seems my greedy is correct after all.

Ohhhh ok I was thinking of the root-to-leaf thing during contest but didn't go through with it ahhh, that's very smart. Cool problem

Actually the solution is easier: first check that number of 1-0 and 0-1 vertices is equal. Then mark all such vertices that there is no vertex on the simple path between them and root of smaller value. Now notice that you only want to shuffle equal number of 1-0 and 0-1 vertices at a time. Go through the marked vertices in dfs traversal order and match the maximum possible number of 1-0 and 0-1 vertices in their subtree. You can return the leftover vertices from dfs to the parent call to avoid any complicated technique of tracking what's been matched and what's not.

It was a simple dfs, nothing special.

Key ideathe main idea was that any shuffling will correspond to some pairs of nodes being swapped, due to the cost being linear in $$$k$$$, the only catch is the $$$a_{u}$$$ factor for those nodes would be the minimum $$$a[i]$$$ value of the nodes from the root to their lca. Note you don't actually need LCA. Complexity : O(N)

Why is this incorrect in D — Find maximum. Then use binary searchto find which subset contains that max element. Ask another query not containing that subset

I passed by doing this. Did you see that when only 2 elements remain, 1 query is enough?

For D does sum of size of $$$k$$$ subsets is equal to n or was it not necessary ?

It isn't necessary that sum of size of subsets be N.

I also did this but I think my binary search is lousy. So it may be taking more than $$$10$$$ for worst case of $$$n=1000$$$.

A harder version of F: https://atcoder.jp/contests/agc032/tasks/agc032_d?lang=en

Damn man, I don't remember having such nice concise no bs questions before. And not to mention that I loved both the graph problems. Jolly good contest bois.

I was only able to solve the first three (took way too long on C) but those were really good and interesting. I especially liked the short and direct statements. Waiting for the editorial..

Very nice contest. Problem E was very interesting.

Indian rounds are allways great!

spookywooky of course dude! Always!!

In D I am getting WA on pretest $$$4$$$. But I think in worst case I am querying only $$$12$$$ times.

My approach is to first put all indexes of subsets in query to get the maximum element. Then I binary search the appropriate subset which has maximum. This should take maximum $$$10$$$ query. Then I leave that subset and query all other subset. This is $$$1$$$ query.

In total $$$12$$$ query where I went wrong? Thank you. Reference submission: link

The union of all subsets may be not the whole array $$$A$$$, so if the maximum value is not in any subset, you will get a WA. Try this:

and array A is $$${1, 2, 3}$$$.

oh yes that is true.

Why do I feel that A is always harder then B and C /:

WAT IS IN PROBLEM A PRETEST 3? SAME STUCKED ON PRETEST 3

n = 7, x = 6, odd = 7, even = 0, I guess that cuz I also got WA on pretest 3 more than 10 times =))

always go for bruteforce if constraints allow in such scenarios.

life of a div2 scrub:

WA on div2A twice, take 15 minutes to solve

skip problem B because misread and thought it was too hard

go to problem C, misread and overcomplicate solution, then spend next hour tilting because you overlooked one bug in your code that messed up an otherwise correct solution (after WAing 6 times)

go back to problem B, realize it's not as hard, but since you have like 10 minutes left you code a greedy solution that probably will TLE once they use stronger tests

pog champ tbh

After 10 mins:

+4000submissions forAand only800 AC.This feels like: Bro, am I joke to you? xDDCan somebody please help me out on why my solution fails for problem A- https://codeforces.com/contest/1363/submission/82135360

1 4 2 3 3 3 3

try 1 4 2 1 1 1 1 expected No

I'm surprised that D didn't have as many solves as E. Maybe the somewhat confusing problem statement threw people off.

That's usually the case with interactive problems, people just get scared of them

Can anyone tell why my solution 82140244 shows WA on pretest 1?

your solution gives $$$!$$$ $$$3$$$ $$$4$$$ as the final answer. It is different from $$$!$$$ $$$4$$$ $$$3$$$ as order matters

Problems are interesting and tricky both.Though i just read a,b,c and solved a & b(with many WA).

A — Find the number of odd and even values in the array, then enumerate how many odd numbers are chosen (or, equivalently, how many even numbers are chosen).

B — A good string is always either some number of 0's followed by some number of 1's, or some number of 1's followed by some number of 0's. Enumerate where this change happens, and maintain the number of 0's and 1's on each side.

C — If x is a leaf, the first player wins. Otherwise, if n is even, the first player wins; if n is odd, the second player wins (I do not know how to prove...)

D — Consider the maximum element of the array. Note that all but at most one value in the password will be this maximum element (because at most one subset can include it). We find the maximum value of the array using 1 query, and binary search to find where it is. Use another query to find the value in the password whose subset contains this maximum element. When n = 1000, exactly 12 queries are used (10 for binary search and also 2 other queries).

E — Set all a[i] to be the minimum a[i] of itself and its ancestors. Then do a DFS and greedily try to match as many values as possible, leaving values that cannot be matched to operations performed further above.

I do not know how to solve F.

C is because in the 2 node case whoever's turn to move wins otherwise it's a race to put the other guy into a losing situation (if anyone knows the 21 game it's kinda like that)

In problem C, you keep removing nodes until a node — x is connected to only 2 nodes. then if player 1 removes the next node then the player 2 wins.

For C, consider this tree of 4 nodes

`1 2`

`1 3`

`1 4`

and the special element being 1. In this case won't the winner be second player?

No. The first player would win in this case.

After the first player removes a leaf (let's arbitrarily assume it is node 2), the tree will become (1, 3) and (1, 4).

After the second player removes either 3 or 4, node 1 becomes a leaf and the first player can remove it, thus winning the game.

Remember that the tree is

notrooted.Thanks for clarifying, I mistook 1 to be a leaf for the whole contest and was trying an overcomplicated solution. Looks like I should stop practicing coding and start practicing reading.

My solution for C was very different: Let dis[i] be distance of i from node x.

Choose a leaf where dis[i] is even and smallest, and remove it.

If no even dis[i] exist then: Choose a leaf where dis[i] is largest, and remove it.

You can see editorial for the proof of C :)

Can somebody help me out with problem B. I couldn't really come up with an algorithm.

Divide the string into 2 parts. The first part' elements are all 1 and the rest are all 0 and vice versa

You can see that for the strings to be good, it should be of one of the following 4 types:

000000...001,000000...011, ... , 011111...111 — 0s followed by 1s

111111...110,111111...100, ... , 100000...000 — 1s followed by 0s

all 1s

all 0s

You can use n^2 solution to check the cost of converting to each type and take minimum of all the cost. O(n) solution would be to use prefix sums to compute the cost of each type and take minimum.

Try to make the sequence monotonic, i.e ..11110000.., ..000111..., ..111.. or ..000.. using bruteforce. Pre count the total number of 1s to do that efficiently.

Count all 1 in string, then loop for the separating point of string (The string should be 11111....00000.... or 00000.....111..... SO find the point where 1 change to 0 of 0 to 1). While looping, keep the count of the number of 1 since the beginning. This way you can know the numbers of 1 and 0 of the first section and second section of the string. And knowing those you can find the minimum number of character you need to change (Sorry if I confused you)

Cries in green tears :)This is really a good contest. D is really interesting.

What's the proof for C?

I'm really shocked by the solution

EDIT: Misread the problem didn't notice it was an unrooted tree :(

No one would pick the node that will let opponent win.

A tree has allways leafs. The player can allways choose a leaf not adjacent to X if such one exists. If it does not exist the tree has size 3. (X and two other nodes).

I'm still confused

Can't X have more than 2 adjacent nodes?

If $$$x$$$ is leaf then it's obvious Ayush will win. Else in last only three node will be left where $$$x$$$ will be in the centre of both of the nodes. Thus problem reduces to NIM game , where we have pile of nodes size n-3 and each player can only remove one at a time and that person will lose who has the turn after n-3 nodes have been removed .it's easy to see that if n-3 is odd Ayush will win else Ashish will win.

Ohh I get it now

Idk why I overcomplicated it

Thanks.

my bad luck ..submitteed problem c solution on problem d ... and then after getting wa .. then leave that question....

must be WA on Pretest 1 ..why don't check again ?

that the mistake ... will take care in future contest

Here is the link of solution of problem — A

https://ide.geeksforgeeks.org/glqVZp3ceg (ide.gfg link)

This is giving wrong answer on pretest 3 Can anyone tell where I did wrong ?

Check this test case

3 2

1 1 1

Your solution should output "Yes" but the answer is "No". The problem here is that the testcase only allows you to choose maximum 2 odds but your solution allows 3.

In C if tree is connected then how can degree of x be 0.(Wrong answer on pretest 6)

I made the same mistake. Consider the case n = 1

Ohh right.Why did i tried to be oversmart when it was given in question regarding degree of leaf node :( Btw thanks.

If there is only one node in the tree

when n=1

I also couldn't solve because of this case when n = 1 degree will be 0.

Any idea of testcase 4 of E. I tried recursive solution. Link to submission: 82138471

Is B is some well-known algorithm?

I kept a count of 1s and 0s at each index, then iterated over the array and at each iteration, calculated the cost of making 00..11 or 11...00 or 00...00 or 11...11. Kept track of min so far.

It's an ad-hoc problem. The observation is that the final string will be composed of two parts, one part is all 1 and one part is all 0. You can simply try all N possible cutting points, keeping track of the number of zeroes and ones in the prefix (using that to calculate cost of each cutting point), and then taking the minimum. Time complexity should be O(N) if you calculate cost of cutting points efficiently.

Fun problems. A friendly suggestion would be to perhaps keep the names of game problems as Alice/Bob or at least something more distinguishable. Would likely be less confusing for people unfamiliar with such similar sounding names.

Good statements, strong pretests, only me left stupid

17 submissions to solve 3 problems, that's a new personal record

Atleast you realised where you were wrong before the contest ended. I realised what i did wrong after the contest ended :(

Wow! what a bad day for me. Overkilled A with Dp and couldn't solve C just because of the case missing when n = 1 i.e. degree of x is 0.

Calm down! The rating doesn't matter much, it will eventually come. Just keep practicing.

I know.. I was just frustrated with myself. Thanks tho.

Great problems! I was wondering if someone has a solution along the lines of Nim for C. I first reduced it as piles of size $$$size[v], v \in N(x)$$$ where $$$size[v]$$$ is the size of the subtree rooted at $$$v$$$. However, that is wrong here since the losing state is not when all piles are empty but when there is at most 1 pile. I wonder if there is a correct reduction.

I also tried it but unfortunately couldn't proceed further because the answer also depends upon the last pile left.

Yeah, I used the exact same approach. The key observation is that no matter what (unless it's a trivial case where x is a leaf) the final state will always be x and two leaf nodes. After that the next person that plays loses as the person after that will take x. The answer will always be the same irregardless of the structure of the tree (again ignoring the trivial case). So the answer will only be dependent on the parity of the number of nodes i.e if n%2==1 then Ashish wins else Ayush.

The nim value would be xor of all the values of $$$size[v] \pmod{2}$$$

I thought codeforces is using an API to get my first name and use it in the problem statement. In between contest I opened the problem statement in incognito to verify! P.S: My name is Shubham and I could only solve the first two problems with my name. Coincidence? Think not. RIP rating btw

I'm kind of mad about D. I didn't read in the string "Correct"

can someone here explain problem C ?