Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round #720 (Div. 2), which will take place on May/07/2021 17:35 (Moscow time). The round will be **rated for the participants with a rating lower than 2100**. Participants from the first division are also welcomed to take part out of competition.

You will be given **2 hours 15 minutes** to solve **5 problems**. All the problems were created and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

Huge thanks to those who helped make this round possible:

- Fliahin for being the first who gave feedback and helped with ideas on some problems.
- Denisov for providing priceless feedback during the entire creation of the round.
- KAN and Aleks5d for their excellent coordination.
- Valera_Grinenko, rkm62, PurpleCrayon, BOGDAN_, okwedook, namanbansal013, chctxdy68, ermakov22, Denisov, 4qqqq, alexX512, IaMaNanBord, perekopskiy, kassutta and never_giveup for testing and providing invaluable feedback.
- MikeMirzayanov for Codeforces and Polygon platforms.

I tried my best to create interesting problems and clear statements, so don't forget to read all ones :)

Scoring: $$$500-1000-1750-2250-2750$$$.

Hope you enjoy it!

**UPD:** Editorial is published!

**UPD: Congratulations to the winners!**

Div. 1:

Div. 2:

hope the problems are as interesting as your rating graph

Interesting!!

Makes sense actually )))

Karavaiev Why are Interaction Problems actually useful when we can do it normally(In the sense standard way of I/O) as well.

for example: https://codeforces.com/contest/1504/problem/D

So interesting（）

The Problems were Interesting btw in my opinion....

PurpleCrayon orz !

As a loyal PurpleCrayon Fan, PurpleCrayon orz.

as also a loyal purplecrayon enthusiast, PurpleCrayon orz!

PurpleCrayon is an inspiration to me. PurpleCrayon orz!

how PurpleCrayon so geniosity orz

as a loyal purplecrayon enjoyer, Purple Crayon orz!

Interesting scoring distribution, hope its_Atrap like CodeCraft-21 and Codeforces Round #711 (Div. 2)

Is it a trap? You can check soon :)

Yes I will check it during contest since I am neither a setter nor a tester :(

It wasn't a trap, rather questions were very interesting!!!

namanbansal013orz!!

Hope problem C will be interactive! :)

Are you a time traveller?

I think he is

Another chance for me to become Specialist... or Newbie

Hope you handle it well!

I know you can do it for Specialist, my friend...

Nice try

crap that didn't go well

I think the problems will be cool!

excited to participate in this contest ... seems to be amazing :)

My First Rated Contest :D, I hope I can make Tanya proud :)

She will be proud of you (for getting so much down vote) xD. Just a joke.

I very well know, these people who are downvoting me are tanya's brothers & relatives trying to seperate us T-T, #cruel_World

SpoilerI know Tanya, You are laughing at this :D

I being Tanya's father reject this relationship.

Huge respect Bhai:-D

ahm...ahm... Say it Again (if you wanna get thrown out the house) :/

Problem C 1750 Points ! a bit scary.

which problem will be interactive? Any guesses?

I guess problem D :P . Don't take it seriously. This is only my guess.

Resolved... Thanks!

Sorry but why down-votes? I was just seeking to get help and improve.

Maybe because it is under round announcement. About problem: i am not actually sure, but function "merge" can slow your code, i reccomend to delete it and write it's code directly in merges places.

I also reccomend to use 64bit version of C++, it is faster

upd: please note that i am not really good in this aspects of C++, so it is probably better not trust me D:

hope i can solve c

man hope is not everything in this curse world. You should practice as much as you can. Then only you can stand apart from the crowd :).

"..., Hope is a good thing, maybe the best of things, and no good thing ever dies."The Shawshank Redemption

May be the best movie I've ever seen.(apart

'Parasite')hope too)

PurpleCrayon orz

Guys, can you please press green triangle to raise this round's contribution

Not for you I guess

The problems seems very elegant after watching their score distribution, you should participate in the round.

Let's hope the server will not get down in this contest

All the best to all the contesters!!! Wish u luck

Want Ashishgup div 2 rounds.

me too :) but cannot offer this one tomorrow :(

One thing i encounter in previous Codeforces round 719 problem F1 interactive problem for someone who attempted such type of problem for the first time. fflush(stdout) didn't work with FAST i/o .

submission link->https://codeforces.com/contest/1520/submission/115326611

you can remove Fast i/o fflush(stdout) that will work

submission link ->https://codeforces.com/contest/1520/submission/115344437

in same code i used cout.flush() it worked with Fast i/o.

submission link -> https://codeforces.com/contest/1520/submission/115336786

endl.

That C's rating makes it so sus for interactive problem!

why? I never attempt an interactive problem before

Interactive problems are not very hard (the ones placed before div2 D) but just cause they are interactive many times (not everytime) they have more points than a usual problem of that difficulty. So as a usual C is not 1750 it might be interactive.

This is just a guess we will get to know tomorrowyou can refer to some numbers given by UpAndDown even though I am not sure if they are calculated or estimated...

[Edit:] Also Codecraft 2021 contest had almost the same score distribution with C being interactive!

Typical interactive problem:

Div.2 C — 70% probability

Binary Search — 95% probability

the same day as my birthday)) (tomorrow)

You can get a birthday color :)

Hoping to learn something new from the questions. All the best to everyone :)

In the last two round of div-2 contests(716 and 717)-the dashboard were consist of only 5 problems(and they were basically number theory and bitmasks related).This contest will be also consisted of 5 problems! It's really tough to be satisfied on the standings column for us(Newbie awa Pupil) when the dashboard has only 5 problems. Scoring only "A" creates a huge differences on the standings column. It's really sorrowful. Actually I mean- 3 "div-2" contests in a row with only 5 problems on the dashboard-it's really painful.

Good Luck Everyone!!!

Hopefully problems will be interesting. Another chance for me to become pupil.

what are the difference between the divs? I'm not very familiar with this CP platform.

Div 1 is more difficult than Div 2.You can not participate in Div 1 if you have less rating than 1900.But you can participate div 2 and div 3 contest. And div 3 should be easier than the other divs. Hope you understand.

You can't join div.1 unless you have got 1900 Ratings. You are not Rated for div.2、div.1 when your Raing is higher than a number.

Thanks a lot. Waiting for the contest

Last Global Round I passed out and my rating reduced. Hope my name turn blue again.

me struggling for cyan.

Hope you can be cyan soon. Moreover,I heard that the disease in India is quite serious now from media，Really？

Yes you heard it correct. But we all r trying our best to fight with it. And I truly believe that we will success in it. :)

Wish everybody safe and sound.

Karavaiev has a handsome avatar.

Thanks )))))

Is that actually you?

Yeap.)

Coming from a straight male, you got a beautiful upper face, to say the least.

Hope everyone will enjoy this contest...

2:15 for 5 problems looks so interesting and challenging :) good luck everyone!

2 hours were probably for A only.

The participants of the first division should participate after the contest (virtual participation) to prevent any slowness in queue or codeforces will go down

I completely disagree. There are too much bigger official participants comparing with participants from div1. Thus the last ones don't affect the competition too much, but their participations the most interesting, to be honest.

Registration:Total: 17738Contestants: 17502Out of competition: 236If those 236 persons didn't participate this will not make any change

its my first contest and i hope i can get top 10

good luck

5 problems in 2 hours 15 mins? Seem hard...

And it was...

Today is indeed a great day for a CF contest. You may not know it but today is the

International Masturbation Day!!! Today we must honor all those valiant kings who stayed sane during these hard times through performing this holy act.Happy Masturbation Dayto all!Can someone tell me what the rating for each of the problems will be rather than score?

That is decided after contest seeing the number of people who solved it during the live contest. So u can't get that before the contest . :)

let us just acknowledge the fact that the testers' list was ordered taken their colors in mind!

gimme some negative contribs, I am hungry fellas

don't you dare give me some positive contribs. I just want to have negative contribs and live a happy life.

A little time left. Be ready Everyone

Looks like there is a long queue of submissions pending to be judged. Hope this contest wont be affected.

Hope enjoy this round

Now rip!!!

Another chance for me to become Specialist...

hoping to become grandmaster in this contest

constructiveforces

Good luck to everybody having fun with this kind of problems.

Nastia play with my tree

Today's A seems tougher than usual A's.

This round is tough for me, getting 4 wrong on first problem only. :(

i got the approach, but was TLE for me, 2nd pretest!!!! this div2, hits me hard!!!

who the hell makes A this tough huh? set question for Div 1 if u want why ruining our scores?

true!!!

Nastia and Negative Rating

Nastia the little b*tch

problem C looks quite hard

Mathforces

There goes my green color

le me* = i dont know what is color!

`A. Nastia and a rating killing problem`

To all those not getting A, ig just read the problem carefully again!

i got the approach but got TLE in pretest2!

There was an O(1) solution to it. Maybe you should not have gone for brute force. I misread the problem, and wasted 30 minutes on it.

my first approach to solve this using maths, but unable to find relation :( that's why thought of brute force

In A if a number isin't divisible by (m*n) it doesnot mean that it is not divisible by m and n separately. So printing A A*b and A*(b+1) for all cases except when b is one gives AC!

I did that and it gave WA on test 2.

the condition you were checking is wrong . You were checking if (a%b==0) actually you only had to check if b is one.

Example:

your code would print NO for this but the answer is

`2 8 10`

That's the reason I wrote

if a number isin't divisible by (m*n) it doesnot mean that it is not divisible by m and n separatelyyeah，it is {a%b==0 ,then cout<<"No"<<endl;} that wa on problem A resulting in AC 0 problem in this test

可达鸭 nb

exactly reading the problem carefully in B was the key, I wasted sround 40 minutes coz of that EDIT : I thought you were talking about B but I faced this thing in B

lol

Stupid dashboard,,,

Totally Mathforces... lol

So, now we are badly in need of another round before the "Eid Day".

MikeMirzayanov

I submitted a solution (WA on given sample test) and then due to some technical problems, not able to continue further.

So, will my rating will be affected or not. I will be considered as participant ?

You, are going down son

Nice experience ::) Going down by 200

Specialist:- MY TIME HAS COME.

I just wonder why an expert deliver this contest ... I really think the quality of problems is bad .

Just because you were not able to solve them early??

Bro Deep down we all know problem A and B are very good.

The statement of A is vague . Otherwise means "if one is false ,then" so I use if(b%a==0)--> no

so this make me wa 4 times

what?? where did you find statement of A vague?

Yeah there wasn't any constraint on B which too tricked me for a while!

That is right (the definition of Otherwise).

If divisible by A*B = good integer

Otherwise (if the above statement is false then)

If divisible by A = nearly good integer

How did you arrive at b%a==0 condition using this??

Exactly man, I did the same...why the hell they can't write the statement properly.

What was bad about them?

About the statement.

I think A and B are like "guess the solution and trial and error them". I did not commit anything, and still not sure about if my solution for A would AC or not.

Edit: And just realized after contest, B: "You don't need to minimize this number." So I worked on another problem.

Yeah, I also worked on minimizing, but then noticed that if it was minimizing sample solution would be suboptimal

If anyone downvote me ,that is ok, i just want to express my feeling.

I don't think the problems were bad per se

But I don't like the steep cliff from B to C

You can downvote me if you want, but I thought C was a pretty shit problem overall. Idk what was so bad about it, my implementation didn't even end up being that bad...just thinking about all the cases and working around that god-awful min-max function ticked me off I guess :\

I don't think it was a bad problem, but do agree that it was hella painful to think about. took me like a decade just to test my program on sample 1

For me it was:

But problem itself was nice for me.

Agreed, everytime I had to test I couldn't just do the queries in my head I had to rewrite some code that evaluated the queries automatically and then remove that to submit.

The problem idea wasn't so bad though, I think the function given just made it really painful.

My thoughts exactly — and even though decoding and testing those equations was painful, it was overall an interesting problem as its solution deviated from the expected binary search solution to interactive problems.

I'm so sorry...，I wanted to upvote you,but I carelessly downvoted you, your comment makes great sense,i think.

I agree, even tho i solved it, it felt very vague.

Nice problems! Слава Україні.

Thanks! Героям Слава)

Doing heavy-light decomposition from arbitrary leaf and then connecting heads and tails isnt optimal in D?

I thought to divide by diameters and then join them. Do you think this is wrong?

I took the diameter of the tree and then added all the other nodes to the diameter one by one ,passed the sample but the logic wasn't correct as it gave wa on pretest 2 ,waiting for the tutorial...

You can consider the graph with 6 nodes in H form, the answer is 1.

Love this Contest!!

Video Tutorial A:https://www.youtube.com/watch?v=DyhSnRc8r0I&t=3s

Video Tutorial B: https://www.youtube.com/watch?v=o4rkgZ3ticM

For God's sake, this round was not Div2... :(

My answr to D is summation{max(0,degree-2)} over all vertices, is the answer less than this?

Waiting for editorial

wouldn’t then give you 0 on the first test?

Consider a graph with 6 nodes shaped like an H. There are two nodes of degree 3, so your answer will be 2. But you can get away with 1 by moving the middle line to the top.

Ohhhhhh, didnt think of this thanks a lot

oh That H Case I spend the whole contest trying to know why my solution not optimal :/

I should have taken more time to understand the questions, made silly mistake in A and B. But loved the overall experience and looking to learn from my mistakes.

what's the cruelest thing one can do?

RESTORE THE ANSWERI don't like it

How the heck to solve C ? Never seen such a problem like this. Actually A was badass. Could have told that the number might be divisible by B, only should not be divisible by AB

I think I was able to come up till 2*n solution but not know what to do for 3*n / 2

in ~[n/2] queries we can find the position of 1 (or n) and then using this position we can find the rest of the numbers in n-1(or n-2, doesn't matter) queries

First try to find position of n in array using query 1. You can do this by checking adjacent pairs and if their result is n-1, check the swap as well. This takes atmost ceil(n/2) + 2 queries.

Using this position of n, you can easily find all values via query 2. This takes at most n-1 queries.

So total queries are well under the limit.

Similar way you can do if you try to find position of 1.

Could you please expand ? I literally dont get it

Use $$$t = 2$$$ and $$$x = 1$$$ to find $$$1$$$ in permutation for $$$n / 2 + few$$$ queries (if $$$p_i == 1$$$ then answer is $$$1$$$);

Use $$$t = 1$$$ and $$$x = n - 1$$$ to find other numbers in permutation for $$$n - 1$$$ queries (if $$$p_i == 1$$$ then answer is $$$p_j$$$).

? t i j x Important observation: t=1 and x=n-1

max(min(n-1,Pi),min(n,Pj)) equals— n-1 if Pi=n — max(Pi,Pj) otherwiset=2 and x=1

min(max(1,Pi),max(2,Pj)) equals— 2 if Pj=1 — min(Pi,Pj) otherwise if anyhow by using t=1 and x=n-1 we get the position of n in the permutation in <= (n/2)+30 queries , we can get remaining elements by using t=2 and x=1 in n-1 queries we can get the remaining elements in n-1 more queries.How to get the index of n ?? we can see that for (i,j) t=1 and x=n-1 the output can be n only when Pj=n if output is n-1 Pi can be n we can check take (i,j) like this ( 1 2 ) ( 3 4 ) ( 5 6 ) . . . if the output during any stages is n we get index_of_n otherwise we get a set of possible values of index_of_n (corresponding to output n-1,with max 2 possibilites)

so we can check the index of n in max (n/2) + 2 queries after that our job is done

I wish I could just unsubmit my solutions and wait for the next contest.

hello, tried to participate for the first time — failed miserably :) (I didn't have full 2 hours anyway, but not sure it would help if I did). One question — what are pretests ? my submission failed pretest 3 (am I supposed to be able to see pretests ?) I only was able to see the example test provided in the description of the problem. Thank you

Pretests are cases that will be tested during the contest. Not all of them will be visible to you. And there will be more tests following in the system test phase after the contest.

Check out this: https://codeforces.com/blog/entry/4088

Pretest are certain test on which your program runs on . You are not able to see the pretest during the contest but you can see them afterwards!

Hope this helped!

Cool, I can see them now. Looks like I should have use longs instead of ints :-) Rookie mistake

Good bye expert

Don't be sad! Good luck on the next contest! You will comeback

How to do C?

My idea was to find any one element via binary search using 30 queries ( preferably the first element), then keep constructing the permutation from left to right using at most 2 queries each. I implemented the second one, but couldn't exactly figure out how to find the first element.

you can find the maximum of the permutation in about n/2 moves with t = 1, x = n-1, changing i and j every time. If you get the result n, j is the position of the max. If you ever find an n-1, try for j and i. If then you get the result n, that means i is the position of the max.

And then using the maximum you can use t = 2, x = 1 to find each element in n moves.

Indices are have to be different. I wasted 30 mins implementing this then noticed the statement.

My not so interesting solution.

HintFind the position of $$$1$$$($$$pos1$$$) and you can determine the values of the remaining positions($$$j$$$ not equal to $$$pos1$$$) with queries of type $$$t = 1$$$, $$$pos1$$$, $$$j$$$ and $$$x = n - 1$$$ in at most $$$n - 1$$$ queries.

Full SolutionWe can find the position of $$$1$$$ in at most $$$n / 2 + 2$$$ queries.

We query the indexes in pairs $$$(1, 2), (3, 4) ... (n - 1, n)$$$ with queries of type $$$t = 2$$$, $$$x = 1$$$.

If a query of returns $$$1$$$ for a pair then it's obvious that the first index in the pair is equal to $$$1$$$.

If the position with $$$1$$$ is the second index in a pair then at most $$$2$$$ of the pairs of queries will return $$$2$$$.

One with $$$1$$$ as a second value and another with $$$2$$$ as a second value.

And we can easily check if any one of those is equal the position with $$$1$$$.

If none of them is then $$$n$$$ is odd and the last position is equal to $$$1$$$.

After that the rest is straightforward

Get the position of $$$1$$$($$$pos1$$$) and you can determine the values of the remaining positions($$$j$$$ not equal to $$$pos1$$$) with queries of type $$$t = 1$$$, $$$pos1$$$, $$$j$$$ and $$$x = n - 1$$$ in at most $$$n - 1$$$ queries.

Asking queries of type 1 with $$$x=n-1$$$ will give you the maximum value among two positions asked. If the answer to the query is $$$n-1$$$, just ask the same two position again with $$$n-1$$$ value and take the greater answer of the two queries asked.

Same thing with min and queries of type 2.

After you get the maximum and the minimum, one query of type one for two position with value equals to $$$minValue$$$ (found above) will tell you which of them is the larger and which is the smaller.

I took 12 queries to figure out exactly what the first three elements are.

Then I query every other element (of index

`idx`

) with the largest known element (of index`maxidx`

)`t=2, i=idx, j=maxidx, x=1`

`t=1, i=maxidx, j=idx, x=n-1`

I update the largest known element along the way.

The worst case is still 2n. To avoid the worst case, I shuffle the remaining queries.

I had exactly this solution: 115619047

To find the value of the first element I used binary search:

After checking different values of $$$x$$$, I relaized that the query of type $$$1$$$ returns $$$x+1$$$ if and only if $$$x \leq p_j$$$. And it doesn't even matter what the value of $$$p_i$$$ is. This allows us to do binary search on $$$x$$$ to find the value of $$$p_1$$$, by doing queries like $$$(t=1, i=2, j=1, x=mid)$$$, where $$$mid$$$ comes from our binary search.

After we found the value of $$$p_1$$$, we can find the value of every other element in at most 2 queries. But in the worst case it might be exactly 2 queries per element, e.g. if the permutation is sorted in reverse. That's why I shuffled the indices, hoping that it will take 1.5 queries on average.

Why was problem statement of B written in reverse order? It was so confusing before the statement got changed. The conversion of pair was written before the condition which didn't make any sense.

Isnt finding the diameter of the tree and then using Topological Sorting the intended solution for D.

ya I am thinking the same, like partition tree into a minimum number of line graphs and then join those graphs, it can be done in O(n) I think, but couldn't implement

Today I learnt that being divisible by

`a*b`

is not equivalent to being divisible by`a`

and divisible by`b`

.how? please give me some example

for example 12 is divisible by 4 and 6. but is not divisible by 24 (4*6)

Your right but

He said the converse, which I think isn't correct.

24 being divisible by 24 is equivalent to 24 being divisible by 4 & 6.

48 being divisible by 24 is equivalent to 48 being divisible by 4 & 6. and so on...

Sometimes the things which appear to be so obvious also turn out to be wrong.

1) ConstructiveForces 2) MathForces 3) PoorForces

My solution for A -> 115536899 and B -> 115585971

Why I kept reading "a*b" as "a and b" in the A problem?

problem B was looking carefully on constraints.

a[i]<=1e9

x,y <=2e9 and 1e9+7>1e9 is prime :)

I just forgot (1e9+7)it was first prime after (1e9) i was using Segmented Sieve to find prime above 10^9 in last minute.

Yaaa, I exploited the same and used a segmented sieve to calculate primes from $$$1e9$$$ to $$$1e9 + 1e7$$$, and turned each number into a prime other than the smallest one.

`int A[] = {1000000409, 1000000411, 1000000427, 1000000433, 1000000439, 1000000447};`

all are primes greater than 1e9 I made this array and turned every element except smallest element into one of these elements.I feel Pepega right now.

Oh shit!!! I didn't notice. Will take care next time...

I didn't notice it too. I used an alternative that does not need to consider the constraint. I first iterate to find the minimum value. Then, change all values to "min" and "min+1" alternatively. So basically, I need n-1 operations for all cases.

realized that except the minimum element all elements can be changed to any other so simply swapped the first and minimum element and did a[i]=a[i-1]+1 for all i bw [1,n-1]

Got it right after the contest T_T.

I approached another simple solution . As all the consecutive pair of integers are co-prime so just find the minimum element and its index from the array. Then change all the elements according to this order. Suppose the array is

`a[]={9, 6, 3, 5, 11}`

minimum element is 3 so change the array into`a[]={5, 4, 3, 4, 5}`

That means make the elements increasing order from the minimum index to left and right.What was the answer to D? What was the counterexample to selecting the maximum diameter for a tree, disconnecting the edges on the maximum diameter path, and then recursing on each individual component to create the bamboo?

Exactly!!! I also tried the same approach but I made a stupid implementation mistake :/, got RE instead. :(

1 2

1 3

1 4

1 5

5 6

5 7

5 8

Dia is 2 — 1 — 5 — 7 but ideally 1 — 5 should be removed

FRICK

What was the actual solution then?

Well, I did a DFS. While leaving nodes I removed iteratively edges, which connect two nodes with both of them with >2 neighbours (this fixes two nodes). Then I traversed all nodes again and removed edges from each node with >2 neighbours (this fixes only one node).

Then I have only sub-Bamboos left and need to stick them together on the ends.

It passed the Pretests, but it is very greedy like this, the only sorting is the DFS. Not sure whether it passes Tests.

Edit: Yes, it passed the Tests: 115602037

I first find the minimum path cover of the tree using dp, and then reconstruct those paths and connect them. 115645578

The following graph with 10 vertices was helpful for me to think about it:

You can solve this with 2 removals, but your method will make more if I understand it correctly

Yeah u rite, I would take 4 while urs 2. What was the actual solution then?

You want to remove as many edges which connect 2 nodes of degree 3 or higher as possible (call these type 1), then remove extra edges off of nodes of degree 3 or higher (call these type 2).

However, the example I showed proves that doing this randomly won't work (what if you accidentally remove the middle edge first? Your answer will be 3.

If you consider the graph of only nodes with degree 3 or higher, then you will always make an ok move if you remove the type 1 edge branching off those nodes. Then when the graph is all singletons, you can just remove the rest of the type 2 edges.

However, this is pretty finicky to implement and there may be a preferable solution. https://codeforces.com/contest/1521/submission/115618524

Yeah, I guess that also sounds like my solution: 115602037. To sort type 1 nodes I used a DFS and checked for them while leaving the nodes.

Consider the tree that looks like an H.

We can build the bamboo with 2 operations by removing the middle edge and reconnecting the both parts then.

With the longest path algo we need 3 operations.

OK... Only solve A... WA 5 times. LOL

Tbh felt more like Div1 than Div2, solving only A and B in Div2 sounds bad..

FOR A why is this incorrect x+y==z (a)+(a*b)==(b+1)*a ng g ng

if(a==b||b==1)---no else yes???

A can be equal to B take 2 2 for example you can make x = 2, y = 4, z = 6

but here there are more than 1 good int..it should PRINT NO ?

Y=4&&Z=4 ARE TWO GOOD INT HERE.

Why is z = 4 ? (2+1)*2 = 6

Only 4 is a good int here ,as good int are divisible by A*B 2 and 6 are nearly good int as they are divisible by A

if(b==1)then only no friend

Why b==1 mate? If we have 7 1 can't we display 7 14 and 21

1 is divisible by all 3

For a = b, a*(b-1) + a = a*b

In case of a==b (of course b is not equal to 1) also , a*b + a = a*(b+1) will work As only there is 1 good int i.e. a*b and 2 nearly good int's a,a*(b+1)

He has written NO for a=b case.

There is answer if $$$a == b$$$

If $$$A = 5, B = 5$$$ then you can print $$$20\ 5\ 25$$$. First two divisible by $$$5$$$. Third divisible by $$$25$$$.

a could be equal to b

For example take a = b = 8, x = 8 , y = 56 and z = 64

I can explain my solution if b is 1 then the answer is no, since in this case b will divide all no.s x=a*(b-1) if b is not 2, y=a , and z=a*b , a*(b-1)+a=a*(b-1+1)=a*b else x=a*(b+1) , y=a , z=a*(b+2) , here since b is 2 , so b will divide (b+2)

print A*B , A , A*B + A when B!=1 and when B==1 answer as NO

Link to Explanation of Problem A

I taught I can solve Problem D- so spent all the time writing and debugging it. Finally got Run Time error in the Hidden Test case. I don't know where I went wrong in my code. but I could have spent time-solving A, B, and maintained my Rating. but I taught of giving a try to know what can I do.

I just need to know, where I took the right decision(lost -150 rating), or is there any better decision I could have made?

What I think is that the ranking is not really important until you are in the top. You followed your instinct, today it didn't work, just try to understand what made you think you could do it "easily" and not repeat the mistake. I think that being fixed on your rating when you are so low does not help you except to demoralize you.

How to solve D ??

I swear those min/max functions in C looked exactly like this on my screen...

I got hitmotised honestly!

Solved A in 2 attempts, and B in 6 !! Really great questions, learned a lot. _/_

My learnings from the contest: Nobody knows what a good array looks like

I was able to solve D by reducing the problem to the minimal path cover problem and solving that using dynamic programming. Is there any other way to solve for the minimal path cover in a tree?

Can you please also give links to minimal path cover good articles?

Also, can you tell any case where minimum answer won't be just cascading child (when >1 for non-root node)? Can't think of even that :(

An Illusion which forces you to find diameter of a tree -

SpoilerProblem D

Truly interesting round, but I lost tons of point on WA :(

By the way, how to solve E...I tried to construct a grid like this:

Where $$$x$$$ presents the number. And then expand this grid's size by one per step, randomly fill other numbers in available positions.

New property found :> being divisible by a and b separately doesn't mean divisible by a*b. :'

I took 30 minutes to realize this XD

In problem B, earlier it was "any i" then it got changed to "all i's".. -- WA.

Also, Goodbye expert :p

The given sample testcases should've cleared it out, I had to check them to make sure I was getting it right. Although all in all yes the question was poorly written at the start of the contest.

My idea for Div2D

Is this logic correct ?

I think, it's wrong. I took this counterexample:

Your algorithm can remove the middle edge and then it can't be done in 2 removals.

Thank you !

i wish, i could undo myself 3 hours back!

Is it round from I_love_myself? (According to the names of the tasks)

Unfortunately, no. But Nastya is happy!!

Thanks for the contest, I really like problems B and E. None of the problems alone are bad, however looking at all of them together felt monotonous. There wasn't much diversity in the set and the statement seemed confusing at times.

div 1.5 huh?

more like div 1.25 tbh

Deleted.

More like 1.3141592653589793238462643383279502884197169399375105820974944 5923078164062862089986280348253421170679821480865132823066470938446095 5058223172535940812848111745028410270193852110555964462294895493038196 4428810975665933446128475648233786783165271201909145648566923460348610 454326648213393607260249141273724587006606315588174881520920 9628292540 9171536436789259036001133053054882046652138414695194151160943305727036 5759591953092186117381932611793105118548074462379962749567351885752724 8912279381830119491298336733624406566430860213949463952247371907021798 6094370277053921717629317675238467481846766940513200056812714526356082 778577134275778960917363717872 tbh

Problem tag of B is showing it's a 2-SAT problem.How???It seemed to me a very normal problem and I solved it.Where is the use of 2-SAT?

Maybe because the way I solved was by assigning conflicting values to 2 prime numbers bigger than the max of the array. Can't say for sure though.

I solved it by using 2 prime numbers bigger than the min of the array. It is 2-SAT because for each index of the array you have choice of 2 values.

Was only able to solve, A and B, so maybe I'm not qualified enough to say this, but the problems were good. Especially the B one, had to stress test my code to find a mistake XD. Also, problem A showed me the importance of reading a problem carefully and not underestimating A (spent over 30 minutes on it LOL). Don't know if I'll sink or swim in this one, but it was a fun one.

for Problem A,

a=1, b=1

why x=1, y=2 ,z=3 is not a answer? x+y=z

Because all three numbers are divisible by $$$A * B = 1$$$. You required that exactly one number is divisible by $$$A * B$$$

Because, x,y,z are good(x,y,z are divisible with a*b=1*1=1)

no ; cause x,y,z all are divisible by A*B mean there all Value is good......but condition is any 1 Value good......

because 1, 2, and 3 are all divisible by (a * b = 1)

Just commenting because I saw the fireboy image and could not find icegirl. Used to think nobody liked the game(except me)

it is a pretty interesting game really... also, its watergirl :)

all of them are divisible by a*b.

There should be only one number that is divisible by a*b

All the numbers are divisible by a*b so all the 3 numbers are good according to the problem

I solved B by converting the array in the following way — {1e9 + 7 , min(a[0],a[1]) , 1e9 + 7, min(a[2],a[3]), 1e9 + 7 ........}. Then if n is odd I make a final operation n-1 and n-2 making a[n-1] = 1e9 + 7 and a[n-2] = min(a[n-1],a[n-2]). Here is my solution(https://codeforces.com/contest/1521/submission/115604019).

explain the approach of A bro? i got TLE!

For A, x = a, y = a*b and z = a*b + a works for all values of a and b except if b = 1, If b is equal to 1 we can prove that solution does not exist

i got this by seeing ur code! but what's the intuition! bdw, thanks I got it!

Link to Explanation of Problem A

Can we place min first and then 1e9 + 7

I think the authors wrote Div.2 instead of Div.1 by mistake. (not saying contest was bad. It's just I was bad at those questions)

true, lol

At least A and B was ok for div2

The comment is hidden because of too negative feedback, click

hereto view itWhy does 115570549 give MLE for B?

If $$$n = 1$$$ you output 0, but don't read the array element, so on the next iteration you'll read the array element instead of $$$n$$$, which can be up to $$$10^9$$$.

Solution for Div2B without using

`10^9+7`

. Find the index of minimum element(if there are more than one choose any). Let's call it`idx`

. Now use this index with every other index`i`

and do,Yes, did the same

I did in same way :)Link

What wrong in my solution? https://codeforces.com/contest/1521/submission/115596986

Try this,

1

3

35 9 5

Answer should be zero . My also giving zero.

I apologize, my bad. Try this,

1

3

2 21 14

Yes got it. Thanks

Mine Even simpler

bad contest, very bad problem C. Please don't allow blue to make any contest from now.

Looks like my dream of becoming an expert will always be a dream :(

no mate you will be there in a month.

Level of questions were very good. Even first problem was good enough to take time.

for problem c i listed all the possibilities, and figured that if query(t = 2, l, r, x) gets the answer exactly x meanwhile query(t = 1, r, l, x) gets the answer lower or equal to x, then p(i) is not more than x. thus we can do binary search and the total queries will not exceed nlogn. however it got WAed on pretest 3, may someone help me?

$$$n * log(n) \ge (3n / 2) + 30$$$ for big $$$n$$$.

Thanks, I even forgot how to compare them during the contest! What a stupid mistake :P

problem (A+B) video Tutorial Link : https://youtu.be/eoG05DnVQik

Hopefully, I can become an expert for the first time. BUT I DID'T

Rebecoming expert here

I really liked the idea behind problem D. It was just amazing. Although i wasn't able to solve D in the contest but learnt a lot.

Btw great contest.

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

In problem A if we give input in which 'a' is a multiple of 'b' the answer should be NO but according to judge it's YES . Can anyone tell me why.