### IgorI's blog

By IgorI, history, 6 weeks ago, translation,

Hi, Codeforces!

I'm glad to invite you to take part in Codeforces Round #696, which will take place on Jan/19/2021 17:35 (Moscow time). Round will be rated for participants with rating less than $2100$. Participants from the first division can take part out of competition.

There will be $6$ problems for $2$ hours. All problems are authored by me. Thanks to adedalic for excellent round coordination and to MikeMirzayanov for Codeforces and Polygon.

Also thanks to testers errorgorn, awoo, rkm62, khiro, AmShZ, IaMaNanBord, Osama_Alkhodairy, Prakash11, Gauravvv, HIS_GRACE, Dragnoid99 for testing the round and giving valuable feedback for problems.

Scoring is $500-1000-1500-2000-2250-3000$.

Good luck!

UPD: Editorial

UPD: Congratulations to the winners!

Of both divisions:

Of the second division:

• +614

 » 6 weeks ago, # |   +103 I have a naive question: Why setters take too much time on selecting the scoring distribution?
•  » » 6 weeks ago, # ^ |   +53 It needs to be balanced, one should not feel like he wasted time solving C and D if E wasn't that hard but worth much more points, converse is also true. I hope you get what I am trying to say.
•  » » » 5 weeks ago, # ^ |   -45 I think, if greens are selected for testing Question A & B Scoring will be more accurate :)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +2 Not revealing score distribution too early doesn't mean it takes so much time for setters. It might change someone's strategy at the beginning of the contest.
•  » » 6 weeks ago, # ^ |   +224 Procrastination
•  » » » 5 weeks ago, # ^ |   +77 As a tester, 1-gon is back for contribution. XD
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +90 Reason ;)...
•  » » » » » 5 weeks ago, # ^ |   +14 Let's make 1-gon rank 1 again!
•  » » » 5 weeks ago, # ^ |   +27 I miss the old 1-gon :D
•  » » » » 5 weeks ago, # ^ |   +17 and we all know that old is gold
•  » » » 5 weeks ago, # ^ |   +1 Who are you?
 » 6 weeks ago, # |   0 Good Luck Participants! — a participant
•  » » 6 weeks ago, # ^ |   0 you too :3
 » 6 weeks ago, # |   +27 When you see some common testers and started thinking how can this be a coincidence?
•  » » 5 weeks ago, # ^ |   +22 As a tester I feel bad that you didn't tag me :-(
•  » » » 5 weeks ago, # ^ |   +2 As a future participant I feel bad that you didn't help me being one of the tester :P
•  » » » » 5 weeks ago, # ^ |   +14 1) I try my best to help problem setters. 2) I try my best to help you and other participants.It is guaranteed that the above two statements are equivalent.Still you can verify that through some algorithm ( if there exist any :-).
•  » » 5 weeks ago, # ^ |   0 it's a trap!
 » 6 weeks ago, # |   +125 this set is nice :3
 » 6 weeks ago, # |   +22 we should be thankful to HIS_GRACE for testing this round
 » 6 weeks ago, # | ← Rev. 4 →   -70
 » 6 weeks ago, # | ← Rev. 4 →   -87 hope it be a good contest and yall good ratings
 » 6 weeks ago, # |   +45 Problems are very interesting! Good Luck!
 » 6 weeks ago, # | ← Rev. 2 →   -82 .
•  » » 5 weeks ago, # ^ |   0 lol
 » 6 weeks ago, # |   -10 I wish the Problems have some bold words. Guess that serves me right for trying too hard to speedsolve.
•  » » 6 weeks ago, # ^ |   -10 I wish the formal statement should be in bold.
•  » » » 6 weeks ago, # ^ |   +18 I wish the Verdict should be in bold.
•  » » » » 6 weeks ago, # ^ |   +37 I wish my performance will be bold.
 » 6 weeks ago, # |   +7 Hoping that my performance will be at least same as my previous performance in your contest.
•  » » 6 weeks ago, # ^ |   -88 Bro you are trying since 6 years on codeforces why you still a Specialist. Is there any mistake you are making, please give some experience advice also mistake you have made i'm a beginner here want to learn from you :).
•  » » » 6 weeks ago, # ^ |   +61 At least he is enjoying what he is doing without worrying much about ratings.
•  » » » » 6 weeks ago, # ^ |   -120 But bro In india geting high rating means high placement, The company would not ask you enjoying or not :( It's reality brother. So I only ask for suggestion that the mistake we could not repeat.
•  » » » » » 6 weeks ago, # ^ |   +45 That is so not true! I think it is this misconception that is leading to the alarming rise in cheating cases. Companies do not ask for a high rating on competitive programming platforms when they hire. They don't even care for it, in most cases.Recruiters only expect candidates to have a good knowledge of Data Structures and Algorithms, and programming problems on platforms like Codeforces and Codechef sometimes require the use of those topics. As a result, being good at DSA is wrongly correlated with having a high rating on these platforms, and a lot of people end up focussing on rating rather than improving their knowledge and problem-solving skills!
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +19 Competitive programming is a sport and it is never meant to be considered as a parameter for getting placements. Read this article for more clarification. https://www.freecodecamp.org/news/mythbusting-competitive-programming/
•  » » 6 weeks ago, # ^ |   -22 Sorry drifter_kabir Mridul323, If you taken it in negative i'm worried as i wasted my 2 years in college and started cp too late would i get job or not :( does not have any right direction how to improve in that less time.
•  » » » 5 weeks ago, # ^ |   +11 cruX_072 It is never late to do anything,but bro I let u know 5 star or candidate master will give negative image on your resume if u have not that true level ,So instead of focussing on rating focus on making ur data structure and algorithm stronger and also create a good dev project side by side.Also most of the guys which are here for more than year or two is doing cp for dopamine rush which they got when they have good contests or even seeing an accepted solution. AND AND NO ONE CARE FOR YOUR RATING NOT EVEN UR BEST BUDDIES OF COLLEGE.
•  » » » » 5 weeks ago, # ^ |   +31 Please don't compare 5 stars on codechef with candidate master on codeforces.
•  » » » » » 5 weeks ago, # ^ |   +7 It's actually Expert in Codeforces
•  » » » » » 5 weeks ago, # ^ |   +2 viwreck U know the feeling right,I just wanted to let cruX_072 know that rating or star shouldnt be your priority ,It will not matter if u are really good in dsa...And I know candidate master should never be compared to codechef any star ,cause I have even seen many people with 6 and 7 star by doing only long challenge(U can see India's no 1 on codechef right now for reference)/
 » 6 weeks ago, # |   +3 I was wondering how they choose the testers , is it a complicated proccess?!
•  » » 6 weeks ago, # ^ |   +33 You just need to connect with author or coordinator to test the round.
 » 6 weeks ago, # |   -28 IGORL ORZ
 » 6 weeks ago, # |   +18 Hoping for shorter problem descriptions just like the announcement.
 » 6 weeks ago, # | ← Rev. 6 →   -48 As a tester, I request some contribution.
•  » » 6 weeks ago, # ^ |   +2 What was that, and who are you? :D
•  » » » 5 weeks ago, # ^ |   +30 To all you downvoting — do you realize that this was in response to the first revision of the comment?
 » 6 weeks ago, # |   0 Can't wait.Excited to face some challenging problems
 » 6 weeks ago, # |   +30 It's just me or someone also felt that Codeforces rounds per month, are less nowadays?
•  » » 5 weeks ago, # ^ |   +13 I also thinks so. Might be Mike and his team are planning to do something against cheaters, because from past 3-4 months everyone knows what is happening...
•  » » » 5 weeks ago, # ^ |   +6 Or maybe, because there are lesser contest proposals these days.
•  » » » » 5 weeks ago, # ^ |   +55 I think the proposal queue is quite long and there are still many writers waiting. From my personal experience, I finally get KAN's review exactly 4 months after I propose my friends' and my contest. Moreover, our contest doesn't even have a coordinator to assign to. Coordinators are so busy and committed to their work. We should thank them for their devotion.Anyway, in the period of less contests, don't forget there are considerable amount of nice problem in GYM and previous contests. Go and solve them!
 » 6 weeks ago, # |   0 Good luck to all of you!
 » 6 weeks ago, # |   +94 As a tester, I can confirm that the problems are awesome and you guys will enjoy the contest.
•  » » 6 weeks ago, # ^ |   -79 Good luck on nullifying ur negative contribution( https://codeforces.com/blog/entry/86882?#comment-749682 ).
•  » » » 5 weeks ago, # ^ |   0 and you saying that got him contribution. People love proving people wrong lol
•  » » » » 5 weeks ago, # ^ |   +2 :(
•  » » 5 weeks ago, # ^ |   0 As a participant, I wish the same.
 » 6 weeks ago, # |   +14 Wish you all luck ^^
•  » » 6 weeks ago, # ^ |   0 ⬆️⬆️⬆️
•  » » 6 weeks ago, # ^ |   0 ❤❤
 » 6 weeks ago, # |   +25 Great round id
 » 6 weeks ago, # |   +21 Since this is a palindromic round ( 696 ). Hoping to see one question on Palindrome :D
 » 6 weeks ago, # |   -10 anyone waiting for round #700?
•  » » 5 weeks ago, # ^ |   -19 Learn to stay in the present.
 » 6 weeks ago, # | ← Rev. 2 →   -56 Chahu me ye chahu dil se me ye chahu k is contest k baad pupil me bun jau.
 » 5 weeks ago, # |   +2 I will try to solve solve A,B,C. Good Luck Every One, Keep Practicing and keep shining.
 » 5 weeks ago, # | ← Rev. 2 →   0 Thank you lgorl for this contest! Good luck to everyone!
 » 5 weeks ago, # |   +18 Hopefully this round lives up to its ID.
 » 5 weeks ago, # |   -6 Good luck to everyone!!
 » 5 weeks ago, # |   +7 IgorI orz
 » 5 weeks ago, # |   0 All the Best !!
 » 5 weeks ago, # |   0 Out of the given 5 or 6, solving how many statements within the 2 hours of the contest would be considered 'reasonable' for a relative novice?
•  » » 5 weeks ago, # ^ |   0 2 on average.
•  » » » 5 weeks ago, # ^ |   0 Lol. Expected a lot of downvotes because of 'Ratism'. Anyway, still a long way to go for me.
•  » » » » 5 weeks ago, # ^ |   0 Good luck. Even solving one problem is enough for a beginner.
•  » » 5 weeks ago, # ^ |   +1 I couldn't solve one for this round :(. It's damn tough.
•  » » » 5 weeks ago, # ^ |   0 I still don't get what was to be done in the second one... Sending the first two primes after 1, each at least d apart from one another, did not always seem to produce the minimum number and checking for every number was a bit too resource intensive.Am curious about the solution...
•  » » » » 5 weeks ago, # ^ |   0 The number has atlest 4 divisors if it's a multiple of 2 primes. The least first prime is $a >= 1 + d$, and second $b >= a + d$. As soon as any number is a multiple of some primes, if we choose only two primes, which are the smallest possible, the result a * b will be the smallest.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, I did just that but weirdly, it was showing 'wrong answer for test case 2'.Eg. outputs of my program:234 -> 114481, 10000 -> 200250077, 1 -> 6, 2 -> 15,Don't know what went wrong...
•  » » » » » » 5 weeks ago, # ^ |   0 Your ansewer for 3 is 28 somewhy. But 2 and 1 is 28 divisors. So, I would assume function findPrime() is not correct
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yes, I did make a mistake. The issue is with this: if(var == 2) {return 2;} Without even checking for the special condition (min. difference of d), I am always returning 2 as one normally would if only whether a number is prime or not was to be checked.A really embarrassing mistake made in the heat of the competition.Thanks for looking into my code.
 » 5 weeks ago, # |   0 Please make short statements for hard problems so we can switch another problem easily if we can't solve
•  » » 5 weeks ago, # ^ |   +8 Short statements are good but I think in contests like ICPC one can struggle if he doesn't have the habit of reading long statements and find the real problem out of it.
 » 5 weeks ago, # |   +22 Am I the only one who don't see English Statements?
•  » » 5 weeks ago, # ^ |   0 sometimes when you open this site , the Russian version is displayed, select the English option in right top corner.
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by IgorI (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Hope to give my best :}
 » 5 weeks ago, # |   +11 I'm just new here..... wish me luck..
•  » » 5 weeks ago, # ^ |   +6 All the best.
 » 5 weeks ago, # |   +7 Hello today i do late comment ..you guys miss me? So i want to say that its been a great journey at codeforces with you all.Such a nice community of coders and mathematicians. Good luck to all div2 participants along with me..lets binge solve tonight wohooo XD
 » 5 weeks ago, # |   +8 Hope this round to be a DIV 2 and not DIV 1.5. All the best everyone!
 » 5 weeks ago, # | ← Rev. 2 →   +123
•  » » 5 weeks ago, # ^ |   0 Thanks for this motivation. My graph has been somewhat like this.
•  » » 5 weeks ago, # ^ |   +33 Unfortunately it's going to be like this for me today...
•  » » » 5 weeks ago, # ^ |   +10 nice graph. Hint for C.
•  » » » 5 weeks ago, # ^ |   0 I think so too(
•  » » » 5 weeks ago, # ^ |   0 same here
•  » » » 5 weeks ago, # ^ |   0 was there only one solution possible for each 'YES' test cases in problem C?
 » 5 weeks ago, # |   0 I am not able to register this contest. It says it is closed. I did't saw register button at the beginning and directly started solving first question. Plz help me out.
•  » » 5 weeks ago, # ^ |   +6 You must register at least 5 minutes before the start of the round
•  » » » 5 weeks ago, # ^ |   +3 Not actually must , for example I missed to register beforehand today . There's something called extra registration which starts ten minutes into the contest , and probably lasts for half an hour .Use that to register if you forget to register beforehand . The only bad little disadvantage is that you cannot submit any solution in the first ten minutes.
 » 5 weeks ago, # |   +28 Problem E's name describe exactly my thought on pretest 2 of E :)
 » 5 weeks ago, # | ← Rev. 2 →   +2 I ruined it. Great Round very good C after a long time ig:/
 » 5 weeks ago, # |   0 Who all fall for the trap in problem B?
•  » » 5 weeks ago, # ^ |   0 Me. I literally skipped it.
•  » » » 5 weeks ago, # ^ |   0 Good question, looked like a tough one but....
•  » » » » 5 weeks ago, # ^ |   0 It's funny one part of my brain says do it but the other half is nah, I'mma skip to C.
•  » » » » 5 weeks ago, # ^ |   +1 CodeForces is expert in publishing problems that seem impossible but actually can be solved with a simple trick.
 » 5 weeks ago, # | ← Rev. 2 →   0 Nice round! Thank you, IgorI!
 » 5 weeks ago, # |   0 some body please tell me about B I was try to find two prime number where first one is greater then or equal to 1+d and second one is a prime number which is greater then first one and difference between two prime number is greater than or equal d but my this process get wrong answer verdict please some one tell me about the approach of B
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 the answer is LCM of 2-th and 3-th primary numbers, and diff between each prime numbers should be >= than d
•  » » » 5 weeks ago, # ^ |   +10 lcm of 2 primes is basically multiplication
•  » » » » 5 weeks ago, # ^ |   0 thanks, I observed this connection but couldn't prove it during the contest
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 lcm of two numbers a and b = (a*b)/gcd(a,b)so lcm of two primes p1 and p2= (p1 * p2) / gcd(p1, p2)obviously the gcd of two distinct primes is 1 since they are relatively prime to each otherlcm = (p1 * p2) / 1= p1 * p2
•  » » » » » » 5 weeks ago, # ^ |   0 It can also be proven directly. A positive integer is a common multiple of primes $p$ and $q$ iff it has both of them as prime factors of which $pq$ is the least.
•  » » 5 weeks ago, # ^ |   +4 find next prime number for 1+d and then next prime number for (previous prime number)+d.
•  » » » 5 weeks ago, # ^ |   0 How can we ensure that it will not cause tle or will exist in range of sieve array ? I know it intuitively but any formal or informal proof ?
•  » » 5 weeks ago, # ^ |   +5 i guess your approach is correct ..you are missing somewhere else i think
•  » » » 5 weeks ago, # ^ |   0 i was find all prime between 1 to 1000000 with sieve method and then start to find my primes is there is the problem my code had faced??or i should find all prime between 1 to 1000000000 ?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 no you didnt find upto that big number..the 1000000 is ok..
•  » » » » » 5 weeks ago, # ^ |   0 i was print multiplication of those two primes
•  » » » » » » 5 weeks ago, # ^ |   0 you dont need to look all the primes so no need for sieve. Just take 1+d, if its prime then ok, if not find next prime from it. then again add 'd' to that number and if that is prime then ok, else find next prime. multiply these two thats the answer.
•  » » » » » » 5 weeks ago, # ^ |   0 You're accessing indexes out of the array bounds for your bool array, set it to n + 1 instead of n.
•  » » » » » 5 weeks ago, # ^ |   0 actually for this, 22000 was enough considering the constraints.
•  » » » » » » 5 weeks ago, # ^ |   0 20011 if you want to be exact about it.
•  » » 5 weeks ago, # ^ |   0 I think that your approach is correct but the calculation of primes takes too much time. For example, your code takes sqrt(100 million) * (100 million / 2) loops just to set multiples of 2 to false. Try the same thing, but with primes up to 50000.
 » 5 weeks ago, # |   0 Is C a graph problem or DSU?
•  » » 5 weeks ago, # ^ |   0 I did brute force , because when we fix the first two numbers , the whole process becomes fixed . I don't know if it will pass system test.
•  » » » 5 weeks ago, # ^ |   0 I thought my solution failed on some edge case where picking wrong maximum for x.
•  » » » 5 weeks ago, # ^ |   0 For what i undestand your solution works in $O(n^3)$, if you notice that in the first two numbers, one of them should be the maximum value of the array, so the complexity become $O(n^2)$
•  » » » » 5 weeks ago, # ^ |   0 Yup , I considered that . But i also used set in c++ to find the biggest number and the other number faster . So mine is $O(n^2logn)$ . Since 2*n was around 2000 i thought it might work .
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 hmmm
•  » » » 5 weeks ago, # ^ |   0 Attempt at a proof. Assume i,j,k to be indices.1) We have to select the maximum number in the array first to create an x [ obvious ] If you don't you cannot exhaust the array as all the maximums you chose must be strictly less than the previous maximums as arr[i]+ arr[j](new max) = arr[k] ( current max), hence arr[j] < arr[k] is an invariant.2) Let's assume that you have multiple combinations of i and j for getting a sum arr[k], let's call them i1,j1 and i2,j2 pairs. If i1 > i2 then j2> i1 hence you cannot select this later per invariant mentioned above. Therefore you can have one possible arrangement of the solution.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 bruh..
•  » » 5 weeks ago, # ^ |   0 greedy+brutoforce (+ multiset)x is always greater than the maximum remaining number; which is a value y; also; x must be equal to y+z; for some z in the remaining values; otherwise; you cannot remove y.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 OK
 » 5 weeks ago, # |   +4 contest not gut!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 » 5 weeks ago, # | ← Rev. 2 →   +1 Very unbalanced problemset, sucks to say it, but it's what it is.
•  » » 5 weeks ago, # ^ |   +59 What's unbalanced about it?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -15 I think he meant gap between B and C
•  » » » » 5 weeks ago, # ^ |   +59 I think $9354 \to 2460$ is a good gap
•  » » » » 5 weeks ago, # ^ |   +29 C and D had the bigger gap imo
 » 5 weeks ago, # |   +16 How to solve D?
•  » » 5 weeks ago, # ^ |   +15 Let dp1[i] means if you only consider the piles in [1,i] and make every piles in [1,i-1] empty, the number of stones in i. Specially, dp1[i] = -1 if you can't make every piles in [1,i-1] empty.Similarly, let dp2[i] means if you only consider the piles in [i,n] and make every piles in [i+1,n] empty......So, not considering the swap opertion, we can see that if for some i, dp1[i]=dp2[i+1]&&dp1[i]!=-1, the answer is YES.For swap operation, just iterate for the position you swap and get the new dp value near the swapped positions, which is O(1).
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 can D be done using prefix and suffix array values?
•  » » » 5 weeks ago, # ^ |   +5 Thanks, it works.
 » 5 weeks ago, # |   +3 Interesting problems! Could D be solved using Segment Trees? I tried but got WA on pretest 2.
 » 5 weeks ago, # |   0 Can I know the approach for div A?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 first char have to be max = 1 store prev char and you have three cases for the rest:prev = 2 -- b[i] == '0' ? '1' : '0'prev = 1 -- b[i] == '0' ? '0' : '1'prev = 0 -- '1'then update prev.
•  » » 5 weeks ago, # ^ |   +6 If you do not have two consecutive digits equal, you get the maximum length number. Going from left to right the first integer, you try to have in d the largest possible number, different from the previous one
 » 5 weeks ago, # |   0 can anyone explain how to solve question 3?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +2 Here comes the key observation. let max(array) = M. M should consist in the first pair. if we don't choose the biggest element, (next 'x') <= M, since all elements are positive, we can't eliminate M since M+1 > x If the first pair is chosen, choosing the rest automatically completes. Let's choose the first pair arbitrary. Eliminate the pair from the array. Then the next 'x' is M. by 1., we should choose the biggest element from the remaining array. But this time we know the sum of the pairs. Now, the pair automatically completes since we know one element and the sum of two elements. After choosing the first pair by brute force, we can complete all the steps in N log N using multiset. The number of possible 'first pair' is N-1. So we can complete the algorithm in O(N^2 log N).
•  » » » 5 weeks ago, # ^ |   0 thanks for explanation
 » 5 weeks ago, # |   +4 How to solve C ?
•  » » 5 weeks ago, # ^ |   +2 Hint: For a particular x you must select two integers where one of them is the max of remaining elements.
•  » » 5 weeks ago, # ^ |   0 X should be >= max(all(ai)), now if you dont choose max(all(ai)) in the first step itself, then you could never choose it because we are choosing elements in a decreasing fashion to satisfy the criteria of selecting maximum everytime. So if you fix any 1 number in the start except the maximum then the whole process is fixed and all you have to do is check if differences of consecutive elements exist and at the end all of them add upto n as there are n maximums to be chosen.
 » 5 weeks ago, # |   0 Apparently multiple people solved C the same way i did, can anyone explain how i got TLE? my code's complexity should be fine...?
 » 5 weeks ago, # |   +1 Stuck on figuring out C for more than 1.5 hrs. Approach anyone?
•  » » 5 weeks ago, # ^ |   0 Its brute force I believe
 » 5 weeks ago, # |   0 What is the intended complexity for C? I think N^2LogN should pass. Or maybe I am calculating it wrongly. Can somebody see? https://pastebin.com/5GypBk22
•  » » 5 weeks ago, # ^ |   0 My solution’s complexity for C was O(N^2). I used a hashmap.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I used OrderedMap so I add the LogN factor. I will try with HashMap.EDIT: It passes with HashMap :/
•  » » » 5 weeks ago, # ^ |   0 Did you use DFS to find out when the no. of child reached N/2 , (basically implemented it brute forcely)
•  » » » » 5 weeks ago, # ^ |   0 Man why to do fucking complicated when normal hashmap O(N*2) solution can be done why to go for such complications dude !!
•  » » » 5 weeks ago, # ^ |   +3 hashmap in worst case if i am correct is $O(n)$ , so isn't that $O(n^3)$
•  » » 5 weeks ago, # ^ |   0 My $O(n^2 log n)$ passed in like 400 ms
 » 5 weeks ago, # |   0 D is amazing, but C... kinda strange problem :/
•  » » 5 weeks ago, # ^ |   +1 How did you solve C
 » 5 weeks ago, # | ← Rev. 2 →   0 For Div2 C, I implemented brute force graphs , but it gave me TLE , its complexity is probably O(T*(N^2)) or O(T*(N^3)) . I am not sure.
•  » » 5 weeks ago, # ^ |   +19 Fun fact:This was div2 only round:)
 » 5 weeks ago, # |   0 How to solve A?? i was trying using string as input but was getting error when i tried to convert the characters into integers for satisfying conditions.
 » 5 weeks ago, # | ← Rev. 2 →   +4 After solving A and C in like 25 minutes , I gave 1.5 hours on B and still I have absolutey no idea how to do it, LOL dont have any maths background ,I am always unable to do these kinds of maths problem.
•  » » 5 weeks ago, # ^ |   +1 how to solve C can u please elaborate your approach thanks in advance !!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Just find the prime numbers upto 10^7 and select the prime numbers at minimum possible distance from d.First divisor = 1Second divisor = (nearest prime number to 1+d)Third divisor = (nearest prime number to Second divisor + d)Fourth Divisor = The number itselfAnswer = Second Divisor * Third Divisor
•  » » » 5 weeks ago, # ^ |   0 10^5 will also work
•  » » » » 5 weeks ago, # ^ |   0 20011 will work.
•  » » » 5 weeks ago, # ^ |   0 This makes sense. How do you know to set the upperbound to 10^7?
•  » » » » 5 weeks ago, # ^ |   0 We need to find 2 primes from [10000 + 1, 2 * 10000 + 1] and [2 * 10000 + 1, 3 * 10000 + 1]. There're multiple ways to check if there's at least 1 in each interval, easiest being searching list of primes on google.Alternatively, an exploratory run of sieve can be done to verify the hypothesis.
•  » » 5 weeks ago, # ^ |   0 You have to just find the product of first two prime numbers such that the difference between (1,p1) and (p1,p2) is atleast d where p1
•  » » 5 weeks ago, # ^ |   +8 Problem B was more logic than maths.
•  » » » 5 weeks ago, # ^ |   +1 How do you separate logic from math?
•  » » 5 weeks ago, # ^ |   0 B was quite easy it just had basic maths of Prime numbers,I wasn't able to solve C :(
 » 5 weeks ago, # |   +8 Thanks for the contest!
 » 5 weeks ago, # |   0 How to solve B?
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 I found C TL to be pretty strict. I'm not sure what the intended is but $O(n^2 \log n)$ in C++ passed comfortably while the same code in Java TLEd.
•  » » 5 weeks ago, # ^ |   0 Same here. It doesn't even go past pretest 2 in Java using TreeMap.
•  » » 5 weeks ago, # ^ |   0 You could avoid the logn factor by using a count array instead of a map(as A[i]<1e6) and after each iteration instead of resetting the entire array you could only reset the values which occurred during that iteration. This solution has a bit more implementation but you would have to worry less about about fst.
•  » » » 5 weeks ago, # ^ |   +16 I can see the $O(n^2)$ solution now. However simply because you can spend extra effort to find a faster solution in order to pass in a certain language doesn't justify the tight TL. Unless if the TL was intended to block log solutions (which it did a bad job of), I think it would've been better to make it looser.
•  » » » » 5 weeks ago, # ^ |   0 Yeah, maybe if n was 2000 it would have blocked even the C++ solutions with extra logn but I'm not sure.
•  » » » 5 weeks ago, # ^ |   0 here is my solution that is nearly equiv to your proposition but it also causes a TLE in java! O(n^2)
 » 5 weeks ago, # |   +6 Some test cases for D that I have caught and resolved 2 8 2 2 2 2 1 3 2 2 7 1 2 3 5 4 6 3 
•  » » 5 weeks ago, # ^ |   0 can you please tell how you resolved it, i'm trying and it's still giving WA on pretest 2.
 » 5 weeks ago, # |   0 Cool contest. I particularly like C, although I wasn't able to solve it in-contest.
 » 5 weeks ago, # |   0 For me figuring out solution for A takes more time than solving B XD...
 » 5 weeks ago, # |   0 Could someone pls tell why my solution TLEd for problem B? https://codeforces.com/contest/1474/submission/104805897
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I didn't read the code carefully, See this comment for the correct answer.
•  » » » 5 weeks ago, # ^ |   0 Why did you use 2e5+5 as the largest possible prime?
•  » » » » 5 weeks ago, # ^ |   0 The first divisor is around $d$ and the second divisor should be around $2d$. 2e5 is just the first number that came to my mind and it's big enough so I used it :)
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 I don't think that is the case. Your code fails because when 'd' is odd, you get and even 'j' and your step size in while loop is 2 so you'll never get out of the while loop. Hence the TLE.https://codeforces.com/contest/1474/submission/104841099This works. I just changed j+=2 with j+=1 and i+=2 with i+=1 (second change not needed AFAIK).
•  » » » » 5 weeks ago, # ^ |   0 I apologize. I just quickly skimmed the code and found that he's checking the prime and got my conclusion.
 » 5 weeks ago, # |   0 Couldn't solve D but loved the problem set and enjoyed a lot.
 » 5 weeks ago, # | ← Rev. 3 →   0 problem A Video Editorial Link : https://www.youtube.com/watch?v=2u6zr-tdEF4
 » 5 weeks ago, # |   0 In Problem B, if d =3 what will be the divisors of the answer ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -11 1 , 5 , 11 , 55
•  » » » 5 weeks ago, # ^ |   0 Why can't it be 28 ? The divisors can be 1,4,7,28 and it's smaller than 55.
•  » » » » 5 weeks ago, # ^ |   +4 all divisors, it's mean 1,2,4,7,14,28. And 2-1=1<3
•  » » » » » 5 weeks ago, # ^ |   0 Oh alright, thanks.
•  » » » » 5 weeks ago, # ^ |   0 You should notice that it contain all divisors,so 28 is 1 2 4 7 14 28,but 2-1 less than 3
•  » » » » 5 weeks ago, # ^ |   0 No, Because as mentioned in the question, two out of any of its divisors should have at least d difference. Here in the case of 28, you can see, that the factors are 1, 2, 4, 7, 14, 28. Here the difference between 1 and 2 is not 3 same as for 2 and 4 have difference 2 instead of 3.
•  » » » » » 5 weeks ago, # ^ |   0 not two every two divisors.
•  » » » » 5 weeks ago, # ^ |   0 I don't know why on earth people have downvoted my message.
 » 5 weeks ago, # |   -38 Probably the simplest solution of C 104805814
 » 5 weeks ago, # | ← Rev. 2 →   +10 I solved problem E 1 minute after contest ended... :(
 » 5 weeks ago, # |   +2 What is the greedy soln to D (if there is ..)? Solely greedy based and no dp ....
•  » » 5 weeks ago, # ^ |   +3 There is n't much dp other than prefix sum calculation.My solution:- if we have to remove all piles lets start from 1st one as it has only one neighbour.so a[0]<=a[1] similarily a[2]>=a[1]-a[0],a[3]>=(a[2]-(a[1]-a[0])) so on.so our problem reduces to finding an array with atmost one swap such that after swap for each position if position is even sum of even indexed number(after swap) >=sum of odd indexed number(after swap).and at final position odd_sum[n-1]=even_sum[n-1] to ensure there is no piles remain at last.Now it is an well known prefix sum implementation problem.If any doubt plz comment.
 » 5 weeks ago, # | ← Rev. 2 →   +7 I am seeing codeforces's upcoming contests list empty for the first time.
 » 5 weeks ago, # | ← Rev. 3 →   +28 I think D was leaked today. Submissions
•  » » 5 weeks ago, # ^ |   +1 Even this looks same, with some added lines to avoid MOSS: Submission104805227
 » 5 weeks ago, # |   +5 Can Someone Pls Explain why my code gives a TLE with complexity O(n^2logn) and some codes with the same complexity pass easily My Submission = https://codeforces.com/contest/1474/submission/104812694Other Submission — https://codeforces.com/contest/1474/submission/104801893Any Help will be appreciated.. I am clueless
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 I believe it because erase(int) will erase all of that number in the set, so then you may erase the begin() of an empty set, which will cause TLE.
•  » » » 5 weeks ago, # ^ |   +5 Thank you so much I was not aware of this STL functionality.
•  » » » 5 weeks ago, # ^ |   0 Hey,Thallium54 I did the correct thing, and my time complexity is right, can you tell me why I am getting a TLE? Submission — 104815636
•  » » 5 weeks ago, # ^ |   +5 You shouldn't do s.erase(a[i]). In this case all a[i] are getting removed while only one should get removed. Now if all elements are same, doing this makes the multiset empty and s.erase()` will give TLE.
•  » » » 5 weeks ago, # ^ |   0 Thank you so much I was not aware of this STL functionality.
 » 5 weeks ago, # |   +50 My 10 months-long fuckups-streak finally broke today. From writing buggy codes, to missing submiting the solutions to difficult problems by a few seconds, many times, and missed reaching the Master as consequences.It all will end today, once the ratings get updated :DThanks for the contest, I'll finally become master today :) :) :)
•  » » 5 weeks ago, # ^ |   -29 Ham kya karein bhai! NO one cares
 » 5 weeks ago, # |   0 Please Ban them!
 » 5 weeks ago, # |   0 in problem B i try to first store all prime number till 2*pow(10,8); my test cases didn't passed but with 2*pow(10,6) it passed.i think according to problem statement the upper limit should be 2*pow(10,8);
 » 5 weeks ago, # |   -27 constructive-adhoc-forces... ... -50 rating ...
 » 5 weeks ago, # |   +28 I misread D ( realized after an hour) and thought you can swap any pair(not necessarily neighboring).Does anyone know how to solve this version?
•  » » 5 weeks ago, # ^ |   0 Same situation... Realized only when 20 minutes left
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   0 Edit: wrong solution.
•  » » » 5 weeks ago, # ^ |   0 I solved D using those two condition but I don't know how to prove they are sufficient. Can you help me out?
•  » » » 5 weeks ago, # ^ |   +48 Hey, I was working on it and I think I found a counter-case.counter-case : n = 8, 3 4 6 4 4 6 4 3This array follows the two condition but it is not a good array. I think the tests were a little weak and I was able to pass through.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thanks. During contest I thought I can prove this by induction. Now I've found a mistake in the proof.
•  » » » » » 5 weeks ago, # ^ |   0 Same here. I thought I had it in the contest. I actually came up with this solution because of the same misreading mistake XD
•  » » » 5 weeks ago, # ^ |   +2 I uphacked your solution ^^
 » 5 weeks ago, # |   +9 Thanks for this contest. I'm very excited that I will reach Master tomorrow morning！
 » 5 weeks ago, # |   0 Video solutions for problem A and B : Problem A Video SolutionProblem B Video Solution
 » 5 weeks ago, # |   0 After a long day a nice C problem. Nice round. Enjoyed!
 » 5 weeks ago, # | ← Rev. 2 →   0 in D i got "NO" for 1 1 3 3 2 1 1 3 3 2, 1 1 3 1 0, 1 1 2 0 0 swap 1 2 1 0 0, 1 1 0 0 0, 0 0 0 0 0 help anyone!!!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Before the start of cleaning, you can select two neighboring piles and swap them
 » 5 weeks ago, # |   0 I think the amount of code in question c is a bit large, maybe it is enough to output yes or no?-
 » 5 weeks ago, # | ← Rev. 3 →   0 My Submissions in the round have been skipped due to coincide with another solution . I don't know how it happened but I'm copying the body of the code as a template form online training I have taken recently and this is a link of a sample of a solution. https://github.com/MohamedAfifii/ProblemSolving--Arabic/blob/master/Solutions/Codeforces/100814I.cppI also copy some algorithms from this training and edit in them and I don't know if this person was talking the same training and is doing something similar but likely it is the case as both of us are Egyptians and the training is Egyptian one and maybe that's why the coincidence has occurred. I'm not cheating from anyone ,I swear it .That's all I want my rating back and your understanding is highly appreciated !
 » 5 weeks ago, # |   0 Can some one tell me what is the difference between g++11 and g++17 that I got WA for my solution for C with g++17 and got accepted with the same code with g++11?!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Maybe undefined behavior?
•  » » 5 weeks ago, # ^ |   +4 I modify your code, and get ac, https://codeforces.ml/contest/1474/submission/104909769 You can compare the differences and think about why. But to be honest, your code style is not flattering. Maybe you should learn a good code style first?
•  » » » 5 weeks ago, # ^ |   0 Thanks for the modification and sorry for the awful coding style :)
 » 5 weeks ago, # |   +10 Does someone happen to know when the next round is going to be? (guess now I'm into cf)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 I can't remember the last time I found the upcoming contest field empty!:(
•  » » 5 weeks ago, # ^ |   0 Not until it appears in the "upcoming contests" section.
 » 5 weeks ago, # |   +12 I am wondering about the reason behind no new upcoming contest. Is it the case that there are no new problems proposals to pick up? Or, it is just a bit of breathing time for the admins since they have been working so hard continuously.
•  » » 5 weeks ago, # ^ |   0 This is a move by MikeMirzayanov to supress cheating.
 » 5 weeks ago, # |   +8 Looking at the empty upcoming contest section , feels sad .
•  » » 5 weeks ago, # ^ |   +4 There is one upcoming AtCoder Beginner Contest this weekend :)
•  » » » 5 weeks ago, # ^ |   +4 Yeah I know there is atcoder round , codechef cookoff etc. But i don't know why codeforces rounds hits me differently :')
•  » » 5 weeks ago, # ^ |   +3 You don't have to be sad anymore! A div3 is scheduled
 » 5 weeks ago, # |   +6 Why there is no upcomming contest ??
•  » » 5 weeks ago, # ^ |   +3 It's there now. Div3 :)
 » 5 weeks ago, # |   +5 Give me a round, or give me death!
•  » » 5 weeks ago, # ^ |   0 RIP .
•  » » » 5 weeks ago, # ^ |   0 There are two upcoming contests as of now, but you may disregard all of them and leave codeforces for good if you like.
 » 5 weeks ago, # |   0 I can't even solve 1st problem in 2 hours :((
 » 5 weeks ago, # |   0 I dont understance why my solution. that uses just arrays and takes only O(n^2) cause a TLE !! Am i force to use c++ instead of Java ?
 » 5 weeks ago, # |   0 problems were good
 » 43 hours ago, # | ← Rev. 2 →   0 B. Different Divisors for input d=381 four divisors should be (1, 1+d, 1+2d, (1+d)*(1+2d)) i.e (1, 382, 763, 291466). So answer should be 291466. but given answer is 294527. I think (1, 1+d, 1+2d, 1+3d) this should 4 divisors instead of (1, p, q, pq) or (1, p, p^2, p^3) please anyone explain this :( Correct me if I am wrong
•  » » 43 hours ago, # ^ |   0
•  » » » 38 hours ago, # ^ |   0 Well, you can't generalize the solution in this case. You are correct the answer in be of the form (1, p, q, pq) where a = pq. Moreover, according to question constraints, p-1>=d, q-p>=d, pq-p>=d. You can read the editorial for the rest of the solution. Your assumption of (1, 1+d, 1+2d, (1+d)*(1+2d)) is wrong because you can't say for sure that 1+d and 1+2d are prime numbers.
•  » » » » 38 hours ago, # ^ |   0 got it :)