Hello, Codeforces community!
I'm glad to invite you to Codeforces Round #691 (Div. 1) and Codeforces Round #691 (Div. 2), which will be held on Dec/19/2020 12:35 (Moscow time). The round will be rated for both divisions.
The problems were taken (mostly) from the ByteDance — Moscow Workshops Online Contest, which is happening at the same time. They were prepared by me, AndreySergunin, and amethyst0. We are very thankful to the testers: low_, rkm62, ecnerwala, Tima, IITianUG, thenymphsofdelphi, mohammedehab2002, namanbansal013, Redux for their time and great feedback. Also big thanks to Bytedance instructors chenjb and Retired_MiFaFaOvO for testing and reviewing the Bytedance online contest.
ByteDance is a global technology company operating a range of platforms that allow people across languages, cultures and geographies to create, discover and connect. ByteDance has partnered with Moscow Workshops and Codeforces to organize a top tier and exclusive training camp for the International Collegiate Programming Contest. The upcoming Programming Camp will be held in Beijing from February 20th to 26th, 2021.
ByteDance — Moscow Workshops Online Contest is an opportunity to participate as teams in this camp.
You can find more information about this training camp, including registration and prizes at https://programcamp.bytedance.com/.
Important update: please be informed that the Bytedance online team contest ends 25 minutes after the Codeforces round does. For this reason, we ask you not to discuss the problems publicly during that time, until 3pm MSK. Code and testcases public display will also be disabled during that time. Thank you for your understanding.
Scoring distribution:
Div. 2: 750-1000-1500-2000-2500-3000
Div. 1: 500-1000-1500-2000-2250-3500
Final update: thanks for participating, hope you had fun! Let's hear it for the winners:
Div. 1 (the only contestants to solve 5 problems):
Div. 2:
- spepd — the only Div.2 contestant to solve 5 problems!
- LebronDurant
- diuven_fanclub
- 1004535809
- CTP_314
Here's a (now complete) editorial.
Happy winter holidays to all of you, and see you again on the leaderboards!
Are the pretests strong?
Of course! No one wants to make the pretests weak.
People might want strong pretests, but that doesn't mean these ones necessarily are. Unless you have seen the tests or are a tester, you don't really know whether they are strong...
Yeah, I was keeping that in mind when I wrote the comment. I was trying to say that a tester would work hard to make the pretests strong, and therefore, the pretests are likely to be strong unless he made a mistake:)
I think it will because the official contest has no hack.
last year there was a similar contest based on byte dance. the pretests were bad so I managed to hack three solutions and get a grandmaster title
Seems like you are planning for the same this year too?
Don't forget to notice the unusual start time!!!
Damm Thanks , I almost didn't notice that !
Thank you Andrey Sergunin, amethysy0 and everyone else for this !!!
I would like to take a moment and thank all the problem setters of the contests because of this contests we get to learn so much!! Thank you <3
I had been FST or hacked five times including just now When my predict score achieve 2000.That's true there were some bugs in my program, but I hope problem writer can make test data stronger, It's not funny When I suffer a disastrous decline
Sympathy for you
Sympathy for you
Sympathy for you
Ohh! UNUSUAL TIME
The start time is very kind to Chinese participants.Thank you! Orz
That's right.But I can't take this contest 555
Master Muxia orz
How will we be able to solve a 5hour contest in just 2 hours as it is a Camp contest ???
Hoping to become specialist soon.
wtf ... why downvote -_-
Codeforces is Best site ever made. I used it like 10 years starting from childhood. Thanks for all creators of this fantastic Website and to everyone who is reading this now !!Happy New Year!!I Wish all of you to solve problems (lvl higher than 3000) and reach Nutella this coming year :)
This is the third time you r saying this, stop spamming bruh!
You can close your eyes.
You registered 3 years ago!! How can you even use codeforces for 10 years!! XD
Dude this is my account for write comments
Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
Don't get demotivated newbie's practice and learn new things we will also become pupil/specialist/expert/cm/../../../../..
Please make Christmas problems!
On the site https://programcamp.bytedance.com it's written that registration for the online contest ended yesterday. Is it possible to extend the registration process?
Because I think that many teams (including my team) learned about this contest from the announcement.
Look's like codeforces got rid of the mask already
For those of you who didn't notice it already, just hover over the Christmas lights near the codeforces logo :P.
Codeforces got in a festive mode. Nice to see this after many days of "Make CodeForces, not CoronaForces" and the mask in the logo.
Let's hope mask doesn't appear again !!
And Let's hope Corona virus doesn't appear again
Oh yeah cause he's clearly gone for now :)
What is the score distribution of the problems?
Unfortunately, I won't be able to use dark mode on codeforces for entire winters
roll 2 die
Was thinking of that too. It's really good to see the festive background design in dark mode but too cumbersome to read texts on the design with the dark mode.
Awesome
Ikr and shifting to light after using dark for so long is like getting hit by a flashbang
how to use dark mode? I didnt know that there was a dark mode also.
Codeforces itself does not have a dark mode. There are browser extensions like "Dark Reader" that make the website to be looked in dark mode.
You can turn on the filter in the Dark Reader setting if that helps
hey buddy can you tell me the hint for prob DIV2 B i want a calculated hint , i mean a hint after which i still need to think about the problem.
https://codeforces.com/blog/entry/85729
You can increase the Contrast to get the better result.
What about the score distribution?
This competition is friendly for Chinese competitor! Thanks Endagorion!
As a tester, I recommend participating.
As a tester, problem statements are short. :)
...
Happy to see, Codeforces is bringing up some different contest rather than the normal ones. Thanks to Endagorion
Seems like Endagorion missed to thank Mike for the platform :(
Btw Can you please change Good Bye 2020 -> Finally Good Bye 2020!!!? Given 2020 was one of the most difficult and sad phase world saw in past many years, I think many of us are waiting for 2020 to end and hoping to have a positive 2021.
Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
Glad to see Retired_MiFaFaOvO appear again ^v^
ByteDance!! nb!!
wtf 2min 2problems?
Tourist about to break his own record!
Please don't discuss the problems until 3pm MSK (25 minutes from now)!
looking at the problem difficulties,they can give us 30 more minutes and then no need to make announcment about "dont discuss problems for 30 minutes after the contest end".
I didn't decide on this, but it may have to do with Atcoder contest starting soon.
Please don't make div2 contest anymore!
Trust me, there's not much to say.
problem C wrong answer on pretest 5 :(
Notice that
gcd(a1, a2, a3, ...)
=gcd(a1, gcd(a2, a3, ...))
andgcd(a1, a2)
=gcd(a1, a2-a1)
.Also notice that
gcd(a1+d, a2+d)
=gcd(a1+d, a2-a1)
andgcd(a1+d, a2+d, a3+d)
=gcd(a1+d, a2-a1, a3+d)
. Then changegcd(a1+d, a2-a1, a3+d, ...)
togcd(a1+d, a2-a1, a3-a1, a4-a1, ...)
.Don't discuss. Some other contest has these problems too.
can you please give me a link to where i can find a proof for this thanks;
You can use the theorem: Let a, b, v be 3 integers, then gcd(a, b) = gcd(a, b+ua).
It's easy to prove that the set of common divisors of a and b is the same as the set of common divisors of a and b+ua.
You can generalize the result to:
gcd(a, b, c) = gcd(a, b+ua, c+va).
thank you very much;
Nice, I did differently, I used randomization to calculate gcd with some ~300 numbers,it's not a good solution but if in case test cases are not strong it will pass.(Though in the solution I submitted, I was foolish enough to take same iterator i at two places and it messed up)
I knew it something like prefix sum
Damn u got carried away on today's b XD
i think it might be overflow case.
shit!, I didn't noticed that during contest ,noticing the size of input, I guess problem setter discouraged randomization in this problem by setting limits high enough.
What a terrible round for me :/
Looking at the scoreboard, you could've given us 30 more minutes instead of telling us to not to discuss for 30 minutes :(
Totally agree!!! With 30 minutes I would likely succeed debugging my C... (or find out that my solution is wrong)
just to inform you guys , there's Atcoder ABC 20 minutes from now
This one was a very nice exam.
Div2 is the new Div1.
I feel your pain. Did my first contest in Div 1 today and I guess Div 1 is the new Div 0 :/
I wasnt the only one!
To be honest, these days div2 has turned into div1.5
Can the problem setters spell BORING?
Only ~8000 participated when ~16000 have registered. Lol
I guess they left after seeing A. :(
probably the unusual time
Yeah, seems like many of them noped out OR because of the unusual time.
Personally, I thought it was okay. Just needed some more time.
glad to know I wasnt the only one to find it extraordinarily tough
+1 kinda devastated since educational round. This added to that
same
Yess, It was ,atleast I too feel so
Wasn't able to solve a single problem and got all the 3 errors : Runtime , TLE and Wrong answer first time in one contest . : ( .....
A very nice contest!
Just a little hard XD
"If you just participated in ByteDance 2021 Online Qualification, you should not take part in this round! "
I hope they didn't
what?
It's past 12:00 UTC now, please open the submissions and others' solutions now.
I've always liked Endagorion's style of problem setting. And I think that this was a great contest. But, I think the jump from C to D in division 2 was a bit too much or it would not have been if the contest was half an hour longer. Nevertheless, the problems were really great. Kudos to all the setters.
Anyone solved problem B using this? OEIS A241496
Me, well sort of. It can be broken down into 2 sequences, one for odds and one for evens.
Yes
Yes!! and I feel terribly bad about it XD
My submission is still in the queue, but I think I used the same approach of deriving a general formula by considering the steps as an alternative sequence of (L,R) and (U,D)
in a matrix if n is even and i+j==even then we can reach that point and if n==odd and i+j==odd we can reach that point ..... i used this concept in B Div 2 whats wrong with it
ll n; cin>>n;
Is this going to be unrated?
Also: Any idea for div2 B?
Lol, any reason why it should be unrated?
just try all possible points and check if they can be reached or not .
If your first move is up/down, then your 3rd,5th,7th,... moves MUST be up/down and 2nd,4th,6th,... moves MUST be left/right. Vice versa if your first move is left/right. The left/right moves determine the x-coordinate of the end point and the up/down moves determine the y-coordinate. Think a little about the possible coordinates of the end point based on your first move.
For me, E was much, much easier than D, because the approach seems pretty straightforward, and D is some kind of ad-hoc which I believe is possible not to come up with at all.
Is it true that in D1D the invariant is — the number of zeros, ones, and a multiset of the balance array?
The invariant is correct. Not sure about sufficiency. The following is correct and sufficient:
Consider a multi-graph on prefix values. Between $$$a$$$ and $$$a + 1$$$, the number of edges is equal to the number of indices i such that $$$p[i] = a, p[i + 1] = a + 1$$$ or $$$p[i] = a + 1, p[i + 1] = a$$$. In this we need to find an eulerian path(/cycle) from 0 to $$$p[n]$$$.
Oh, thanks
Do I need to know some property about inverse of a permutation in order to solve div1 C? If so,what is it?
Ok,no property need to be known... Just based on definition.All in all,it is a great problem,thanks!
for problem div2 B i search on oeis 1,4,4,12, from there i got the pattern.
damn... I simulated upto 6 and came up with formula by hand :(
what is it?
I simulated upto 6 on paper and got values for each. And then noticed that odd steps were always a multiple of 4 plus the value of the previous odd answer. And even steps had the same multiple of 4 plus the value of the second last even number.
So I came up with this iterative formula: 101745717
I'm sure it could be further improved to be O(1) solution but O(n) passes fine.
Great!
69th place, nice!
Problems in div1 were fairly interesting, I'd say. My (and probably intended) solution for C is to store pairs (row, column, value), where "inverse" operations flip either "row" or "column" with "value" and the other four only increment/decrement "row" or "column".
My solution is the same as yours, i would say problem C is the nicest problem i ever see!
Is Div2 D/Div1 B DP?
yes
Although didn't participate in the contest, but it seems that Div1 B is standard DP
PS: Waiting to submit my code and check
That looks pretty straightforward to me at first but I just cannot solve it- -.
I am using state like dp[i][number of chosen bottle][unfilled volume] probably I am wrong:/
I tried using dp[i][j] where i is the number of bottles chosen and j is the filled volume, dp[i][j] stores the maximum possible empty volume for given i and j.
Check my code here : http://codeforces.com/contest/1458/submission/101768798
thanks, how to do the transitions ?
how to solve div 2 B plzzzzzz help???
I tried to calculate the first few steps manually to try and get the pattern. I figured that there must be some recursion in it as loops of 2 and 4 could end up in the same place
It has a pattern. I draw some cases on graph. So it is- for base cases -> if x=0, then 1 if x=1, then 4 if x=2, then, 4 Now, if x is odd, the answer is- 2*((x/2)+1)*(x/2) if x is even then it is square of (a/2)+1
I solved using brute force . Notice that ceil(n/2),floor(n/2) is maximum number of times we can travel along x-axis and y-axis respectively and vice-versa . Also distance traveled along x-axis is independent of y-axis . Maximum number of points we can travel along x-axis is bounded by 1000 . So you can brute force total number of distinct points that can be reached along x-axis and y-axis and multiply them to get the answer .
code for more details .
For even n, you have to take n/2 steps in x direction and n/2 in y direction. If n/2 is even, since you are starting from 0, you can land at even positions. If n/2 is odd, you can land at odd positions. So you have to find number of vertices (x, y) with x y even (or odd) and bound -n/2 and +n/2.
Similar reasoning for odd n, with a little precaution that you can take one extra step in a direction. This will result in (odd, even) or (even, odd) vertices.
I tried to solve problem Div2 D , glass half spilled using dynamic programming . Where at dp[i][j] is stored a pair {maximum water that can be stored in j glasses if k==j,maximum water that is left corresponding to first value in pair}.
Could some one tell what is wrong in this approach .
UPD : I understood the mistake . I was not keeping track of space left which can be used to fill more.
Why do we have to wait, to submit? Could you turn on the practice mode?
Why would you include 2 problems that can easily be googled like div2 B and C? I mean if people thinking first of trying to cheat search them fast, they will get way higher in standings than someone that really tried to solve them on their own.
Oh, didn't know that people actually do this on short contests. Hope the question creators make them unsearchable.
That's true. I almost needed all the time to figure out the pattern of q.B. that's why I couldn't submit my solution within the time . Now, I find out that what I was thinking is correct. But those who searched on OEIC or something easily solved it.
it is not cheating.
Yes, you are right, judging by codeforces rules it is not, so I should rephrase what I really meant: these rounds are "competitive programming contests" not "google search contests" and at the very end the standings should be based just on someone's cp skills. If we were to pick the people that solved the first 2 or 3 problems from div2 and give them another contest to solve, we might obtain very different standings compared to the standings of this contest because of B and C. I'm not hating on the round but this is what I think about B and C in particular.
How would you google C?
link
This problem is quite easy to find. You can just search "range GCD" in google.
first comment in this blog : https://codeforces.com/blog/entry/9722 by searching range gcd codeforces
C requires segment tree?
My solution without segment tree Click
gcd of n nubmers if each number is increased by x :) link just sort all numbers & take care for n=1
Oh. Thanks all. I need to get better at googling.
Me too
Div1A — 712 solved Div1B — 551 solved
Div2C — 1701 solved Div2D — 104 solved
Really weird difference in gap.
In div2 , many people tried to solve A,B before C,D thus more mental effort and time . Also people get intimidated many times by 'D' even though it's not difficult .
For me it's difficult to thought up of DP almost every time (except the most primitive). Even now I read about states and cannot implement it.
I just thought that this is true difference between Div1 and Div2 participants)
Tourist is ready to cross his own highest rating record.
when will ratings update
HOPE TO BE SPECIALIST (fingers crossed)
Did anybody else bruteforce Div.2B like me 101739165
...
I solve it by using bfs https://codeforces.com/contest/1459/submission/101749804
Can you please explain your approach a bit.
I check all coordinates from -1000,-1000 to 1000,1000. If I can reach that i add this to ans.
I think the author thinks this is a positive solution because n is less than 1000. If n ^ 2 is not allowed, n can be allowed to be much larger ( O(1) )
https://oeis.org/A241496
ans = 1 + (3 * n * (n + 4) + 2 - n ^ (-1) * (n * (n + 4) + 2)) / 8;
How do you find a sequence on OEIS? I scratched my head to solve B but was unable to.
I calculated first eight answers with a trivial solution and searched sequence on OEIS =)
https://ideone.com/CKqPOr this is a brute forces solution O(2^n) which explores all possible paths and stores the end — points in a set
This solution is O(2^n) so you can't get ac with using that.
Yes it will give TLE, can you please explain how to do it without using OEIS, I don't feel there is the need of doing BFS or DFS traversal
Simulate the process on paper and its not very hard to come up with a recursive formula.
Yes, or use some proof-work without simulating anything.
For $$$N(mod)2=0$$$:
Lets define $$$X$$$ and $$$Y$$$ as the absolute value of any position on grid relative to the origin for x axis and y axis. It is easy to see:
$$$X,Y<=N/2$$$
Also, if we want to reach any other position, if we considered $$$X=N/2$$$, If we do an opposite move once, then it will be: $$$X=N/2-2$$$. Therefore:
$$$X(mod)2=(N/2)(mod)2$$$
$$$Y(mod)2=(N/2)(mod)2$$$
Satisfying above equations, we can get the answer for any even N.
For $$$N(mod)2=1$$$:
$$$(X+Y)(mod)2=1$$$.
$$$X,Y<=N/2+1$$$
As we have this time $$$X$$$ or $$$Y$$$ one of them only must be odd, then with this operation, we can negate another operation by going to opposite direction. Therefore, we only need to check $$$(X+Y)(mod)2=1$$$ because basically, either X or Y we can reach any position and the other is based on satisfying the modulo so no need to handle each one by a modulo alone. Satisfying those, will get you the answer for odd N.
You can also further optimize that in only $$$O(N)$$$ as we can know the range values of $$$Y$$$ when solving the system of equations for both cases. We can further optimize it to $$$O(1)$$$ with some stars and bars and combinatorics but I won't explain that as I myself is too lazy to proof and I got it by pattern finding lol.
Try to use DP in this problem: https://ibb.co/cDwvv9d
My submission: https://codeforces.com/contest/1459/submission/101781352
I know, I'm just explaining how to get the first few terms of the sequence as the comment asked. I didn't use that to get ac.
can you explain why you choosen to take mod wih 4 ?
Hi . Good job ! When will the ratings change ?! Thank you for your great time i really liked it and i'm not joking.
Please wait :)
ok
Did not liked Div2 this time. To much math, to less programming.
lol A,B,C, tagged as 'math', 'math' and 'math'.
Solved Div2C with help of second last comment of this article
I think you misspronounced Solved it need to be Stole
I think you misspelled misspronounced, It needs to be Mispronounced.
How could anyone mispronounce mispronounced as misspronounced?
same : )
How to reduce the running time of this solution for problem B? Also I have tried only one part of the coordinate and multiply with 4 but same result TLE.
My solution is O(1) though by
listing conditions and then getting a system of equations then improving from O(N^2) to O(N) with some basic combinatorics then to O(1) using some basic stars and bars and handling even/odd alonepattern finding lol.Damn it! Easy pattern but I didn't look for a pattern during the contest :(
Yay ! Today expecting to become specialist for the first time :)
but look's like they forgot to update that
https://codeforces.com/contest/1459/submission/101768759 please help why i am getting error in test case 21 in problem div2c thanks in advance.
Is div 2 problem C similar to another problem?
It's so sad that C can be found here out some years ago :(
When will the changes in rating will be reflected ? Nothing specified in the announcement.
Have patience.
not the color though :(
why the digits don't need to be sorted in problem A?
https://codeforces.com/contest/1459/submission/101721508
https://codeforces.com/contest/1459/submission/101718794
They must not be sorted, because the order is fixed on the cards. a[i] is on the same card as b[i]. So, if sorted we would sort the pairs. But there is also no point in sorting the pairs.
Why would you like to sort the data?
True, I got the problem totally wrong for not having noticed it.
thanks!
It is possible that I made amazingly silly mistake but for now I can't understand why did my Submission_TLED get a TLE ?
Array b should be of size m, but is that related to TLE?
You wrote "t=1; while(t--)".
Bro I m not an Expert yet as you but I know that it is correct as there was only one test case and this condition is totally correct for the problem . :) If there was more test cases he would have input t using cin>>t and then go on using this.
size of array B should be m not n.
Is it still rated now?
Why not?
I know DIV2 A was very easy just we to find for how many cars upper no is greater and same for lower written no's cards. but my code is ruturing something different even something wired here is my code
include<bits/stdc++.h>
using namespace std; int main( ) { #ifndef ONLINE_JUDGE freopen("input.text", "r", stdin); freopen("output.text", "w", stdout); #endif int T; cin>>T; while(T--){ int n; cin>>n; int a[n]; int b[n]; int r = 0 , c = 0; for ( int i = 0; i<n; i++){ cin>>a[i]; } for ( int j= 0; j<n ; j++){ cin>>b[j]; } for ( int k = 0; k<=n; k++){ if ( a[k] > b[k]){ r++; } else if ( a[k] < b[k]){ c++; } } if ( r > c){ cout<<"RED";
Look at input format
You missed a '{' on the last else.
Does anyone know how to solve problem-c
Hint for C
Thanks :)
Did you solve the problem during the contest watching that blog/quora?
No, I solved it after the contest
Can someone please tell me sources to learn fast googling techniques . It took me too much time to think for B and was unable to think C , Which would have been a matter of Minutes if I would have knew good googling techniques
Wouldn't it be better to just come up with the idea by yourself? I think coming up with an idea is the key point for doing CP. If you want to google it just for knowledge, you can google it after the contest end. If you google for rating, then I believe that although your rating might increase this time, it will eventually fall if you lack the skill.
Try googling.
Submissions not getting judged at the moment. Why?
How to solve Div2D ?
https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/practice-problems/algorithm/employee-performance-1/description/
Problem C of today's contest can easily be solved using this already available problem
I have a talent at not being able to solve questions
2C is very similar to this problem G from ccpc Guilin site ccpc
Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
censored(:
censored
Here is a pupil with a rating of 1488.
Hello everyone, Can anyone tell me why I'm still at newbie while my rating is 1255?
Thanks in advance.
Can someone elaborate on the intuition/observations to solve 2E/1C?
I obsessed over problem 'A' so much that I would not continue until it was solved. Despite having the right idea, and implementing what looks like a solution, it failed on pretests over and over. When the contest was done and I looked at the solution, it looked the same as my solutions roughly with not many differences, only a slight bug in equality, that i'm not going to fix. This contest should go down in history as the Worst contest ever and Byte Dance should be ashamed to set it up in such a way. Problem setters should try even harder as a result. We're done.
Cool
why is sorting the two hands un-necessary, and even wrong? I tried the exact method only with a sort, and it fails pretest #2. explain.
https://codeforces.com/contest/1459/submission/101809794 https://codeforces.com/contest/1459/submission/101809822
I thought we were done, why do you keep jerking me around like this ;(
Fine. You can't sort the two strings separately since the cards have to be moved as whole objects, with matching red and blue digits (which is the whole point of having cards instead of just numbers in the first place), and separate sort decouples red digits from blue ones. Happy?
Actually, I found this difference in C++14 Compiler and C++17 Compiler. WTF? Accepted on GNU 14 not GNU 17. This should NOT fail on GNU 17! Sorting the hand should make this algorithm stronger, and not fail.
https://codeforces.com/contest/1459/submission/101810226
Rating changes rolled back, round unrated.
Why are you sorting at the end or are you just trolling us?
No, I see that now. I did two things. Implement sort (without checking), then changing the compiler from 14 to 17. It fails on the pretests when sorted, but I'm not convinced entirely as to why. Oops from me, let me figure it out.
Div1C is a very beautiful problem, thank you! Amazing to see how a seemingly complicated set of operations can reduce to something so simple and elegant.
However, I think this problem fits Div1D better. There was a big gap between Div1B and Div1C.
Absolutely, it is very nice. I'd been trying it for the whole contest (from 00:18) and got totally confused, but the editorial is extremely simple and elegant. Thank you.
Rating update?
Is it rated? If it is,where are the rating changes?
Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
rating change plz, I want to attend the next Div 1 :(
Have the rating changes been rolled back? If so, why?
@contest_generator взляги какую прогу для codeforce создали
Hello , Why the rating rolled back?
codeforces's new record
How can we read and submit the rest problems of the camp contests ?