### Endagorion's blog

By Endagorion, history, 2 months ago,

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:

1. spepd — the only Div.2 contestant to solve 5 problems!
2. LebronDurant
3. diuven_fanclub
4. 1004535809
5. CTP_314

Here's a (now complete) editorial.

Happy winter holidays to all of you, and see you again on the leaderboards!

• +492

 » 2 months ago, # |   -31 Are the pretests strong?
•  » » 2 months ago, # ^ |   0 Of course! No one wants to make the pretests weak.
•  » » » 2 months ago, # ^ |   +42 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...
•  » » » » 2 months ago, # ^ |   +43 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:)
•  » » 2 months ago, # ^ |   0 I think it will because the official contest has no hack.
•  » » 2 months ago, # ^ |   +33 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
•  » » » 2 months ago, # ^ |   0 Seems like you are planning for the same this year too?
 » 2 months ago, # | ← Rev. 3 →   +51 Don't forget to notice the unusual start time!!!
•  » » 2 months ago, # ^ |   -17 Damm Thanks , I almost didn't notice that !
 » 2 months ago, # |   -16 Thank you Andrey Sergunin, amethysy0 and everyone else for this !!!
 » 2 months ago, # |   -16 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
 » 2 months ago, # |   -46 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
•  » » 2 months ago, # ^ |   -25 Sympathy for you
•  » » » 2 months ago, # ^ |   -18 Sympathy for you
•  » » » » 2 months ago, # ^ |   -17 Sympathy for you
 » 2 months ago, # |   -39 Ohh! UNUSUAL TIME
 » 2 months ago, # |   +5 The start time is very kind to Chinese participants.Thank you! Orz
•  » » 2 months ago, # ^ |   -10 That's right.But I can't take this contest 555
•  » » 2 months ago, # ^ |   0 Master Muxia orz
 » 2 months ago, # |   +22 How will we be able to solve a 5hour contest in just 2 hours as it is a Camp contest ???
 » 2 months ago, # |   -25 Hoping to become specialist soon.
•  » » 2 months ago, # ^ |   0 wtf ... why downvote -_-
 » 2 months ago, # |   -82 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 :)
•  » » 2 months ago, # ^ |   +4 This is the third time you r saying this, stop spamming bruh!
•  » » » 2 months ago, # ^ |   0 You can close your eyes.
•  » » 2 months ago, # ^ |   +25 You registered 3 years ago!! How can you even use codeforces for 10 years!! XD
•  » » » 2 months ago, # ^ |   0 Dude this is my account for write comments
 » 2 months ago, # |   -15 Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
 » 2 months ago, # |   -22 Don't get demotivated newbie's practice and learn new things we will also become pupil/specialist/expert/cm/../../../../..
 » 2 months ago, # |   -12 Please make Christmas problems!
 » 2 months ago, # |   +32 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.
 » 2 months ago, # |   +50 Look's like codeforces got rid of the mask already
 » 2 months ago, # |   +17 For those of you who didn't notice it already, just hover over the Christmas lights near the codeforces logo :P.
 » 2 months ago, # |   +56 Codeforces got in a festive mode. Nice to see this after many days of "Make CodeForces, not CoronaForces" and the mask in the logo.
•  » » 2 months ago, # ^ |   +17 Let's hope mask doesn't appear again !!
•  » » » 2 months ago, # ^ |   +3 And Let's hope Corona virus doesn't appear again
•  » » » » 2 months ago, # ^ |   +8 Oh yeah cause he's clearly gone for now :)
 » 2 months ago, # |   0 What is the score distribution of the problems?
 » 2 months ago, # |   +34 Unfortunately, I won't be able to use dark mode on codeforces for entire winters
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Awesome
•  » » 2 months ago, # ^ |   +5 Ikr and shifting to light after using dark for so long is like getting hit by a flashbang
•  » » 2 months ago, # ^ |   +1 how to use dark mode? I didnt know that there was a dark mode also.
•  » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0 You can turn on the filter in the Dark Reader setting if that helps
•  » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0
•  » » 2 months ago, # ^ |   0 You can increase the Contrast to get the better result. :)
 » 2 months ago, # |   +2 What about the score distribution?
 » 2 months ago, # |   +31 This competition is friendly for Chinese competitor! Thanks Endagorion!
 » 2 months ago, # |   +33 As a tester, I recommend participating.
•  » » 2 months ago, # ^ |   0 As a tester, problem statements are short. :) Participate in huge numbers....
 » 2 months ago, # |   +2 Happy to see, Codeforces is bringing up some different contest rather than the normal ones. Thanks to Endagorion
 » 2 months ago, # |   -6 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.
 » 2 months ago, # |   +1 Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
 » 2 months ago, # |   +57 Glad to see Retired_MiFaFaOvO appear again ^v^
 » 2 months ago, # |   -19 ByteDance!! nb!!
 » 2 months ago, # |   +49 wtf 2min 2problems?
 » 2 months ago, # |   +72 Tourist about to break his own record!
 » 2 months ago, # |   +103 Please don't discuss the problems until 3pm MSK (25 minutes from now)!
•  » » 2 months ago, # ^ |   +5 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".
•  » » » 2 months ago, # ^ |   +55 I didn't decide on this, but it may have to do with Atcoder contest starting soon.
•  » » » » 2 months ago, # ^ |   -126 Please don't make div2 contest anymore!
•  » » » » 2 months ago, # ^ |   0 Trust me, there's not much to say.
 » 2 months ago, # |   -6 problem C wrong answer on pretest 5 :(
•  » » 2 months ago, # ^ |   +12 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, ...).
•  » » » 2 months ago, # ^ |   0 Don't discuss. Some other contest has these problems too.
•  » » » 2 months ago, # ^ |   0 can you please give me a link to where i can find a proof for this thanks;
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » 2 months ago, # ^ |   0 thank you very much;
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 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)
•  » » » 2 months ago, # ^ |   0 I knew it something like prefix sum
•  » » » 2 months ago, # ^ |   0 Damn u got carried away on today's b XD
•  » » 2 months ago, # ^ |   0 i think it might be overflow case.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
 » 2 months ago, # |   -16 What a terrible round for me :/
 » 2 months ago, # |   +274 Looking at the scoreboard, you could've given us 30 more minutes instead of telling us to not to discuss for 30 minutes :(
•  » » 2 months ago, # ^ |   +8 Totally agree!!! With 30 minutes I would likely succeed debugging my C... (or find out that my solution is wrong)
 » 2 months ago, # |   +47 just to inform you guys , there's Atcoder ABC 20 minutes from now
 » 2 months ago, # |   -25 This one was a very nice exam.
 » 2 months ago, # |   +39 Div2 is the new Div1.
•  » » 2 months ago, # ^ |   +4 I feel your pain. Did my first contest in Div 1 today and I guess Div 1 is the new Div 0 :/
•  » » 2 months ago, # ^ |   0 I wasnt the only one!
 » 2 months ago, # |   -8 To be honest, these days div2 has turned into div1.5
 » 2 months ago, # |   +15 Can the problem setters spell BORING?
 » 2 months ago, # |   0 Only ~8000 participated when ~16000 have registered. Lol
•  » » 2 months ago, # ^ |   0 I guess they left after seeing A. :(
•  » » » 2 months ago, # ^ |   +12 probably the unusual time
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
 » 2 months ago, # | ← Rev. 2 →   +14 glad to know I wasnt the only one to find it extraordinarily tough
•  » » 2 months ago, # ^ |   +14 +1 kinda devastated since educational round. This added to that
•  » » » 2 months ago, # ^ |   0 same
•  » » 2 months ago, # ^ |   0 Yess, It was ,atleast I too feel so
 » 2 months ago, # | ← Rev. 2 →   0 Wasn't able to solve a single problem and got all the 3 errors : Runtime , TLE and Wrong answer first time in one contest . : ( .....
 » 2 months ago, # |   -6 A very nice contest!Just a little hard XD
 » 2 months ago, # | ← Rev. 2 →   +14 "If you just participated in ByteDance 2021 Online Qualification, you should not take part in this round! "I hope they didn't
•  » » 2 months ago, # ^ |   +7 what?
 » 2 months ago, # |   +21 It's past 12:00 UTC now, please open the submissions and others' solutions now.
 » 2 months ago, # |   +31 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.
 » 2 months ago, # |   +14 Anyone solved problem B using this? OEIS A241496
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Me, well sort of. It can be broken down into 2 sequences, one for odds and one for evens.
•  » » 2 months ago, # ^ |   0 Yes
•  » » 2 months ago, # ^ |   0 Yes!! and I feel terribly bad about it XD
•  » » 2 months ago, # ^ |   0 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)
 » 2 months ago, # |   0 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 codell n; cin>>n; ll even=0; ll odd=0; ll x=(n%2==0)?0:1; for(int i=0;i<=n+x;i++){ for(int j=0;j<=n+x;j++){ //deb(i,j); if((i+j)%2==0) even++; else odd++; } } //deb(even,odd); //ret(even); if(n%2==0) ret(even) else ret(odd); 
 » 2 months ago, # |   +1 Is this going to be unrated?Also: Any idea for div2 B?
•  » » 2 months ago, # ^ |   +1 Lol, any reason why it should be unrated?
•  » » 2 months ago, # ^ |   0 just try all possible points and check if they can be reached or not .
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # | ← Rev. 2 →   +20 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.
 » 2 months ago, # |   +10 Is it true that in D1D the invariant is — the number of zeros, ones, and a multiset of the balance array?
•  » » 2 months ago, # ^ |   +10 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]$.
•  » » » 2 months ago, # ^ |   0 Oh, thanks
 » 2 months ago, # |   +21 Do I need to know some property about inverse of a permutation in order to solve div1 C? If so,what is it?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Ok,no property need to be known... Just based on definition.All in all,it is a great problem,thanks!
 » 2 months ago, # | ← Rev. 2 →   +3 for problem div2 B i search on oeis 1,4,4,12, from there i got the pattern.
•  » » 2 months ago, # ^ |   +11 damn... I simulated upto 6 and came up with formula by hand :(
•  » » » 2 months ago, # ^ |   0 what is it?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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: 101745717I'm sure it could be further improved to be O(1) solution but O(n) passes fine.
•  » » » » » 2 months ago, # ^ |   0 Great!
 » 2 months ago, # | ← Rev. 2 →   +90 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".
•  » » 2 months ago, # ^ |   +14 My solution is the same as yours, i would say problem C is the nicest problem i ever see!
 » 2 months ago, # |   0 Is Div2 D/Div1 B DP?
•  » » 2 months ago, # ^ |   0 yes
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Although didn't participate in the contest, but it seems that Div1 B is standard DPPS: Waiting to submit my code and check
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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:/
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +11 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
•  » » » » » 2 months ago, # ^ |   0 thanks, how to do the transitions ?
 » 2 months ago, # |   0 how to solve div 2 B plzzzzzz help???
•  » » 2 months ago, # ^ |   0 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
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 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
•  » » 2 months ago, # ^ |   0 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 .
•  » » 2 months ago, # ^ |   +4 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.
 » 2 months ago, # | ← Rev. 3 →   -8 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 code#include using namespace std; #define ll long long #define ld long double #define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) //cout<<"Case #"< dp[N][N],c[N]; ld s,v,temp; int main() { IOS; ll i,j,n; cin>>n; for(i=1;i<=n;++i) cin>>c[i].first>>c[i].second; for(i=1;i<=n;++i) { s += c[i].second; for(j=0;j<=i;++j) { if(j==0) dp[i][j]={0,s}; else { dp[i][j] = {dp[i-1][j].first,dp[i-1][j].second+c[i].second}; v = dp[i-1][j-1].second; temp = min(v/2.0,c[i].first-c[i].second); if((dp[i-1][j-1].first+c[i].second+temp)>dp[i][j].first) { dp[i][j].first = dp[i-1][j-1].first+c[i].second+temp; dp[i][j].second = (v-2*temp); } else if((dp[i-1][j-1].first+c[i].second+temp)==dp[i][j].first) { if((v-2*temp)>dp[i][j].second) dp[i][j].second = v-2*temp; } } } } for(i=1;i<=n;++i) { cout<
 » 2 months ago, # |   +1 Why do we have to wait, to submit? Could you turn on the practice mode?
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   0 Oh, didn't know that people actually do this on short contests. Hope the question creators make them unsearchable.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +4 "trying to cheat". it is not cheating.
•  » » » » 2 months ago, # ^ |   +6 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.
•  » » 2 months ago, # ^ |   +3 How would you google C?
•  » » » 2 months ago, # ^ |   +3 linkThis problem is quite easy to find. You can just search "range GCD" in google.
•  » » » 2 months ago, # ^ |   +3 first comment in this blog : https://codeforces.com/blog/entry/9722 by searching range gcd codeforces
•  » » » » 2 months ago, # ^ |   0 C requires segment tree?
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 My solution without segment tree Click
•  » » » 2 months ago, # ^ |   +3 gcd of n nubmers if each number is increased by x :) link just sort all numbers & take care for n=1
•  » » » 2 months ago, # ^ |   0 Oh. Thanks all. I need to get better at googling.
•  » » » » 2 months ago, # ^ |   0 Me too
 » 2 months ago, # |   +21 Div1A — 712 solved Div1B — 551 solvedDiv2C — 1701 solved Div2D — 104 solvedReally weird difference in gap.
•  » » 2 months ago, # ^ |   +9 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 .
•  » » » 2 months ago, # ^ |   +4 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)
 » 2 months ago, # | ← Rev. 2 →   +10 Tourist is ready to cross his own highest rating record.
 » 2 months ago, # | ← Rev. 2 →   +3 when will ratings updateHOPE TO BE SPECIALIST (fingers crossed)
 » 2 months ago, # | ← Rev. 2 →   +3 Did anybody else bruteforce Div.2B like me 101739165 Spoiler...
•  » » 2 months ago, # ^ |   +3 I solve it by using bfs https://codeforces.com/contest/1459/submission/101749804
•  » » 2 months ago, # ^ |   0 Can you please explain your approach a bit.
•  » » » 2 months ago, # ^ |   0 I check all coordinates from -1000,-1000 to 1000,1000. If I can reach that i add this to ans.
•  » » » » 2 months ago, # ^ |   0 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) )
•  » » 2 months ago, # ^ | ← Rev. 3 →   +7 https://oeis.org/A241496ans = 1 + (3 * n * (n + 4) + 2 - n ^ (-1) * (n * (n + 4) + 2)) / 8;
•  » » » 2 months ago, # ^ |   0 How do you find a sequence on OEIS? I scratched my head to solve B but was unable to.
•  » » » » 2 months ago, # ^ |   0 I calculated first eight answers with a trivial solution and searched sequence on OEIS =)
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 2 months ago, # ^ |   0 This solution is O(2^n) so you can't get ac with using that.
•  » » » » » » 2 months ago, # ^ |   0 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
•  » » » » » » » 2 months ago, # ^ |   0 Simulate the process on paper and its not very hard to come up with a recursive formula.
•  » » » » » » » » 2 months ago, # ^ |   +1 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.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Try to use DP in this problem: https://ibb.co/cDwvv9d
•  » » » » » » » 2 months ago, # ^ |   -8 My submission: https://codeforces.com/contest/1459/submission/101781352
•  » » » » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0 can you explain why you choosen to take mod wih 4 ?
 » 2 months ago, # |   0 Hi . Good job ! When will the ratings change ?! Thank you for your great time i really liked it and i'm not joking.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -11 Please wait :)
•  » » » 2 months ago, # ^ |   0 ok
 » 2 months ago, # |   -39 Did not liked Div2 this time. To much math, to less programming.
•  » » 2 months ago, # ^ |   -18 lol A,B,C, tagged as 'math', 'math' and 'math'.
 » 2 months ago, # |   -6 Solved Div2C with help of second last comment of this article
•  » » 2 months ago, # ^ |   +23 I think you misspronounced Solved it need to be Stole
•  » » » 2 months ago, # ^ |   -9 I think you misspelled misspronounced, It needs to be Mispronounced.
•  » » » » 2 months ago, # ^ |   -6 How could anyone mispronounce mispronounced as misspronounced?
•  » » 2 months ago, # ^ |   0 same : )
 » 2 months ago, # | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   +1 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.
•  » » » 2 months ago, # ^ |   0 Damn it! Easy pattern but I didn't look for a pattern during the contest :(
 » 2 months ago, # |   +9 Yay ! Today expecting to become specialist for the first time :)
•  » » 2 months ago, # ^ |   +2 but look's like they forgot to update that
 » 2 months ago, # | ← Rev. 3 →   0 https://codeforces.com/contest/1459/submission/101768759 please help why i am getting error in test case 21 in problem div2c thanks in advance.
 » 2 months ago, # |   0 Is div 2 problem C similar to another problem?
 » 2 months ago, # |   0 It's so sad that C can be found here out some years ago :(
 » 2 months ago, # |   +8 When will the changes in rating will be reflected ? Nothing specified in the announcement.
•  » » 2 months ago, # ^ | ← Rev. 5 →   -15 Have patience.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 not the color though :(
 » 2 months ago, # |   +8 why the digits don't need to be sorted in problem A?https://codeforces.com/contest/1459/submission/101721508https://codeforces.com/contest/1459/submission/101718794
•  » » 2 months ago, # ^ |   +1 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?
•  » » » 2 months ago, # ^ |   +3 True, I got the problem totally wrong for not having noticed it.thanks!
 » 2 months ago, # | ← Rev. 2 →   0 It is possible that I made amazingly silly mistake but for now I can't understand why did my Submission_TLED get a TLE ?
•  » » 2 months ago, # ^ |   +9 Array b should be of size m, but is that related to TLE?
•  » » 2 months ago, # ^ |   -15 You wrote "t=1; while(t--)".
•  » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0 size of array B should be m not n.
 » 2 months ago, # |   0 Is it still rated now?
•  » » 2 months ago, # ^ |   0 Why not?
»
2 months ago, # |
Rev. 2   -29

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";

    }
else if ( r < c){
cout<<"BLUE";

}
else
cout<<"EQUAL";
cout<<endl;
}
}

•  » » 2 months ago, # ^ |   +10 Look at input format
•  » » 2 months ago, # ^ |   -10 You missed a '{' on the last else.
 » 2 months ago, # |   0 Does anyone know how to solve problem-c
•  » » 2 months ago, # ^ |   0
•  » » » 2 months ago, # ^ |   0 Thanks :)
•  » » » 2 months ago, # ^ |   0 Did you solve the problem during the contest watching that blog/quora?
•  » » » » 2 months ago, # ^ |   0 No, I solved it after the contest
 » 2 months ago, # | ← Rev. 2 →   -11 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
•  » » 2 months ago, # ^ |   +17 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.
•  » » 2 months ago, # ^ |   +1 Try googling.
 » 2 months ago, # |   +2 Submissions not getting judged at the moment. Why?
 » 2 months ago, # |   +1 How to solve Div2D ?
 » 2 months ago, # |   0 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
 » 2 months ago, # |   +4 I have a talent at not being able to solve questions
 » 2 months ago, # |   0 2C is very similar to this problem G from ccpc Guilin site ccpc
 » 2 months ago, # |   0 Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   0 censored(:
 » 2 months ago, # | ← Rev. 2 →   0 censored
 » 2 months ago, # |   0 Here is a pupil with a rating of 1488.
 » 2 months ago, # |   0 Hello everyone, Can anyone tell me why I'm still at newbie while my rating is 1255?Thanks in advance.
 » 2 months ago, # |   0 Can someone elaborate on the intuition/observations to solve 2E/1C?
 » 2 months ago, # |   -56 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.
•  » » 2 months ago, # ^ |   +92 Cool
•  » » » 2 months ago, # ^ |   -8 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.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +12 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?
•  » » » » 2 months ago, # ^ |   -20 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/101810226Rating changes rolled back, round unrated.
•  » » » » » 2 months ago, # ^ |   +10 Why are you sorting at the end or are you just trolling us?
•  » » » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +43 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.
•  » » 2 months ago, # ^ |   +10 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.
 » 2 months ago, # |   +42 Rating update?
 » 2 months ago, # | ← Rev. 2 →   +40 Is it rated? If it is,where are the rating changes?
 » 2 months ago, # |   +1 Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).
 » 2 months ago, # |   +28 rating change plz, I want to attend the next Div 1 :(
 » 2 months ago, # |   +41 Have the rating changes been rolled back? If so, why?
 » 2 months ago, # |   0 @contest_generator взляги какую прогу для codeforce создали
 » 2 months ago, # | ← Rev. 2 →   +42 Hello , Why the rating rolled back?
 » 2 months ago, # |   +25 codeforces's new record
 » 2 months ago, # |   0 How can we read and submit the rest problems of the camp contests ?