### PurpleCrayon's blog

By PurpleCrayon, history, 19 months 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 244mhq 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

| Write comment?
 » 19 months ago, # |   -395 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » 19 months ago, # ^ |   -394 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » 19 months ago, # ^ |   -397 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » 19 months ago, # ^ |   -407 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » » 19 months ago, # ^ |   -393 Omg purplecrayon orz. Can't wait to solve your geniosity problems
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +204 The comment is hidden because of too negative feedback, click here to view it
•  » » » » » » » 19 months ago, # ^ |   -220 The comment is hidden because of too negative feedback, click here to view it
•  » » » » » » » 19 months ago, # ^ |   +43 Don't steal my tricks. lol
•  » » » » » » 19 months ago, # ^ |   -26 Whatta coincidence! The sequence of their profile picture is like Mocha bear is rotating milk bear in some order :o
•  » » » » » » » 19 months ago, # ^ |   +53 that's the point... cf is tired of gyrating cats
•  » » » » » » » » 19 months 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.
•  » » » » » » » » » 19 months ago, # ^ |   +11 well, purplecrayon is part of our gyrating cat club :P
•  » » » » » » » 19 months ago, # ^ |   +23 Those are bears..? For so long I thought they were cats.
•  » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 .
•  » » » » » » 19 months ago, # ^ |   -153 It's a bad sight that the first five comments on the blog have all these negative votes!Suggest removing it, MikeMirzayanov
 » 19 months ago, # |   +144 I hope everyone enjoys our problems and learns something new!
 » 19 months 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!
 » 19 months ago, # |   +46 Maybe I get purple on PurpleCrayon's round
•  » » 19 months ago, # ^ |   +28 I feel really sad to say it won't happen but you might get blue in this round :P
•  » » » 19 months ago, # ^ |   +5 BlueCrayon orz
•  » » » » 19 months ago, # ^ |   0 What is orz?
•  » » » » » 19 months ago, # ^ |   +4 It's a person bowing, 'o' is head, 'r' is arms and 'z' is folded legs.
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 So, if I say "someone" orz, this means I would like to shoot "someone"?
•  » » » » » » » 19 months ago, # ^ |   +3 No, it means you pay respect to someone and admire them.
•  » » » 19 months ago, # ^ |   0 Why not? QWQmaster got from Specialist to CM in a recent contest and there are more such examples.
•  » » » » 19 months ago, # ^ |   +124 What is purple?
•  » » » » » 19 months ago, # ^ |   +15 You are lucky to never find out.
•  » » » » » 19 months ago, # ^ |   +9 afterall: What is yellow?
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +35 Come from real id 👉 👈
 » 19 months ago, # |   +38 As a tester, give me ..As a tester I can assure you that you will write purplecrayon orz after contest (before too)
•  » » 19 months ago, # ^ | ← Rev. 2 →   -46 Here. I can give you this latest striver meme. SpoilerLol downvoting my greatness :(
•  » » » 19 months ago, # ^ |   0 waifu sauce please
•  » » » » 19 months ago, # ^ |   0 Just search Rikka, she's famous.
 » 19 months ago, # |   +67 Each division will have 5 problems and 2 hours and 15 minutes to solve them. This line scares me.
 » 19 months ago, # |   -35 Why is the rating limit for Div.2 is 1899? Shouldn't it be 2099?
•  » » 19 months ago, # ^ |   +23 I think because this contest has Div 1 too.
 » 19 months ago, # |   -37 Score distribution for this round will be really interesting I guess. 5 problems in 2:15 is very challenging
 » 19 months ago, # |   +25 Damn, 5 problems in 2:15 hours. Seems like a Div-1.5 :)
 » 19 months ago, # |   +31 If both divisions are 2 hours and 15 minutes why here the length is 2 hours? Spoiler
 » 19 months ago, # | ← Rev. 7 →   -107 .
•  » » 19 months ago, # ^ | ← Rev. 2 →   +38 Don't tag them unnecessarilyEdit1: Lol you totally changed the main idea of your comment
•  » » 19 months ago, # ^ |   +14 Mind your own rating! :P
•  » » 19 months ago, # ^ |   0 You could reply me instead of writing my name ....
 » 19 months ago, # |   +15 As a tester, I can confirm problems are awesome! Good luck in the round!
•  » » 19 months ago, # ^ |   +4 but u said problems will be awesome!!!
 » 19 months ago, # |   -66 Hope to be expert.
•  » » 19 months ago, # ^ | ← Rev. 3 →   +38 Just don't cheat again. GL;HF.
 » 19 months ago, # |   -10 As someone purple did not allow test the round, give me contribution!
•  » » 19 months ago, # ^ |   -56 As someone purple also did not allow to test this round, give me contribution!
 » 19 months ago, # | ← Rev. 2 →   0 As a participant, I hope my fellow comrade hbarp and I can become purple in this PurpleCrayon blessed round, unlike last time. Wish us luck!! xD
•  » » 19 months ago, # ^ |   +15 Good luck to you :)
 » 19 months ago, # |   +41 As a tester, I can say that I enjoyed the problems. Good luck to everyone participating :)
 » 19 months ago, # |   +1 I hope my colour change with a +ve delta :)
 » 19 months ago, # |   +6 Unfortunately, most of IOI participants can't participate in this round :(
 » 19 months 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!
•  » » 19 months ago, # ^ |   +6 It's not started yet :)
 » 19 months ago, # |   +17 Excited for the round, knowing the writers I have no doubt it will be great!
 » 19 months ago, # |   +10 I wish problem statements would be as clean as this announcement
•  » » 19 months ago, # ^ |   +45 I wish statements would be as short and clear as the annoucement, too.
 » 19 months ago, # |   +1 I wish that this contest has Graph theory and DP related problems !
•  » » 19 months ago, # ^ |   +2 sounds funny
•  » » 19 months ago, # ^ |   0 Thats all you had to say
 » 19 months ago, # |   -54 .
 » 19 months 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
 » 19 months ago, # |   0 PurpleCrayon is not even purple Sadge
 » 19 months ago, # |   -11 "You, for participating!" This line hit hard :(
 » 19 months ago, # |   +20 As a cyan, D seems not killable.So, speedforces :(
 » 19 months ago, # |   -51 As a tester,who wasnt able to solve a single problem
 » 19 months ago, # |   +1 Really excited to participate in div2.. All the best everyone.
 » 19 months ago, # |   0 The scoring distribution for div2 is weird. I hope I get positive delta.
 » 19 months 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?
•  » » 19 months 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.
•  » » » 19 months ago, # ^ |   +5 Why does the easy version has a higher rating than the hard version?
•  » » » » 19 months ago, # ^ |   +5 This is a fine move by the setters so that we lame programmers can feel better.
•  » » » » 19 months 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.
 » 19 months ago, # |   0 Hope that I can become a crayon today ^_^
 » 19 months ago, # |   +3 Is it logical that the second part of the last problem of div2 has the same score as in div1 (750)?
 » 19 months ago, # | ← Rev. 2 →   0 .
•  » » 19 months ago, # ^ |   +3 It's 38 mins dear
 » 19 months ago, # |   0 how to solve D when you are green?
•  » » 19 months ago, # ^ |   +15 How to solve D when you are blue ?
•  » » » 19 months ago, # ^ |   0 How to solve D when you are Cyan?
•  » » » » 19 months ago, # ^ |   0 I am waiting for someone to say become red! xD
•  » » » » 19 months ago, # ^ |   0 Respect the unusual timing as a usual one. That could work probably work. :D
•  » » » 19 months ago, # ^ |   +1 Seems to solve current D, I need to be atleast 4000 rated :/
•  » » » » 19 months ago, # ^ |   0 Well you are speaking facts. D is too OTZ levelled. T_T :(
 » 19 months ago, # |   +18 So are we solving E2 after A?
•  » » 19 months ago, # ^ |   0 Went with that approach at start. Only to return back sad faced after reading E1 fr 5 mins. T_T . Dumb me!!
 » 19 months ago, # |   +1 I wish everybody an awesome codeforces round
 » 19 months ago, # |   +1 gl
 » 19 months ago, # |   +8 i think today i become pupil
•  » » 19 months ago, # ^ |   +15 F
 » 19 months ago, # |   +45 Anyone in Div 2 feeling like they accidentally participated in Div 1?
 » 19 months ago, # |   +30 Speedforces, redefined.
 » 19 months ago, # |   +15 The game of hand speed.
 » 19 months ago, # |   +87 The expected value to solve D by myself is 0.
 » 19 months ago, # |   +36 Most difficult div.2 D ever?
 » 19 months ago, # |   +36 Never seen such a big jump in difficulty from C to D
 » 19 months ago, # |   +3 What is Normal Red?
 » 19 months ago, # |   +17 Div 2 is definitely a speed force.
 » 19 months ago, # |   +21 speedforces
 » 19 months ago, # |   +60 I have no idea on 1B or 2D, wtf
 » 19 months ago, # |   +260 Some relavant meme:
•  » » 19 months ago, # ^ |   +17 I want to give 200 upvotes T_T
•  » » 19 months ago, # ^ |   +17 E1 is like Atcoder grand contest math problem.
 » 19 months ago, # | ← Rev. 2 →   +19 ive read all the problems and they are really nice good job!
 » 19 months ago, # |   0 Solved 3! Then saw D. WTF only 13 submissions!?
•  » » 19 months ago, # ^ |   +16 Started with D, read it & thought something, then saw A. WTF crossed 10,000 submissions!?
•  » » » 19 months ago, # ^ |   +7 I actually never read D..just saw the submissions lol.
 » 19 months ago, # | ← Rev. 2 →   -9 Forget about it
•  » » 19 months ago, # ^ |   +27 It's probably hard to solve problems when you are creating memes during the contest.
•  » » » 19 months ago, # ^ |   +48 There must be more than 16k people creating memes, because only 15 people could solve the problem
 » 19 months ago, # |   +8 I feel like this was speedforces but at the same time wasn't speedforces :)
 » 19 months ago, # |   +8 So by Div 2 u meant Div 1.5
 » 19 months ago, # | ← Rev. 3 →   -7 Good and challenging problems ! Good job but the difference of difficulties of problems between c and d was a lot !
 » 19 months ago, # |   +65 Literally 15 mins on 1A and 2 hours on crying
•  » » 19 months ago, # ^ |   +1 Same pinch !!
•  » » 19 months ago, # ^ |   +5 Same here , 5 min and then nothing
•  » » 19 months ago, # ^ |   0 Same ...
 » 19 months ago, # |   +19 That sums it up :(
 » 19 months ago, # |   +14 I hate probability.
 » 19 months 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.
 » 19 months 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.
•  » » 19 months ago, # ^ |   0 Can you share your approach to DIV 2 b ?
•  » » » 19 months 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)
•  » » » » 19 months 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 :)
•  » » » » » 19 months ago, # ^ |   +3 Yes you are right. Thnx.
 » 19 months ago, # |   +7 Am I the only that forgot numbers in B are distinct and wasted more than 20 min because of that
•  » » 19 months ago, # ^ |   +1 no
•  » » 19 months ago, # ^ |   +4 Yep. Me too. But it's my fault.
 » 19 months ago, # |   +14 Seems like I'm getting dumber with each passing day, half of the world solved C in one go.
•  » » 19 months ago, # ^ |   +7 :) while I could not able to solve it.
•  » » » 19 months ago, # ^ |   0 :( another rough day for us
•  » » » 19 months ago, # ^ |   0 Same here :(I wonder how 4k+ people solved C. Was it that easy?
•  » » 19 months 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
•  » » 19 months ago, # ^ | ← Rev. 2 →   +1 I get wa on both A and B :( ,same pinch bro,I also feel same
 » 19 months 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. :(
•  » » 19 months ago, # ^ |   0 3.5 but no idea what the actual fractions going into it were
•  » » 19 months ago, # ^ |   0 I guess it's 7/2
 » 19 months ago, # |   0 Thanks for the contest! I really enjoyed it.
 » 19 months 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.
 » 19 months ago, # |   +6 ok ...i hate my life now
 » 19 months ago, # |   0 I entered 25 minutes later and after 35 minutes I left by topping in my room! This line describes the contest!
 » 19 months ago, # |   +98 MEET AN EXPRIENCED & SHAMELESS CHEATER This is how Master_Jiraya 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 ......Master_Jiraya 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 Master_Jiraya 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]++;
•  » » 19 months ago, # ^ |   +43 Others Template; #include <>Your Template: MEET AN EXPRIENCED & SHAMELESS CHEATER.. kedos123And you submit it after every contest in announcement. Keepitup.
•  » » 19 months ago, # ^ |   +1 One more guy vadapavandchill check his submissions with obsfucated code 120565541 120557993
 » 19 months ago, # |   +1 Can anyone explain Div2 problem C
 » 19 months ago, # | ← Rev. 3 →   0 ..
•  » » 19 months ago, # ^ |   +3 On above that put that as Div2D :(
 » 19 months 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?
•  » » 19 months 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 .
 » 19 months ago, # | ← Rev. 3 →   0 How to solve B ? I don't know how it can be solved in o(n)
•  » » 19 months 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.
•  » » 19 months 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).
•  » » » 19 months ago, # ^ |   0 I feel more dumb now because i got the same idea but thought it would give TLE ; _ ;
•  » » » » 19 months 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.
•  » » 19 months 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)$.
 » 19 months ago, # |   0 How to solve problem C ?
•  » » 19 months 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.
•  » » 19 months 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$.
•  » » » 19 months ago, # ^ |   0 I really don't understand how you do it
•  » » » » 19 months 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.
•  » » » » » 19 months 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.
•  » » » » » » 19 months 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.
•  » » » » » » » 19 months 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..
 » 19 months 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 :(
 » 19 months ago, # | ← Rev. 3 →   -36 Hello! Nice problems but the leveling of the questions was not very good. D Div2 was very hard
 » 19 months 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)$?
•  » » 19 months ago, # ^ |   0 ah, that was my idea too! I coded it up but got WA on the example pretest #3 :(
•  » » 19 months 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.
•  » » 19 months 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.
 » 19 months ago, # |   0 How to solve Div 1C/2E?
•  » » 19 months 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.
 » 19 months ago, # |   +12 Couldn't submit 1B by 10 seconds :(
 » 19 months 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.
 » 19 months ago, # |   +1 Biggest drop of my contest history. Well, worth a fall if I hope to perform well again!
 » 19 months 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.
 » 19 months ago, # |   +8 How to solve div-2 D ??
 » 19 months 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).
 » 19 months 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
 » 19 months ago, # |   +26 Pure speedforces
 » 19 months ago, # | ← Rev. 3 →   -7 c
•  » » 19 months 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
 » 19 months 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<
•  » » 19 months ago, # ^ |   +1 Can you put it in a spoiler message, please?
 » 19 months 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.
 » 19 months ago, # |   0 how to solve B div2
•  » » 19 months 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))
•  » » 19 months 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.
 » 19 months ago, # |   +8 Where are those cats with their generosity problems now?
 » 19 months 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...
 » 19 months ago, # |   +20 First time to solve a problem as difficult as div1D!
 » 19 months ago, # |   +13 This is the most difficult Div.2 problem D I have ever seen.
 » 19 months ago, # |   +20 120609085 my sweet O(NQ) solution has passed... :)
•  » » 19 months ago, # ^ |   +26 I also wrote the same code, and I think it is hackable. I'm very happy that it passed!!
•  » » » 19 months ago, # ^ |   +8 friends!!!!!
•  » » » » 19 months ago, # ^ |   +39 Hacked both of you :)
•  » » » » » 19 months ago, # ^ |   +5 Nope, I was first.
 » 19 months 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?
•  » » 19 months ago, # ^ |   +23 Here we go.
 » 19 months ago, # |   0 Is there going to be a hacking period?
 » 19 months ago, # | ← Rev. 3 →   -28 why downvotes?
•  » » 19 months 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.
 » 19 months 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
 » 19 months ago, # |   0 How to solve D? Can anyone explain? Never seen such a big difficulty jump between C and D.
 » 19 months ago, # |   0 How to prove the correctness of problem C's solution?
 » 19 months ago, # |   0 Auto comment: topic has been updated by PurpleCrayon (previous revision, new revision, compare).
 » 19 months ago, # |   0 the round wasn't balanced :(
 » 19 months ago, # |   +2 how to solve D?
 » 19 months ago, # |   0
 » 19 months 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!
 » 19 months ago, # |   0 Did anyone noticed weird template of this guy tampa (Rank 1 in today's div 2 contest)
•  » » 19 months ago, # ^ |   +3 I think he is simply using the atcoder library templates.
 » 19 months ago, # |   +32 Diego nice
•  » » 19 months ago, # ^ |   +13 I never understood how it happened
•  » » » 19 months ago, # ^ |   +8 Do you mean that you don't know what "Unexpected verdict" means?
•  » » » » 19 months ago, # ^ |   +5 Yes. And I don't know, why it happened on my hack
•  » » » » » 19 months ago, # ^ |   +23 You've hacked the model solution (it got TLE or RE, probably TLE here).
•  » » » » » » 19 months ago, # ^ |   +38 Oh, realy nice!
•  » » » » » » » 19 months 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
•  » » » » » » » » 19 months 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.
•  » » » » » » » 19 months ago, # ^ |   +49 One of slowest solutions we considered correct, to be precise. But it doesn't belittle your achievement, congrats!
•  » » 19 months ago, # ^ |   0 Hey Radewoosh please tell me how to solve div-2 D (div-1 B)
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +63 Sure. Read the statement, then start thinking about the solution.EDIT Or read the editorial.
 » 19 months ago, # |   -9 :'/
 » 19 months ago, # |   -20
•  » » 19 months ago, # ^ |   +86 This contest which had no corner cases:
 » 19 months ago, # |   +3 This round, Will be rated?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Yes, you can see the rating changes on the standings page.
•  » » » 19 months ago, # ^ |   +7 Tranks you :)
•  » » 19 months ago, # ^ |   0 Did you get any solution from system yet? phoenix_slayer
•  » » » 19 months 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!!
•  » » » » 19 months ago, # ^ |   0 You atleast got your rating changed bro!!
 » 19 months ago, # | ← Rev. 5 →   -16 ...,,..
•  » » 19 months ago, # ^ | ← Rev. 3 →   -10 ...
•  » » » 19 months 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??
•  » » » 19 months 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.
•  » » » » 19 months ago, # ^ | ← Rev. 8 →   0 .....
•  » » » » » 19 months 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.
•  » » 19 months 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.
 » 19 months 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.
 » 19 months ago, # |   0 Where is contest's rate Lol
•  » » 19 months ago, # ^ |   -8 Seeking your kind attention!!! MikeMirzayanov I hope you will look into this matter. About submitting an easy problem so late, i was busy solving C and B first, this is why i solved A at last because B and C mattered to me much as A was straight forward problem and i knew everyone who participated the contest could solve it with 1 less than 1 month of experience. Please, Check this out.
•  » » » 19 months ago, # ^ |   0 No brother.. Rather say that,you got the solution of B and C first and you made a slight change so that plag detector Won't catch you and at last you got A and you didn’t change it much. Lol.have some brain before cheating.
•  » » » » 19 months ago, # ^ |   0 Do you even know me bro that you are so sure about your accusation? WHO basically needed solution for A? Kindly check my profile and then say that, i finally got solution for A!!!!! and then didnt change it!!!! Kindly stop creating new accounts and scamming please. This community is becoming full of scammers day by day!
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Your solution for C and B is exactly same as the leaked code(you know but wont confess)and you just changed a little bit. I saw you just started doing good in last few days.Why you needed to cheat in this circumstances.you could hold a little bit for your rating to continue in expert rather than cheating. Such a shame
•  » » » » » » 19 months ago, # ^ |   0 So you saying i copied b,c and changed the codes. But didn't bother to change code of A? Makes sense? Who would be this dumb bro? I literally have no idea what leaked code you are talking about tho. Ideas can match of a solution!This is why we should record while participating a contest as a emergency proof. Gonna do it from next rounds though!
•  » » » » » » » 19 months ago, # ^ |   +4 Sorry to say but you submitted all three with a delay of 8 and 7 mins, that clearly shows you got the answer and just uploaded them after few changes but unluckily you got plag. in A.(But you will not accept it)
•  » » » » » » » » 19 months ago, # ^ |   0 Yes bro, you live in my house, so you can predict everything what happened during contest time
•  » » 19 months ago, # ^ |   0 Were you using ideone or pastebin?
•  » » » 19 months ago, # ^ |   0 No. I didn't use that.
 » 19 months ago, # |   -18 So poisonous mathforces round!
 » 19 months ago, # | ← Rev. 4 →   +10 Seeking your attention MikeMirzayanov PurpleCrayon !I got the message that my solution 120541662 significantly coincides with solution 120540725 of user Sky200 whom I don't even know. The similarities in code are because code was short and for the case of odd, "3 1 2" was given in the sample case so, I have used same the user also have used the same. The problem was quite straightforward and almost everyone implemented using two loops. I haven't copied any single line of code from anyone. I have participated in 60+ contests and solved 400+ problems. I think our thinking was the same and because of short code, they are having similarities.Even Official Editorial followed the exact same approach!!Kindly check it again. Thanks!
 » 19 months ago, # |   +3 Seeking your attention MikeMirzayanov PurpleCrayon!I got a message from the system stating that me and FranSkarica have copied in some way the solution of 1541A - Pretty Permutations. But I do not even know the person and did all my code locally. So there is no chance of that person coping my code or me copying his. The reason it has been caught in this type of test is because the logic is extremely simple (div-2 A) and most people would have got the same logic. The code is also very small which could lead to higher probability of this being a coincidence. I have particpated in 100+contests and solved around 1000 problems, I think I will definitely be able to solve A problem by myself. I also see that many have faced the same issue in the comments section. Kindly have a look at all the requests and do what is necessary
•  » » 19 months ago, # ^ |   0 Same thing happened with me
 » 19 months ago, # |   0 Became blue by courtesy of speedforces.
 » 19 months ago, # | ← Rev. 2 →   0 Seeking your attention MikeMirzayanov PurpleCrayon!I got the message that "Your solution 120588348 for the problem 1541A significantly coincides with solutions jatin3028/120548283, Saitama1227/120548701, TheBeardedCoder/120549565, yog_111/120550555, Ali_salloum/120550818, Atom_Bomb/120559071, phoenix639/120560190, sanskar00/120562876, Astro_Aditya/120563489, reshma_27/120569500, Dilip24/120573780, Shalika22/120582653, Farhan_meb/120588348, Paavan_parekh/120595630, Dlip/120597081. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation" But i don't know any of them at all!.The similarities in code are because code was short and for the case of odd, "3 1 2" was given in the sample case so, I have used same the user also have used the same. The problem was quite straightforward and almost everyone implemented using two loops. I haven't copied any single line of code from anyone. For this i got -184 which is a really big downfall for me.I have participated in 200+ contests and solved 800+ problems. I dont think i am unable to solve problem A. I think our thinking was the same and because of short code, they are having similarities.Even Official Editorial followed the exact same approach!!Kindly check it again.Thanks!
 » 19 months ago, # | ← Rev. 4 →   0 Seeking your attention MikeMirzayanov PurpleCrayonThis is regarding a mail I received for plagiarism in my first solution [ GordeyZav/120537624, pranav_mehta/120551724 ], I would just say that 1st solution was itself very intuitive and I believe a ton of users would have used the same logic, thereby the logic being same should not be a deciding factor, now if the plagiarism is because I used same iterator "i" and variable "n" then I believe the basic coding books and online tutorials are to be blamed, I don't really care about the rating or stuff, however getting a plagiarism badge on you when you didn't cheat isn't something anyone would want.
•  » » 19 months ago, # ^ |   0 You got your rating changed bro?
•  » » » 19 months ago, # ^ |   0 nop
•  » » » » 19 months ago, # ^ |   0 You didn't even get any penalties bro?
•  » » » » » 19 months ago, # ^ |   +1 People get penalties in the second or third time when they are plagarised. In the first time simply the participant becomes unrated. Rating not gonna down.As your rating got down,obviously you have previous history of coincidence / plagiarism