### Karavaiev's blog

By Karavaiev, 6 weeks ago,

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:

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:

• +273

 » 6 weeks ago, # |   +63 hope the problems are as interesting as your rating graph
•  » » 6 weeks ago, # ^ |   +8 Interesting!!
•  » » 6 weeks ago, # ^ |   +33 Makes sense actually )))
•  » » » 5 weeks ago, # ^ |   0 Karavaiev Why are Interaction Problems actually useful when we can do it normally(In the sense standard way of I/O) as well.
•  » » » » 5 weeks ago, # ^ |   +4 for example: https://codeforces.com/contest/1504/problem/D
•  » » 5 weeks ago, # ^ |   +4 So interesting（）
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 They were mostly like this symbol :): Its on you how you feel.....The Problems were Interesting btw in my opinion....
 » 6 weeks ago, # |   +21 PurpleCrayon orz !
•  » » 6 weeks ago, # ^ |   +48 As a loyal PurpleCrayon Fan, PurpleCrayon orz.
•  » » » 6 weeks ago, # ^ |   +48 as also a loyal purplecrayon enthusiast, PurpleCrayon orz!
•  » » » » 6 weeks ago, # ^ |   +44 PurpleCrayon is an inspiration to me. PurpleCrayon orz!
•  » » » » » 6 weeks ago, # ^ |   +36 how PurpleCrayon so geniosity orz
•  » » » » 6 weeks ago, # ^ |   +24 as a loyal purplecrayon enjoyer, Purple Crayon orz!
 » 6 weeks ago, # | ← Rev. 2 →   +2 Interesting scoring distribution, hope its_Atrap like CodeCraft-21 and Codeforces Round #711 (Div. 2)
•  » » 6 weeks ago, # ^ |   +16 Is it a trap? You can check soon :)
•  » » » 6 weeks ago, # ^ |   +2 Yes I will check it during contest since I am neither a setter nor a tester :(
•  » » » 5 weeks ago, # ^ |   +15 It wasn't a trap, rather questions were very interesting!!!
 » 6 weeks ago, # |   -39 namanbansal013orz!!
 » 6 weeks ago, # | ← Rev. 2 →   +10 Hope problem C will be interactive! :)
•  » » 5 weeks ago, # ^ |   +7 Are you a time traveller?
•  » » » 5 weeks ago, # ^ |   0 I think he is
 » 6 weeks ago, # |   +17 Another chance for me to become Specialist... or Newbie
•  » » 6 weeks ago, # ^ |   +16 Hope you handle it well!
•  » » 5 weeks ago, # ^ |   +1 I know you can do it for Specialist, my friend...
•  » » 5 weeks ago, # ^ |   0 Nice try
•  » » 5 weeks ago, # ^ |   +1 crap that didn't go well
 » 6 weeks ago, # | ← Rev. 2 →   -9 I think the problems will be cool!
 » 6 weeks ago, # |   +5 excited to participate in this contest ... seems to be amazing :)
 » 6 weeks ago, # |   -52 My First Rated Contest :D, I hope I can make Tanya proud :)
•  » » 6 weeks ago, # ^ |   +29 She will be proud of you (for getting so much down vote) xD. Just a joke.
•  » » » 6 weeks ago, # ^ |   -43 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
•  » » » » 6 weeks ago, # ^ |   +173 I being Tanya's father reject this relationship.
•  » » » » » 5 weeks ago, # ^ |   -7 Huge respect Bhai:-D
•  » » » » » 5 weeks ago, # ^ |   +22 ahm...ahm... Say it Again (if you wanna get thrown out the house) :/
 » 6 weeks ago, # |   +26 Problem C 1750 Points ! a bit scary.
 » 6 weeks ago, # |   +9 which problem will be interactive? Any guesses?
•  » » 5 weeks ago, # ^ |   0 I guess problem D :P . Don't take it seriously. This is only my guess.
 » 6 weeks ago, # | ← Rev. 2 →   -32 Resolved... Thanks!
•  » » 6 weeks ago, # ^ |   +23 Sorry but why down-votes? I was just seeking to get help and improve.
•  » » » 6 weeks ago, # ^ | ← Rev. 4 →   +41 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 fasterupd: please note that i am not really good in this aspects of C++, so it is probably better not trust me D:
 » 6 weeks ago, # |   +1 hope i can solve c
•  » » 6 weeks ago, # ^ |   +4 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 :).
•  » » » 6 weeks ago, # ^ |   +6 "..., Hope is a good thing, maybe the best of things, and no good thing ever dies." The Shawshank Redemption
•  » » » » 5 weeks ago, # ^ |   0 May be the best movie I've ever seen.(apart 'Parasite')
•  » » 6 weeks ago, # ^ |   +1 hope too)
 » 6 weeks ago, # |   +7 PurpleCrayon orz
 » 6 weeks ago, # | ← Rev. 2 →   -52 Guys, can you please press green triangle to raise this round's contribution
•  » » 6 weeks ago, # ^ |   0 Not for you I guess
 » 6 weeks ago, # |   +7 The problems seems very elegant after watching their score distribution, you should participate in the round.
 » 6 weeks ago, # |   +4 Let's hope the server will not get down in this contest
 » 6 weeks ago, # |   0 All the best to all the contesters!!! Wish u luck
 » 6 weeks ago, # |   -37 Want Ashishgup div 2 rounds.
•  » » 6 weeks ago, # ^ |   +75 me too :) but cannot offer this one tomorrow :(
 » 6 weeks ago, # |   -13 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/115326611you can remove Fast i/o fflush(stdout) that will worksubmission link ->https://codeforces.com/contest/1520/submission/115344437in same code i used cout.flush() it worked with Fast i/o.submission link -> https://codeforces.com/contest/1520/submission/115336786
•  » » 6 weeks ago, # ^ |   0 endl.
 » 6 weeks ago, # |   0 That C's rating makes it so sus for interactive problem!
•  » » 6 weeks ago, # ^ |   0 why? I never attempt an interactive problem before
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 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 tomorrow you 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!
•  » » 6 weeks ago, # ^ |   +25 Typical interactive problem:Div.2 C — 70% probabilityBinary Search — 95% probability
 » 6 weeks ago, # |   +7 the same day as my birthday)) (tomorrow)
•  » » 6 weeks ago, # ^ |   +3 You can get a birthday color :)
 » 6 weeks ago, # |   +3 Hoping to learn something new from the questions. All the best to everyone :)
 » 6 weeks ago, # | ← Rev. 3 →   0 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.
 » 6 weeks ago, # |   0 Good Luck Everyone!!!
 » 6 weeks ago, # |   0 Hopefully problems will be interesting. Another chance for me to become pupil.
 » 6 weeks ago, # |   0 what are the difference between the divs? I'm not very familiar with this CP platform.
•  » » 6 weeks ago, # ^ |   +3 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.
•  » » 6 weeks ago, # ^ |   0 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.
 » 6 weeks ago, # |   0 Thanks a lot. Waiting for the contest
 » 6 weeks ago, # |   0 Last Global Round I passed out and my rating reduced. Hope my name turn blue again.
•  » » 6 weeks ago, # ^ |   0 me struggling for cyan.
•  » » » 6 weeks ago, # ^ |   0 Hope you can be cyan soon. Moreover,I heard that the disease in India is quite serious now from media，Really？
•  » » » » 6 weeks ago, # ^ |   0 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. :)
•  » » » » » 6 weeks ago, # ^ |   0 Wish everybody safe and sound.
 » 6 weeks ago, # |   +27 Karavaiev has a handsome avatar.
•  » » 6 weeks ago, # ^ |   +6 Thanks )))))
•  » » » 6 weeks ago, # ^ |   0 Is that actually you?
•  » » » » 6 weeks ago, # ^ |   +12 Yeap.)
•  » » » » » 6 weeks ago, # ^ |   +17 Coming from a straight male, you got a beautiful upper face, to say the least.
 » 6 weeks ago, # |   -8 Hope everyone will enjoy this contest...
 » 5 weeks ago, # |   +3 2:15 for 5 problems looks so interesting and challenging :) good luck everyone!
•  » » 5 weeks ago, # ^ |   +6 2 hours were probably for A only.
 » 5 weeks ago, # | ← Rev. 3 →   -70 The participants of the first division should participate after the contest (virtual participation) to prevent any slowness in queue or codeforces will go down
•  » » 5 weeks ago, # ^ |   +42 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.
•  » » 5 weeks ago, # ^ |   +16 Registration:Total: 17738Contestants: 17502Out of competition: 236If those 236 persons didn't participate this will not make any change
 » 5 weeks ago, # |   +8 its my first contest and i hope i can get top 10
•  » » 5 weeks ago, # ^ |   +11 good luck
 » 5 weeks ago, # | ← Rev. 3 →   0 5 problems in 2 hours 15 mins? Seem hard...
•  » » 5 weeks ago, # ^ |   0 And it was...
 » 5 weeks ago, # |   -65 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 Day to all!
 » 5 weeks ago, # |   0 Can someone tell me what the rating for each of the problems will be rather than score?
•  » » 5 weeks ago, # ^ |   +5 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 . :)
 » 5 weeks ago, # |   +13 let us just acknowledge the fact that the testers' list was ordered taken their colors in mind!
 » 5 weeks ago, # |   -53 gimme some negative contribs, I am hungry fellas
•  » » 5 weeks ago, # ^ |   -42 don't you dare give me some positive contribs. I just want to have negative contribs and live a happy life.
 » 5 weeks ago, # |   0 A little time left. Be ready Everyone
 » 5 weeks ago, # |   +22 Looks like there is a long queue of submissions pending to be judged. Hope this contest wont be affected.
 » 5 weeks ago, # |   0 Hope enjoy this round
•  » » 5 weeks ago, # ^ |   0 Now rip!!!
 » 5 weeks ago, # |   0 Another chance for me to become Specialist...
 » 5 weeks ago, # |   +17 hoping to become grandmaster in this contest
 » 5 weeks ago, # |   +90 constructiveforces
 » 5 weeks ago, # |   +29 Good luck to everybody having fun with this kind of problems.
 » 5 weeks ago, # |   0 Nastia play with my tree
 » 5 weeks ago, # |   -9 Today's A seems tougher than usual A's.
 » 5 weeks ago, # |   0 This round is tough for me, getting 4 wrong on first problem only. :(
•  » » 5 weeks ago, # ^ |   -12 i got the approach, but was TLE for me, 2nd pretest!!!! this div2, hits me hard!!!
 » 5 weeks ago, # |   -25 who the hell makes A this tough huh? set question for Div 1 if u want why ruining our scores?
•  » » 5 weeks ago, # ^ |   -16 true!!!
 » 5 weeks ago, # |   +47 Nastia and Negative Rating
•  » » 5 weeks ago, # ^ |   +30 Nastia the little b*tch
 » 5 weeks ago, # |   +1 problem C looks quite hard
 » 5 weeks ago, # |   -12 Mathforces
 » 5 weeks ago, # |   +2 There goes my green color
•  » » 5 weeks ago, # ^ |   0 le me* = i dont know what is color!
 » 5 weeks ago, # |   +27 A. Nastia and a rating killing problem
 » 5 weeks ago, # |   0 To all those not getting A, ig just read the problem carefully again!
•  » » 5 weeks ago, # ^ |   -8 i got the approach but got TLE in pretest2!
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   0 my first approach to solve this using maths, but unable to find relation :( that's why thought of brute force
•  » » » » » 5 weeks ago, # ^ |   0 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!
•  » » » » » » 5 weeks ago, # ^ |   0 I did that and it gave WA on test 2.
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 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: 1 2 4 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 separately
•  » » » » » » » » 5 weeks ago, # ^ |   0 yeah，it is {a%b==0 ,then cout<<"No"<
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 5 weeks ago, # |   +41
 » 5 weeks ago, # |   +125
•  » » 5 weeks ago, # ^ |   0 lol
 » 5 weeks ago, # |   +8 Stupid dashboard,,,
 » 5 weeks ago, # |   -34 Totally Mathforces... lol
 » 5 weeks ago, # |   0 So, now we are badly in need of another round before the "Eid Day".
 » 5 weeks ago, # | ← Rev. 2 →   -22 MikeMirzayanovI 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 ?
•  » » 5 weeks ago, # ^ |   +37 You, are going down son
•  » » » 5 weeks ago, # ^ |   0 Nice experience ::) Going down by 200
•  » » 5 weeks ago, # ^ |   0 Specialist:- MY TIME HAS COME.
 » 5 weeks ago, # | ← Rev. 2 →   -12 I just wonder why an expert deliver this contest ... I really think the quality of problems is bad .
•  » » 5 weeks ago, # ^ |   +16 Just because you were not able to solve them early??Bro Deep down we all know problem A and B are very good.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +31 The statement of A is vague . Otherwise means "if one is false ,then" so I use if(b%a==0)--> noso this make me wa 4 times
•  » » » » 5 weeks ago, # ^ |   +3 what?? where did you find statement of A vague?
•  » » » » 5 weeks ago, # ^ |   0 Yeah there wasn't any constraint on B which too tricked me for a while!
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +4 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 integerHow did you arrive at b%a==0 condition using this??
•  » » » » 5 weeks ago, # ^ |   0 Exactly man, I did the same...why the hell they can't write the statement properly.
•  » » 5 weeks ago, # ^ |   +6 What was bad about them?
•  » » » 5 weeks ago, # ^ |   0 About the statement.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -11 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.
•  » » » » 5 weeks ago, # ^ |   0 Yeah, I also worked on minimizing, but then noticed that if it was minimizing sample solution would be suboptimal
•  » » 5 weeks ago, # ^ |   0 If anyone downvote me ,that is ok, i just want to express my feeling.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 I don't think the problems were bad per seBut I don't like the steep cliff from B to C
 » 5 weeks ago, # |   +225 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 :\
•  » » 5 weeks ago, # ^ |   +32 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
•  » » 5 weeks ago, # ^ |   +6 For me it was: Lack of simple way to check implementation instead of writing test interactor (maybe I just didn't find one of course). min/max conditions was too far away of concrete samples. Scrolling up/down or rewrite to paper or open two tabs in one screen — neither of them is nice for me. But problem itself was nice for me.
•  » » » 5 weeks ago, # ^ |   +10 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.
•  » » » 5 weeks ago, # ^ |   +3 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.
•  » » » » 5 weeks ago, # ^ |   +2 I'm so sorry...，I wanted to upvote you,but I carelessly downvoted you, your comment makes great sense,i think.
•  » » 5 weeks ago, # ^ |   +8 I agree, even tho i solved it, it felt very vague.
 » 5 weeks ago, # |   +18 Nice problems! Слава Україні.
•  » » 5 weeks ago, # ^ |   +13 Thanks! Героям Слава)
 » 5 weeks ago, # |   +6 Doing heavy-light decomposition from arbitrary leaf and then connecting heads and tails isnt optimal in D?
•  » » 5 weeks ago, # ^ |   0 I thought to divide by diameters and then join them. Do you think this is wrong?
•  » » » 5 weeks ago, # ^ |   0 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...
•  » » » » 5 weeks ago, # ^ |   +12 You can consider the graph with 6 nodes in H form, the answer is 1.
 » 5 weeks ago, # |   -12 Love this Contest!!
 » 5 weeks ago, # |   -17 Video Tutorial A:https://www.youtube.com/watch?v=DyhSnRc8r0I&t=3sVideo Tutorial B: https://www.youtube.com/watch?v=o4rkgZ3ticM
 » 5 weeks ago, # |   +24 For God's sake, this round was not Div2... :(
 » 5 weeks ago, # |   +11 My answr to D is summation{max(0,degree-2)} over all vertices, is the answer less than this?Waiting for editorial
•  » » 5 weeks ago, # ^ |   0 wouldn’t then give you 0 on the first test?
•  » » 5 weeks ago, # ^ |   +52 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.
•  » » » 5 weeks ago, # ^ |   0 Ohhhhhh, didnt think of this thanks a lot
•  » » » 5 weeks ago, # ^ |   +3 oh That H Case I spend the whole contest trying to know why my solution not optimal :/
 » 5 weeks ago, # |   +5 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.
 » 5 weeks ago, # |   +66 what's the cruelest thing one can do? RESTORE THE ANSWER
 » 5 weeks ago, # |   +11 I don't like it
 » 5 weeks ago, # | ← Rev. 2 →   +14 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
•  » » 5 weeks ago, # ^ |   +1 I think I was able to come up till 2*n solution but not know what to do for 3*n / 2
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +10 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
•  » » 5 weeks ago, # ^ |   +4 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.
•  » » » 5 weeks ago, # ^ |   +3 Similar way you can do if you try to find position of 1.
•  » » » 5 weeks ago, # ^ |   0 Could you please expand ? I literally dont get it
•  » » 5 weeks ago, # ^ |   +3 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$).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 ? 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
 » 5 weeks ago, # |   +24 I wish I could just unsubmit my solutions and wait for the next contest.
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 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!
•  » » » 5 weeks ago, # ^ |   0 Cool, I can see them now. Looks like I should have use longs instead of ints :-) Rookie mistake
 » 5 weeks ago, # |   +29 Good bye expert
•  » » 5 weeks ago, # ^ |   +1 Don't be sad! Good luck on the next contest! You will comeback
 » 5 weeks ago, # | ← Rev. 2 →   +4 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 Indices are have to be different. I wasted 30 mins implementing this then noticed the statement.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 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) First I use a type 2 query that works if the other element is smaller t=2, i=idx, j=maxidx, x=1 If the other element is larger, I follow up with a type 1 query 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.
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   +17 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.
 » 5 weeks ago, # |   0 Isnt finding the diameter of the tree and then using Topological Sorting the intended solution for D.
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   +56 Today I learnt that being divisible by a*b is not equivalent to being divisible by a and divisible by b.
•  » » 5 weeks ago, # ^ |   0 how? please give me some example
•  » » » 5 weeks ago, # ^ |   +1 for example 12 is divisible by 4 and 6. but is not divisible by 24 (4*6)
•  » » » » 5 weeks ago, # ^ |   0 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...
•  » » 5 weeks ago, # ^ |   0 Sometimes the things which appear to be so obvious also turn out to be wrong.
 » 5 weeks ago, # |   -7 1) ConstructiveForces 2) MathForces 3) PoorForces
 » 5 weeks ago, # |   -20 My solution for A -> 115536899 and B -> 115585971
 » 5 weeks ago, # |   +30 Why I kept reading "a*b" as "a and b" in the A problem?
 » 5 weeks ago, # | ← Rev. 2 →   +15 problem B was looking carefully on constraints.a[i]<=1e9x,y <=2e9 and 1e9+7>1e9 is prime :)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   +1 I feel Pepega right now.
•  » » 5 weeks ago, # ^ |   0 Oh shit!!! I didn't notice. Will take care next time...
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 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]
•  » » 5 weeks ago, # ^ | ← Rev. 7 →   0 Got it right after the contest T_T. if(n==1) cout<<0<
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 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 isa[]={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.
 » 5 weeks ago, # |   +7 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?
•  » » 5 weeks ago, # ^ |   0 Exactly!!! I also tried the same approach but I made a stupid implementation mistake :/, got RE instead. :(
•  » » 5 weeks ago, # ^ |   +8 1 2 1 3 1 4 1 5 5 6 5 7 5 8Dia is 2 — 1 — 5 — 7 but ideally 1 — 5 should be removed
•  » » » 5 weeks ago, # ^ |   0 FRICKWhat was the actual solution then?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 5 weeks ago, # ^ |   0 I first find the minimum path cover of the tree using dp, and then reconstruct those paths and connect them. 115645578
•  » » 5 weeks ago, # ^ |   +5 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
•  » » » 5 weeks ago, # ^ |   0 Yeah u rite, I would take 4 while urs 2. What was the actual solution then?
•  » » » » 5 weeks ago, # ^ |   +5 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
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 5 weeks ago, # ^ |   +6 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.
 » 5 weeks ago, # |   0 OK... Only solve A... WA 5 times. LOL
 » 5 weeks ago, # |   +2 Tbh felt more like Div1 than Div2, solving only A and B in Div2 sounds bad..
 » 5 weeks ago, # |   0 FOR A why is this incorrect x+y==z (a)+(a*b)==(b+1)*a ng g ngif(a==b||b==1)---no else yes???
•  » » 5 weeks ago, # ^ |   0 A can be equal to B take 2 2 for example you can make x = 2, y = 4, z = 6
•  » » » 5 weeks ago, # ^ |   0 but here there are more than 1 good int..it should PRINT NO ?Y=4&&Z=4 ARE TWO GOOD INT HERE.
•  » » » » 5 weeks ago, # ^ |   0 Why is z = 4 ? (2+1)*2 = 6
•  » » » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 if(b==1)then only no friend
•  » » » 5 weeks ago, # ^ |   0 Why b==1 mate? If we have 7 1 can't we display 7 14 and 21
•  » » » » 5 weeks ago, # ^ |   0 1 is divisible by all 3
•  » » 5 weeks ago, # ^ |   0 For a = b, a*(b-1) + a = a*b
•  » » » 5 weeks ago, # ^ |   0 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)
•  » » » » 5 weeks ago, # ^ |   0 He has written NO for a=b case.
•  » » 5 weeks ago, # ^ |   0 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$.
•  » » 5 weeks ago, # ^ |   0 a could be equal to bFor example take a = b = 8, x = 8 , y = 56 and z = 64
•  » » 5 weeks ago, # ^ |   0 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)
•  » » 5 weeks ago, # ^ |   +1 print A*B , A , A*B + A when B!=1 and when B==1 answer as NOLink to Explanation of Problem A
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 How to solve D ??
 » 5 weeks ago, # |   +338 I swear those min/max functions in C looked exactly like this on my screen...
•  » » 5 weeks ago, # ^ |   +1 I got hitmotised honestly!
 » 5 weeks ago, # |   +3 Solved A in 2 attempts, and B in 6 !! Really great questions, learned a lot. _/_
 » 5 weeks ago, # |   +14 My learnings from the contest: Nobody knows what a good array looks like
 » 5 weeks ago, # |   +234 :(
 » 5 weeks ago, # |   +1 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?
•  » » 5 weeks ago, # ^ |   0 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 :(
 » 5 weeks ago, # |   0 An Illusion which forces you to find diameter of a tree - SpoilerProblem D
 » 5 weeks ago, # |   0 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: x x x 0 0 0 x x x Where $x$ presents the number. And then expand this grid's size by one per step, randomly fill other numbers in available positions.
 » 5 weeks ago, # |   0 New property found :> being divisible by a and b separately doesn't mean divisible by a*b. :'
•  » » 5 weeks ago, # ^ |   0 I took 30 minutes to realize this XD
 » 5 weeks ago, # |   +1 In problem B, earlier it was "any i" then it got changed to "all i's".. -- WA.Also, Goodbye expert :p
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 My idea for Div2D Greedily remove the edges (u,v) with degree[u] > 2 && degree[v] > 2. Then again, iterate over the edges and remove the edges (u,v) with degree[u] > 2 || degree[v] > 2 Connect all the nodes with zero degree together to form a chain. If there is only one zero degree node, then connect it with a one degree node. (There must be atleast 2 one degree nodes in a tree) Collect all the nodes with degree 1 and connect them together only if they don't form a cycle. (This could be done using a DSU and 2 pointers) Is this logic correct ?
•  » » 5 weeks ago, # ^ |   +13 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.
•  » » » 5 weeks ago, # ^ |   0 Thank you !
 » 5 weeks ago, # |   +11 i wish, i could undo myself 3 hours back!
 » 5 weeks ago, # |   0 Is it round from I_love_myself? (According to the names of the tasks)
•  » » 5 weeks ago, # ^ |   +5 Unfortunately, no. But Nastya is happy!!
 » 5 weeks ago, # |   +24 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.
 » 5 weeks ago, # |   -15 div 1.5 huh?
•  » » 5 weeks ago, # ^ |   -10 more like div 1.25 tbh
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   -10 Deleted.
•  » » » » 5 weeks ago, # ^ |   -16 More like 1.3141592653589793238462643383279502884197169399375105820974944 5923078164062862089986280348253421170679821480865132823066470938446095 5058223172535940812848111745028410270193852110555964462294895493038196 4428810975665933446128475648233786783165271201909145648566923460348610 454326648213393607260249141273724587006606315588174881520920 9628292540 9171536436789259036001133053054882046652138414695194151160943305727036 5759591953092186117381932611793105118548074462379962749567351885752724 8912279381830119491298336733624406566430860213949463952247371907021798 6094370277053921717629317675238467481846766940513200056812714526356082 778577134275778960917363717872 tbh
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +5 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.
 » 5 weeks ago, # |   0 for Problem A, a=1, b=1why x=1, y=2 ,z=3 is not a answer? x+y=z
•  » » 5 weeks ago, # ^ |   0 Because all three numbers are divisible by $A * B = 1$. You required that exactly one number is divisible by $A * B$
•  » » 5 weeks ago, # ^ |   -10 Because, x,y,z are good(x,y,z are divisible with a*b=1*1=1)
•  » » 5 weeks ago, # ^ |   0 no ; cause x,y,z all are divisible by A*B mean there all Value is good......but condition is any 1 Value good......
•  » » 5 weeks ago, # ^ |   0 because 1, 2, and 3 are all divisible by (a * b = 1)
•  » » » 5 weeks ago, # ^ |   0 Just commenting because I saw the fireboy image and could not find icegirl. Used to think nobody liked the game(except me)
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 it is a pretty interesting game really... also, its watergirl :)
•  » » 5 weeks ago, # ^ |   0 all of them are divisible by a*b.There should be only one number that is divisible by a*b
•  » » 5 weeks ago, # ^ |   0 All the numbers are divisible by a*b so all the 3 numbers are good according to the problem
 » 5 weeks ago, # | ← Rev. 4 →   0 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).
•  » » 5 weeks ago, # ^ |   0 explain the approach of A bro? i got TLE!
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 i got this by seeing ur code! but what's the intuition! bdw, thanks I got it!
•  » » » 5 weeks ago, # ^ |   +1
•  » » 5 weeks ago, # ^ |   0 Can we place min first and then 1e9 + 7
 » 5 weeks ago, # | ← Rev. 2 →   -11 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)
•  » » 5 weeks ago, # ^ |   0 true, lol
•  » » 5 weeks ago, # ^ |   +9 At least A and B was ok for div2
 » 5 weeks ago, # |   -74 The comment is hidden because of too negative feedback, click here to view it
 » 5 weeks ago, # | ← Rev. 3 →   0 Why does 115570549 give MLE for B?
•  » » 5 weeks ago, # ^ |   0 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$.
 » 5 weeks ago, # | ← Rev. 2 →   +6 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, if(i
•  » » 5 weeks ago, # ^ |   0 Yes, did the same
•  » » 5 weeks ago, # ^ |   0 I did in same way :)Link
•  » » 5 weeks ago, # ^ |   0 What wrong in my solution? https://codeforces.com/contest/1521/submission/115596986
•  » » » 5 weeks ago, # ^ |   0 Try this,1335 9 5
•  » » » » 5 weeks ago, # ^ |   0 Answer should be zero . My also giving zero.
•  » » » » » 5 weeks ago, # ^ |   0 I apologize, my bad. Try this,132 21 14
•  » » » » » » 5 weeks ago, # ^ |   0 Yes got it. Thanks
•  » » 5 weeks ago, # ^ |   0 Mine Even simpler print(n/2) for(int i=0;i+1
 » 5 weeks ago, # |   -48 bad contest, very bad problem C. Please don't allow blue to make any contest from now.
 » 5 weeks ago, # | ← Rev. 2 →   0 Looks like my dream of becoming an expert will always be a dream :(
•  » » 5 weeks ago, # ^ |   0 no mate you will be there in a month.
 » 5 weeks ago, # |   +1 Level of questions were very good. Even first problem was good enough to take time.
 » 5 weeks ago, # |   +4 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?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 $n * log(n) \ge (3n / 2) + 30$ for big $n$.
•  » » » 5 weeks ago, # ^ |   +1 Thanks, I even forgot how to compare them during the contest! What a stupid mistake :P
 » 5 weeks ago, # |   0 problem (A+B) video Tutorial Link : https://youtu.be/eoG05DnVQik
 » 5 weeks ago, # | ← Rev. 2 →   +1 Hopefully, I can become an expert for the first time. BUT I DID'T
•  » » 5 weeks ago, # ^ |   -7 Rebecoming expert here
 » 5 weeks ago, # | ← Rev. 2 →   0 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.
 » 5 weeks ago, # |   +130 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
 » 5 weeks ago, # | ← Rev. 2 →   0 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.