Hi, Codeforces!
Я рад пригласить Вас на Codeforces Round #696, который состоится во 19.01.2021 17:35 (Московское время). Раунд будет рейтинговым для всех участников с рейтингом меньше $$$2100$$$. Участники из первого дивизиона могут принять участие вне конкурса.
Вам будет предложено $$$6$$$ задач на $$$2$$$ часа. Все задачи раунда придуманы мной. Спасибо adedalic за замечательную координацию раунда и MikeMirzayanov за системы Codeforces и Polygon.
Также благодарю тестеров awoo, errorgorn, RetiredPlayer, kalki411, AmShZ, IaMaNanBord, Osama_Alkhodairy, Prakash11, HIS_GRACE, Gauravvv, Dragnoid99 за тестирование раунда и полезные комментарии к задачам.
Разбалловка: $$$500-1000-1500-2000-2250-3000$$$.
Всем удачи!
UPD: Разбор
UPD: Поздравляем победителей!
Обоих дивизионов:
Второго дивизиона:
Удачи участникам! — Участник
I have a naive question: Why setters take too much time on selecting the scoring distribution?
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.
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.
Procrastination
As a tester, Monogon is back for contribution. XD
...
Let's make Monogon rank 1 again!
I miss the old Monogon :D
and we all know that old is gold
Who are you?
Good Luck Participants! — a participant
you too :3
When you see some common testers and started thinking how can this be a coincidence?
As a tester I feel bad that you didn't tag me :-(
As a future participant I feel bad that you didn't help me being one of the tester :P
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 :-).
it's a trap!
this set is nice :3
we should be thankful to HIS_GRACE for testing this round
https://codeforces.me/blog/entry/8681
hope it be a good contest and yall good ratings
Problems are very interesting! Good Luck!
I wish the Problems have some bold words. Guess that serves me right for trying too hard to speedsolve.
I wish the formal statement should be in bold.
I wish the Verdict should be in bold.
I wish my performance will be bold.
Hoping that my performance will be at least same as my previous performance in your contest.
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 :).
At least he is enjoying what he is doing without worrying much about ratings.
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.
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!
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/
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.
itiswhatitizChiyu_0_O 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.
Please don't compare 5 stars on codechef with candidate master on codeforces.
It's actually Expert in Codeforces
viwreck U know the feeling right,I just wanted to let itiswhatitizChiyu_0_O 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)/
I was wondering how they choose the testers , is it a complicated proccess?!
You just need to connect with author or coordinator to test the round.
Hoping for shorter problem descriptions just like the announcement.
As a tester, I request some contribution.
What was that, and who are you? :D
To all you downvoting — do you realize that this was in response to the first revision of the comment?
It's just me or someone also felt that Codeforces rounds per month, are less nowadays?
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...
Or maybe, because there are lesser contest proposals these days.
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!
As a tester, I can confirm that the problems are awesome and you guys will enjoy the contest.
Good luck on nullifying ur negative contribution( https://codeforces.me/blog/entry/86882?#comment-749682 ).
and you saying that got him contribution. People love proving people wrong lol
:(
As a participant, I wish the same.
Wish you all luck ^^
❤❤
Great round id
Since this is a palindromic round ( 696 ). Hoping to see one question on Palindrome :D
anyone waiting for round #700?
anyone waiting for round #700?
Learn to stay in the present.
I will try to solve solve A,B,C. Good Luck Every One, Keep Practicing and keep shining.
поставь + пж
Thank you lgorl for this contest! Good luck to everyone!
Hopefully this round lives up to its ID.
Good luck to everyone!!
IgorI orz
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?
I couldn't solve one for this round :(. It's damn tough.
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...
The number has atlest 4 divisors if it's a multiple of 2 primes. The least first prime is $$$a \gt = 1 + d$$$, and second $$$b \gt = 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.
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...
Your ansewer for 3 is 28 somewhy. But 2 and 1 is 28's divisors. So, I would assume function findPrime() is not correct
Please make short statements for hard problems so we can switch another problem easily if we can't solve
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.
Hope a good result for all
Am I the only one who don't see English Statements?
sometimes when you open this site , the Russian version is displayed, select the English option in right top corner.
Auto comment: topic has been updated by IgorI (previous revision, new revision, compare).
I'm just new here..... wish me luck..
All the best.
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
Hope this round to be a DIV 2 and not DIV 1.5. All the best everyone!
Thanks for this motivation. My graph has been somewhat like this.
Unfortunately it's going to be like this for me today...
nice graph. Hint for C.
I think so too(
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.
You must register at least 5 minutes before the start of the round
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.
че за говно?
Please? doing this contest unrated
Problem E's name describe exactly my thought on pretest 2 of E :)
I ruined it. Great Round very good C after a long time ig:/
Who all fall for the trap in problem B?
Me. I literally skipped it.
Good question, looked like a tough one but....
CodeForces is expert in publishing problems that seem impossible but actually can be solved with a simple trick.
Nice round! Thank you, IgorI!
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
the answer is LCM of 2-th and 3-th primary numbers, and diff between each prime numbers should be >= than d
lcm of 2 primes is basically multiplication
thanks, I observed this connection but couldn't prove it during the contest
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 other
$$$lcm = (p1 * p2) / 1$$$
$$$= p1 * p2$$$
find next prime number for 1+d and then next prime number for (previous prime number)+d.
i guess your approach is correct ..you are missing somewhere else i think
Is C a graph problem or DSU?
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.
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)$$$
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 .
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.
contest not gut!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Very unbalanced problemset, sucks to say it, but it's what it is.
What's unbalanced about it?
I think he meant gap between B and C
I think $$$9354 \to 2460$$$ is a good gap
C and D had the bigger gap imo
How to solve D?
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).
can D be done using prefix and suffix array values?
Thanks, it works.
Interesting problems! Could D be solved using Segment Trees? I tried but got WA on pretest 2.
Can I know the approach for div A?
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
can anyone explain how to solve question 3?
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).
что то на пендосском
How to solve C ?
Hint: For a particular x you must select two integers where one of them is the max of remaining elements.
Apparently multiple people solved C the same way i did, can anyone explain how i got TLE? my code's complexity should be fine...?
Stuck on figuring out C for more than 1.5 hrs. Approach anyone?
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
My solution’s complexity for C was O(N^2). I used a hashmap.
I used OrderedMap so I add the LogN factor. I will try with HashMap.
EDIT: It passes with HashMap :/
Did you use DFS to find out when the no. of child reached N/2 , (basically implemented it brute forcely)
hashmap in worst case if i am correct is $$$O(n)$$$ , so isn't that $$$O(n^3)$$$
My $$$O(n^2 log n)$$$ passed in like 400 ms
D is amazing, but C... kinda strange problem :/
How did you solve C
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.
Fun fact:This was div2 only round:)
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.
how to solve C can u please elaborate your approach thanks in advance !!
Just find the prime numbers upto 10^7 and select the prime numbers at minimum possible distance from d.
First divisor = 1
Second divisor = (nearest prime number to 1+d)
Third divisor = (nearest prime number to Second divisor + d)
Fourth Divisor = The number itself
Answer = Second Divisor * Third Divisor
10^5 will also work
This makes sense. How do you know to set the upperbound to 10^7?
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.
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<p2.
Problem B was more logic than maths.
How do you separate logic from math?
Thanks for the contest!
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.
Same here. It doesn't even go past pretest 2 in Java using TreeMap.
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.
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.
Yeah, maybe if n was 2000 it would have blocked even the C++ solutions with extra logn but I'm not sure.
Some test cases for D that I have caught and resolved
can you please tell how you resolved it, i'm trying and it's still giving WA on pretest 2.
Cool contest. I particularly like C, although I wasn't able to solve it in-contest.
Could someone pls tell why my solution TLEd for problem B? https://codeforces.me/contest/1474/submission/104805897
I didn't read the code carefully, See this comment for the correct answer.
Why did you use 2e5+5 as the largest possible prime?
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 :)
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.me/contest/1474/submission/104841099
This works. I just changed j+=2 with j+=1 and i+=2 with i+=1 (second change not needed AFAIK).
I apologize. I just quickly skimmed the code and found that he's checking the prime and got my conclusion.
Couldn't solve D but loved the problems.
Couldn't solve D but loved the problem set and enjoyed a lot.
In Problem B, if d =3 what will be the divisors of the answer ?
1 , 5 , 11 , 55
Why can't it be 28 ? The divisors can be 1,4,7,28 and it's smaller than 55.
all divisors, it's mean 1,2,4,7,14,28. And 2-1=1<3
Oh alright, thanks.
Probably the simplest solution of C 104805814
I solved problem E 1 minute after contest ended... :(
What is the greedy soln to D (if there is ..)? Solely greedy based and no dp ....
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.
I am seeing codeforces's upcoming contests list empty for the first time.
I think D was leaked today.
104795039
104793591
104802409
Even this looks same, with some added lines to avoid MOSS:
104805227
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.me/contest/1474/submission/104812694
Other Submission — https://codeforces.me/contest/1474/submission/104801893
Any Help will be appreciated.. I am clueless
I believe it because
erase(int)will erase all of that number in the set, so then you may erase thebegin()of an empty set, which will cause TLE.Thank you so much I was not aware of this STL functionality.
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
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 ands.erase()will give TLE.Thank you so much I was not aware of this STL functionality.
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 :D
Thanks for the contest, I'll finally become master today :) :) :)
Ham kya karein bhai! NO one cares
constructive-adhoc-forces... ... -50 rating ...
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?
Same situation... Realized only when 20 minutes left
Edit: wrong solution.
I solved D using those two condition but I don't know how to prove they are sufficient. Can you help me out?
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 3
This 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.
Thanks. During contest I thought I can prove this by induction. Now I've found a mistake in the proof.
Same here. I thought I had it in the contest. I actually came up with this solution because of the same misreading mistake XD
I uphacked your solution ^^
Thanks for this contest. I'm very excited that I will reach Master tomorrow morning！
.
Before the start of cleaning, you can select two neighboring piles and swap them
I think the amount of code in question c is a bit large, maybe it is enough to output yes or no?-
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?!
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?
Does someone happen to know when the next round is going to be? (guess now I'm into cf)
I can't remember the last time I found the upcoming contest field empty!:(
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.
This is a move by MikeMirzayanov to supress cheating.
Looking at the empty upcoming contest section , feels sad .
There is one upcoming AtCoder Beginner Contest this weekend :)
Yeah I know there is atcoder round , codechef cookoff etc. But i don't know why codeforces rounds hits me differently :')
You don't have to be sad anymore! A div3 is scheduled
Why there is no upcomming contest ??
It's there now. Div3 :)
Give me a round, or give me death!
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
Dragnoid99
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.