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_, kalki411, ecnerwala, Tima, IITianUG, thenymphsofdelphi, mohammedehab2002, namanbansal013, Redux for their time and great feedback. Also big thanks to Bytedance instructors chenjb and jqdai0815 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
- wk_tzc
- 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

unlesshe 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!!!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

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 ???

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).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

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.

You can turn on the filter in the Dark Reader setting if that helps

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. :)

Participate in huge numbers....

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 jqdai0815 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!

problem C wrong answer on pretest 5 :(

Notice that

`gcd(a1, a2, a3, ...)`

=`gcd(a1, gcd(a2, a3, ...))`

and`gcd(a1, a2)`

=`gcd(a1, a2-a1)`

.Also notice that

`gcd(a1+d, a2+d)`

=`gcd(a1+d, a2-a1)`

and`gcd(a1+d, a2+d, a3+d)`

=`gcd(a1+d, a2-a1, a3+d)`

. Then change`gcd(a1+d, a2-a1, a3+d, ...)`

to`gcd(a1+d, a2-a1, a3-a1, a4-a1, ...)`

.Don't discuss. Some other contest has these problems too.

i think it might be overflow case.

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

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 :/

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

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

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

Yes!! and I feel terribly bad about it XD

Is this going to be unrated?

Also: Any idea for div2 B?

Lol, any reason why it should be unrated?

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

how to solve div 2 B plzzzzzz help???

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 .

my codeUPD : 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?

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

Spoiler...

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.

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

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 alone~~pattern finding lol.Yay ! Today expecting to become specialist for the first time :)

but look's like they forgot to update that

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.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--)".

size of array B should be m not n.

Is it still rated now?

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

Does anyone know how to solve problem-c

Hint for C

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

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?

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?

Hello , Why the rating rolled back?

codeforces's new record

How can we read and submit the rest problems of the camp contests ?