Hi fellow Coders!
AntiBsayer, Salem_Alwarawreh and I are glad to invite you to take part in Codeforces Round 699 (Div. 2), which will take place on Feb/05/2021 17:35 (Moscow time). Round will be rated for participants with rating less than 2100. Participants from the first division are also welcomed to take part out of competition.
You will be given 2 hours to solve 6 problems, each problem has a picture and a story above it. The stories are skippable if you want to focus on the real problems.
We would also like to thank:
- adedalic for the coordination and discussion of this round!
- Motarack, namanbansal013, Jellyman102, stack_overflows, manik.jain, morzer and _HossamYehia_ for phase one testing and valuable feedback.
- kclee2172, awoo, karavaiev, SlavicG, low_, kalki411, HIS_GRACE and nvmdava for phase two testing and incredible feedback.
- My friend Khaled for drawing pictures for all the problems to make them more colorful.
- Last but not least MikeMirzayanov for great Codeforces and Polygon!
Score distribution will be announced before the start of the round, hopefully.
We hope you like the problems and enjoy solving them!
UPD: Scoring is 500 — 750 — 1500 — 2000 — 2500 — 3000
UPD: Editorial
UPD: Congratulations to the winners
Div1 :
Div2 :
Thank you all for participating!
Finally an expert in problem setting :)
I don't know what's wrong with your comment. You mentioned a rare fact and some people just demotivated you. A couple of contests before I wrote a fact that if code is not optimized then it shouldn't pass pretest and I got negative contributions for saying that. And a red coder just puts a dot and he gets a 100 contribution. This is what it is now.
yes bro I am also wondering why I am getting too much downvotes :(
Codeforces is a huge competitive programming community. People expect some worth in reading comments. Useful comments may get hidden by "not so useful" comments/facts like yours. So in my opinion, we should comment only if it's highly necessary.
No one expects anything useful in comments before the contest.
1-gon usually just puts a dot, and he ridiculously got first in contributions, while Errichto did hundreds of explanatory comments and helped a lot of people, and he really deserves his place.
You are right! Many new coders like me hesitate to ask something in the comments as maybe it is very trivial and easy for some people and could lead to a downvote! (I don't want to have negative contributions!) [ Please don't downvote on this comment :) ]
Why are you afraid of negative contribution? It means nothing. Contribution points are not intended to scare you off from seeking help from the community.
And about the thing u said about red coders is not always true. example: http://mirror.codeforces.com/blog/entry/86048?#comment-738203
I haven't said always... And about the worth reading part, see below u will find it's not always about knowledge sharing or "highly useful" comments. You should have checked this comment section below first before replying. You should have.
I knew that you are gonna point to HealthyUG's comment. XD
But why do you care about contributions? Is it worth having +100 contributions( What you would do with those contributions trade them with money? ), rather we are here for CP and most importantly to enjoying solving problems.
No, I cared once but not anymore. I thought people with more contribution points are providing something that others aren't. So I even tried following someone like Errichto.
See there is a difference between doing something for contribution and getting contribution for what you did.
As a non tester, I just commented to make SlavicG's comment appear further down.
As a tester, :(
P.S: Amazing Round! Recommending everyone to participate!
sure :)
Sure!!!
Jordanian round ❤
That's real.
omg meet you huh.
Howevr F is too hard...
Kevin090228 became Master at the age of 11!
stO Kevin090228 Orz
WTF! mind blown. There's crazy talent on this site Lol. I'm a decade older than he is. gj Kevin.
Yeah.I'm a year older than him but he is much stronger than me.
Wow, good job to you too, keep it up! An advice I'll give is, if you'd like, try and build some projects too with your skills.
I do wish I had started programming a bit earlier, not that I'd have been as good as you guys, but that would have been fun. I started in college.
Above all, keep having fun, even if you don't like building any projects.
How to solve A? :)
I don't even want to see what that dog looks like.
Your memes are great.
Me on problem B: Got WA on pretest 2 :(
how to solve problem B
If one boulder falls into the collection system,the ones after it will end up in the same place.
We can simulate the boulders' actions until one falls into the collection system.Then we can simply output -1.
If no boulders fall into the collection system,we can just output the result of the last boulder.
There will be at most 100n boulders that end up on a mountain,So this is an $$$O(100n)$$$ solution.
Absolutely your are true.
then comes me How to solve B?
wrong test
How to solve C :<
Thank U AntiBsayer, Warawreh & Salem_Alwarawreh so much for setting problems on this round, I am sure the problems are gonna be so much fun to think of, also to solve ^^ Can't wait to participate!
Jordanian round ❤
Even though final exams, we don't have contest prepared by our neighbors everyday.
Jordanian round ❤
As a participant, I thank Khaled for drawing pictures for all the problems.
Looking forward to the colorful pictures!
Thanks for the stories and also making them skippable. They are really fun to read, but only when the contest is over :D
We definitely need more picture problems :) Also, please lesser of these
It's a joyful thing to me to see Arabic round again. Hope our contribution in problem solving community keep it's progress and see more Arabic rounds in the future.
I am realy intersted to praticipate in your round ,thank you guys.
I wonder who's gonna read all those interesting stories?
Div. 1 participants)
It feels so good having a contest in your birthday when you're lifeless and have nothing to do.
My Pledge for round #699: I will solve at least Three problems! And then declare the Fourth great Ninja War!
No Worries AntiBsayer will be there to end the war once kaguya finishes you :)
We hope you like the problems and enjoy solving them!How to enjoy when one is not able to solve them? reading stories xd?
The more you think about your delta, the less interesting the round becomes.
Play your favorite song before the contest, have a sportsman spirit, and try your best not to think about failure/success during the competition.
Have fun solving problems :D
Playing my favourite song before the contest actually worked in my last contest!!
Doesn't it gives earworm sometimes ? It ruins the concentration .
Not during the contest but before the contest!
You are right, though I can't remember having this issue. It seems like for me, the problems are too interesting to be distracted from :)
As a tester, I recommend enjoying problems!
AntiBsayer == Thanks :D
yo how can u add one to a letter, this would runtime error.
each character has a unique ASCII code where The 'S' ASCII code is 83 and the 'T' ASCII code is 84 So char('S'+1)=='T'.
I guess c++ is weird.
You came to the wrong place saying this. :)
Best comment seen in a while... eugalt
thanks for the skippable stories :hearts:
Pictorial explaination of all the problems, nice !! It seems an interesting round.
As a tester, I wish everyone good luck!
Downvote this comment for ancient goodluck curse !
Irrelevant
As a participant, I'm happy with the frequency of the contests! ;)
Hope it will be a good round
What's the point of stories in problems if they are skippable? Like tourist mentioned in one of his streams, the stories must sync in with the problems themselves, similar to like Google Codejam's problems. Otherwise, why not just remove stories altogether for the problems that do not require such?
In any case, hopefully, the contest will be enjoyable.
It has happened where the story and the statement do sync up, but the authors just choose to separate it to make it easier for participants. They separate the informal statement and the formal one, so participants can choose whether they want to read it or not. I personally like this choice, because it makes the problems more enjoyable for the participants (and the authors to write), without getting in the way of the actual problem solving if the participant doesn't actually want to read it.
.
Нужно переносить раунд. В 17:30 по мск начинается стрим папича по шреку!!!
Hello.
Go to your profile's blog, and create a new blog in the corner .
Tonight I can write the saddest lines.
Write, for example, “The night is starry and the blue stars shiver in the distance.”
The night wind revolves in the sky and sings.
Tonight I can write the saddest lines. I loved her, and sometimes she loved me too.
Through nights like this one I held her in my arms. I kissed her again and again under the endless sky.
She loved me sometimes, and I loved her too. How could one not have loved her great still eyes.
Tonight I can write the saddest lines. To think that I do not have her. To feel that I have lost her.
To hear the immense night, still more immense without her. And the verse falls to the soul like dew to the pasture.
What does it matter that my love could not keep her. The night is starry and she is not with me.
This is all. In the distance someone is singing. In the distance. My soul is not satisfied that it has lost her.
My sight tries to find her as though to bring her closer. My heart looks for her, and she is not with me.
The same night whitening the same trees. We, of that time, are no longer the same.
I no longer love her, that’s certain, but how I loved her. My voice tried to find the wind to touch her hearing.
Another’s. She will be another’s. As she was before my kisses. Her voice, her bright body. Her infinite eyes.
I no longer love her, that’s certain, but maybe I love her. Love is so short, forgetting is so long.
Because through nights like this one I held her in my arms my soul is not satisfied that it has lost her.
Though this be the last pain that she makes me suffer and these the last verses that I write for her.
Me but for orange rating.
The contests are very rewarding I will be participating in the upcoming contests.
Yeah, a nice contest. What is your age
Hope to be Master
Shanks, Salem_Alwarawreh and Warawreh thankyou to all of you for another contest.
Expecting the problems difficulty order to A<B<C rather than (A or B)<C<(B or A).
And Shorter queues as well..
All the best to everyone participating in the contest.
If existing muti-solve in problemC, just output a random one?
Any valid answer is ok.
Hello who can point me to a good tutorial covering graphs topic?
Go for Competitive Programmer's Hand book by antti laaksonen. There graphs are explained very well. the you can simply try for simple problems.
Tasks was interesting. Thank you
Why are C's and D's implementations so dirty?
don't know about C, but D wasn't implementation heavy.
C wasn't too.
I agree
C wasn't dirty, but it was confusing... I couldn't find error in my code... :sob:
How to solve D?
For odd $$$m$$$, we can see that any sequence of the form $$$i, j, i, \ldots$$$ is valid as it will either be something like $$$ab \ldots ba$$$ or $$$a \ldots a$$$.
For even, lets notice that a sufficient condition for the answer to exist is at least one of the following two conditions:
A node pair of nodes $$$x, y$$$ such that $$$x \rightarrow y$$$ and $$$y \rightarrow x$$$ are coloured similarly (the sequence will be of the form $$$a \ldots a$$$ or $$$b \ldots b$$$)
A node $$$x$$$ such that it has an edge $$$i \rightarrow x$$$ into it and an edge $$$x \rightarrow j$$$ out of it with the same colour, then $$$j \rightarrow x$$$ and $$$x \rightarrow i$$$ will have the opposite colour (or condition 1 will hold). So we can just generate a sequence of the form $$$aa(bbaa)*$$$ or $$$(abba)*$$$ as needed to satisfy $$$m \mod 4 = 2$$$ or $$$m \mod 4 = 0$$$ respectively.
Clearly if neither of these conditions hold, any sequence generated will be of the form $$$abab\ldots$$$ or $$$baba\ldots$$$, so it is necessary as well.
While unneeded, it can also be shown that this condition will always exist for a complete graph of $$$3$$$ or more nodes.
Out of curiosity, is there something wrong with this proof for general graphs or is problem D just a complete graph for the sake of elegance? I think this find the answer if it exists for any arbitrary graph given that both directions exist for each edge in $$$O(n + m)$$$.
How to solve D?
Case working. 1. if m%2 = 1, it is possible.(1, 2, 1, 2, ..) 2. if i -> j = j -> i, it is possible (i, j, i, j, ..) 3. if n = 2 and m is even, it is impossible 4. if n >= 3 and m is even, it is always possible. It needs only 3 vertices
I can see how the implementation for D could be tricky, but C's implementation seems fine, the core part of the logic could be coded in 20-30 lines using an array of vectors.
In D, is ans always possible except for the case when n=2 and m%2=0?
Yes.
2 WA submissions on C for writing n instead of m and half an hour to find this bug that feels like shit especially I fu**ed in B
(dying sad dog picture)How to solve B?
brute force
After some boulders are thrown , the heights of mountain will become such that no case of hi<h(i+1) exists and then the boulder will always roll to the end, so we can find which ends first, k or no case of hi<h(i+1) and print the answer. Since heights are <=100 and n<=100 , it can be done with brute force.
that's what I did I'm really pissed off I have no idea why it's WA
Same bro I keep getting WA on test 2
Bro You know more than me, but I think your code is computing the total need element to level from right to left on every term smaller than the next one. But you have to give the solution as sequence way for eg: 10 7 1 1 1 1 1 1 1 1 1 3 your code will give 6(for 9 k-2, for 8 k-2,for 7 k-2 and for 6 k-2) now k=-1; but the answer is 3(for 9 k--,for 8 k--,for 7 k--,for 6 k--,for 5 k--,..,for 3 k--) now k=0; it your code you can change a[0]=INT_MAX; and make it 1 based index then,
in the while loop and since the constraint are 100 ans 100 it will not give tle. Hope it make some sense.
As heights are less than or equal to 100 in the worst case (1,1,1..100) after throwing around 10000 stones all remaining stones will fall into waste system. So if k is greater than 10^4 answer is no else just brute force.
idk about the limit when the answer will always be "NO" . I was too lazy to find out so i just break my loop when my counter reached 10^4.
use 2 pointer
Simple simulation.
One fact to know is that once an boulder falls into the collection system,the ones after it will also do that.
How to solve E?
Use DP.
https://mirror.codeforces.com/contest/1481/submission/106600288
Can someone give a test-case for which my code fails for problem C WA_CODE
did u check if the map was empty at last?
This is invalid input. See a fixed input in a comment below.
Try this:
The only possibility is to assign both painters to the first plank.
https://mirror.codeforces.com/contest/1481/submission/106594191
Can you tell me a test case for which my code fails?
This is invalid input. See a fixed input in a comment below.
Try this instead:
Both painters should have chosen the second plank.
Anyways i figured out bug in my code due to this test case and got AC.
Thanks
Is this a valid test case? Cause $$$ 1 \le c_j \le n $$$
Right, I missed that restriction.
How about this instead
A great and well balanced problem-set. Also, C was a nice question, although it took me an hour to implement it and fix bugs :(.
I think who passed the first test case of the c problem he must pass all pretests
No. I pass the first test case and wrong in test case 2 :D
Same, my logic seems fine tho. Probably a stupid bug im missing
Is that the case because if pretest are weak many people's solution will fail on real test in these implementation heavy questions
The NOs in pretest 1 can be identified with just observing whether the color of the last painter appear in the required array. This is insufficient alone.
Pretest one does not cover the possibility that there is not enough painters to paint all fences to the required color.
For me, I still have not identified all the cases where it is a NO. I return NO if my own checker finds a fault in my constructive solution. This passed the pretests.
I have codeforces account and wanted to participate in above contest. But I haven't registered for it. Why CodeForces don't allow to participate unregistered coders like me in Contest.
According to rules:
If you are late to register in 5 minutes before the start, you can register later during the extra registration. Extra registration opens 10 minutes after the contest starts and lasts 20 minutes.B turned out to be a bluff
I was so close on solving D just did not have had the time... You just had to notice that when there is no such pair that edge[i][j] = edge[j][i] and when m%2 != 1 (which are the 2 conditions that one can solve very easily with constructive solutions) then you could see that if you had 3 vertices again a constructive solution is possible.
can you tell me what is wrong with this submission for problem C https://mirror.codeforces.com/contest/1481/submission/106608493
Loved the art! Thanks for a great contest!
One of the best CF rounds I have recently taken part in. Finally, we had WriteSomeCodeForces rather than omnipresent Notice1E9ThingsAndWriteOneLineForces. Kudos!
More like ThinkNothingAndWriteCodeMindlesslyForces. At least till C.
Are you sure about "codeMindlessly" in C ?
Pretty sure.
Can anyone help me find why my code for B always get TLE? I thought the complexity for my code is O(10^6) Thanks ;w; http://codepad.org/Nf4Rkb1n
Is it the problem of n=1?
Exactly.
May I know what is pretest 2 of B?
UPD: Managed to solve it, my brute force was not brute force enough and missed some corner cases sigh
Hey, please have a look at my latest solution. I'm unable to figure out why is it failing test 2. Would be of great help!
I think you misread the question? With the following input
the correct output is
2. The four thrown boulders will go to the 5th, 4th, 3rd, and 2rd mountains in that order.Nice pictures in problems! I like them.
How to solve B?? I was getting TLE on 2nd test case.
Brute force worked for me, although since k can be large you have to stop as soon as a rock goes off the end.
check if your code goes wrong when n=1
Very nice problems set in this contest. Can anyone explain how to solve E?
A dp approach:
https://mirror.codeforces.com/contest/1481/submission/106600288
In part D , what was needed to handle the case when there is no such pair of nodes (i,j) such that a[i][j] = a[j][i] and M was an Even number. I think this was the entire question , because rest all part were quite easy. How to solve for this case?
Hint 1: Suppose a valid path exists when m is even. This implies that there must exist some nodes u, v, w such that a[u][v] = a[v][w] (Think of the middle two characters in palindromic string).
Hint 2: Consider the case when you start at u, and the case when you start at v, and only travel between these three nodes in a cyclic fashion.
Yeah, thanks lavish315 for this. Now, it is evident that if there are 3 such nodes such that a[u][v] = a[v][w]. I can complete (M-2)/2 visits between (u,w) and then end at either u or w. Take 2 more steps to go to the alternate vertex w or u. And then , continue another (M-2)/2 visits.
I was wondering the proof of the existence of (u,v,w) is quite satisfactory. But , if such a (triplet)/(a cycle with all edges of same letters) does not exist , can we say for sure that solution does not exist?
Yes, we can claim so. Consider m = 2k, and let say there is no such triplet. Assume that a possible path exists. Then, again by the same logic, character at position k and k+1 are same, and by contradiction, this implies that such a triplet/cycle exists.
You can proof that there must be a method in three random vertices
If m is even and If there are 3 edges that form the pattern aabb/bbaa when you go from 1-2-3-2-1 then answer exists and you just have to repeat the pattern or else answer is No.
Hint 1: You're right, that's the case you need to figure out to solve the problem.
Hint 2: In this case, consider 3 vertices and the path between them.
Hint 3: In this case, if there exist distinct i,j,k such that a[i][j] = a[j][k] then does it work? What values of M does it work for?
Hint 4: Can you make it work for the remaining values of M?
Extra credit: What about if they don't exist, can you prove that it doesn't work? Even stronger, you can actually prove that for n>=4 there will always be i,j,k that satisfy the condition.
Really loved the problems! While I didn't really give my best performance (something close to the opposite actually xP) but the experience was definitely appreciable.
Huge thanks to everyone involved in the creation and conduction of the contest! :)
I felt this round to be more implementation based !!
Problem D is a trash and third-class problem. Stop setting such brain-dead problems. They take away time from the really interesting problems.
Pretty sure this garbage D would have been rejected if Anton was the coordinator.
problem C wasn't world class too . It was also just mess implementation .
Bruh problem D is very anton-style. Your code is just awful.
Most of it is just copy-paste. I am not angry about the code length. I am disappointed that it was just very obvious and all you had to do was code.
Why? since when are (prove->code) problems brain-dead third class problems?
I liked problem D, I don't see what here is copy-paste or brain-dead. Even more, I liked DEF, thanks setters for the contest!
Got to say, a great contest finally after a long time. Loved the problemset !
How to solve D ??
and Is CF little bit slow to browse ??
You can proof that there must be a method in three random vertices
I didn't like problem D because even though I had the entire idea it took way too long to code it. I don't find these types of problems enjoyable. If they are interesting that is another case. But it was neither interesting nor easy to code.
Despite having done horribly in this contest, I'd like to say that this was a nice contest!
In problem A & C there are sentences like
but in problem D there's not. This is only a minor issue but i think it's better to be consistent about the case of YESs and NOs.
Why h in B is not <= 10e9 too? With h<=10 it's just straight simulation, Div2B should be something more difficult than it.
Loved the problems... This went too good to be true for me...
When I saw problem B and see 1<k<=10^9, I thought the h must also be 10^9, so I just use a stack to implement, which take me over half an hour.
I was wondering why so many people get accepted by problem B until I see the constraint 1<h<100.
Oh, shit! If I saw this at the first glance, I will have enough time to do problem D.
it took me the entire contest and I realized it in the last second :/
Even with h <= 10^9 code is simple enough.
Hey, can you please explain why my code is failing in TC 2? Would be of great help!!
for 3 2 1 1 3 your code will give 2, but correct ans is 1
I'm lost 1 hour and 30 min to find the bug in problem C and I can't find it :(. I can AC D but I'm lost too much time in problem C :( This is my big lesson. Specialist time.
one step back to accelerate (rating -23)
They updated ratings?
no you can see your rating changings with cf-predictor
https://mirror.codeforces.com/contest/1481/submission/106608013 Div2C could someone kindly provide me a test which causes wrong answer?
Try this:
thank you! i fixed it and got AC https://mirror.codeforces.com/contest/1481/submission/106615717
Lol just look at my time 1996ms Thin ice :)
Why am I getting Memory Limit exceeded on this? Any help?
Submission: 106602826
AntiBsayer Salem_Alwarawreh
Warawreh MikeMirzayanov
106611585
This is my code for Round 699 div 2 task b. I have used dynamic memory allocation for the array. In this approach i am getting memory limit exceeded. Whereas the same approach with static memory allocation works just fine. I know that i haven't deallocated the memory after every iteration but it was given that sum of n over all test cases is less than 100 so i dont see why deallocating that array after every iteration is required because at the end of the day i am only making a long long array of size 100
Please Help and point out my mistake here if any.
My Condolence.
Probably the worst way to get System Test Fail.
Thanks for letting us know though.
My solution for D is wrong answer on test 2's 145th test case! Can someone give me a smaller example to debug?106582694
106598727 (My submission for Problem B) . Can anyone please point out why this code is failing ? I am really not able to figure out the possbile reason. Thanks.
Reread the question again? If the heights of the mountains are 1, 1, and 100, then the first thrown boulder goes to the 2nd mountain, but the second thrown boulder goes to the 1st mountain.
that is why I have dont i=1 after every increment.
But if I'm reading your code correctly, with two boulders, you'll throw them together at the second mountain?
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Thanks for the quick rating change and the extra work that you have to put in for removing the cheaters!.
How to solve C?
The tutorial is already available, you can check here...
I can't seem to figure out the mistake in C. My idea is the same as given in the tutorial. Some help would be really appreciated. Here is my submission Submission
Try this:
Thanks for fast tutorial release
Here is my Screencast for today's contest, if anybody is interested in watching a noob attempt this round xD
YouTube Video
Thank you very for the contest
In Div 2 Problem C: Fence Painting
I read the editorial and tried writing it's code however it is giving me TLE, can someone please help me out?
We must first see that the most important painter is the last one (and he will paint plank x where bx=cm) because of two reasons: when he paints plank x it won't be changed and if some other painter have a color that we don't need we can make him paint plank x, which will be repainted later.
Now we need to find x where bx=cm, there are three options:
bx≠ax. bx=ax. There are no bx=cm this case is impossible and the answer is "NO". If the first two are true we choose x such that bx≠ax, then we greedily distribute all painters j (1≤j<m) such that:
There is plank i such that bi=cj and bi≠ai then the jth painter will paint plank i (as a result the color of the ith plank will be changed). There is no plank i such that bi=cj and bi≠ai then the jth painter will paint plank x. At the end there might be some planks that didn't end up as we want so we make a last liner check on all planks i and check if bi=ai, the total time is O(n).
Code Link: https://ide.geeksforgeeks.org/DqHB8ngckI
The continue statement in line number 56 does not continue the outer while loop but it continues the for loop in which it is present. Hence the value of k is becoming negative there itself and so the outer while loop becomes an infinite loop, giving TLE.
Thanks for helping out!
Weak pretests :( In problem C, by mistake i did l=mid-1 and r=mid+1. I should have to assign l=mid+1 and r=mid-1. But still it passed the pretests. It's just the reverse which we have to do with some extra element from other side. Link
MikeMirzayanov
Problem ratings for this round have not been updated, although the ratings for the round after this (Round $$$700$$$) have been updated.
EDIT: wow, that was fast :P