### Imakf's blog

By Imakf, history, 17 months ago,

Hello, Codeforces!

Daniel_yuan, waaitg, smg23333 and I are glad to invite you to Codeforces Round #706 (Div. 1) and Codeforces Round #706 (Div. 2), which will take place on Mar/10/2021 15:05 (Moscow time). Note the unusual time of the round. In both divisions, you will be given 6 problems and 2 hours to solve them all.

We would like to thank:

Score distribution will be announced before the round.

Hope you all gain positive ratings $\Delta$ in this round!

UPD1: Score distribution is

Div. 2: $500-1000-1500-2000-2500-3000$

Div. 1: $500-1000-1500-2000-2500-3250$

UPD2: Editorial

UPD3: Congratulations to the winners:

Div 1:

Div 2:

• +580

 » 17 months ago, # |   +408 As a problem setter, I set some problems.
•  » » 17 months ago, # ^ |   +361 As a problem setter, I set some problems.
•  » » » 17 months ago, # ^ |   +163 Tao God, eternal God! fkami, my superhero!
•  » » » 17 months ago, # ^ |   +218 As a tester, the statements are short and pretests are strong and give me contribution.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +48 As a contestant, I will take back my up-vote, if the tests turn out to be weak.
•  » » » » » 17 months ago, # ^ |   +10 You can't do that.
•  » » » » » » 17 months ago, # ^ |   -37 I can,by down-voting from an alt account.
•  » » » » 17 months ago, # ^ |   0 how does one become tester?
•  » » » » 17 months ago, # ^ |   +33 As a contestant, this claim was incorrect.
•  » » » » 17 months ago, # ^ |   +17 pretests are strong!codeforces × FSTForces √ :(
•  » » » 17 months ago, # ^ |   +130 I love this round and wish I could participate in this nice round (but sadly as a tester I can't, but can I get some contribution?) XDGood Luck!
•  » » » 17 months ago, # ^ | ← Rev. 3 →   -9  It was good
•  » » 17 months ago, # ^ |   +161 As a problem setter, I want some contribution, too. XD
•  » » 17 months ago, # ^ |   +14 "In the upcoming round, you can use only Kotlin." is this notification for this round?
•  » » » 17 months ago, # ^ |   +58 Apparently no. That's the notification for Kotlin Heroes: Episode 6. This round is a normal Codeforces round in which C++, Java, Python, etc. can be used.
•  » » 17 months ago, # ^ |   +56 As a contestant, I will solve some problems. :-)
•  » » » 17 months ago, # ^ |   +18 As a contestant, I will try to solve more problems than create?..
•  » » » » 17 months ago, # ^ |   +1 Sure.. you can but for this, you have to solve problem sets for past contests. :)
•  » » » » » 17 months ago, # ^ |   +3 I just meant I don't want to be additional problem for the contest creators :D
•  » » » 17 months ago, # ^ |   -13 As a contestant, i will try to solve all problems:)
•  » » » » 17 months ago, # ^ |   -7 BEST OF LUCK BRO. ;)
•  » » 17 months ago, # ^ |   +9 Okay, I am a bit serious now, how to be a tester and what are the perks of being a tester ?
•  » » 17 months ago, # ^ |   +6 It is NOT funny anymore, stop repeating this stupid flat joke 100th time in a row after every announcement.
•  » » 17 months ago, # ^ |   0 As a participant I solved some problems.
•  » » 17 months ago, # ^ |   0 Why still no rating changes for div2? Over 16 hours from the end of the contest passed and still nothing
 » 17 months ago, # | ← Rev. 3 →   +172 As a tester,this round is really nice,statements are short and clear and problems are interesting.Wish you can enjoy the problems and get high rating!Don't forget to upvote me XDupd:Imakf why you steal the first comment >_<
•  » » 17 months ago, # ^ |   0 as a participant i hope for +ve change in rating.
 » 17 months ago, # |   +158 As a tester, the statements are short and pretests are strong and give me contribution XD
•  » » 17 months ago, # ^ |   +64 Not so strong pretests apparently :/Why doesn't B have multiple testcases (like A and C have) to check for edge cases in the pretests?
 » 17 months ago, # |   +120 As a tester, the statements are short and pretests are strong and give me contribution XD
•  » » 17 months ago, # ^ |   -78 soulist /se
•  » » » 17 months ago, # ^ |   -110 why downvote me? i do nothing wrong!
 » 17 months ago, # | ← Rev. 2 →   +25 Another Chinese round! It's a pity that I won't be able to participate in it because of my classes :(Anyway, I wish good luck to all participants!
•  » » 17 months ago, # ^ |   +28 Me too :(
•  » » 17 months ago, # ^ | ← Rev. 2 →   +85 If a $\text{Div-1 Round}$ and $\text{The Whole Education System}$ were dangling from a cliff, I would sacrifice $\text{The Whole Education System}$ to save the $\text{Div-1 Round}$
•  » » » 17 months ago, # ^ |   +10
 » 17 months ago, # |   +148 As a tester, I want contribution!The problems are fun and interesting, so don't forget to participate!
 » 17 months ago, # |   +104 Hope you all gain positive ratings Δ in this round!It is theoretically impossible sadly :/
•  » » 17 months ago, # ^ |   +31 It's not sad . If everyone gets positive rating then it won't remain fun and competitive.
•  » » » 17 months ago, # ^ |   -26 You could have it both ways.Create rolling sum that increases after each round, add the max rank to it each time. Each rank would be than sum + actual rank. Increases every time!. And yet distances between users stay the same! :DYeah I know its silly and impractical. But it is possible.
•  » » 17 months ago, # ^ |   +1 What if there was only 1 participant (initially rated 0) who solved all questions during the round? What about this "theoretical possibility"?
•  » » » 17 months ago, # ^ |   0 If it's his "2nd " account on CF
 » 17 months ago, # |   +25 As a tester, the statements are short and pretests are strong and give me contribution XD
•  » » 17 months ago, # ^ | ← Rev. 2 →   -70 please don't keep downvoting me!
 » 17 months ago, # |   +83 As a tester, I really recommend you to check your code carefully before submitting.(btw : it's the first time for me to test in a CodeForces round)
•  » » 17 months ago, # ^ | ← Rev. 3 →   -51 rui_er! /seupd: Why I got so many downvotes? I'm just a classmate of rui_er :(
•  » » 17 months ago, # ^ | ← Rev. 2 →   +47 Well I really wonder why I got so many downvotes. Maybe you disagree with me, but this is just a kind suggestion, so please be more friendly to a person who is still a new hand but always tries his best to do every job. :(
•  » » 17 months ago, # ^ |   0 You are right!
•  » » 17 months ago, # ^ | ← Rev. 2 →   +2 " I really recommend you to check your code carefully before submitting. "Well, you are right. But why you guys didn't make the pretests of B strong? I think it's easy to be done. :)
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +25 I'm really sorry if this makes you confused, but I'm only a tester (not problem setter), so I don't know whether the pretests are strong enough. I started my virtual participation and tested some solutions and the constraints. This is the first time for me to do this job, so maybe I'm lack of experience. I'm sorry again and I'll try to work better next time. :)
•  » » » » 17 months ago, # ^ |   +4 Thanks for your reply. It's always hard to make something perfect in the first time. And I think you will do better in next contest.
 » 17 months ago, # |   +6 Are contest timings decided by problem setters?
•  » » 17 months ago, # ^ |   +31 Yes. This unusual timing is because the problem setters are Chinese and they have to go to school the next day (maybe.
 » 17 months ago, # |   -43 Chinese round!!! Chinese time!!! I can take part in the contest at school!!!
 » 17 months ago, # | ← Rev. 3 →   +90 Chinese Round is coming!Gaining positive rating $\Delta$ is not the most important thing that you got from a contest. Passing interesting problems and benefiting from them are the core purpose of participating in the contest. Otherwise, if everyone only want to increase rating, the utilitarians may fill the community.Of course, getting high rating can be your motivation for progress. But I also wish you not go against your original intention of studying Computer Programing.And, good luck! XD
•  » » 17 months ago, # ^ |   +26 Now found someone like me who also dislikes people yelling for rating here.Followed you buddy.
•  » » » 17 months ago, # ^ |   +16 Why would you dislike someone for having a different motive than you?
•  » » » » 17 months ago, # ^ |   +26 I also don't have answer to this as somethings which are felt can't be described. It is a feeeeeling. I can't describe it. Remember in my comment yelling is not meant as motive. motive is something different. some people just freak out on social media if they gain something. some people just cry here in the discussion when they suffer huge delta this deviates the purpose of this blog. 100 / 400 comments in every round discussion says about. "Hope I become expert/ specialist/master today!. "Oh shit damn due to a silly mistake I lost 150 delta". "OMG what a tough round". "WTF the pretest 2".This all things are fairly common in present comments in the announcement pages . And ya most popular trend. "As a Tester ....shit"
•  » » » » » 17 months ago, # ^ |   +1 Everything aside, you are a legend man. You are from Ukraine, study in China and have an Indian meme as your dp. XD
•  » » 17 months ago, # ^ |   +2 lmfao that said from your mouth lol
•  » » 17 months ago, # ^ |   0 You are quite right
 » 17 months ago, # |   +79 China is an actually a good country :D
•  » » 17 months ago, # ^ |   +61 I agree with you
 » 17 months ago, # |   -81 Wow a newbie testers
•  » » 17 months ago, # ^ |   +43 Wow a pupil comment
•  » » » 17 months ago, # ^ |   -53 Wow a Specialist reply
•  » » 17 months ago, # ^ |   0 Wow a pupil comment
 » 17 months ago, # | ← Rev. 2 →   -14 Attention, time is unusual !!!
•  » » 17 months ago, # ^ |   +2 lollll :DD, I try to remind people but people don't like it =))
•  » » 17 months ago, # ^ |   0 It is really unusual,I don't have any time to pretend to be weak to my friends!:)
•  » » » 17 months ago, # ^ |   -9 what do you mean ?
•  » » » » 17 months ago, # ^ |   0 Only a joke.Take it easy.
 » 17 months ago, # | ← Rev. 3 →   +90 Maymay...[]()Codeforces Supremacy
 » 17 months ago, # |   +117 As a tester, give me upvote!Hope you can enjoy it. When you get stuck by one, you can just read problems after. :)
 » 17 months ago, # | ← Rev. 2 →   +43 I saw lots of brilliant coder testing the round, maybe this means the contest won't be easy.I want to become purple after finishing the contest(Daydreaming, of course.), so I'll try my best.Hope everyone enjoys the fun of coding, like I do. Stay Cheeki Breeki :-)
•  » » 17 months ago, # ^ |   +22 The contest being hard or easy doesn't makes much difference in ratings outcome maybe because The contest is same for everyone....
•  » » » 17 months ago, # ^ |   +3 Yeah, you're right.
 » 17 months ago, # |   0 What does it means- " In the upcoming round, you can use only Kotlin. You can read the code examples here."
•  » » 17 months ago, # ^ | ← Rev. 2 →   +17 That is for kotlin heros contest you can use only kotlin
•  » » 17 months ago, # ^ |   +24 Why downvotes, it wasn't needed. I just asked.
•  » » » 17 months ago, # ^ |   0 Because your question was already answered. Plus, it's quite obvious that the announcement is for the Kotlin contest.
•  » » 17 months ago, # ^ |   0 I think the notification was for Kotlin Heroes: Episode 6 not for Codeforces Round #706 .
 » 17 months ago, # |   +46 As a tester, the statements are short and pretests are strong and give me contribution XD
 » 17 months ago, # |   +45 This is my second time to be a problem tester.Thanks to Imakf for giving this valuable opportunity.The problems are well-prepared with interesting stories.Hope you enjoy them.At last,good luck and have fun and get high ratingAs a tester,please give me some contribution XD
•  » » 17 months ago, # ^ |   0 (σﾟ∀ﾟ)σ⁶⁶⁶⁶⁶⁶
 » 17 months ago, # |   +27 Aaeria
•  » » 17 months ago, # ^ |   +5 ScarletS
•  » » » 17 months ago, # ^ |   -8 Binod
 » 17 months ago, # | ← Rev. 3 →   +13 This is my first time to be a codeforces tester, I feel glad. Thanks to all of the writers! This round will be very interesting. Wish everyone good luck! (The statements are short and pretests are strong and give me contribution XD)
 » 17 months ago, # |   +9 Colorful testers :D
 » 17 months ago, # |   -42 Imagine getting + delta in a div1 as a low purple
 » 17 months ago, # |   -29
•  » » 17 months ago, # ^ |   +3 you know you could at least read the comments before reposting a meme
•  » » 17 months ago, # ^ |   +12 Spoiler...
•  » » 17 months ago, # ^ |   +1 Contribution > problem solving
 » 17 months ago, # | ← Rev. 2 →   +10 An Orange-blue Round XD.
 » 17 months ago, # |   -41 why my contribution is in negative?
 » 17 months ago, # |   -11 Feels great to see newbie in testers :)
 » 17 months ago, # |   +1 As a grey colour, I'll solve A and attempt to solve B.
•  » » 17 months ago, # ^ |   -8 no, A will be too hard for you, sorry
•  » » » 17 months ago, # ^ |   0 Kuso!
•  » » » » 17 months ago, # ^ |   0 just small predict
•  » » » 17 months ago, # ^ |   0 hahaha
•  » » » 17 months ago, # ^ |   +6 You were right, A was too hard. But B wasn't. So I solved B
•  » » » » 17 months ago, # ^ |   0 Good job!
•  » » » » » 17 months ago, # ^ |   0 Thanks :)
•  » » 17 months ago, # ^ |   +1 Believe me! Just try to solve A and B quickly and you'll become specialist like me not long after that :)
•  » » » 17 months ago, # ^ |   0 That's the plan :)
 » 17 months ago, # |   -20 As a problem solver, I want some contribution, too. XD
 » 17 months ago, # |   0 I hope the difficulty level is according to the score
 » 17 months ago, # | ← Rev. 2 →   -59 The start time is too early. Sad, Chinese Round should be destroyed.
 » 17 months ago, # |   -8 Good luck to everyone!!!
 » 17 months ago, # |   -34 As a problem solver, I want some contribution, too. XD
•  » » 17 months ago, # ^ |   +3 whenever you comment to get upvotes, every time get downvotes XD so please Stop now XD
 » 17 months ago, # |   +20 May we know number of common problems between divisions?
 » 17 months ago, # |   +52 As a resident of UTC+7 please give me more chinese rounds
•  » » 17 months ago, # ^ |   +17 More Chinese rounds — less rating, I warned you
•  » » » 17 months ago, # ^ |   +24 Another 17:35 msk lover
•  » » » » 17 months ago, # ^ |   +42 Sorry guys
 » 17 months ago, # |   -40 As a contestant didn't do anything I want some contribution
 » 17 months ago, # |   0 At long there is a game whose time is suitable for me.
 » 17 months ago, # |   -15 vote for the Dogecoin
 » 17 months ago, # |   +12 It will be evening in India and will be missing playing footbal.. Hope I give it my all and make it worthwhile
 » 17 months ago, # |   -14 As a participant, the statements are short and pretests are strong and I want +ve delta XD
 » 17 months ago, # |   0 What mean rejected problems? see about it in almost all contest announcements. Why everybody write about it?
•  » » 17 months ago, # ^ |   +16 coordinator can reject problem, and it is often case if you are new in problemsetting
 » 17 months ago, # |   +26 When you know you are going to lose rating, but still want to participate (Chinese round fact)
•  » » 17 months ago, # ^ |   -7 For me, it's just like when you know there is a round today, but you have classes :(
 » 17 months ago, # |   -29 At least the timing is reasonable. Usually its late and uncomfortable. I like it when I can actually make it a round without loosing sleep or having to turn up to work a dead beat.
 » 17 months ago, # |   -51 After reading prob D(lets go hiking)- others — Try to solve the problem. me — lets leave this and starts searching for hiking destinations to visit post Covid.
•  » » 17 months ago, # ^ |   0 You must be kidding.
 » 17 months ago, # |   0 Joined about an hour late because of classes and then not able to solve even a single problem. :( feeling bad
 » 17 months ago, # |   -9 I fucking hate double in problem C I have right algorithm and because of double it doesn't accept on first pretest
•  » » 17 months ago, # ^ |   0 I also had the same problem.
•  » » 17 months ago, # ^ |   0 mine failed at pretest 2
 » 17 months ago, # | ← Rev. 2 →   +51 No one tester noticed that statement of div1B is confusing? Really? I lost 0.5 hour and made 2 excess submissions because of that, and I am angry now
•  » » 17 months ago, # ^ |   -25 I am in similar pain because of other problems. Come on setters and tester could have done a better job.
 » 17 months ago, # |   0 How to solve B ? And what's wrong with this solution ?? WA
•  » » 17 months ago, # ^ |   0 if mex is equal to n then ans is n+k otherwise answer can atmost be increased by 1.
•  » » 17 months ago, # ^ |   0 Your method for calculating mex only works for sorted array.
•  » » 17 months ago, # ^ |   0 unique_numbers is a value of unique numbers in array on the start.if mex < max then we have dont have a result of (Math.Ceiling((mex + max) / 2)) in our array then result would be (unique_numbers + 1). if mex < max and we already have a result of Math.Ceiling((mex + max) / 2) in array or k == 0, then result would be (unique_numbers).if mex > max then result would be (unique_numbers + k)
•  » » 17 months ago, # ^ |   0 Your logic for finding the mex is not correct because the input is not necessarily in sorted order. For example, if the input was 1 2 0, then the mex you find is 1. But the correct mex for this input is 3. Try applying the same logic while iterating over the sorted set of elements after you have inserted every element into the set.
•  » » » 17 months ago, # ^ |   0 Thanks mate. Now, I am Feeling like shit :(
 » 17 months ago, # |   0 I think Problem C should not be in the position of C...
•  » » 17 months ago, # ^ |   0 Very easy or very hard?
•  » » » 17 months ago, # ^ |   +4 I actually write a math proof to verify my algorithm, but I believe there are people who had their fingers crossed and passed XD.
•  » » » » 17 months ago, # ^ |   0 Can you give proof?
•  » » » » » 17 months ago, # ^ |   0 In which part?First of all you can move all the mines and miners at negative positions to positive positions, since this doesn't affect the distance formula.Then I simply try to proof that when using a line connecting miners and mines, there should not have any intersection.
•  » » » » » » 17 months ago, # ^ |   0 nooo... i mean the logic part of it...like what should we take first the miner with the highest distance and coal with shortest distance(antisorted) or both in sorted orders? I took minimum of both cases lol by maintaining 4 priority queues xD.
•  » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 simply sort the miners and mines by their distance to the origin, and pair them one by one.
•  » » » » » » » » 17 months ago, # ^ |   -8 give proof
•  » » » » » » » » » 17 months ago, # ^ |   -19 This is not meant to be proofed. Just guess and submit works fine.Asking for the proofe here is asking for a formular. Google it.
•  » » » » » » » » » 17 months ago, # ^ |   -8 Editorial gives nice proof.
•  » » » » » » » » » 17 months ago, # ^ |   0 This is no proof. They just draw a picture and say "It is that we must pair them in order."
•  » » » » » » » » » 17 months ago, # ^ |   -8 noooooooooo..
•  » » » » » » » » » 17 months ago, # ^ |   0 It takes some time to write down my proof at the below link
•  » » » » » » » » 17 months ago, # ^ |   0 i did the same thing, but why did it fail on pretest 2?? https://codeforces.com/contest/1496/submission/109623427
•  » » » » » » » » » 17 months ago, # ^ |   +8 I think it is probably because the square part gives you overflow
•  » » » » » » » » 17 months ago, # ^ |   +3
•  » » » » » » » » » 17 months ago, # ^ |   0 That's nice!But you did not write that while contest, did you?
•  » » » » » » » » » 17 months ago, # ^ |   0 The last line should be $(c^2 - a^2)(b^2 - d^2) < 0$ , Hence (a) is better than (b).
•  » » » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 actually I did xd, but with a lot of note and calculation.My contest proof version https://ibb.co/bLDDx0C LOL
•  » » » » » » » » » 17 months ago, # ^ |   +8 just use triangle inequalityhttps://ibb.co/Xp8yVnS
•  » » » » » » » » » 17 months ago, # ^ |   +5 What a nice proof!!
•  » » » » » 17 months ago, # ^ |   -8 f
•  » » » 17 months ago, # ^ |   0 Very dumb
 » 17 months ago, # | ← Rev. 2 →   0 Thanks authors for good problem setting. This time i haven't feeled myself as cryptographer who deciphers the cipher.
 » 17 months ago, # |   -27 As a 中国人, I'm sorry I can't solve these problems. (Just started competitive coding with python)
 » 17 months ago, # |   -10 What is in the 3rd pretest in div1C?btw, div1B is elegant imo :)
 » 17 months ago, # |   0 Round A Video Tut:https://www.youtube.com/watch?v=ug-g4z1giEk
 » 17 months ago, # |   -14 I want to cry, I want to rant, I want to do some things to some people.I am sure I am not the only one with these feelings.
 » 17 months ago, # |   +7 I think 1B should have highlighted the fact the two inequality signs are different for the two people's possible moves. Also I should learn to read better :(.
•  » » 17 months ago, # ^ |   0 Turns out I wrote the wrong thing then ):
•  » » 17 months ago, # ^ |   +1 Same to me. It seems that having wrong interpretation can pass all the samples and the first few pretests, especially when there is no explanation of the samples.
•  » » 17 months ago, # ^ |   0 Wtf. I actually realized this after reading your comment.
•  » » 17 months ago, # ^ |   0 Same T_T
•  » » 17 months ago, # ^ |   0 Same :(
 » 17 months ago, # | ← Rev. 2 →   0 Can Any one tell why i am getting TLE? I am just using sort and sqrt functions This is my submission:https://codeforces.com/contest/1496/submission/109622532
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 instead of double use long long for x, y because the comparison between doubles take more time than long long
•  » » 17 months ago, # ^ |   0 multiset are very slow (something like 20 time slower than a sort), try with arrays of size n and counters to know where to add, or with vectors it should pass
 » 17 months ago, # |   +1 Whats the approach for Div2 D. I am getting WA on pretest 9.
 » 17 months ago, # | ← Rev. 2 →   0 author should provide explanation for first test case of Div2D, I even asked them during the contest and they have responded as "no comments", this is not good.
 » 17 months ago, # |   +8 Div 1 D has such a scary time limit. I spent a bunch of time doubting if $\mathcal{O}(n^2 m)$ would pass, and it turns out my $\mathcal{O}(n^2 m)$ passed pretests in 2.13s/2.5s. It doesn't have any optimisations, so the runtime should be fairly independent of the input, but still, I'm scared of the systests.
 » 17 months ago, # |   0 anybody who can explain what's the deal with using Fast io and setprecision together resulting in TLE for C ??
•  » » 17 months ago, # ^ |   0 Because you read the input in doubles when the input is integers. Doubles read for a long time. It will be faster if you read ints and convert into doubles.
•  » » » 17 months ago, # ^ |   0 Also, I read at someplaces that sorting doubles is costly. Is that true?
•  » » » » 17 months ago, # ^ |   0 I don't know
 » 17 months ago, # |   +11 I think the differentiation of problem C is TOO low.
 » 17 months ago, # |   +71 [Div1 B] Am I the only one to not notice that the conditions for x and y are opposite and made 3 WA submissions?
•  » » 17 months ago, # ^ |   +1 I also didn't notice that at first. Fortunately I spotted that before submitting anything.
•  » » 17 months ago, # ^ |   +3 I noticed it now :(
 » 17 months ago, # |   +1 what's with the 4th pretest of div2 c?
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 Just don't take the container in which you are storing miners and mines of long double type, take it of int type. And rather take miner[i]*miner[i] + mine[i]*mine[i] as a long double variable to pass to sqrt function. And it passed for me after a number of Time Limit errors. Edit : also sqrtl() in place of sqrt()
•  » » » 17 months ago, # ^ |   0 and why is that?
 » 17 months ago, # |   0 Can anyone explain their approach for Problem C ? Thanx in advance .
•  » » 17 months ago, # ^ |   0 separate the x axis and y axis values and take the absolute values only . After that sort both x-axis and y-axis arrays . Now we can pair same index values in both arrays .
•  » » » 17 months ago, # ^ |   0 Implemented the same ! but wrong answer :(
•  » » » » 17 months ago, # ^ |   0 first square the coordinates then apply.
•  » » » » 17 months ago, # ^ |   0 Int is not enough to store square of coordinates
•  » » 17 months ago, # ^ |   0 just sort x axis values and y axis values choose max from both
 » 17 months ago, # |   +1 How to D?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +9 I am not sure if this correct approach , I think answer will be always $1$ or $0$ .Answer will be $1$ only when there exist some index $i$ such that array is decreasing in both right and left direction of index $i$ and size of the maximum decreasing sub array in both directions are equal,even and maximum in the whole array. Update this approach is correct : 109629126
•  » » » 17 months ago, # ^ |   0 ohk cool, never thought like that..never thought of anything..the problem just seemed impenetrable..was sitting blank for an hour xD.
•  » » 17 months ago, # ^ |   +16 Rewrite input as mountain profile. Then first player only go down, and second player only go up. The players can't collide. First player should always start on peak. Otherwise, if he is in hole, he can't do any move, if he is on slope, second player can start under first player. Find for every peak its length to the left and to the right. If there are two peaks with same maximum length to the left/right, then first player always lose. Assume he starts on one peak, then second player will start on bottom of another peak, and since he is second, when they walk same distance, the first player will must do move. Now, we have the only peak with its length to left and right. This is the only position, where first player has chance to win. So the answer is either 0 or 1. First player wins if and only if the lengths of peak are equal in both sides and even.
•  » » » 17 months ago, # ^ |   0 Very elegant thanks..will try to implement!
•  » » » 17 months ago, # ^ |   0 First player wins if and only if the lengths of peak are equal in both sides and even.Shouldn't it be odd ??
•  » » » » 17 months ago, # ^ |   0 Oh, yes, depends on your definition of length. I defined length as number of edges: here $[1, 2, 6, 5, 4, 3]$ length to the left is $2$ and to the right is $3$.
•  » » » » » 17 months ago, # ^ |   0 Hm, right
 » 17 months ago, # | ← Rev. 2 →   +1 In, div2 C, using a vector of double caused TLE, while a vector of long long passed the pretests :(
•  » » 17 months ago, # ^ |   0 same. wasted 1 hr :)
•  » » 17 months ago, # ^ |   0 why is it that the vector of double givees tle?
 » 17 months ago, # | ← Rev. 2 →   +72 I misread statement from problem B and I thought that both players could make the same movements (I didn't see that $p_{y'} > p_{y}$). Goodbye div1 :(I'm really surprised that all my submissions reached pretest 7.
•  » » 17 months ago, # ^ |   0 lol, it happened to me too :(
•  » » 17 months ago, # ^ |   0 so unfortunate
 » 17 months ago, # |   +33 When you read Div 2. D as py′
•  » » 17 months ago, # ^ |   +3 That is bad problem statement. I did read it like 25 times before noticing.
•  » » 17 months ago, # ^ |   0 Providing the explanation in problem D before hand would have saved a lot of time and maybe that could have been utilized in writing better solution.
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 I was still solving it for the same until I saw your comment. Still getting a positive delta but could have done better.
 » 17 months ago, # |   +3 What was Div1B Pretest 7?
 » 17 months ago, # |   0 Nice problem A.
 » 17 months ago, # | ← Rev. 2 →   +8 Div.2 E / Div.1 C has elegant solution, just think about a pattern. SpoilerWhat if you clear every $k$-th row? Think about suitable $k$.Upd. Managed to construct a solution which uses regexes (Perl): 109637022
 » 17 months ago, # |   0 Can someone explain why I got TLE in D2C? :((((https://codeforces.com/contest/1496/submission/109611221
•  » » 17 months ago, # ^ |   0
•  » » 17 months ago, # ^ |   0 use long long int instead of long double, the sort will be faster (I know it's weird)
 » 17 months ago, # |   0 Why my code is wrong in Div2C?
•  » » 17 months ago, # ^ |   0 firstly the value you set ans to is too low, it can be up to 2 10^13, define it by the first value and it should become correct (to my mind). However, according to others bad experience, you should use vector of long long int and not long double because elsewise sort will be too slow on test 4
 » 17 months ago, # |   +6 In recent contests I spent most of the time in asking myself, "How could I missunderstood the problem statement so that my solution does not work?"Of course it is not allways the reason for WA, but if something does not work as expected, than usually such missunderstanding is the reason.
 » 17 months ago, # |   +24 Would've really appreciated if the sample explanation for B were added beforehand. Thought the p’ > p signs were same for both players and solved for that. I take full blame for my mistake, but would've been nicer if at least one simple simulation were shown in notes, just sucks to lose so much time on a misread. Gotta be more careful I guess
 » 17 months ago, # |   0 in problem C, why is (https://codeforces.com/contest/1496/submission/109623109) giving WA? answers almost same but can't understand what is wrong
•  » » 17 months ago, # ^ |   0 you must sort it in ascending order of their absolute values
•  » » » 17 months ago, # ^ |   0 same with me too. https://codeforces.com/contest/1496/submission/109620775 here is my submission. can anyone help plz?
•  » » » » 17 months ago, # ^ |   0 I dont know, can you use other functions for quicksort in c++, but you can put the absolute values to array. And your solve will become correct.
•  » » » 17 months ago, # ^ |   0 why will it make a major differnce? can someone tell a test case where this part code would be wrong? vector> x,y; for(int i=0;i<2*n;i++) { cin>>a>>b; if(a==0) y.push_back({a,b}); else x.push_back({a,b}); } sort(x.begin(),x.end()); sort(y.begin(),y.end());
 » 17 months ago, # |   +26 The FST rate of div1B looks so scary...I am so curious about the pitfalls...
 » 17 months ago, # |   0 Why is this solution giving TLE for 1496C?Question Link: 1496C Submission Link: 109603686The solution is under the constraints and the approach and method is same as most of the accepted solutions that I have seen. Why is my particular solution giving TLE?
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 use vector type long long
•  » » » 17 months ago, # ^ |   0 Okay, using long long in vector worked, but why? Both long double and double give TLE, why? I have seen accepted answers using double in vector?
•  » » 17 months ago, # ^ |   +1 dont use long double in vector
•  » » » 17 months ago, # ^ |   +3 Okay, using long long in vector worked, but why? Both long double and double give TLE, why? I have seen accepted answers using double in vector?
•  » » » » 17 months ago, # ^ |   0 I really don't know much about others.. But I've experienced this problem several times
 » 17 months ago, # |   +183
 » 17 months ago, # | ← Rev. 2 →   0 Please tell whats wrong with these solutions ?? (Today's div2-c) Link1 Link2 I was at ~200 position after solving 2nd problem then there comes this problem :(.
•  » » 17 months ago, # ^ |   0 you must sort it in ascending order of their absolute values
•  » » 17 months ago, # ^ | ← Rev. 4 →   0 Use vector long long vect1,vect2 rather than long double vect1,vect2. I had the same problem made 8 submissions before making the right change. Sorting is O(nlogn) but there is considerable overhead sorting long doubles than integers. Stupid C++ :)
 » 17 months ago, # |   0 I just want to know, why i have got WA in Problem C :( 109590727
 » 17 months ago, # |   +22 Problem statement for this problem "Let's Go Hiking" was very fuzzy. It could have been more clear with test case explanation.
 » 17 months ago, # |   +22 I think the number of pretests of Div2D/1B are too few...
 » 17 months ago, # |   +13 Damn D's are failing fast.
 » 17 months ago, # | ← Rev. 2 →   0 I can't understand why I have got TLE for problem C in Div.2 for this solution: https://codeforces.com/problemset/submission/1496/109589906but OK for this solution: https://codeforces.com/problemset/submission/1496/109596686
 » 17 months ago, # |   -88 Downvote me to hell but no more participation in Chinese rounds and Russian middle school rounds.Indians tend to prepare much much better rounds. Racist? Yes. Factually correct? Also yes.
 » 17 months ago, # |   0 how to solve D div1 ?
•  » » 17 months ago, # ^ |   +49 A solution should be available on the editorial, but here's an outline of my thought process.Precompute the pairwise distances between all nodes. Then, we'll compute the answer separately for each pair of nodes.The key observation is that a pair of nodes has answer zero if there are multiple shortest paths between them. We can prove that any edge on a shortest path from i to j must be in a BFS tree that can be rooted at both i and j, and if multiple shortest paths exist, this will necessarily create a cycle.The shortest path from i to j is unique if, for every d from 0 to dist[i][j], there exists a single node k such that dist[i][k] = d and dist[k][j] = dist[i][j] — d. We can check this criterion in O(n). Then, the BFS tree becomes a forest containing a tree rooted at each node on the shortest path from i to j. We can then show that vertex k not on the shortest path such that dist[i][k] = a and dist[j][k] = b must be connected to a parent vertex p satisfying dist[i][p] = a-1 and dist[j][p] = b-1. Therefore, we can compute the answer by multiplying together the number of possible parents for each vertex.We can thus deal with each pair of vertices in $O(n+m)$ time, so the total complexity is $O(n^2(n+m)).$
•  » » » 17 months ago, # ^ |   0 It is more clear than the tutorial, thanks.
•  » » » 17 months ago, # ^ |   0 Thanks for the explanation.I am your fan xd
 » 17 months ago, # |   0 Thanks for this round!!! :>
 » 17 months ago, # |   +15 There is a huge difference of who solved A,B,C and who solved A,B,C. :(
•  » » 17 months ago, # ^ |   0 How ?
•  » » » 17 months ago, # ^ |   +6 There are only 544 people Passed the D.So who passed A,B,C quickly will make great grade.
 » 17 months ago, # | ← Rev. 2 →   0 Hey could anyone explain when using long double rather than long long, its giving TLE on div2C?(https://codeforces.com/contest/1496/submission/109596148) (https://codeforces.com/contest/1496/submission/109613452) I know sorting has considerable overloads for long double but still wouldnt the complexity still be O(N*64*LOG(N*64))?
 » 17 months ago, # |   0 Got TLE in div2-C but don't know why . can anyone help?? 109609708
•  » » 17 months ago, # ^ |   0 I did pretty much the same thing and got AC, not sure why your TLEs, let me know if you figure it out so I can avoid it in the future :D, anyway here's what I did: Spoilervoid solve(int tc = 0) { ll n; cin >> n; vector x, y; FOR(0, 2 * n){ //for loop 0 to 2 * n ll a, b; cin >> a >> b; if(a < 0) a = -1*a; if(b < 0) b = -1*b; if(a == 0){ y.push_back(b); }else if(b == 0){ x.push_back(a); } } sort(x.begin(), x.end()); sort(y.begin(), y.end()); double e = 0; FOR(0, n){ //change sqrt x[i] *= x[i]; y[i] *= y[i]; double t = x[i] + y[i]; // cout << x[i] << " " << y[i] << "\n"; e += sqrtl(t); } cout << setprecision(12) << fixed; cout << e << "\n"; } 
•  » » » 17 months ago, # ^ |   0 Just changed double x, y to long long x, y and it passed :)
 » 17 months ago, # | ← Rev. 2 →   +4 Solution for Div.1 C : Consider partitioning about columns, that is mark complete columns as empty for columns 1, 4, 7 .... in 1 based indexing. Now between each 2 consecutive columns, if there is at least 1 cell that was originally empty, eg. in column 2 and 3 while considering columns 1 and 4, join both the columns using that row's elements in between them. Otherwise join them by the first row if no such empty cells exist. Finally if the number of columns are divisible by 3, we have to join the last column elements to the rest of the elements joined till now. To do that, for each such original empty cell in the last column, mark it's previous column (same row) element as empty.
 » 17 months ago, # |   +8 Again, not good presets XD
 » 17 months ago, # |   0 Why is my code incorrect: https://codeforces.com/contest/1496/submission/109627982
•  » » 17 months ago, # ^ |   0 At least, we can show that the solution must be 0 or 1, but your output for test 5 is 57.
 » 17 months ago, # | ← Rev. 2 →   -9 Why is Problem E easier than D —— even Problem B?
•  » » 17 months ago, # ^ | ← Rev. 2 →   -8 Oh,I'd made a mistake.Now fixed.
•  » » » 17 months ago, # ^ |   0 You can just edit your comment...
 » 17 months ago, # |   +122 :D finally fst on 1B, because of some small bugs.But it's still a nice trip, isn't it?In the end, my rank reduced by 60. Luckily I still become an IGM, with various motions in my heart.It's an exciting and unforgettable day for me, although this round maybe my last time to participate in a codeforces round.It's time for me to stop studying Computer Programing, because of too many hard competitions and the stress of studying subjects. Otherwise I must try my best to become a top OIer in China, it's too hard for me ...Wish you all good luck! And, thanks. :D
•  » » 17 months ago, # ^ |   0 Have a good trip and hope you'll achieve your target! :)
 » 17 months ago, # |   +7 My code is printing 1 on my pc and ideone but on codeforces its printing 0.Whats wrong?mentioning: MikeMirzayanov
 » 17 months ago, # |   +1 For div.2 C problem. Can someone tell me why is 109605593 getting TLE and 109609603 getting accepted when both are having the same logic?Just printf statement is different. %.15f in one while %.15lf in second.
 » 17 months ago, # |   +13 "strong" pretests for B. I think that there aren't too many situations but the pretests didn't include those. Anyway, you should consider all the possible situations. :(
 » 17 months ago, # |   0 Pretests for problem D were very weak!! I mean look at the 30th case and 20th test case, how can one not include it in the pretests? Anyway it didn't affect my ratings but still those got WA on those test cases are unlucky :(
 » 17 months ago, # |   +3 With many participants happened this: one of the solutions got TLE, the other one got OK, but they have the same logic (problem Div.2-C).Why??
 » 17 months ago, # |   +41 Thanks for the round! I thought the problems were very high-quality, and I enjoyed thinking through them for a few hours. (This was probably the most intense CF round I've ever taken--finishing C and solving D in the last ten minutes saved me on the order of 150 rating.)One point of criticism: I'm not entirely sure why B did not use multitesting. There's no particular reason it would have been more annoying to write up if multiple test cases were included in each input, and this sort of problem (i.e., problems with only a handful of possible answers where determining which one is correct relies on checking some fixed criteria) always seem to lead some competitors to janky solutions that break down on relatively rare edge cases. The resulting FSTs would have been avoidable if multitesting was employed: for example, many solutions FSTed on a case with $n = 5$, and this could easily be prevented by a single batch test containing all inputs from $n = 2$ to $n = 7.$
 » 17 months ago, # | ← Rev. 2 →   +4 Because of the pretest of div2D/div1B , lots of people are disappointed.But you should consider all the details.If you can't consider all the details , please improve yourself , do not blame the problem.
•  » » 17 months ago, # ^ |   0 but a wrong solution which passed pretest will make people relax vigilance
 » 17 months ago, # |   +4 how weak 2D's pretests are!
•  » » 17 months ago, # ^ |   -6 sorry I accidently downvoted you .... consider you upvotes to be (current_votes+2)
•  » » » 17 months ago, # ^ |   0 sorry I accidently downvoted you .... consider you upvotes to be (current_votes+4)
 » 17 months ago, # | ← Rev. 3 →   +8 Proof of Problem C that we should not have intersecting lines in the midway somewhere. EDIT : D22 — D12 should be in the next equation. I hope you all can understand it. Please tell me in the comments if you have any issue in this. Also i missed to write +k when simplifying D22.
•  » » 17 months ago, # ^ | ← Rev. 3 →   +35 Well, i think it can be proved by https://imgtu.com/i/6Y36IISorry i don't know how to insert a picture
•  » » » 17 months ago, # ^ |   +8 Nice and short proof!!
•  » » » 17 months ago, # ^ |   +16 $OA+AB \geq AB$ I think you want to say $OA+OB \geq AB$
•  » » » » 17 months ago, # ^ |   0 Yes, you're right, it was a mistake
•  » » » 17 months ago, # ^ |   0 sto IGM MonkeyKing!!
•  » » 17 months ago, # ^ |   0 Connect possible lines between two points ，It can also be proved by Geometric intuitionistic proof（The sum of the two sides of a triangle is greater than the third side）
•  » » 17 months ago, # ^ |   +39 It can also be proved by looking at the scoreboard.
•  » » » 17 months ago, # ^ |   0 Can't agree more :)
 » 17 months ago, # |   +29 Nice contest, but author of problem F should learn the difference between a circle and a square.
 » 17 months ago, # |   0 Problem CCan anyone proof it to me.
•  » » 17 months ago, # ^ |   0
•  » » » 17 months ago, # ^ |   0 It's clear nowThank you.
 » 17 months ago, # |   0 Less participation = -vve rating
 » 17 months ago, # |   +57 As a tester of some past contests, did the testers who say "pretests are strong" really check the pretests? I sometimes checked the (sys.) test during testing, but I never see the tasks on Polygon(because almost always testers don't access or don't have READ rights on there) during testing and then I couldn't check which tests are included in the PT.
•  » » 17 months ago, # ^ |   +10 This is a problem.. It seems like testers nowadays are just spamming "Statements are short and pretests are strong" to get contribution. Logically not every round they test can be that perfect, yet I see these comments on every round.
 » 17 months ago, # |   0 waiting for rating change:)
 » 17 months ago, # |   0 messed up C due to overflow issues
 » 17 months ago, # | ← Rev. 3 →   0 .
 » 17 months ago, # |   0 Can anyone tell me why this doesn't work for problem B? I think my idea is correct.
•  » » 17 months ago, # ^ |   0 There is something called "Time Complexity". Learn it first...
•  » » » 17 months ago, # ^ |   +3 Ok, I don't know much about time complexity, but my code gives me wrong output, not TLE.
•  » » » » 17 months ago, # ^ |   0 There are cases where the max of array is not constant such as case#4 (0 1 2) so you need to update your max_ hence the ans every round of k loop. In your code you keep it constant.
•  » » » » » 17 months ago, # ^ |   0 I was thinking about this, but can you help me how to do it?
•  » » » » » » 17 months ago, # ^ |   0 import sys import math input = sys.stdin.readline for _ in range(int(input())): n, k = [int(i) for i in input().split()] a = [int(i) for i in input().split()] max_ = max(a) mex_ = [int(i) for i in range(n+1) if i not in a] if len(mex_) > 0: res = min(mex_) else: res = max_ + 1 ans = int(math.ceil((max_ + res) / 2)) for i in range(k): ans = int(math.ceil((max_ + res) / 2)) a.append(ans) if res > max_: max_ = max(a) res = max_ + 1 print(len(set(a))) this is the "fixed" version of your code. it runs but this will TLE anyway because you actually don't need to go through this k loop. you can check my contest submission or the editorial.
•  » » » » » » » 17 months ago, # ^ |   0 Thank you very much!
•  » » 17 months ago, # ^ |   0 i think change  ans = int(math.ceil(max_ + res) / 2) to  ans = int(math.ceil((max_ + res) / 2)) 
•  » » »