Endagorion's blog

Codeforces Round #691, based on ByteDance — Moscow Workshops Online Contest
By Endagorion, history, 3 years ago, In English

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

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

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!

  • Vote: I like it
  • +492
  • Vote: I do not like it

Comments Comments (188)
| Write comment?
»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Are the pretests strong?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course! No one wants to make the pretests weak.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

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

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it will because the official contest has no hack.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems like you are planning for the same this year too?

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +51 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -46 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -82 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    This is the third time you r saying this, stop spamming bruh!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    You registered 3 years ago!! How can you even use codeforces for 10 years!! XD

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dude this is my account for write comments

      → Reply
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Please make Christmas problems!

→ Reply
»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Look's like codeforces got rid of the mask already

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the score distribution of the problems?

→ Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

:(
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Ikr and shifting to light after using dark for so long is like getting hit by a flashbang

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    how to use dark mode? I didnt know that there was a dark mode also.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can increase the Contrast to get the better result.

    :)
    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What about the score distribution?

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

This competition is friendly for Chinese competitor! Thanks Endagorion!

→ Reply
»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester, I recommend participating.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a tester, problem statements are short. :)

    Participate in huge numbers.
    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Glad to see jqdai0815 appear again ^v^

→ Reply
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

ByteDance!! nb!!

→ Reply
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

wtf 2min 2problems?

→ Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Tourist about to break his own record!

→ Reply
»
3 years ago, # |
  Vote: I like it +103 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +55 Vote: I do not like it

      I didn't decide on this, but it may have to do with Atcoder contest starting soon.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -126 Vote: I do not like it

        Please don't make div2 contest anymore!

        → Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

problem C wrong answer on pretest 5 :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it might be overflow case.

    → Reply
»
3 years ago, # |
  Vote: I like it +274 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Totally agree!!! With 30 minutes I would likely succeed debugging my C... (or find out that my solution is wrong)

    → Reply
»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Div2 is the new Div1.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I feel your pain. Did my first contest in Div 1 today and I guess Div 1 is the new Div 0 :/

    → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can the problem setters spell BORING?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Only ~8000 participated when ~16000 have registered. Lol

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

A very nice contest!

Just a little hard XD

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

"If you just participated in ByteDance 2021 Online Qualification, you should not take part in this round! "

I hope they didn't

→ Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Anyone solved problem B using this? OEIS A241496

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is this going to be unrated?

Also: Any idea for div2 B?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Lol, any reason why it should be unrated?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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]$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Ok,no property need to be known... Just based on definition.All in all,it is a great problem,thanks!

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    damn... I simulated upto 6 and came up with formula by hand :(

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is it?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like 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.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +90 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    My solution is the same as yours, i would say problem C is the nicest problem i ever see!

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Div2 D/Div1 B DP?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Although didn't participate in the contest, but it seems that Div1 B is standard DP

    PS: Waiting to submit my code and check

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve div 2 B plzzzzzz help???

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, didn't know that people actually do this on short contests. Hope the question creators make them unsearchable.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      "trying to cheat".

      it is not cheating.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    How would you google C?

    → Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Div1A — 712 solved Div1B — 551 solved

Div2C — 1701 solved Div2D — 104 solved

Really weird difference in gap.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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)

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Tourist is ready to cross his own highest rating record.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

when will ratings update

HOPE TO BE SPECIALIST (fingers crossed)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Did anybody else bruteforce Div.2B like me 101739165

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I solve it by using bfs https://codeforces.com/contest/1459/submission/101749804

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your approach a bit.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I check all coordinates from -1000,-1000 to 1000,1000. If I can reach that i add this to ans.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    https://oeis.org/A241496

    ans = 1 + (3 * n * (n + 4) + 2 - n ^ (-1) * (n * (n + 4) + 2)) / 8;

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you find a sequence on OEIS? I scratched my head to solve B but was unable to.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I calculated first eight answers with a trivial solution and searched sequence on OEIS =)

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This solution is O(2^n) so you can't get ac with using that.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Simulate the process on paper and its not very hard to come up with a recursive formula.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                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.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Try to use DP in this problem: https://ibb.co/cDwvv9d

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              My submission: https://codeforces.com/contest/1459/submission/101781352

              → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -39 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Solved Div2C with help of second last comment of this article

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I think you misspronounced Solved it need to be Stole

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is div 2 problem C similar to another problem?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      True, I got the problem totally wrong for not having noticed it.

      thanks!

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It is possible that I made amazingly silly mistake but for now I can't understand why did my Submission_TLED get a TLE ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it still rated now?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

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;
    }
}
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to solve problem-c

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try googling.

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Submissions not getting judged at the moment. Why?

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Div2D ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I have a talent at not being able to solve questions

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

censored(:

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

censored

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -56 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Rating update?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

Hello , Why the rating rolled back?

→ Reply
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

codeforces's new record

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply