diskoteka's blog

By diskoteka, 11 months ago, In English

(っ▀¯▀)つ Heeey Codeforces (っ▀¯▀)つ

I and pavlekn are glad to invite everyone to participate in Codeforces Round 885 (Div. 2). The round will take place on 16.07.2023 17:35 (Московское время).

This round is dedicated to an amazingly beautiful girl Vika that I love very much. Every problem will be about her and related to her life.

The round will be rated for participants with rating lower than 2100. We will be glad to see the participants with a higher rating to take part in our round unofficially as well!

You will be given 6 problems to solve in 2 hours.

We would like to thank everyone that makes this round possible:

  1. Artyom123 for coordinating the round

  2. MikeMirzayanov for great Polygon and Codeforces platforms

  3. teraqqq, Be_dos, mibig, FairyWinx, princebelkovetz for red testing

  4. Dominater069, mbolgov, I.Gleb, induk_v_tsiane, Alexdat2000, maomao90, irkstepanov, fishy15 for yellow testing

  5. Serik2003, alwyn for blue testing

  6. TkachDan, ak2006 for cyan testing

  7. maksimb2008 for grey testing

Scoring distribution: 500 — 1000 — 1500 — 2000 — 2250 — 2750.

We wish you all good luck and a high rating!

UPD: Editorial published

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

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping for a lovely contest.

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

    Hoping that you find love too :)

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

      Hoping you ask out your crush too :)

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

        Hoping you guys find Peace ;)

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +25 Vote: I do not like it

          Hoping You find piece . One Piece

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
            Rev. 2   Vote: I like it -18 Vote: I do not like it

            Definitely! :) Well I would love to eat meat first.

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

              SING MINA MINA PLZ!

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

                Minami no shimawaaa atakai ♪ Paina-puru-puru, Atama boka boka, Aho baakaaaaaaa! ♪ ~~~~~~~~~~~~~~~~~~

                Ni ban!

                Kita no shima wa samuiii ♪ Hyakkoi-koi-koi, Atama buru buru, Aho baakaaaaaaa! ♪ ~~~~~~~~~~~~~~~~~~

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        HOTS : Find best time to propose your crush.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    oh look! the guy who got caught copying few contests back.

»
11 months ago, # |
  Vote: I like it +58 Vote: I do not like it

Love round

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice!

»
11 months ago, # |
  Vote: I like it +96 Vote: I do not like it

LoveForces

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

So you are saying there is hope for me :) ? Do I need to reach purple first :) ?

»
11 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Hope the problems are lovely as well :)

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

very beautiful hearts drawn by yourself?

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

<3 Lovely <3

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Rooting for your lovee! :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This guy really love his girlfriend.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This guy is really original. No one thought about dedicating their girlfriends a codeforces round :,)

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope they don't have a fight.

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Goals

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone please answer why suddenly round-882(div2),round-884(div1+div2),round883(div2) became unrated?I did really well at those rounds.IS it a temporary bug or anything else?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    most probably temporary, ratings are often rolled back, after plagrised codes are removed.

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

      So, will our ratings stay like this, or are they going to be changed back? I participated in the previous Div.3 round, and my rating was 789, but now it is 614.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Yes. Rating will be recalculated and changed back. and it is generally more than previously calculated rating.( for you it will be more than 789 after recalculation, if your code is not plagiarized).

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

        Congrats for the increase in the ratings...

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

      Thanks a lot brother.

»
11 months ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Hello everybody!

I would like to become a student in this competition (green). And I hope that this competition will be interesting.

Good luck to everyone!

Best, Jelal

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Hi, Jelal. Your comment has been very informative and I sure wish that you post more of these amazing messages on all codeforces announcements and I cant imagine the world without them.

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it -19 Vote: I do not like it

    Thank you diskoteka and others for an interesting competition!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice :3

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I reach purple this contest, will I also get gf?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of Luck everyone!

»
11 months ago, # |
  Vote: I like it +106 Vote: I do not like it

I hope every problem doesnt remind me how single I am

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

Where purple and green testing?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for the lovely round.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

'Relationship Goals' Round

»
11 months ago, # |
  Vote: I like it +70 Vote: I do not like it

Codeforces is the last place I thought I'd see PDA in.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Let's hope his gf is a beginner then

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Aww! Vika sweet name.

»
11 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I won't participate because of cringy subject

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what topics could be expected for A,B and C. anyone??

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it's so cute

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OK i upvoted the blog.

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

<3

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

UwU

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

no wonder it took that long to annaunce

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if you have a social life you must not be a real cp-er

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +105 Vote: I do not like it

    there is not any statement in the announcement, which implies that author had any social interactions with Vika

»
11 months ago, # |
Rev. 2   Vote: I like it +58 Vote: I do not like it

Finally, a round that doesn't clash with my schedule! Going for purple, good luck everyone! :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The announcement is so cute (face_holding_back_tears)

»
11 months ago, # |
  Vote: I like it +74 Vote: I do not like it

Still a better love story than Alice and Bob

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

think the problems will be good (based on the last div3 rounds they writy)

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

Best way to celebrate Love and others Loneliness

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Feels inferior to Genshin Impact :D

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

1<<Love Round

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope love rating change

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

6

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Meanwhile single people like me reading this blog ^⁠_⁠^

»
11 months ago, # |
  Vote: I like it +52 Vote: I do not like it

Remember guys heartbreak is the key to unlocking codeforces mastery

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This announcement is accompanied by a beautiful picture.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think today his girlfriend very happy

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to reach expert this contest.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Best of luck everyone, I hope everyone attempts this one with Love..

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Contests are quite rare these days!

»
11 months ago, # |
  Vote: I like it +55 Vote: I do not like it

This relationship got 6 problems and we have 2 hours to solve them. Lesssgo.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Giving contest to increase rating NA Giving contest to know their love story Yes

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want a marriage proposal in one question

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A codeforces master with a GF, what do I do to gain a glimpse at this power?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

a newcomer like me can solve one problem? what do you guys expect.(hiding imoji)

»
11 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Normal People express love through Roses and Chocolates. Legends prepare a whole Contest...

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm curious how long I need to train to get to green.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution looks scary

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

LoveForces...hoping to reach blue..

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the watermelon in Artyom123 profile cheering up!

»
11 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I also love ... love competitive programming. It is the only thing that understood me like a human being. #sigmagrindset

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this will be a nice contest! Love codeforces

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't wait to enjoy the problems.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces probably the only place where i may find love ;(

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I suggest you to have a grey bo'oh'o'wa'er next to you during the contest

»
11 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Setter be like :

  • Tu Aake Dekh Le
  • Ho Maine Contest Kitne Saare
  • Teri Yaadon Mein Banaye Sohniye
  • Sohniye
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Kanroji-san is that you?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest about love?

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I hope that no issue would ever make me realize how alone I am.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

+ve delta

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a hacking session in this round?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No pink testing??

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope we will still love the contest after rating changes

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a lovely contest!

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope we will still love the contest after rating changes lol

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

"Every problem will be about her and related to her life" every relationship ever ;-;

»
11 months ago, # |
  Vote: I like it -39 Vote: I do not like it

The round is cool, recommend to everyone!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wedding when?

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

    Expecting a breakup party instead, after seeing the votes on the announcement!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this will be the second participation on cf

»
11 months ago, # |
  Vote: I like it +60 Vote: I do not like it

Plz vika help him to create problem language more understandable.

»
11 months ago, # |
  Vote: I like it +7 Vote: I do not like it

What went wrong at F?

»
11 months ago, # |
  Vote: I like it +74 Vote: I do not like it

You should have proofread the statements before the contest. E and F contain silly contradictions and unclear sentences and both were edited after wasting some time trying to unravel them.

»
11 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Couldnt Participate SED

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This contest is as unattractive as the bridge mentioned in problem B. Worst problem statements ever.

»
11 months ago, # |
  Vote: I like it +90 Vote: I do not like it

I really hate Vika now

»
11 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Problem statements are very difficult to understand.

»
11 months ago, # |
  Vote: I like it +60 Vote: I do not like it

For me hardest Div 2 problem A ever.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's me or I have seen F statement somewhere before?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem div 2B , my code giving write output in my machine and wrong answer on codeforces !! Very frustrating experience

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Vika is too difficult to get vro

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

6

»
11 months ago, # |
  Vote: I like it +84 Vote: I do not like it

maybe problemsetter should have spent less time obsessing over vika and more time making correct tests

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Someone get Vika a translator

»
11 months ago, # |
Rev. 2   Vote: I like it +91 Vote: I do not like it

one of the worst things about codeforces's problems which is problem statement is too long for no reasons , just keep it simple like atcoder ,we don't have time to read the entire story

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    so true , it's always too long to the point you can't even understand it

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Vika is too hard to understand bru. I can now understand your pain :(

»
11 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Worst contest ever.

»
11 months ago, # |
  Vote: I like it -9 Vote: I do not like it

It'll be better to make this contest unrated.

»
11 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Problem Statements are quite difficult for me to understand.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

(love)storyforces

»
11 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Super math round.

»
11 months ago, # |
  Vote: I like it +50 Vote: I do not like it

How to solve F in 5 min?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I have seen something similar to it tho i tried to solve it but i got TLE in pretest 20, it's approach is kinda easy tho

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Definitely not a lovely contest...

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve A?

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

    Even if once the distance(|x1-x2|+|y2-y1|) is even then answer is no as somehow they will diogonally orient). else answer is YES.

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

      distance as in distance between vikas's corrdinates and any of the friends coordinrates

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

    think about a chessboard: if Vika is in a black square, then she can only be reached by someone on a black square and vice versa for white. Also if there's someone on her same color they can always reach her. Colors are just the parity (i+j)%2

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

      there must be atleast two other person otherwise if there's one girl on black and vikka is also on black then she will never got caught

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        If you think about how to chase her it's easy to drive Vika into a corner (this sounds very bad lmao).

        Like near the wall


        ...| X.V| ...| becomes ..V|//(now she can only go up until she reaches a corner) .X.| ...|

        otherwise just going towards her should do the trick

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

      thx for explaining. However as soon as I see this div2a I skipped the contest. Its too hard to be in this position.

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

      Have you seen or solved a similar problem/idea before ? If yes, do you remember where or from when ? Maybe when you used to do math competitions or something ?

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

        probably yes, but i don't remember any examples. A simple observation is "if a and b are on cells of different colors they'll never meet". From this observation you can think about when Vika can escape from X if they're on the same color. And after some thinking you can understand that Vika cannot escape when there's somebody on the same color

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it hard for me or people solving F in 3 mins lol

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?, I guess using number theory... multiples like stuff? but couldn't get it!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A was tricky, Little harder than B.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Little? B is straightforward. Its just obvious what you have to do in B. Instead I think you solve A only if you have seen something very similar before.

»
11 months ago, # |
  Vote: I like it +17 Vote: I do not like it

I don't like probllem E. It is very OEIS-able. Also can anyone explain why we didn't have a fixed MOD in this problem. The MOD being 100 made the implementation tougher.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Getting to the conclusion that the answer is the number of odd divisors of X is not that trivial. I agree on the MOD part.

»
11 months ago, # |
  Vote: I like it +81 Vote: I do not like it

I think Vika is his ex so now he want everybody to hate her

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve D? Do I need to use ternary search?

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the approach to D?

I understand that we can ternary search for the solution on f(x), where x is in [0, k] and an integer, and represents the number of times we will increase our number first, and then spend the rest of (k-x) moves on redeeming this number.

It seems to produce correct results for the first 4 sample testcases, but fails on the 2 large ones by a marginally small amount (~1e9 off the answer of ~1e18).

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

    I made it accepted by using ternary search first, and then I padded the borders L and R by some 1000, so that it became L-1000, R+1000, somehow it got ac. But, I fear it can fst though..

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

      I thought to do padding but didn't try. :(

      Does anyone has explanation why padding is working?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    • Ternary search only works for a function who has a single local maximum in the range you search on.
    • Let us define g(n) = The discount after adding the last digit to itself n times. We want to maximise the function f(n) = g(n) * (k - n).
    • We know that, ignoring the cases where the digit ends in zero or five, that the function g(n) increases by a constant amount 20 every time n increases by four, past a certain constant c.
    • If we perform a ternary search in the range [c, k] across all numbers such that they are ≡ r (mod 4) for each r ∈ [0, 4), then we know that f(4n+r) = (20n + b) * (-4n + (k-r)), because of what was said above.
    • This is a multiplication of two linear functions of n, so the result is a quadratic in n. Also, the leading coefficient of the quadratic is negative, so it must only have one maximum since it has an upside-down U shape.
    • This shows why it works when you ternary search over every four. When the amount that g is increasing by is no longer constant, we can no longer guarantee that the shape of the graph is nice. Below is a short and informal proof if you're interested :)
    (Dis)proof by Counter-Example
»
11 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Should I quit CP? [](https://imgur.com/a/Vx3xutf)

»
11 months ago, # |
Rev. 5   Vote: I like it -21 Vote: I do not like it

Suggest banning the authors for at least a year until they recover from Vika

»
11 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Quite new and interesting problems, I liked this round. Also, I think my D could fst, so can someone share their approach to D?

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

nice div1 contest

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Not able to solve A. LOL

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

rip vika lover author's english

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was testcase7 of D

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to calculate the number of steps in C?

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

    The process is similar to the Euclidean Algorithm for computing gcd.

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve C? I figured out that I need to compute the following value: "how many steps you need to do to make first element zero modulo 3", and calculate it for every $$$(a[i], b[i])$$$ pair. Is that a way to go or I'm missing smth? If that idea is ok, how to compute it fast enough?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    That idea is good. To compute it quickly enough, note that if x<<y, then we can compress it down quickly by observing the fact that (x, y) -> (y, y-x) -> (y-x, x) -> (x, y-2x), noting that we can reduce y by 2x in 3 moves without changing anything. You can figure out how many times to compress it down by using math, noting the difference between y-x.

    There is an edge case where it starts off as (0, 0), then this pair should not be considered at all as it will always be 0.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      Thanks! That was insightful

      UPD: got accepted yay!

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We have a set of two numbers, {a[i], b[i]}, where each number can be greater than, less than, or equal to the other. If a[i] is less than b[i], we perform one move to transform the set into {b[i], b[i] — a[i]}. Otherwise, if a[i] is greater than or equal to b[i], we perform moves until the set becomes {b[i], a[i] % b[i]}.

    For example, consider the set {11, 3}. It undergoes the following transformations: {11, 3} -> {3, 8} -> {8, 5} -> {5, 3} -> {3, 2} -> {2, 1} -> {1, 1} -> {1, 0} -> {0, 1}

    Here, 3 (b[i]) remains in the set until the number 2 appears, which is 11 mod 3. At that point, the transformation proceeds when a[i] >= b[i] to get {b[i], a[i] % b[i]}.

    We notice a pattern in the moves: a[i] — b[i] appears after the first move, a[i] — 2 * b[i] appears after the second move, a[i] — b[i] * 3 appears after the fourth move, a[i] — b[i] * 4 appears after the fifth move, and so on. These differences follow a sequence of +2, +1, +2, +1, and so on.

    By utilizing this pattern, we can determine the number of operations it takes to transform {a[i], b[i]} into {b[i], a[i] % b[i]} efficiently, in constant time complexity (O(1)).

    Here's code: 214083155

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem F seems some sort of Binary search on each bit of a[i].

for j'th bit, we will find when the bit will turn zero for all a[i], 0 <= i <= n-1 .

How did rainboy solved in just 6 minutes !!!!!

submission in just 6 minutes !!!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one share code for problem c?

»
11 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Statement of problem C was wrong + testcase for problem E was wrong. I spent 15 minutes just to figure out what was problem C asking. I think it's fair enough to make contest unrated.

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

    yeah wtf. Problem statement for C and examples are contradictory af.

    The statement says that the planks can't have different color after repaint at most once, but the example has the first and last planks of different colors then the rest. In total the girl walks over 3 different colors wtf?

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

You can end your search, you have found the dislike button for problem A ----->

»
11 months ago, # |
  Vote: I like it +31 Vote: I do not like it

The worst content I have seen.

»
11 months ago, # |
  Vote: I like it +250 Vote: I do not like it

screenshot

Am I happy for solving F or frustrated for not solving A?

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    I solved C and couldn't do A :clown:

    Edit: Turns out I exited the program before reading all my input. :clown: :clown: :clown: :clown:

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      tgp07 , you haven't yet solved A. So "Literally" you are wrong.

      UPDATE : tgp seems to have updated the comment.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        My bad lol. I forgot about that :clown:

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    you like odd indexes i guess

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +131 Vote: I do not like it

    It is ironic how this red-green pattern you achieved is the key idea for solving A.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I didn't realize they can also catch Vika if the distance to one of the girls is 1 :) Spent last 20 mins on problem A

      UPD: i meant distance 2

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        That's not true, the catch happens only after the friends move

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

          Oh no, it's only required to check if parity of one girl is the same XDXD

          I thought it's only possible to catch if 2 girls have the same parity, and in some other edge cases

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    For A, I spent whole 30 minutes... and then I played cat and mouse run-chase on 10*10 board. And, I found that if pairity of (x+y) % 2 matches with any of the friends co-ordinates, then she can always get caught.

    This is not A level question honestly.

    How to solve F ? any insights please ?

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can you find array after n operations quickly? If you could, then binary search would do it :)

      (Actually, simple binary search is probably too slow, but i think it's easy to remove one log n from time complexity)

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

        I could see some pattern like,

        pattern spoiler
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          Pattern is:
          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ohhh shiiiit, I was so close to solving it then... Does this mean answer will always be one of the power of 2 ?

            If that is the case, then I think I can solve it.

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

              answer doesn't have to be the power of 2, but you can quickly find the array after power of 2 steps in O(n) time, which means:

              e.g. to find array after 12 operations
              you can apply 8 operations
              then apply 4 operations

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

                got it, now makes more sense. thanks :) . I think I can solve it now.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  There is an easier way to do it. To add the x-coordinate and y-coordinate together. If two people stay in one room, this sum should be equal. And every change will +1 or -1 to the sum. It will change odds to evens and evens to odds. So if Vika's sum is an odd number, then all the girls with an even sum will not be able to catch her. But when they are both even/odd, other girl could make Vika get to the wall by following her. Then when Vika is driven to the corner, those girls with even sums could 100% catch her.

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

    i grinned from ear to ear when i saw your board, come on man,hahahahahaha

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

    not even Master cant solve A, its so crazy

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In A problem I coudnt understand what does "adjacent to the side room" mean?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could have been 700 higher position if i didnt forget to put a command inside the brackets.

in C everytime one element is smaller than half of the the other element, every 3 steps the other number get decreased 2 times from the smaller number right? we count how many steps each number needs and see if they meet. once the number in array a is zero it will be zero again after 3 steps so we can see if the numbers will be zero at the same time.

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

Don't like when there are only math problems (at least A,B,C and D)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The A question in this game is incredibly mind-blowing, it's a spectacle like never seen before.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bruh what's with F

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    What's wrong with it?

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

      the amount of solves is quite high compared with average F, and it happens two times in div2 round in a row

»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

What a lovely contest! I am so glad that i participated in this contest!! (i will be green again)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to handle both a[i] and b[i] even case in C ??

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

    Try to think about the trailing zeroes of a, that's why when a is odd you'll have 121212. The distance between 1 and 2 is 2 ^ x where x is the number of trailing zeroes of a.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

C was a monster this time! I hoped that at least I will solve till C, but B kept me occupied most of the time.

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

love was cruel

»
11 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Loveforces shouldn't be Cringeforces

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got to see new types of problems, not based on common datastructures or techniques. Contest was harder overall, never did I see so less accepted in each question of a div2 contest xD

»
11 months ago, # |
  Vote: I like it +27 Vote: I do not like it

I cannot solve A lol

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

(

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I am new here and now I am scared of cf, quit!!!!

»
11 months ago, # |
  Vote: I like it -16 Vote: I do not like it

This is by far the best round I've ever participated!

By the way, why the answer in E does not equal to the number of odd divivsors?

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

With problem statements like this, Vika won't understand a thing.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we solve B using the Binary search??

  • »
    »
    11 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    Yes.

    All $$$x$$$, $$$0\leq{x}<ans$$$ are impossible.

    All $$$x$$$, $$$ans\leq{x}\leq{n}$$$ have some $$$y$$$ such that $$$y\leq{x}$$$ and $$$y$$$ can be an answer.

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

    It's not binary search, perhaps the problem description is just tricking you into using binary search

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

    I think so, I used binary search too, and passed the system tests.

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

      can you share the logic

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I'm sorry, but I'm not a good English speaker, so It'll be hard to me to explain my logic. But at least I can share my code.

        The main idea is — Can we cross the bridge by jumping maximum $$$i$$$ planks at once?

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

    Ya I also tried off doing so But Get WA on test 2 :(

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

    Yes, Here is my Binary search code for B. SOLUTION

»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I wish u to be a single

»
11 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem F is well known in Latvia, a simplified version was used in 2017 for our team selection contest (https://lio.lv/arhivs/arhivs2/2017_4_d2_uzd.pdf problem "Aplis")

»
11 months ago, # |
  Vote: I like it -19 Vote: I do not like it

trash contest imo...hope Vika havent participated

»
11 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

When you are in a "try not to write retarded problem statements" competition, and your opponent is diskoteka

Well, I see my comment also doesn't make much sense. After effects of this contest ig.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I got the answer for problem C now (10 mins after contest ended). want to see if it is correct.

I am not able to see the option to test my solution (at summit code), where can I test it?

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

    Wait until the system testing ends and then you can test your solution

»
11 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Does problem A remind anyone of king opposition in chess? Wish I solved it during contest.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I literally picked up my chess board and played an entire end game with no pawns to study problem A

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

No hate to authors but I would like to provide feedback regarding the contest, as I found it to be poorly organized and frustrating to participate in.

»
11 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Today's C was amazing!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any clue so that no TLE, problem F 1848F - Vika and Wiki

my submission 214069066

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    2^20 = 1048576. In this test just a long array where all elements will never become zero.

    UPD: More precisely, it reaches all 0 for a large volume of operations

»
11 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone help me figure out if my idea is wrong for A? My idea was that if at least one friend is on a cell with the same color as Vika, then Vika will eventually be caught. And the color of a cell is determined through a chess-board like coloring.

Here's my submission: 214092967

Edit: I'm going to kms now

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

    Vika and her friends are in the same type of room by calculating the sum of the absolute differences in their coordinates. If this sum is even, it means Vika and her friend are in the same type of room. If the sum is odd, they are not in the same type of room.

    For example, if Vika's coordinates are (2, 2) and her friend's coordinates are (1, 2), the sum of the absolute differences is 1 + 0 = 1, which is an odd number. This means Vika and her friend are not in the same type of room.

    Based on this logic, if any of Vika's friends are in the same type of room as Vika, she cannot escape. If none of her friends are in the same type of room, she can escape.

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

    The problem is that you are answering before you read all the data. If you will remove the return in the while loop at all — all should pass

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

    You return early without reading the inputs when they start on the same square.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good problems but hard.

»
11 months ago, # |
Rev. 7   Vote: I like it +64 Vote: I do not like it

A: If the parity of x+y is same as any x[i]+y[i], then Vika will be caught. Otherwise, Vika will not be caught.

B: For each color we record their positions. For a certain color t, we list all positions with this color, and add 0 to the front of the list and n+1 to the back, and calculate the distance of adjacent positions. For the largest distance D, we can add a position with color t between them to make D-> floor(D/2), ceil(D/2), and (the maximum distance — 1) will be the answer for this color. We can look for all colors and take the minimum answer.

C: If a[i]=b[i]=0, they will always be zero (and this pair can be ignored), Otherwise, they will go into some circulation like (k,k,0,k,k,0,...) with period of 3, so we can find t[i]%3 where t[i]=the number of operations to make (a[i], b[i]) into (0, k). We can find t[i]%3 recursively: For (k, k) return 2, for (k, 0) return 1, for (0, k) return 0, for (a, b) where a>=2*b solve for (a%(2*b), b) recursively (because (a, b) --> (b, a-b) --> (a-b, a-2*b) --> (a-2*b, b)), otherwise let (a, b) <-- (b, abs(a-b)), solve recursively and add 1. Thus we can solve in O(n*log(max(a, b))).

D: If s%10==0, then s will not change in the 2nd operation, so the answer is s*k. If s%10==5, then s will become s+5 after any positive number of 2nd operations, so the answer is max(s*k, (s+5)*(k-1)). Otherwise, s%10 will go into the (2 --> 4 --> 8 --> 6 --> 2) circulation, and each time of loop will make (s, k) <-- (s+20, k-4). So we can do (s, k) <-- (s+s%10, k-1) for 4 times, each time we look for the maximum value of f(t) = (s+20*t)*(k-4*t) where t>=0. (We don't need to consider the case for 4*t>k because f(t) will be negative) This value can be found using ternary search in O(log(k)), or in O(1) by setting t0=max(0, (5*k-s)/40) and check f(floor(t0)) and f(ceil(t0)).

E: The answer is the number of odd divisors of X, so we can solve the problem using prime sieve, and for each odd prime factor p, we make cnt[p]++ and ans=ans*(cnt[p]+1)/cnt[p]. But since modular number M can be small, sometimes cnt[p] will be the mutiple of M and can't be inversed. So we need to record the number of p such that cnt[p]%M==0 and process case for cnt[p]%M==M-1, cnt[p]%M==0 separately.

Explanation for the answer

F: We can solve for each bit of a[i] and take the maximum answer. Now assume a[i]<=1 and we can use bitset to store it. We can find that after 2^t operations a[i] will become a[i] xor a[i+2^t], so we can find the number of operations to make a[i]=0 by binary search, using shift operations of bitset. Thus we can solve the problem in O(n*log(n)^2*log(max(a[i]))/w). But this is hard to pass the time limit. But if we doing binary search like what we do for binary search on the fenwick tree or finding LCA by binary lifting, we can solve in O(n*log(n)*log(max(a[i]))/w).

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it +19 Vote: I do not like it

    I got F in $$$O(N \log N)$$$ time. We don't need to binary search, simply start at $$$M = N$$$ and check if $$$a[i]$$$ ^ $$$a[i + M]$$$ is 0 for all $$$i$$$, if so then the answer is at most $$$M$$$. Otherwise, set $$$a[i]$$$ to $$$a[i]$$$ ^ $$$a[i+M]$$$ for all $$$i$$$ and divide $$$M$$$ by $$$2$$$, and continue, adding $$$M$$$ to the final result.

    Then, add $$$1$$$ to the final answer, unless the array started at all zeroes. Then, the answer is $$$0$$$.

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

    IN problem D, why we are not considering the cases when we start and end at different positions in cycle. (like intially s%10=2 and at the end s%10 = 4 or 6 or 8)

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      These cases can be found by setting (s, k) <-- (s+s%10, k-1) for 4 times, and each time we found the answer assuming we will use 4*t additional operations.

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Did the same thing while upsolving C but i couldnt really prove the fact that the solution won't TLE, is there any way to bound the number of cases when b[i]<=a[i]<2*b[i].

    Also in D, there are a 1-4 steps usually before we go into the 2-4-8-6 loop, shouldn't we check those cases too, or will that case never be the answer.

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

    D is not solvable using ternary search, you can check this comment

    https://codeforces.com/blog/entry/118293?#comment-1048731

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

what an amazing contest! (i love pupil)

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Solved 1 problem only. But it means I'll probably learn a lot from editorial which is good.

»
11 months ago, # |
  Vote: I like it +56 Vote: I do not like it

Problems A, B, C and D were all non-fun to solve. Problem statements were so unnecessary long. Problem D isn't even CP problem it's just math. Vika will never love you.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Totally agree. I believe that most people gave up on the contest when they saw the text of the problem A. Pls don't write rounds anytime again.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Bro is malding over someone else's relationship on a competitive programming forum of all places.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I could not wrap my head around A (gonna be cyan now lol). I also think C was a beautiful problem requiring many interesting insights even though I didn't solve it in contest.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    +1 gonna be cyan as well)

    Can't agree, that C was a good CP problem, D was much-much-much easier and CP-alike. I figured out the solution for D after reading statement for the 1st time, but after 1h 40m spent on A+C, so couldn't implement it in time...

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I didn't get purple because I forgot to use doubles for D to calculate (k — s / 5) / 2. sad T-T

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

chill guys don't downvote, we just not good enough to solve the problems

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Only 8k solve in A?? Keep in mind that 25k registered for the contest

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

did anyone else solve F with SOS-DP?

»
11 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Bad Problem Statement and unbalanced round

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw a variation of A when practising for the Facebook Hacker Cup once, and that's probably the only reason I solved it so quickly :)

»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

worst contest

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

what's up with people hating on A? it's just parity check right? The parity for (x+y) changes everytime, and friends can always try to come near Vika so it all comes down to is there a cell that has the same parity from original position between Vika and at least one of the friend

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

    Oh, then prove it. Always comes close by what sense?

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

      the distance between Vika and a friend is always non increasing, and since the board is finite it must eventually decrease

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

        given distance always non increasing and board is finite
        it must eventually decrease

        No, it could just not increase without decreasing, aka stay equal, at least given only your two observations.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 2   Vote: I like it +13 Vote: I do not like it

          um ok. more specifically, if Vika wishes for the distance to never decrease, then she must move away from the friend on each move. this is because the friend will always move one square closer each turn. this limits Vika to the same subset of moves for all of her turns, so eventually she will not be able to make a move without decreasing the distance. note that except for a single exception on the first move, it is not possible for two opposite direction moves to both increase the total distance, so this is true.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      imagine the board has only 2 people. Because the board is limited, one person can always chase toward the other on at least one of the dimension.

      Like if A tries to runaway on X dimension, B can always follow A until A has to turn around or stop on that dimension, then B advances one more position toward A on X. Keep repeating that until they meet.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Let's check Vika's possible moves:

      1. If she moves towards her friend, her friend will also move towards her and the (manhattan)distance between them decreases by 2.

      2. If she moves away, her friend will do the same move and she will be closer to catching Vika because she can't run indefinitely, she will hit the walls then the corners(and then not be able to move away).

      Note: Towards means that the area of the bounding box containing both Vika and her friend will decrease. Moving away means the area will increase.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It's not a bad problem, but it can be really frustrating if you don't have that intuition. It shouldn't be on a Div2A.

»
11 months ago, # |
  Vote: I like it +141 Vote: I do not like it

Vika better not read those comments or she'll start packing her bags!

»
11 months ago, # |
  Vote: I like it +27 Vote: I do not like it

For problem E, my submission works even when $$$M$$$ is not prime. We need to find the number of odd prime factors of $$$x$$$. So we can keep dividing $$$x$$$ by $$$2$$$ until $$$x$$$ becomes odd. Now we assume that $$$x$$$ is odd. Basically we not need to find $$$(y_1+1) \cdot (y_2+1) \cdot (y_3+1) \ldots (y_k+1)$$$ % $$$M$$$ where $$$x={p_1} ^ {y_1} \cdot {p_2} ^ {y_2} \cdot {p_3} ^ {y_3} \ldots \cdot {p_k}^{y_k}$$$, and $$$p_1, p_2, \ldots p_k$$$ are distinct prime factors of current $$$x$$$.

So we can have an array $$$A$$$ of length $$$MAX(MAX=10^6)$$$ such that $$$A_i = 1 + $$$ exponent of $$$i$$$ in the prime factorisation of $$$x$$$. Note that $$$A_i = 1$$$ if $$$i$$$ is not prime. After $$$i-$$$th update, we need to change the values of $$$A_{q_1}, A_{q_2}, \ldots A_{q_z}$$$ where $$$q_1, q_2, \ldots q_z$$$ are prime factors of $$$x_i$$$. After changing all the required values, we need to find the product of all elements. These operations can be performed easily with a segment tree.

If $$$x$$$ contains a prime factor larger than $$$MAX$$$, its exponent will never change. So, we can take care of that separately.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need complete help or hints in Prb A..

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

    +the length of road to go from all to vika position

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

      you can find that the length of all roads from (x,y) to (a,b) is only odd or even

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

    If the difference between Vika and her friend's position is even then they can catch her. By difference in position i mean [abs(a-c) + abs(c-d)]. Remember that all A problems have a trick only, and if you look at the example tests, you can see this pattern

»
11 months ago, # |
Rev. 3   Vote: I like it +22 Vote: I do not like it

When you planned to solve 5 and end up solving just 1: Pain,
codeforces please drop me to pupil. I want to give div 4

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

    I bet you will get promoted to Expert again before the occurrence of next Div4 contest.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A > B

»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

stop using google translate

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

Problem E is absolute DOG SHIT, imagine a problem-setter who can't come up with original ideas so he decided to adopt a Div2-C problem and then mess with the modulo. Next time, try to be less creative!

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Mathforces!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

I could think of a ternary search solution, but seems like something is missing...

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

    S mod 10 goes in cycles

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let t be the number of second operations used. For sufficiently large values of t, the bonus is increased by ~5t. So you can approximate the value function f(t) := (s+5t)(k-t). Note that f(t)-f(t-1) = -5k+s+10t-5, so the maximum value is reached when t roughly equals (s-5k)/10. Then you can just search in the range [(s-5k)/10-100, (s-5k)/10 + 100] or some larger range if you want to be safe.