### PurpleCrayon's blog

By PurpleCrayon, history, 6 weeks ago,

Hello Codeforces!

ijxjdjd and I are pleased to invite you to participate in Codeforces Round #728 (Div. 1) and Codeforces Round #728 (Div. 2) which will be held on Jun/25/2021 18:35 (Moscow time). Please note the unusual timing. Each division will have 5 problems and 2 hours and 15 minutes to solve them.

We would like to thank:

Read all of the statements carefully, and we hope you enjoy the problems! Wish you high ratings!

UPD: I would also like to thank Roberticey, golions, and kefaa2 for testing.

UPD: Here's the score distribution:

Div 1: 500 — 1250 — (1500 + 750) — 3000 — 3500

Div 2: 500 — 1000 — 1500 — 2250 — (2500 + 750)

UPD: The editorial is out!

UPD:

Congratulations to the winners!

Div. 1:

Div. 2:

• +490

 » 6 weeks ago, # |   -395 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » 6 weeks ago, # ^ |   -394 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » 6 weeks ago, # ^ |   -397 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » 6 weeks ago, # ^ |   -407 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » » 6 weeks ago, # ^ |   -393 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +204 The comment is hidden because of too negative feedback, click here to view it
•  » » » » » » » 6 weeks ago, # ^ |   -220 The comment is hidden because of too negative feedback, click here to view it
•  » » » » » » » 6 weeks ago, # ^ |   +43 Don't steal my tricks. lol
•  » » » » » » » » 5 weeks ago, # ^ |   -24 Thanks for the blog, hope to see u in purple next time ;)
•  » » » » » » 6 weeks ago, # ^ |   -26 Whatta coincidence! The sequence of their profile picture is like Mocha bear is rotating milk bear in some order :o
•  » » » » » » » 5 weeks ago, # ^ |   +53 that's the point... cf is tired of gyrating cats
•  » » » » » » » » 5 weeks ago, # ^ |   +10 Is it a coincidence that the first question in div 2 contained gyrating cats. I am not into vodoo stuff but this sh*t is deep.
•  » » » » » » » » » 5 weeks ago, # ^ |   +11 well, purplecrayon is part of our gyrating cat club :P
•  » » » » » » » 5 weeks ago, # ^ |   +23 Those are bears..? For so long I thought they were cats.
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 .
•  » » » » » » 5 weeks ago, # ^ |   -153 It's a bad sight that the first five comments on the blog have all these negative votes!Suggest removing it, MikeMirzayanov
 » 6 weeks ago, # |   +144 I hope everyone enjoys our problems and learns something new!
 » 6 weeks ago, # |   +90 PurpleCrayon is a skilled programmer, and I'm excited to see the tasks he and ijxjdjd have prepared. Good luck to all participants, and hopefully we can see more crayon rounds in the future!
 » 6 weeks ago, # |   +46 Maybe I get purple on PurpleCrayon's round
•  » » 6 weeks ago, # ^ |   +28 I feel really sad to say it won't happen but you might get blue in this round :P
•  » » » 6 weeks ago, # ^ |   +5 BlueCrayon orz
•  » » » » 5 weeks ago, # ^ |   0 What is orz?
•  » » » » » 5 weeks ago, # ^ |   +4 It's a person bowing, 'o' is head, 'r' is arms and 'z' is folded legs.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 So, if I say "someone" orz, this means I would like to shoot "someone"?
•  » » » » » » » 5 weeks ago, # ^ |   +3 No, it means you pay respect to someone and admire them.
•  » » » » » » » » 5 weeks ago, # ^ |   0 Ver_Nick orz?
•  » » » 6 weeks ago, # ^ |   0 Why not? QWQmaster got from Specialist to CM in a recent contest and there are more such examples.
•  » » » » 6 weeks ago, # ^ |   +124 What is purple?
•  » » » » » 6 weeks ago, # ^ |   -24 Spoiler
•  » » » » » 6 weeks ago, # ^ |   +15 You are lucky to never find out.
•  » » » » » 6 weeks ago, # ^ |   +9 afterall: What is yellow?
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +35 Come from real id 👉 👈
 » 6 weeks ago, # |   +38 As a tester, give me ..As a tester I can assure you that you will write purplecrayon orz after contest (before too)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -46 Here. I can give you this latest striver meme. SpoilerLol downvoting my greatness :(
•  » » » 6 weeks ago, # ^ |   0 waifu sauce please
•  » » » » 6 weeks ago, # ^ |   0 Just search Rikka, she's famous.
 » 6 weeks ago, # |   +67 Each division will have 5 problems and 2 hours and 15 minutes to solve them. This line scares me.
 » 6 weeks ago, # |   -35 Why is the rating limit for Div.2 is 1899? Shouldn't it be 2099?
•  » » 6 weeks ago, # ^ |   +23 I think because this contest has Div 1 too.
 » 6 weeks ago, # |   -37 Score distribution for this round will be really interesting I guess. 5 problems in 2:15 is very challenging
 » 6 weeks ago, # |   +25 Damn, 5 problems in 2:15 hours. Seems like a Div-1.5 :)
 » 6 weeks ago, # |   +31 If both divisions are 2 hours and 15 minutes why here the length is 2 hours? Spoiler
 » 6 weeks ago, # | ← Rev. 7 →   -107 .
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +38 Don't tag them unnecessarilyEdit1: Lol you totally changed the main idea of your comment
•  » » » 6 weeks ago, # ^ |   0 He is just trying to confuse everybody. :)
•  » » 6 weeks ago, # ^ |   +14 Mind your own rating! :P
•  » » 6 weeks ago, # ^ |   0 You could reply me instead of writing my name ....
•  » » » 6 weeks ago, # ^ |   0 Read the previous revisions of his comment. You'll get it.
 » 6 weeks ago, # |   -34 Can't wait to see the geniosity problems !purple orz .
 » 6 weeks ago, # |   -53 note the unusual timing.
 » 6 weeks ago, # |   +15 As a tester, I can confirm problems are awesome! Good luck in the round!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 As a Participant. I liked Your WordsUpvoted<3
•  » » 5 weeks ago, # ^ |   +4 but u said problems will be awesome!!!
 » 6 weeks ago, # |   -66 Hope to be expert.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +38 Just don't cheat again. GL;HF.
•  » » » 6 weeks ago, # ^ |   -38 hello to you too.
 » 6 weeks ago, # |   -10 As someone purple did not allow test the round, give me contribution!
•  » » 6 weeks ago, # ^ |   -56 As someone purple also did not allow to test this round, give me contribution!
 » 6 weeks ago, # | ← Rev. 2 →   0 As a participant, I hope my fellow comrade LostCoder16 and I can become purple in this PurpleCrayon blessed round, unlike last time. Wish us luck!! xD
•  » » 6 weeks ago, # ^ |   +15 Good luck to you :)
 » 6 weeks ago, # |   +41 As a tester, I can say that I enjoyed the problems. Good luck to everyone participating :)
•  » » 5 weeks ago, # ^ |   -29 Plz don't participate
•  » » 5 weeks ago, # ^ |   0 Are there strong pretests ??
 » 6 weeks ago, # |   +1 I hope my colour change with a +ve delta :)
•  » » 5 weeks ago, # ^ |   0 I also want to see what is the colour below newbie :)
•  » » » 5 weeks ago, # ^ |   0 It's White
•  » » » » 5 weeks ago, # ^ |   0 It's Grey
•  » » » » » 5 weeks ago, # ^ |   0 Nah, he said below newbieSee Antonov225Mriya for example, it's White.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Lower than 100,you will be see white.Lower than 0,you will white.
 » 6 weeks ago, # |   +6 Unfortunately, most of IOI participants can't participate in this round :(
 » 6 weeks ago, # | ← Rev. 2 →   0 I think upcoming contest was little bit tricky..so,I hope u all are enjoying this contest and learns something new!
•  » » 6 weeks ago, # ^ |   +6 It's not started yet :)
•  » » » 6 weeks ago, # ^ |   0 Yaaa bro..lol
 » 6 weeks ago, # |   +17 Excited for the round, knowing the writers I have no doubt it will be great!
 » 6 weeks ago, # |   -23 i expect if I participate, i will get green in this round :)
•  » » 6 weeks ago, # ^ |   0 then do participate ¯\_(ツ)_/¯
•  » » » 6 weeks ago, # ^ |   0 i try to attend on time but i may not be able to do so
•  » » » 6 weeks ago, # ^ |   0 can also participate later?
•  » » » » 6 weeks ago, # ^ |   0 yes you can virtually participate later or just solve problems without virtually participating too
•  » » » » » 5 weeks ago, # ^ |   0 i know about it, i said that i can participate in the rankings even after the competition was over
•  » » » » » » 5 weeks ago, # ^ |   0 No, after the contest finishes you cannot participate in the official standings, and cannot gain/lose rating
•  » » » » » » » 5 weeks ago, # ^ |   0 understandable! thanks
 » 6 weeks ago, # |   +10 I wish problem statements would be as clean as this announcement
•  » » 6 weeks ago, # ^ |   +45 I wish statements would be as short and clear as the annoucement, too.
 » 6 weeks ago, # | ← Rev. 2 →   0 .
 » 6 weeks ago, # |   +1 I wish that this contest has Graph theory and DP related problems !
•  » » 5 weeks ago, # ^ |   +2 sounds funny
•  » » 5 weeks ago, # ^ |   0 Thats all you had to say
 » 6 weeks ago, # |   -54 .
 » 6 weeks ago, # |   0 Why do the recent contests take place in unusual time...
 » 5 weeks ago, # |   +2 I will remember the contest start time properly this time, the previous contest div 2 which I thought usually to start at 20:05 but it was around 3pm RIP
 » 5 weeks ago, # |   0 PurpleCrayon is not even purple Sadge
 » 5 weeks ago, # |   -84 I will not take part in this contest just because of unusual time!!
 » 5 weeks ago, # |   -11 "You, for participating!" This line hit hard :(
 » 5 weeks ago, # |   +20 As a cyan, D seems not killable.So, speedforces :(
 » 5 weeks ago, # |   -51 As a tester,who wasnt able to solve a single problem
 » 5 weeks ago, # |   +1 Really excited to participate in div2.. All the best everyone.
 » 5 weeks ago, # |   -32 Benq only competes when he knows he will get first. Otherwise, he doesn't compete to protect his rating. Conspiracy?
 » 5 weeks ago, # |   0 The scoring distribution for div2 is weird. I hope I get positive delta.
 » 5 weeks ago, # |   -9 I hope i can solve at least 3 questions.
 » 5 weeks ago, # |   -39 The contest timings 20.05 IST were better. Hope it changes from next contest.
 » 5 weeks ago, # |   0 Can anyone tell what does (1500 + 750) mean in the score distribution? Does that mean the score of the question can be (1500 or 750) or does that mean the score would be 2250?
•  » » 5 weeks ago, # ^ |   0 It means the problem has an easy version and a hard version. Solving just the easy version would give you a max 1500 score, solving both would give you a max 2250 score.
•  » » » 5 weeks ago, # ^ |   +5 Why does the easy version has a higher rating than the hard version?
•  » » » » 5 weeks ago, # ^ |   +5 This is a fine move by the setters so that we lame programmers can feel better.
•  » » » » 5 weeks ago, # ^ |   +5 Why it shouldn't be?The complete score is the score of the "hard version". Easy version should be considered as partial score for partial solution. If it contains significant part of the final solution, it is natural that is worth significant part of the final score.
 » 5 weeks ago, # |   0 Hope that I can become a crayon today ^_^
 » 5 weeks ago, # |   0 hope i can solve 1 or 2 question
 » 5 weeks ago, # |   +3 Is it logical that the second part of the last problem of div2 has the same score as in div1 (750)?
 » 5 weeks ago, # | ← Rev. 2 →   0 .
•  » » 5 weeks ago, # ^ |   +3 It's 38 mins dear
 » 5 weeks ago, # |   0 how to solve D when you are green?
•  » » 5 weeks ago, # ^ |   +15 How to solve D when you are blue ?
•  » » » 5 weeks ago, # ^ |   0 How to solve D when you are Cyan?
•  » » » » 5 weeks ago, # ^ |   0 I am waiting for someone to say become red! xD
•  » » » » 5 weeks ago, # ^ |   0 Respect the unusual timing as a usual one. That could work probably work. :D
•  » » » 5 weeks ago, # ^ |   +1 Seems to solve current D, I need to be atleast 4000 rated :/
•  » » » » 5 weeks ago, # ^ |   0 Well you are speaking facts. D is too OTZ levelled. T_T :(
 » 5 weeks ago, # |   +18 So are we solving E2 after A?
•  » » 5 weeks ago, # ^ |   0 Went with that approach at start. Only to return back sad faced after reading E1 fr 5 mins. T_T . Dumb me!!
 » 5 weeks ago, # |   +1 I wish everybody an awesome codeforces round
•  » » 5 weeks ago, # ^ |   0 thank you
 » 5 weeks ago, # |   +1 gl
 » 5 weeks ago, # |   +8 i think today i become pupil
•  » » 5 weeks ago, # ^ |   +15 F
 » 5 weeks ago, # |   +45 Anyone in Div 2 feeling like they accidentally participated in Div 1?
 » 5 weeks ago, # |   +30 Speedforces, redefined.
 » 5 weeks ago, # |   +15 The game of hand speed.
 » 5 weeks ago, # |   +87 The expected value to solve D by myself is 0.
 » 5 weeks ago, # |   +36 Most difficult div.2 D ever?
 » 5 weeks ago, # |   +36 Never seen such a big jump in difficulty from C to D
 » 5 weeks ago, # |   +3 What is Normal Red?
 » 5 weeks ago, # |   +17 Div 2 is definitely a speed force.
 » 5 weeks ago, # |   +21 speedforces
 » 5 weeks ago, # |   +60 I have no idea on 1B or 2D, wtf
 » 5 weeks ago, # |   +260 Some relavant meme:
•  » » 5 weeks ago, # ^ |   +17 I want to give 200 upvotes T_T
•  » » 5 weeks ago, # ^ |   +17 E1 is like Atcoder grand contest math problem.
 » 5 weeks ago, # | ← Rev. 2 →   +19 ive read all the problems and they are really nice good job!
 » 5 weeks ago, # |   0 Solved 3! Then saw D. WTF only 13 submissions!?
•  » » 5 weeks ago, # ^ |   +16 Started with D, read it & thought something, then saw A. WTF crossed 10,000 submissions!?
•  » » » 5 weeks ago, # ^ |   +7 I actually never read D..just saw the submissions lol.
 » 5 weeks ago, # | ← Rev. 2 →   -9 Forget about it
•  » » 5 weeks ago, # ^ |   +27 It's probably hard to solve problems when you are creating memes during the contest.
•  » » » 5 weeks ago, # ^ |   +48 There must be more than 16k people creating memes, because only 15 people could solve the problem
 » 5 weeks ago, # |   +8 I feel like this was speedforces but at the same time wasn't speedforces :)
 » 5 weeks ago, # |   +8 So by Div 2 u meant Div 1.5
 » 5 weeks ago, # | ← Rev. 3 →   -7 Good and challenging problems ! Good job but the difference of difficulties of problems between c and d was a lot !
 » 5 weeks ago, # |   +65 Literally 15 mins on 1A and 2 hours on crying
•  » » 5 weeks ago, # ^ |   0 Same Sad......
•  » » 5 weeks ago, # ^ |   +1 Same pinch !!
•  » » 5 weeks ago, # ^ |   +5 Same here , 5 min and then nothing
•  » » 5 weeks ago, # ^ |   0 Same ...
 » 5 weeks ago, # |   +19 That sums it up :(
 » 5 weeks ago, # |   +14 I hate probability.
 » 5 weeks ago, # | ← Rev. 3 →   +1 Me in Div2 today:First, solve three problems.Second, look at the accepted number of problem DThird, give up and go to the comment section.
 » 5 weeks ago, # |   0 DIV-2: When I solved B there were ig 200-300 people who solved C, When I solved C there were 2 people who have solved D. Got the idea about the question before reading it.
•  » » 5 weeks ago, # ^ |   0 Can you share your approach to DIV 2 b ?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 just brute force over numbers that i+j = input[i] * x, where x is any natural number.for example: input: 3 1 2 4 53 is at place 1, so u can take only number 2, 5, 8 etc. because u won't be able to get number not divisible by 3, if u multiply 3 by anything, so just check numbers that after summing gives number divisible by it
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Iterated i from 1 to n-1; We have to find the all the possible (j>i) & (j<=n) which satisfy the given condition.For this number at ith position. i+j can range from i+i+1(a) to i+n(b);v[i]*v[j] = i+j.=> We have v[i] and range of i+j in hand. So what is the possible range of v[j]? ((a/v[i]) + (a%v[i]==0?0:1)) (c) to (b/v[j]) (d); Now iterate from c to d (possible v[j]) and find whether the number in this range exist at respectively jth index, such that a[i]*a[j] = i+j;Take sum.Time complexity should be O(n). The range of c-d is maximum when a[i]=1 ~ n but since all numbers are different so if at next index a[i]=2 then range of c-d shuld be n/2 . Now n+ n/2 +n/3 + ... ~ O(n)
•  » » » » 5 weeks ago, # ^ |   +2 Probably sum of n + n/2 + n/3 + ... is O(N*logN), as harmonic series (without n factor in each summand) is equivalent to logarithm. But yeah, that is still AC :)
•  » » » » » 5 weeks ago, # ^ |   +3 Yes you are right. Thnx.
 » 5 weeks ago, # |   +7 Am I the only that forgot numbers in B are distinct and wasted more than 20 min because of that
•  » » 5 weeks ago, # ^ |   0 I wasted 90 min because of that lol
•  » » 5 weeks ago, # ^ |   +1 no
•  » » 5 weeks ago, # ^ |   +4 Yep. Me too. But it's my fault.
 » 5 weeks ago, # |   +14 Seems like I'm getting dumber with each passing day, half of the world solved C in one go.
•  » » 5 weeks ago, # ^ |   +7 :) while I could not able to solve it.
•  » » » 5 weeks ago, # ^ |   0 :( another rough day for us
•  » » » 5 weeks ago, # ^ |   0 Same here :(I wonder how 4k+ people solved C. Was it that easy?
•  » » » » 5 weeks ago, # ^ |   0 same old story..solutions were available for free on internet
•  » » 5 weeks ago, # ^ |   +3 for me it was pretty hard to understand the problem for first 10 minutes, then it went from graphs -> dp -> sorting and turn out to be easy problem lol
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 I get wa on both A and B :( ,same pinch bro,I also feel same
 » 5 weeks ago, # | ← Rev. 3 →   +8 What should the answer be for the 3rd example testcase for div2D? I got 141/40 = 925000010 but it should be 500000007. What's the actual fraction that gives 500000007 though?agh i think i figured it out.. I was computing the probability of marking X before Y, given the heights from the root of X and Y, but it really should have been the heights from the LCA of X and Y, not from the root. :(
•  » » 5 weeks ago, # ^ |   0 3.5 but no idea what the actual fractions going into it were
•  » » 5 weeks ago, # ^ |   0 I guess it's 7/2
 » 5 weeks ago, # |   0 Thanks for the contest! I really enjoyed it.
 » 5 weeks ago, # |   +71 The maximum boring problem set in Div2. Three observation based problems, and D + E ridiculously difficult. The contest was practically over after 20 minutes.
 » 5 weeks ago, # |   +6 ok ...i hate my life now
 » 5 weeks ago, # |   0 I entered 25 minutes later and after 35 minutes I left by topping in my room! This line describes the contest!
 » 5 weeks ago, # |   +98 MEET AN EXPRIENCED & SHAMELESS CHEATER This is how kedos123 bypasses Plagiarism testing.i reported to codeforces and MikeMirzayanov about him from past 2 contest and he does cheating in it also and got plagiarism , thanks to u for upvote my comment so that he got punished . and today again he cheated in the contest , pls again upvote my comment ......kedos123 does cheating from starting and i reported about it to MikeMirzayanov and he got plag in last 2 rounds , he abused me in private chat becz i reported him https://ibb.co/JmhSwKL . guys show your support and again upvote my comment so he again got punished.People like kedos123 are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .his todays contest submission 120565019 120557120 , saw his submission timing and also see this dummy variables snippet xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++;xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++; xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++;xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++; xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++;xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++; xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++;xx[3]++;xx[1]++;xx[3]--;xx[1]--;xx[5]++;
•  » » 5 weeks ago, # ^ |   +43 Others Template; #include <>Your Template: MEET AN EXPRIENCED & SHAMELESS CHEATER.. kedos123And you submit it after every contest in announcement. Keepitup.
•  » » 5 weeks ago, # ^ |   +1 One more guy vadapavandchill check his submissions with obsfucated code 120565541 120557993
 » 5 weeks ago, # |   +1 Can anyone explain Div2 problem C
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 sort the number in increasing order, then just for every 0<=i
 » 5 weeks ago, # | ← Rev. 3 →   0 ..
•  » » 5 weeks ago, # ^ |   +3 On above that put that as Div2D :(
 » 5 weeks ago, # |   0 My logic for C, take the sum of differences of all pairs and subtract the difference of adjacent elements from it and print the answer with a negative sign. Why is this failing?
•  » » 5 weeks ago, # ^ |   0 The answer is take the absolute differnce of each pair and then subtract maximum value from array d and then multiply with. 1 , The logic is that to minimise the cost you should add as many -ve no. You can and as less +ve no. You can , So for +ve no. you will take maximum no. As the sum of difference between adjacent sorted no. will lead to it and for -ve add All -ve no.s .
•  » » » 5 weeks ago, # ^ |   0 Found the mistake in my solution. Missed sorting. Just adding that and submitting again gave me an AC :(
 » 5 weeks ago, # | ← Rev. 3 →   0 How to solve B ? I don't know how it can be solved in o(n)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 It's not O(n). Rewrite the eqn as aj = (i+j)/aiNow, as aj is an integer, i+j must be a multiple of ai, you need to check only ai blocks in each case. Since ai is distinct, this is similar to prime sieve in terms of time complexity.
•  » » » 5 weeks ago, # ^ |   0 Yes I got your point ! actually i spent so much time trying to make it only O(n) and i couldn't
•  » » 5 weeks ago, # ^ |   0 Ok now i feel dumb ,All of that time i thought if used another for loop with i+=array[i] as a step it will be more than o(n)
•  » » 5 weeks ago, # ^ |   0 For any $a_i$, we need $a_j = (i+j)/a_i$. Hence you only have to look at all $j$ such that $i+j$ is divisible by $a_i$ instead of all the $n$ elements. Note that since there are n elements and $1<=a_i<=2n$, and all elements are distinct, at worst it will take $O(n+n/2+n/3+..)$ or $O(nlogn)$ complexity.
•  » » 5 weeks ago, # ^ |   0 Let us start with the brute force approach..You would initialise two for loops.. one from i (1 to n) and the inner one j (i+1 to n) .. iterating over all values and obtaining all such pairs. However, this would take order of n*n and is not feasible.So, the key observation is it can be reduced to approximately nlogn per testcase, by only considering the valid indices that occur after i that are themselves multiples of a[i] , incrementing j by a[i] each time. The first such j for which i+j is a multiple of ai can be found by simple math (because ai*aj=i+j, so i+j has to be a multiple of ai).
•  » » » 5 weeks ago, # ^ |   0 I feel more dumb now because i got the same idea but thought it would give TLE ; _ ;
•  » » » » 5 weeks ago, # ^ |   0 It would indeed give tle if all elements of the array were not unique.. as it would now tend towards n*n for big n and small ai.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 Based on what I observed in my room, there were 2 major ways to solve B: Either an $O(n\sqrt n)$ solution or $O(nlogn)$, which I thought was pretty cool.$O(n\sqrt n)$:First, create a map $where[n]$ for all $a[i]$ -> $i$. Now, iterate over all integers $i$ from 1 to $2n$. Get the factors of each integer $i$. Now, for each factor $f$, check if $where[f] + where[i/f]$ = $i$. If so, increment the answer.$O(nlogn)$: We iterate over every multiple $k$ of each $a[i]$ and check if there exists an index $j$ where $j > i$ and $j + i = k$. If so, check if $a[j] = k$. If so, increment the answer. This works since all $a[i]$ are distinct, so the time complexity is bounded by the harmonic series $n (1 + \frac {1}{2} + \frac {1}{3}...)$ which is well known to have an upper bound of $O(nlogn)$.
•  » » 5 weeks ago, # ^ |   0 I think most of the people first tried to solve it in O(n). That's why submissions were late.
 » 5 weeks ago, # |   0 How to solve problem C ?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +6 Sort the input as the order of pastures doesnt matter. Then notice that more the roads between pastures more minimal the time will be. Now create a difference array from the sorted array as they will correspond to our postive edges in graph. Now we take make negative edges for every pair of pastures. The sum of these will be the negative of sum of all subarrays of difference array(Call it NEG). This can be calculated in O(n) using contribution technique.So final answer would be sum of positive edges(all elements in difference array) + NEG.This is greedily the minimal ig. You can check my submission out. I feel it is neat.
•  » » » 5 weeks ago, # ^ |   0 A question about the problem C div 2. The parsing says: Instead, you can sort d and calculate the contribution of each node to the answer. Please explain how to count the contribution of each node in the answer in more detail. You can use an example. Thanks.
•  » » » » 5 weeks ago, # ^ |   0 Idk how they have done it in the tutorial but the contribution thing I was referring to was this : https://www.geeksforgeeks.org/sum-of-all-subarrays/. It has examples read it through.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Note that you need to arrange the vertices in such a way so we minimize the sum of positive edge, which can be done by sorting the array and taking minimum times to be a difference of two consecutive elements.Eg:- $w x y z$ be the sorted array then $(x-w), (y-x)$ and so on will be the costs of edges which gives a path from patch 1 to all patches with minimum positive cost.Now we can need to add negative backward edges to make the total sum of each cycle zero. Let us say the edges are $a,b,c,d,e$. Then the negative edges cost will be $N=(a+b+c+d+e) + (a+b+b+c+c+d+d+e) + (a+b+c+d+b+c+d+e) + (a+b+c+d+e)$. Each term corresponds to nullifying cycles of with 2,3,4 and 5 vertices respectively. Generalize the summation for $n$.The answer would be $a+b+c+d+e-N$.
•  » » » 5 weeks ago, # ^ |   0 I really don't understand how you do it
•  » » » » 5 weeks ago, # ^ |   +3 Here the cost of each curved arc will be a negative value such that the total cost of its respective cycle becomes zero.
•  » » » » » 5 weeks ago, # ^ |   0 Farmer John guarantees that it is impossible for the cows to get stuck in a time loop, where they can infinitely go back in time by traveling across a sequence of roads.can u explain where does the above statement play a role in your solution? As I thought that it doesn't allow more than one longest cycle to form in the graph.
•  » » » » » » 5 weeks ago, # ^ |   0 "As I thought that it doesn't allow more than one longest cycle to form in the graph." ==> It does not allow a cycle with the total sum of edge weights < 0.
•  » » » » » » » 5 weeks ago, # ^ |   0 Ahhh... Thanks for clearing the doubt as it kept bugging me during the contest and couldn't ask the author the same thing during the contest thought it might violate any rules..
 » 5 weeks ago, # |   0 Is there any chance to pass Div.1 D by $O(n^2 \log n)$ solution...? I know $3e9$ per second sounds insane :(
 » 5 weeks ago, # | ← Rev. 3 →   -36 Hello! Nice problems but the leveling of the questions was not very good. D Div2 was very hard
 » 5 weeks ago, # |   +3 Div2D was so hard, only 18 people solved it.I thought of doing something like this: For the tree rooted at $i$, what's the probability that node $j$ is reached before node $k$? And inversion counting like that, but I didn't work out the details of how to figure that out.Was the intended complexity $O(N^3)$?
•  » » 5 weeks ago, # ^ |   0 ah, that was my idea too! I coded it up but got WA on the example pretest #3 :(
•  » » 5 weeks ago, # ^ |   0 It might be possible to do it in $N^3$ but my solution was $O(N^3\text{log}N)$. The bottleneck was finding the $O(N^2)$ lca's for each pair of nodes given a fixed root.
•  » » 5 weeks ago, # ^ |   0 I asked instead: Given nodes $i$ and $j$, what is the probability that $i$ comes before $j$? This leads to an $O(N^3)$ solution. However it took me 2 hours past the end of the contest to correctly work out how to implement it.
 » 5 weeks ago, # |   0 How to solve Div 1C/2E?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 it seems that initial array is valid if and only if $\sum_{i=1}^k a_i \ge \sum_{i=1}^k (x+s_i)$ holds for all $1 \le k \le n$, where $s_i=\sum_{j=1}^{i-1} b_j$. But I have not submitted, so i have no idea if there is anything wrong or not.
 » 5 weeks ago, # |   0 I still didn't get what is the notes he's referring to, in Problem E1.
 » 5 weeks ago, # |   +12 Couldn't submit 1B by 10 seconds :(
 » 5 weeks ago, # | ← Rev. 2 →   0 Well I'm glad to see I wasn't the only one having trouble with 2D. It's a nice problem though, I think I have a solution but it will take me a few hours to implement it.
 » 5 weeks ago, # |   +1 Biggest drop of my contest history. Well, worth a fall if I hope to perform well again!
 » 5 weeks ago, # |   +23 Felt like the entire contest was me making little progress on C1 and secretly hoping the solve count would stop rising :P at least I did well in the speedforces race.
 » 5 weeks ago, # |   0 when will the ratings be updated ? any ideas?
 » 5 weeks ago, # |   +8 How to solve div-2 D ??
 » 5 weeks ago, # |   +5 Anyone remember when galen_colin said that your rank can really depend on the time you take to solve the problems? Welp, it's even more severe this contest, being from positions 19 - 4269 (approx).
 » 5 weeks ago, # |   -15 PurpleCrayon, I liked the problems a lot, but I think that most of Div. 2 participants will disagree and say that it was not very balanced, turning things into speedforces somewhat
 » 5 weeks ago, # |   0 Where can I find it's solution!!!!! Can anyone tell me??????
 » 5 weeks ago, # |   +26 Pure speedforces
 » 5 weeks ago, # | ← Rev. 3 →   -7 c
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +8 Because you have UB, you're accessing index out bound, your array is not big enoughFor heaven's sake. If you're writing code in c++ you should know about UB and consider it whenever something inexplicable happens
•  » » » 5 weeks ago, # ^ |   0 thanks for pointing out. I know about UB but i missed it completely out of frustration.
 » 5 weeks ago, # | ← Rev. 2 →   -19 Check out time complexity for problem BIf anyone has better approach then you can add here SpoilerYour code here... #include using namespace std; const long int N=100000; int main() { int t; cin>>t; while(t--){ long int n,len=0; cin>>n; long int a[n],b[n]; long int c[N]={0}; for(int i=0;i>a[i]; c[a[i]]=i+1; } sort(a,a+n); for(long int i=3;i<=(2*n-1);i++){ int x=sqrt(i); int k=0; while(a[k]<=x&&a[k]*a[k]!=i){ if(i%a[k]==0){ int d2=i/a[k]; if(c[d2]>0 && (c[d2]+c[a[k]])==i) len++; } k++; } } cout<
•  » » 5 weeks ago, # ^ |   +1 Can you put it in a spoiler message, please?
 » 5 weeks ago, # |   +10 The problems are pretty good,but the diffculty gap between Div2 C and Div2 D are too big,making this Div2 round a "speedforces" round,so to my opinion,not very enjoyable because the round is not very balanced. Again,the contest is great,but I think there are room for improvements.
 » 5 weeks ago, # |   0 how to solve B div2
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +5 Iterated i from 1 to n-1; We have to find the all the possible (j>i) & (j<=n) which satisfy the given condition.For this number at ith position. i+j can range from i+i+1(a) to i+n(b);v[i]*v[j] = i+j.=> We have v[i] and range of i+j in hand. So what is the possible range of v[j]? ((a/v[i]) + (a%v[i]==0?0:1)) (c) to (b/v[j]) (d);Now iterate from c to d (possible v[j]) and find whether the number in this range exist at respectively jth index, such that a[i]*a[j] = i+j;Take sum.Time complexity should be ~ O(nlog(n)). The range of c-d is maximum when a[i]=1 ~ n but since all numbers are different so if at next index a[i]=2 then range of c-d shuld be n/2 . Now n+ n/2 +n/3 + ... ~ O(nlog(n))
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For each element you can find the number of elements that have product less than 2*n that is max(i+j). By mathematics you can prove that total such pairs are not more that nlogn. Hence brute force will work under time limits.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   +8 Where are those cats with their generosity problems now?
 » 5 weeks ago, # |   +24 The gap between div2-C and div2-D is too large so if u submit some wrong answers in the first three questions u get a bad rank...
 » 5 weeks ago, # |   +20 First time to solve a problem as difficult as div1D!
 » 5 weeks ago, # |   +13 This is the most difficult Div.2 problem D I have ever seen.
 » 5 weeks ago, # |   +20 120609085 my sweet O(NQ) solution has passed... :)
•  » » 5 weeks ago, # ^ |   +26 I also wrote the same code, and I think it is hackable. I'm very happy that it passed!!
•  » » » 5 weeks ago, # ^ |   +8 friends!!!!!
•  » » » » 5 weeks ago, # ^ |   +39 Hacked both of you :)
•  » » » » » 5 weeks ago, # ^ |   +5 Nope, I was first.
 » 5 weeks ago, # |   +18 Can somebody post the screen with Swistakk's comment about $O(n \cdot \sqrt{n} \cdot \log(n))$ vs $O(n^2)$, please?
•  » » 5 weeks ago, # ^ |   +23 Here we go.
 » 5 weeks ago, # |   0 Is there going to be a hacking period?
 » 5 weeks ago, # | ← Rev. 3 →   -28 why downvotes?
•  » » 5 weeks ago, # ^ |   +9 Multiple reasons for you getting downvotes. You didn't even mention which problem. Man, how do you expect to get help? Second, no one is going to voluntarily debug your code (unless he is too kind). There is a certain approach to ask for help. That is to share your logic, and people will find out what you are missing.
 » 5 weeks ago, # |   +10 What I don't like about observation problems that it is too easy to cheat and too difficult to catch the cheatersAnd this was like all the problems were observation based Even though I kind of tired of cheaters topics as well
 » 5 weeks ago, # |   0 How to solve D? Can anyone explain? Never seen such a big difficulty jump between C and D.
 » 5 weeks ago, # |   0 How to prove the correctness of problem C's solution?
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by PurpleCrayon (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 the round wasn't balanced :(
 » 5 weeks ago, # |   +2 how to solve D?
 » 5 weeks ago, # |   0
 » 5 weeks ago, # | ← Rev. 2 →   +26 Very enjoable contest! Very enjoable not math tasks! Very enjoable raiting everybody've gained! Very enjoable enjoy i've felt. Good job! Good job! Good job!
 » 5 weeks ago, # |   0 Can someone please explain solution to C problem
 » 5 weeks ago, # |   0 Did anyone noticed weird template of this guy tampa (Rank 1 in today's div 2 contest)
•  » » 5 weeks ago, # ^ |   +3 I think he is simply using the atcoder library templates.
 » 5 weeks ago, # |   0 I think that we should make the problem more clearly or at least give us more example to understand what exactly we have to solve. It's not funny when you read a long text and understand nothing :((
 » 5 weeks ago, # |   +32 Diego nice
•  » » 5 weeks ago, # ^ |   +13 I never understood how it happened
•  » » » 5 weeks ago, # ^ |   +8 Do you mean that you don't know what "Unexpected verdict" means?
•  » » » » 5 weeks ago, # ^ |   +5 Yes. And I don't know, why it happened on my hack
•  » » » » » 5 weeks ago, # ^ |   +23 You've hacked the model solution (it got TLE or RE, probably TLE here).
•  » » » » » » 5 weeks ago, # ^ |   +38 Oh, realy nice!
•  » » » » » » » 5 weeks ago, # ^ |   +13 Well, I'm not that sure, it should not happen if everything would be prepared correctly, but shit happens. And yep, for you it's nice :P
•  » » » » » » » » 5 weeks ago, # ^ |   +13 Maybe "shit" is too much actually. I that guess it means that one of the solutions marked as a correct one got TLE, it doesn't mean that the main one got it.
•  » » » » » » » 5 weeks ago, # ^ |   +49 One of slowest solutions we considered correct, to be precise. But it doesn't belittle your achievement, congrats!
•  » » 5 weeks ago, # ^ |   0 Hey Radewoosh please tell me how to solve div-2 D (div-1 B)
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +63 Sure. Read the statement, then start thinking about the solution.EDIT Or read the editorial.
 » 5 weeks ago, # |   -9 :'/
 » 5 weeks ago, # |   -20
•  » » 5 weeks ago, # ^ |   +86 This contest which had no corner cases:
 » 5 weeks ago, # |   -16 My nice explanation of Problem B and check out problem A also.https://www.youtube.com/watch?v=frb_ngCPXOg
 » 5 weeks ago, # |   +3 This round, Will be rated?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you can see the rating changes on the standings page.
•  » » » 5 weeks ago, # ^ |   +7 Tranks you :)
 » 5 weeks ago, # |   -23 Guyjj and gals ! Probmle A, Nice and smooth explanation here !https://youtu.be/Me6sGr9s5FM
•  » » 5 weeks ago, # ^ |   0 Did you get any solution from system yet? phoenix_slayer
•  » » » 5 weeks ago, # ^ |   0 No not yet.. But I got my rating change!! But still there's a warning which I would like to get removed from them!! Like A question always have same kind of submissions and don't know why they plagiarised!! I don't think they will correct it!!
•  » » » » 5 weeks ago, # ^ |   0 You atleast got your rating changed bro!!
 » 5 weeks ago, # | ← Rev. 5 →   -16 ...,,..
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   -10 ...
•  » » » 5 weeks ago, # ^ |   +1 You can say you didn't cheat and can ask for not to give any punishment. But why you will be in huge pain and stress just because of loosing some rating?.do you think life is that much cheap??
•  » » » 5 weeks ago, # ^ |   +19 solution 120576906 for the problem 1541C significantly coincides with solutions kritarth2121/120575849, kritarth21/120576906 You have participated in the contest using two accounts and this is forbidden by the rules.If kritarth2121 is actually some imposter rather than your alt account, then the obvious code similarity is very suspicious. What are the chances to have similarly named accounts submitting similar solutions just accidentally? just because of same function which is written to avoid plague took me into plague Code obfuscation is also forbidden by the rules. Even though this is not actively enforced yet.
•  » » » » 5 weeks ago, # ^ | ← Rev. 8 →   0 .....
•  » » » » » 5 weeks ago, # ^ |   +2 Yes, must be a coincidence that as soon as kritarth2121 solution to problem B and C got accepted, you submitted it after that with your additional useless functions.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 ....
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +5 I am removing this comment now . I don't want to give him more mental stress but i am hoping that he will never cheat again.
 » 5 weeks ago, # |   0 Sorry but it was a coincidence .. I published my code on ideone.com that's why the problem has occured. Please give my ratings back and i hope you can see that i have made 2 attempts which gave a TLE and hope you can recoganise it. if i were to cheat i wouldnt have made wrong attempts.hope to get rigth decision fron codeforces. thankyou
 » 5 weeks ago, # | ← Rev. 3 →   +1 Nowdays codeforces solutions are available in net during contest. Someone are getting ideas from live streaming and someone are getting direct code. I don't know what do you want to achieve by cheating? Rating? Show some courage. The problem solvers who are practicing hardly they won't get a correct rating for your cheating during the contest.
 » 5 weeks ago, # |   0 Hello codeforces, I was using ideone.com as I did not have my personal machine, and I think that's the reason that this problem has occurred. I have been sincere in my attempts for this as well as previous contests and I will ensure that I don't use ideone.com again. Thank you.
•  » » 5 weeks ago, # ^ |   0 This is your mistake. Just do another contest and achieve ratings
 » 5 weeks ago, # |   0 Congratulations to tourist for winning second place!
 » 5 weeks ago, # |   0 Where is contest's rate Lol
 » 5 weeks ago, # |   0 Hey MikeMirzayanov I received following system message regarding plagiarism in both of my code submission-Your solution 120549299 for the problem 1541A significantly coincides with solutions manvi2912/120544816, Action_Kamen/120549299, satejansh/120561800This is definitely an error on the part of the system because 1) I didn't cheat a single line from anyone 2) If you check the time taken by the system on concerned submission all time taken are different 3) I was using a predefined template for both of my submissions, which is different from the template (or boiler plate) code used by other submission 4) In the problem B I submitted using a map but none of the above submission used map. 5) While some of the code for A might be matching that is due to sheer luck as the variable used are quite general such as t to test case i for loop counter( logic in the question was also pretty straightforward)So please, MikeMirzayanov do the needful as I am working hard for this and also after a long time any of my contest went well.Thank You