Hello, Codeforces!
I'm glad to invite you to Round 643 which will start at May/16/2020 14:35 (Moscow time). Please notice the unusual time.
There will be 6 problems in round, one of them will be interactive. If you are not familiar with interactive problems, you can learn about them here.
Round is based on Team Olympiad in Lipetsk which is being held for the fifth time. Problems were prepared by fake123, iura, Masha237, Villen3tenmerth, Inessa Shujkova (Lipetsk teams' coach) and me. I would like to thank antontrygubO_o for CF round coordination and testers: KAN, I_love_Tanya_Romanova, vepifanov, Merkurev, golikovnik, Ekler and some other people who asked me not to write about them :)
Of course, I'd like to thank all Codeforces team for this beautiful platform!
Scoring distribution will be announced later.
Wish you good luck and high rating!
UPD.1 Scoring distribution: $$$750-750-1250-1500-2000-3000$$$.
UPD.2 Editorial is available here.
UPD.3 Congratulations to winners!
Official participants:
Unofficial participants:
UPD.4 Full problemset from the olympiad is available on gym: The fifth Lipetsk collegiate programming contest. Finals. 8-11 form
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
A bet:
Before Round:
Rated
After Round
Unrated because of technicol issues like round 639
So miserable.
Just joking.
Edit: Why are you downvoting me? I said I was just joking.
I am the type of guy that don't want to hurt peoples.
But really you are the worst joke teller I've ever seen.
Sorry.
Please don't spread this kinda demotivating jokes. Especially it's hurt peoples those works hard to make the round successful.
People are downvoting as using nested spoilers doesn't make it a joke
Thank You MikeMirzayanov, for excellent Codeforces and Polygon platform.
.
When People are being polite but others know how to do it(The downvote). LOL!
Unfortunately, we cant say something like this about the testing servers
is it rated?
IT IS GONNA RATED OR UNRATED DOESN'T MATTER... MY COMMENT GONNA GET DOWNVOTE...i don't know why though.
try changing your profile pic and please stop shouting :)
understood
Excited about the solo div 2 round after a long time.
Is it me or anyone else observed, bulleted list make announcement look bigger!
Yay! Another contest, hopefully I get a positive delta, as I have got a very bad feeling about my rating after how bad my previous contest went :P
it's been long time since we solved last interactive problem
Thank you Code forces Team and all problem setter for this contest frequency in this pandemic time.
Google jam round 2 is just after this round. 4500 participates has qualified for this code jam round and most of them wouldn't prefer to give two contests in a row... So wouldn't it be great if the contest is rescheduled to 18th May? So that more people could participate.
I don't see any problem here. There is almost 30min break between contests, for some people it's even better to solve a few problems before contest. There were a lot of situations with multiply contests in one day.
I am agreeing for some people there performance improves if they solve some problems before a contest but there is also another type of people who prefers a cool mind before a contest.So if the contest is rescheduled, then both type of would get the chance to prepare themselves to the fullest as well as participating in this round...
See the point is, if you are in div 2 and thinking that you are going to be in top 1000 in codejam then you are either lying to yourself or living in world of fantasy or will be some mere coincidence
Maybe you are right, it would super hard for me to be in the top 1000. I am still a beginner, I need to improve myself a lot. If I don't do different types of contest, how would I improve! I would definitely going to aim the top 1000, so that I can do my best and most importantly improve myself!
I will also have to skip this round because of the Code Jam. Get what you are saying. I also perform poorly with 2 contests a day. But I think the unusual starting time is maybe because of the Round 2.
25 minutes not 30 :D
There are 25 minutes between Codeforces Round finishing and GCJ beginning. Of course it's not too much but in my opinion it's not a problem. I also don't think we can reschedule this round to 18th May because it's based on olympiad which is scheduled for 16th May. Some participants can start discussing problems and it will ruin the round.
Oooh... I understood the fact.
I want to thank the author. Hope all the participants can achieve higher rating after this contest, especially me.
and when mike actually considers your request making the contest rated
"Decrease by -100" actually means "increase by 100"
.
Three contests back to back! Thanks for saving us this lockdown
what will i get if i get a succesfull hacking attempt? i mean how will it affect my rating?
You will gain points, like when you solve a problem. So you will be better at standings.
Thank you...But even in Div 3??
In
div.3there's no points/penalty for (un)successful hacks.In
div.2100 points for a successful hack, -50 points for an unsuccessful one.So how about
div.1The same as
div.2
)
Oops, I am lated for the contest. Nevermind, I will try my best solving problems ^^
Can I get 100 downvote?
You got 140 as of now, hehe peoples hands are itching to give down votes.
The starting time is very considerate for the contestants participating in Google Code jam :D
Long time no interactive problem! Look forward to it.
hoping for strong pretests this time
please change your fucking profile picture
edit: thank you!
I need to delete the original comment just to say this. For f*ck sake.
Seriously, Codeforces community has a major problem. Not all of them, but some of them. They keep disliking comments, whether it is good or not. This is not good and need to be changed.There are a lot of nice comments and they are so underrated.
I don't say this just for my comment, but for all negative comments out there.
Recently, arrogant and memes are getting so much upvotes, while others are not.
The underrated comments are having so much downvotes because they are having a movement against the commenter.
So please, vote properly. Every comment is just the commenter's ideas and doesn't deserve to be downvoted.
Again, I don't say this to my comment. But, if you downvote someone that has literally good comments and innocent, you are a loser.
That's all I have to say. Vote properly, or you will make the Codeforces community worse.
STOP BEING RUDE TO PEOPLE.
I tried to be polite, but I need to say this.
Thanks for reading.
a simple advice .. don't take downvotes personally anyone's comment could be downvoted just don't post your meme unless you think it's funny in the previous contest I had no funny memes in my mind so I didn't post anything if I did put some meme that isn't really funny I'll get downvoted as well let your comment adds something new if it doesn't it will look like a noise and will get downvoted probably
Thanks for your advice! It helped me so much...
(hmm... Interesting.)
The comment section of an announcement is supposed to discuss about the round such as time, quality of problems, solution etc. People looks for informative comments here.
Making jokes, sharing meme on same topic and same idea doesn't make any sense. It gets boring. Discussion on irrelevant topic such as contribution, downvotes are also not good topics to discuss in an announcement.
People gives contests here and solve problems so that they need to discuss something here. Don't make it like we need contribution so we solve problems and give contest.
Nahh, As long as the memes are good it's a win-win
But posting same memes or posting memes on same idea again and again is really irritating.
would be my first round as an expert
Don't let it be the last. Good luck
lol
That'd be great if this becomes his last contest as an expert and he becomes a candidate master after it :)
I am new in cp.i don't understand the contest rating system of Codeforces. Plz someone tell me about it.
.
I think Codeforces-Logo needs a Mask of different color as Masks need to be changed after some time !
There's much mystery in this contest announcement:
Well, there's always a reason to it! Thanks for the link!
I wonder why this grandmaster is such a big fan of Tanya Romanova, I wish I knew her.
_**its iftar time in bangladesh. so u need to change the time otherwise contestants will be decreased dramatically. _
Nice, smaller queue!
.
Every time it is on weekday during school days many American high school students can't take part, yet they don't complain every single time it conflicts, and that is many more times than because of iftar. It's not about religion or really even when most people can take round, it's about when problem setter can have round and have semi-consistency with times i.e. being within a few hours of normal time, and no matter the time some people will have conflicts. In other words, just deal with it.
It must be a good contest.
Is it rated? (Let's have -40 likes)
Educational Codeforces Round 87 (Rated for Div. 2) — May 17th (14:35 — 16:35 IST) clashes with Google Kickstart Round C 2020 — May 17th (16:30 — 19:30 IST). If this is a problem for many codeforces participants, please consider rescheduling Educational Codeforces Round 87.
That's great. Consecutive contests for 2 days.
am i the only one who can not spell
Lipetsk(~˘▾˘)~ (~˘▾˘)~Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
My rating has been increasing since 7 contests, hope to continue streak.
I would compare div. 3 and div. 4 peape to paralympians. I hate pupils newbies and specialists. They should give up programming.
first, change your profile picture. It scared me.
second, you need to know that you are still a newbie. you shouldn't say something like that, especially when you are one of them.
He got what he deserves Downvotes :P
Lol this is my alt account, Can you guess? That's why you deserve to be noob...
so be polite to everyone.
You are not a noob for solving contests, but you are a noob at making content.
Sorry for not being nice to you. I need to say this for everyone you hate, including me.
Are you trying to make a record for most downvoted comment?
750 points for problem A. Is it for the first time?
no
While quarantine, time is always usual. Stay home, stay safe, do coding.
This is a friendly time for China.
Interactive?? In this round, Im in the rated ~~ BAAAAAAAAMMMMMMM
When you start to submit problem F...
Submit...
WA on pretest 5.
"WTF!!!"
Is the difficulty level of A and B same ?
bad time
I think A and B will have nearly the same difficulty and A might also be a little harder than usual A problem in the rest Div.2. Just guessing based on the Scoring! Hoping for a great contest!
then D will be easy as compared to other contests
Stop making contests with unusual time please :( many participants have trouble with this new timings, like coincide with university or school online class, Iftar time in Muslim countries, and ... You try hard about one week to make a beautiful contest but you annoy many participants because of the unusual timing(I'm sure you have your reasons for that but I think they aren't enough to change the usual time about 2 hours)
EDIT : Sorry, I didn't know the Google Codejam time :(
First, you don't know about Code jam? It will be starting 25-30 minutes after the contest. It would be annoying to almost every Code jam users that is using both 2 webs if we delay the contest by 2 hours.
Second, if you don't feel fine with unusual time, enjoy your thing with your family, friends, and participate in other contests in the future. Your rating won't change.
If you want, you can give virtual contests a try. I hope it would be good for you :)
Sorry, I didn't know the google Codejam time(Google Codejam is unavailable for Persians because of USA sanctions, so I wasn't aware of that)
Codeforces is the best platform to develop your cp skills. Thank you codeforces.
Good Luck, have a nice day!!
My first contest after Candidate Master.I hope good for me!
Why do I see all the normal comments downvoted?
I see all the normal comments having +1000
Because it's codeforces and not codechef.
The time is friendly to Chinese students!
and MC players in China
HaHaHa！That's right!
The second earliest announced score distribution in Codeforces history !
I love Div.2.
I think you will be Div1 soon.
Registration for educational codeforces started, so we would find masters in educp rated.
sorry-forces everywhere . . .
In problem D, does the subarry have to be consecutive?
Ask through the system inside "Problems" tab, they will answer you
thx
I remember registering for this contest but am not able to make any submissions . the system message says that I haven't registered. where exactly am I going wrong?
maybe you forget
C and D should swap their positions.
so should A and B
idk, i did A in one go but made 1 wrong submission in B, that was the case with a friend too, iterating through the array in reverse after sorting(ascending) seemed to be more intuitive for me, but that was obviously wrong.
If not F, it could easily be an Educational round.
F is so weird
how to solve A.I have know idea after two hours of thinking. Pls help me somebody.
0 will appear some time, you can just simulate the process till a fixed point i.e a = simulate(a) then stop
do you need unsigned long long?
minDigit(a_n) will become 0 rather quickly and then your answer does not change anymore, because 0*x == 0
Video Tutorial for C
Enjoy watching!
Awesome contest!!! During the first 30 min, I was like holy shit!!! none accepted ...which question to try...
How to solve E?
Ternary search
During the contest, I thought of binary search to reduce the solution search space in each iteration(which was wrong), why ternary search works and not binary?
The final value of height = sigma(abs(final-h[i])*constant value) sigma(abs(final-h[i])) is a convex function so ternary search works
https://mirror.codeforces.com/blog/entry/11497
Am I the only one, Who try to consider each one in one of the group. Problem B.
I solved D, but can't prove solution.
I can prove solution in C, but can't solve it :)
How you have solved D? I solved C, but can't D.
https://mirror.codeforces.com/contest/1355/submission/80328985
$$$K = S — 1$$$. There should be no $$$i$$$, that $$$a[i] = 1$$$.
Can u give the proof for A.How can we prove that the solution terminates after some number of steps?
Firstly, $$$1 \leq minD * maxD \leq 81$$$. Secondly, let's notice that $$$0 \leq \frac{a[i+1]}{100} - \frac{a[i]}{100} \leq 1$$$. It means that $$$minD = 0$$$ in $$$a[901].$$$ Therefore, $$$a[901] = a[902] = a[903] = \dots$$$
In D you could make the array like 1 1 1 1 n-1 times and then S-n +1. In this way only possible sums are between S-n+1 to S both inclusive and 0 to n-1 So Just check if the union of both ranges is not 0 to S , as long as its that a K can be found, n<=k<=s-n and s-k would also fall between that same range. So you can't find s-k also.
My solution is easy to prove:
https://mirror.codeforces.com/submissions/Leonardo_Paes
C: "Non-degenerate triangles".
CF users:
Solved C and D but couldn't solve A and B ,I was blank for the fist 30 mins XD
When you will get to know the solution of A, then you will be surprised possibly. I was laughing at myself. peace!!
Specialist rank here I come...
lol I used FFT in C.
Wait what?
I still don't know where FFT is usefull and know even less about what FFT really do, and I destroyed two forests with draft copies, please, save the earth and tell me how to use it xD
The naive solution is like that. Basically, I just create two polynomials X and Y.
X = 0 + ... 1x^(a) + 1x^(a+1) + ... 1x^(b)(everything is zero before a)Y = 0 + ... 1x^(a) + 1x^(b+1) + ... 1x^(c)(everything is zero before b)I multiply the two using FFT in
O(nlogn), then we get polynomial product. We check all terms in the product, and count how manyz(third side) can we build using it.I know there are simpler solutions, but my brain is tired today lol
Your solution link.
If you want to solve it without using FFT. It can be solved easily, by some pref arrays(two). you can see my submission.
Note : x + y > z Hence i made a prefix array for all possible values of z — y.(x > z — y). and then make another prefix array in which, pref2[i] denotes total number ways to obtain sum < i.
so we can simply iterate over all x.
I didn't say there is a need.
No offence, but i am trying to say like this. My intention is not to harm you, but just want to say that, there can be easy way !! sorry, if i offended you.
what FFT means? i solved C by fixing x and finding optimum y and z in o(1) time https://mirror.codeforces.com/contest/1355/submission/80351154
Fast Fourier Transform
Newbie rank here i come...
IF D would be A it would have at least 10000 sucessful submissions. Poor score distrubution
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
I can say that when the writer(s) are writting problem F, they are listening to something interesting...
It's only my opinion, but I found the C waaaay more difficult than the D. It tooks me like one hour to do math and two paper sheets died in the C, and the D tooks me 10 minutes and 1 minute of thinking... or maybe there were some formula that I didn't knew about which would be very helpful for the C ?
Maximum solved doesn't cross even 8000.Hardest round without a doubt.
Problem writer should have boldened this line "It's not necessary to include every explorer in one of the groups: some can stay in the camp" in problem B. Created a lot of trouble for me today.
Same, Like when there these types of conditions, Generally It is written in the Note section.
C and D should be exchanged.! C looked pretty easy at first, but gave a Hard time because of so many corner cases!
Tbh the contest is really good. Regardless the hard C.
I found C rather easy to think but troublesome to implement. Had to think exhaustively forthe edge cases and ultimately that took more than an hour in the end. Let's hope it doesn't fail the system tests :)
I can't understand why am I getting a TLE if the code was submitted in C whilst the same code being submitted in CPP gives me AC.
My code : https://mirror.codeforces.com/contest/1355/submission/80368483
RIP codejam
If the problems are meant to be in the increasing order of their difficulty then the setters should strictly follow it.
Irritating A. I could not think of any logic, then I just wrote recursion, and surprisingly it was terminating to a single value every time. Can anyone explain why it settles on one value. Is it not possible for minimum digit to be never zero. And for the fact that C was much harder than D it should have more points.
Maybe it's possible for the last digit to never be zero, but since the number increases by at most 81 every time (in the absolute worst case), the third last digit can't skip over zero, and since in each iteration (before any digit becomes zero) the number increases by at least 1, it will take less than 100 iterations.
Note that the maximum term that can be added ever to a(i) is 81. We start from a[1] and keep adding terms to obtain new a's. Now as soon as the thousands place changes (i.e. increases by 1), the corresponding hundreds place will always be 0. This will obviously take less than 1000 steps.
Thanks finally understood what you are trying to say. if a number less than 1000 (let's take 987), if it crosses 1000, than 100th place has to be zero because we can add maximum up to 81. In this case a(i+1) = 1050 (987 + 7 * 9).
That's right.
ahhh shit, starting from C was bad strategy mehn
How to solve E? Is it 3-point search?
Yes, Ternary Search
Thx bro.I must have made some stupid mistakes QwQ
Solved A, B and D, but all of them just a guess. Would not be suprised to fail all three of them in system testing.
Difficulty level : A>B && C>D .. Not sorted and even I can not solve A but solved D .
for A, key observation is when min_digit = 0 then next numbers will be equal
Constructive Forces!
it's good.. constructive algo help us build strong observations and logic
Ya Truely Said!
Why problem E satisfy binary search?
ternary search
I solved it using binary search on the answer.
The graph of the cost vs height would be a parabola. So the only thing monotonic is the slope.
So find the cost of building walls of height mid and then also find the cost of mid+1 and mid-1.
this would give you a fair idea as to where the slope is negative.
The binary search conditions would be:
and always keep updating the answer as minimum of previous answer and val(mid)
Link to my code
The pretests for Problem D were weak. Solutions only considering K, not S-K were passed. They should have included test case like
I solved C.
I guessed A,B and D.
Pro Guesser! Gawd
How to prove that choose k=1 and a[i]=2(except the last one) in D is the optimum solution? I attempted to prove it in the contest but failed. Wasted a lot of time...
I wasted one hour on C, and still wasn't able to do it. Could have easily done D in that time. Waiting for the C problem editorial.
Editorial is published? Why are you waiting?
A think more code less round. I like this although i can't complete thinking of C in time.
In problem D, can the selected array contain 0?
Nah. Positive integers its integers >= 1. Non negative integers its integers >= 0.
I see, Didn't know that. I thought positive integers include 0. Thanks.
No, as described in the statement "positive integers".
No we can only take positive numbers in array not non negative numbers.Though even if you have confused it with we can choose k=0 then the other player can always find S-k=S by taking the whole array
what if we take (n-1) 0s and 1 S and take k = n/2?
Yes that would have been possible if you could take 0 but since we can only take positive numbers it is not a suitable answer.
yeah yeah got that, thanks
Can anyone please tell me why this submission for problem A got TLE? https://mirror.codeforces.com/contest/1355/submission/80313479 Similar solutions got ac.I don't know why!
Does this cast work as expected?
l = min(l, (int)n%10);If it casts n instead of the remainder it would fail.
Thanks man! Ya, it casts n.
My bad, I thought of something else
It is possible to get negative reminder, when n = 2^31, your cast will return -2^31.
How about we have strong pretests once in a while? D had >= 21 pretests, so I thought my logic was solid and I should not waste my time on thinking over it, and now I got it failed at test 24. Amazing.
Does anyone know why my solution for B got TLE https://mirror.codeforces.com/contest/1355/submission/80331871? I can see that other similar solutions submitted with PyPy2 got accepted.
Use fast input/output. Did the same mistake :(
Do you have an example of fast input/output?
codeforces setters be like
I wonder what is this pretest 24 of D many people are failing on it
The pretests of F are extremely "strong". :)
Almost 70% of the pretest-passed submissions to Problem F failed on system tests... What a scary ratio...
I got a WA on test case 5 of Prob C. When I ran the same test case on the same code in my system, I got the right answer. Can somebody tell me when does such a situation arise? I had used the same logic as given in the Editorial.
Link the submission here, somebody will tell you why it fails.
BADC
Find the minimum number of swaps to sort the contest. Still a good contest..Thanks for efforts :)
BADC == BAD C? :"D
It was all there in plain sight...
C and D should swap their position
When does rating gets updated?
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!
Can someone pls explain me the 1st question ie Sequence with Digits of today's contest,I have seen the editorial ,but then also I am not getting the thought process behind the sol of other people. I would be so thankful if any body can help me
Have you understood the problem? If yes then just implement it straight forward. Just keep in mind that once you get 0 as min digit then the no will never change. So you can break when you get 0 as min digit.
The fact is proof of solution that it will not exceed tl and overflow 64bit integer.
As min*max can be atmost 81 so you can't add more than 1000 as one of the digit will be 0 by this time.
Does anyone have a faster solution on E
@DishonoredRighteous It says TLE for O(n) solution in Pypy 3 after system testing, same code works in Python 3. Can you please check the time limits. Thanks
Problem B
There are many solutions that didn't pass TL on Python. It's hard to read $$$5 \cdot 10^5$$$ numbers in Python.
So, will there be any changes in the time limit or shall we just take it as a lesson? :p
It's a well known fact that Python is not very fast :) So there won't be any changes. What is more, there are some solutions on C++ that din't use fast IO and got TLE too. I think participants should know about their language's qualities.
Is there any reason for rolling back the ratings?? Please let us know if you know. Thank you
I don't now. Probably MikeMirzayanov is deleting cheaters now and he rolled back the ratings.
Ok, thanks for replying :HappyEmoji:
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
Hello, I don't know why my solutions are giving TLE on Test Case 22 for Problem D. Can someone please help?
Solution 1
Solution 2 — this was taken from Ashish Gupta's C++ solution. I just wanted to check whether it is being accepted in my case or not. But its the same story.
May be
System.out.println()is not enough fastAah. That's weird. Never came across with 'sopl' having any problem w.r.t time limit before.
I think problem E is so easy and I solve first 5 problems in only one hour while I only can solve less than 4 pronlems in others div2 rounds...
I can't believe it is div2(and thank for +83 lol).
Wrote in wrong competition :)
Нужно просто делать cout команд.
why set is slower than map in STL?
For 643 div2-B, the same algorithm with set TLE (test #26) but map AC.
set code:
map code:
Your set code seems to have a excessively common problem: the line
memset(cnt, 0, sizeof(cnt));dominates the running time for tests where there are very many small test cases, as it clears the whole array every time.