Блог пользователя Endagorion

Автор Endagorion, история, 5 лет назад, По-английски

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 19.12.2020 12:35 (Московское время). 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 EvenImage 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):

  1. tourist
  2. Um_nik
  3. 142857
  4. maroonrk
  5. DmitryGrigorev

Div. 2:

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

Here's a (now complete) editorial.

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

  • Проголосовать: нравится
  • +492
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -31 Проголосовать: не нравится

Are the pretests strong?

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +51 Проголосовать: не нравится

Don't forget to notice the unusual start time!!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

The start time is very kind to Chinese participants.Thank you! Orz

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

How will we be able to solve a 5hour contest in just 2 hours as it is a Camp contest ???

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -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 :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Раунд от создателей тик-тока пропускать нельзя.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

КАК ЖЕ Я ЛЮЛБЛЮ ТИКТОК, ПЕЙТОНА САТОРИАСА И ОСТАЛЬНЫХ КОНЕЧНО Я БУДУ ПИСАТЬ УРА

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

Please make Christmas problems!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +50 Проголосовать: не нравится

Look's like codeforces got rid of the mask already

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

For those of you who didn't notice it already, just hover over the Christmas lights near the codeforces logo :P.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

Screenshot-2020-12-19-011637

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is the score distribution of the problems?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +34 Проголосовать: не нравится

Unfortunately, I won't be able to use dark mode on codeforces for entire winters

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

What about the score distribution?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

This competition is friendly for Chinese competitor! Thanks Endagorion!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +33 Проголосовать: не нравится

As a tester, I recommend participating.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Happy to see, Codeforces is bringing up some different contest rather than the normal ones. Thanks to Endagorion

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +57 Проголосовать: не нравится

Glad to see EvenImage appear again ^v^

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -19 Проголосовать: не нравится

ByteDance!! nb!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +49 Проголосовать: не нравится

wtf 2min 2problems?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +72 Проголосовать: не нравится

Tourist about to break his own record!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +103 Проголосовать: не нравится

Please don't discuss the problems until 3pm MSK (25 minutes from now)!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

problem C wrong answer on pretest 5 :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +274 Проголосовать: не нравится

Looking at the scoreboard, you could've given us 30 more minutes instead of telling us to not to discuss for 30 minutes :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +47 Проголосовать: не нравится

just to inform you guys , there's Atcoder ABC 20 minutes from now

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +39 Проголосовать: не нравится

Div2 is the new Div1.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

Can the problem setters spell BORING?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Only ~8000 participated when ~16000 have registered. Lol

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +14 Проголосовать: не нравится

glad to know I wasnt the only one to find it extraordinarily tough

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

A very nice contest!

Just a little hard XD

»
5 лет назад, скрыть # |
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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

It's past 12:00 UTC now, please open the submissions and others' solutions now.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Anyone solved problem B using this? OEIS A241496

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Is this going to be unrated?

Also: Any idea for div2 B?

»
5 лет назад, скрыть # |
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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Is it true that in D1D the invariant is — the number of zeros, ones, and a multiset of the balance array?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Do I need to know some property about inverse of a permutation in order to solve div1 C? If so,what is it?

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

for problem div2 B i search on oeis 1,4,4,12, from there i got the pattern.

»
5 лет назад, скрыть # |
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".

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is Div2 D/Div1 B DP?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how to solve div 2 B plzzzzzz help???

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 .

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
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

UPD : I understood the mistake . I was not keeping track of space left which can be used to fill more.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Why do we have to wait, to submit? Could you turn on the practice mode?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Div1A — 712 solved Div1B — 551 solved

Div2C — 1701 solved Div2D — 104 solved

Really weird difference in gap.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

Tourist is ready to cross his own highest rating record.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

when will ratings update

HOPE TO BE SPECIALIST (fingers crossed)

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Did anybody else bruteforce Div.2B like me 101739165

Spoiler
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hi . Good job ! When will the ratings change ?! Thank you for your great time i really liked it and i'm not joking.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -39 Проголосовать: не нравится

Did not liked Div2 this time. To much math, to less programming.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Solved Div2C with help of second last comment of this article

»
5 лет назад, скрыть # |
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.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Yay ! Today expecting to become specialist for the first time :)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is div 2 problem C similar to another problem?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It's so sad that C can be found here out some years ago :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

When will the changes in rating will be reflected ? Nothing specified in the announcement.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится
»
5 лет назад, скрыть # |
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 ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is it still rated now?

»
5 лет назад, скрыть # |
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;
    }
}
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone know how to solve problem-c

»
5 лет назад, скрыть # |
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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Submissions not getting judged at the moment. Why?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Div2D ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

I have a talent at not being able to solve questions

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

2C is very similar to this problem G from ccpc Guilin site ccpc

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

censored(:

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

censored

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone elaborate on the intuition/observations to solve 2E/1C?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +42 Проголосовать: не нравится

Rating update?

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +40 Проголосовать: не нравится

Is it rated? If it is,where are the rating changes?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by Endagorion (previous revision, new revision, compare).

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

rating change plz, I want to attend the next Div 1 :(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +41 Проголосовать: не нравится

Have the rating changes been rolled back? If so, why?

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +42 Проголосовать: не нравится

Hello , Why the rating rolled back?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

codeforces's new record

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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