Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Endagorion's blog

Codeforces Round #691, based on ByteDance — Moscow Workshops Online Contest
By Endagorion, history, 9 months 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_, 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):

  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. 1004535809
  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 (242)
»
9 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Are the pretests strong?

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

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

    → Reply
    • »
      »
      »
      9 months 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
      • »
        »
        »
        »
        9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Damm Thanks , I almost didn't notice that !

    → Reply
»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Thank you Andrey Sergunin, amethysy0 and everyone else for this !!!

→ Reply
»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
9 months 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
»
9 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Ohh! UNUSUAL TIME

→ Reply
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Hoping to become specialist soon.

→ Reply
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can close your eyes.

      → Reply
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dude this is my account for write comments

      → Reply
»
9 months 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
»
9 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Don't get demotivated newbie's practice and learn new things we will also become pupil/specialist/expert/cm/../../../../..

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

Please make Christmas problems!

→ Reply
»
9 months 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
»
9 months ago, # |
  Vote: I like it +50 Vote: I do not like it

Look's like codeforces got rid of the mask already

→ Reply
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the score distribution of the problems?

→ Reply
»
9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

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

    https://codeforces.com/blog/entry/85729

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

    You can increase the Contrast to get the better result.

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

What about the score distribution?

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

This competition is friendly for Chinese competitor! Thanks Endagorion!

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

As a tester, I recommend participating.

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

    As a tester, problem statements are short. :)

    Participate in huge numbers.
    → Reply
»
9 months 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
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Glad to see Retired_MiFaFaOvO appear again ^v^

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

ByteDance!! nb!!

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

wtf 2min 2problems?

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

Tourist about to break his own record!

→ Reply
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months 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
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -126 Vote: I do not like it

        Please don't make div2 contest anymore!

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

        Trust me, there's not much to say.

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

problem C wrong answer on pretest 5 :(

→ Reply
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

      can you please give me a link to where i can find a proof for this thanks;

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

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

        → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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)

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

      I knew it something like prefix sum

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

      Damn u got carried away on today's b XD

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

    i think it might be overflow case.

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

      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.

      → Reply
»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

What a terrible round for me :/

→ Reply
»
9 months 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
  • »
    »
    9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it -25 Vote: I do not like it

This one was a very nice exam.

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

Div2 is the new Div1.

→ Reply
  • »
    »
    9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wasnt the only one!

    → Reply
»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

To be honest, these days div2 has turned into div1.5

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

Can the problem setters spell BORING?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Only ~8000 participated when ~16000 have registered. Lol

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

    I guess they left after seeing A. :(

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

      probably the unusual time

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

      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.

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

Wasn't able to solve a single problem and got all the 3 errors : Runtime , TLE and Wrong answer first time in one contest . : ( .....

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

A very nice contest!

Just a little hard XD

→ Reply
»
9 months 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
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Anyone solved problem B using this? OEIS A241496

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

    Me, well sort of. It can be broken down into 2 sequences, one for odds and one for evens.

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

    Yes

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

    Yes!! and I feel terribly bad about it XD

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

    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)

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

code
→ Reply
»
9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Lol, any reason why it should be unrated?

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

    just try all possible points and check if they can be reached or not .

    → Reply
  • »
    »
    9 months 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
»
9 months 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
»
9 months 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
  • »
    »
    9 months 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
»
9 months 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
  • »
    »
    9 months 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
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is it?

      → Reply
      • »
        »
        »
        »
        9 months 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
»
9 months 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
  • »
    »
    9 months 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Div2 D/Div1 B DP?

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

    yes

    → Reply
  • »
    »
    9 months 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
    • »
      »
      »
      9 months 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve div 2 B plzzzzzz help???

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

    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

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

    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

    → Reply
  • »
    »
    9 months 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
  • »
    »
    9 months 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
»
9 months 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
»
9 months 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
»
9 months 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
  • »
    »
    9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      "trying to cheat".

      it is not cheating.

      → Reply
      • »
        »
        »
        »
        9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    How would you google C?

    → Reply
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months 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
»
9 months 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
»
9 months 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
»
9 months 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
  • »
    »
    9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain your approach a bit.

    → Reply
    • »
      »
      »
      9 months 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
      • »
        »
        »
        »
        9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months 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
      • »
        »
        »
        »
        9 months 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
      • »
        »
        »
        »
        9 months 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
        • »
          »
          »
          »
          »
          9 months 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
          • »
            »
            »
            »
            »
            »
            9 months 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
            • »
              »
              »
              »
              »
              »
              »
              9 months 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
              • »
                »
                »
                »
                »
                »
                »
                »
                9 months 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
            • »
              »
              »
              »
              »
              »
              »
              9 months 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
            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

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

              → Reply
          • »
            »
            »
            »
            »
            »
            9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain why you choosen to take mod wih 4 ?

    → Reply
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Solved Div2C with help of second last comment of this article

→ Reply
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn it! Easy pattern but I didn't look for a pattern during the contest :(

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

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

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

https://codeforces.com/contest/1459/submission/101768759 please help why i am getting error in test case 21 in problem div2c thanks in advance.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is div 2 problem C similar to another problem?

→ Reply
»
9 months 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
»
9 months 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
»
9 months 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
  • »
    »
    9 months 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
    • »
      »
      »
      9 months 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
»
9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Array b should be of size m, but is that related to TLE?

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    You wrote "t=1; while(t--)".

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

      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.

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

    size of array B should be m not n.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it still rated now?

→ Reply
»
9 months 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to solve problem-c

→ Reply
»
9 months 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
  • »
    »
    9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try googling.

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

Submissions not getting judged at the moment. Why?

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

How to solve Div2D ?

→ Reply
»
9 months 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
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I have a talent at not being able to solve questions

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

censored(:

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

censored

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a pupil with a rating of 1488.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone, Can anyone tell me why I'm still at newbie while my rating is 1255?

Thanks in advance.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +92 Vote: I do not like it

    Cool

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

      why is sorting the two hands un-necessary, and even wrong? I tried the exact method only with a sort, and it fails pretest #2. explain.

      https://codeforces.com/contest/1459/submission/101809794 https://codeforces.com/contest/1459/submission/101809822

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -20 Vote: I do not like it

        Actually, I found this difference in C++14 Compiler and C++17 Compiler. WTF? Accepted on GNU 14 not GNU 17. This should NOT fail on GNU 17! Sorting the hand should make this algorithm stronger, and not fail.

        https://codeforces.com/contest/1459/submission/101810226

        Rating changes rolled back, round unrated.

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

          Why are you sorting at the end or are you just trolling us?

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

            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.

            → Reply
»
9 months 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
  • »
    »
    9 months 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
»
9 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Rating update?

→ Reply
»
9 months 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
»
9 months 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
»
9 months ago, # |
  Vote: I like it +28 Vote: I do not like it

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

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

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@contest_generator взляги какую прогу для codeforce создали

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

Hello , Why the rating rolled back?

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

codeforces's new record

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

// Problem B in O(1) without using any DP ;-)

include

using namespace std; typedef long long ll;

ll solve() { ll ans=0; ll n; cin>>n; if(n==1) return 4; else if(n==2) return 4; else if(n==3) return 12; if(n%2==0) { ans=((n/2)+1)*((n/2)+1); } else { ans=(n/2+1)*(n+3); } return ans; }

int main() { cout<<solve()<<endl; return 0; }

→ Reply