FairyWinx's blog

Codeforces Round #777 (Div. 2)
By FairyWinx, 3 years ago, translation, In English

Привки, Кодефорсес (ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

(Hello, Codeforces on Russian)

Igorbunov and I are happy to invite you to participate in Codeforces Round 777 (Div. 2), all the tasks of which will be about a little girl Madoka. It will take place on Mar/11/2022 17:35 (Moscow time). The round will be rated for all participants with rating strictly lower than 2100. You will have 2 hours to solve 6 problems.

I would also like to express my gratitude to the following people:

I wish you high rating, and I also hope that I will help you to distract from bad news at least a little ( ❤ ω ❤ )

Scoring distribution: 500 — 1250 — 1500 — 2000 —2500 — 3000

UPD1: Editorial

UPD2: Congratulations to the contest winners

Div 1+2

1 jqdai0815 9457
2 Geothermal 9219
3 rainboy 8649
4 End. 8529
5 kshitij_sodani 8250

Div 2

1 shnirelman 6955
2 zzfzzfzzfzzf 6558
3 Kaname-Madoka 6539
4 peuch 6317
5 rsy 6301

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

Comments Comments (161)
| Write comment?
»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

cute ^.^

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

(´･ω･`)

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

As a tester of one problem I can say that only anime girls can solve all problems

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

I would also like to express my gratitude to the mother of princebelkovetz ♡

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

As a tester, I am sad I can't participate in this awesome round (ಥ⌣ಥ)

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

    Good luck in participating in round!

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

Hoping you wouldn't get -100 contribution after your first round, as it happened to ilyakrasnovv before

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

    hoping you wouldn't get -100 contribution after your second comment.

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

As a tester, I recommend you to read all problems

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

a chance to be close to specialist :)

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

Good luck everyone! I won't wish everyone nonnegative delta because that would make the round unrated :P

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

madoka is a cute magical girl anime suitable for little children! the design and atmosphere of the show is so bubbly and warm! the girls are all lovable in a world of happiness!

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

As a tester... Oh, wait, I wasn't included in testers list. Well... So... Just good luck everyone!

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

I see that the authors are very cute! UwU

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

cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute cute

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

Upvoted for the Madoka Magica propaganda

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

Why so cuteeeeee >~<

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

Madoka!!!

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

nice testers list

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

╱/( ◕‿‿◕ )\╲

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

Madoka/se

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

Puella Magi Madoka Magica(魔法少女まどか☆マギカ) is the best anime I've ever seen.I hope the round goes well.

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

please motivate me i am tired of getting wrong answer and lacking the will power to start over again and again

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

    It's a sport and we play sport for fun, we don't have to be good at it untill or unless we want to be professional player. So enjoy buddy...

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

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

aww >_<

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

expecting a cute contest

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

Gonna use baryon mode then!!! First contest in expert yay

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

goofy ass announcement made me skip round

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

Who is Madoka

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

I hope I will become Candidate Master tonight UwU

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

Artyom123, will you marry me?

( ❤ ω ❤ )( ❤ ω ❤ )( ❤ ω ❤ )

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

777 is a good digital.I think the digital will appear in problem. Good luck everyone !

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

    It is guaranteed that the sum of the values of n and the sum of the values of m for all test cases do not exceed 777.

    in problem b do not exceed 777

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

Hope the problems will be as cute as Madoka ^v^

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

Wow! I really like this anime! My avatar is even Homura (cp of madoka >_<). Hope everyone has a happy round!

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

expecting cute statements like the cute blog

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

People with high rating in this contest will automatically become magical girls to save the world!

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

Problem "B" has a score of 1250 where "A" has a score of 500 !!! This would be great for those who will start with "B" and score as quickly as possible.

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

    Thank you for sharing this AHMADUL!!

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

    Problem F has 3000 score!!! This would be great for those who will start with "F" and score as quickly as possible.

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

    well... let's say you can solve A or B on 5m, and the other on 10m.

    B first -> 1250-penalty*5+500-penalty*10=1750-penalty*15

    A first -> 500-penalty*5+1250-penalty*10=1750-penalty*15

    no difference XD

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

      Actually the penalty of a problem per minute is dependent on the original point value of the problem. There is a subtle difference. But it is probably unnoticeable, maybe just ten points or something more, even less than a penalty submission.

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

I have already fallen in love with this little girl named Madoka. I hope she will bring a great happiness to me in this contest.

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

No worry, those Russians, who are not involved with the war, have my full supports.

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

Good luck and high rating!

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

disgusting

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

FU ANIME HATERS!!!

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

I want to comment here so badly and I want to be familiar with you all.. But I am afraid of getting downvotes in my comment. I have already negative contribution. I am sad!

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

Saluting cf for organizing so much contests

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

Dear everyone, I'm very sad right now because of my powerless. I have gone through my examination of national olympic about CP. It's not hard but … I'm really hopeless.

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

Why make so confusing statements?

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

    after reading statement of D 10 times, i can confirm i still didn't get anything. you gotta have peak mathematical reasoning to actually understand that.

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

      yeah...I wrote at least 3 versions of code before I realize what it really means.

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

        She: I hate it when you can't catch up on my hints.

        Also, the hints she gives : statement of D.

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

Had a stroke trying to understand the problem statement of B

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

its not good to put such big implementation problems in A B its hard for new coders and newbies/pupils to implement that much

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

    implementation is a secondary thing..first thing is itself the language of question.

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

I struggled so much in B,and I felt that C is much easier than B, anyone else?
but overall I liked the problems!

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

How to solve D?

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

    It felt like a heavy case work problem to me ;_;. Though maybe it has a simpler idea

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

    In Problem D I calculated how often you can divide $$$x$$$ by $$$d$$$ , called this amount $$$c$$$ and called the residual $$$r$$$. So $$$r \cdot d^c=x$$$ and $$$d$$$ does not divide $$$r$$$. Then I checked, whether $$$r$$$ and $$$d$$$ are prime. Then I had a huge casework. Most of the cases were simple, the most difficult one was $$$d$$$ not prime, $$$r$$$ prime and $$$c=3$$$.

    But somehow I still must have had an error in my reasoning... 149309714

    Edit: Oh, I forgot, the first (annoying) step was parsing the task. $$$g$$$ is a good number if $$$d$$$ divides $$$g$$$. $$$b$$$ is a beautiful number if $$$d$$$ divides $$$b$$$ but $$$d \cdot d$$$ does not divide $$$b$$$. You need to find two different sets of numbers, that are beautiful and multiplied together yield $$$x$$$.

    Edit 2: Found my mistake. When searching for factors of $$$x$$$ by iterating $$$i$$$ from $$$2$$$ to $$$sqrt(x)$$$, then not only $$$i$$$ is a divisor of $$$x$$$, but also $$$x/i$$$ ... Brainfart.

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

      "Аррр, тысяча ифов!". Seems there is no straight translation of it. I think, the closest one is "Bloody hell(ifs)". Thank you

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

        Yeah, as long as it solves the problem they are fine I guess. I wasn't happy either, trust me.

        And I speak fluent ukrainian so I got the gist also without translation :D But is this some kind of common saying/insider? Never heard it before.

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

How to solve C -.-?

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

    Notice you only need to do [0, 1] operation either vertically or horizontally (chessboard of size 1x2 or 2x1). Do this backwards for every row and column where there is a black cell. Edge case is when top left column is black.

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

      DANGGGGGGGGGGGGG, I didn't think of using anything smaller than 2x2. Thanks.

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

    Notice that the cell at (0,0) can't be 1. In all other cases, if cell (i,j) is marked '1', then you can take a window of size (1x2) or (2x1) on the cells (i,j-1),(i,j) or (i-1,j),(i,j) respectively and then color it like a chessboard.

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

    If grid[0][0] is black then answer is -1.
    Otherwise answer exists always. To color a cell (i,j) black apply operation (i-1, j, i, j) or (i, j-1, i, j). To color a cell (i,j) white apply operation (i, j, i, j).

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

    The $$$2 \cdot 1$$$ and $$$1 \cdot 2$$$ rectangles paint the cell to white and the bottom/right cell to black. These rectangles are enough. Iterate from bottom/right to top/left and set all cells to corresponding color, except the $$$(1,1)$$$. Notice, that this cell is always impossible to paint to black. This is the only case, when the answer does not exist.

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

    Note that if the first cell of the table is 1, then answer is always NO, as it is impossible to paint it black.
    Now each and every other cell can be painted black.
    1)for cells not in first row by taking that cell and cell left of it.
    2)for cells in first row except 1st cell, by taking that cell and cell above it.

    these paintings should happen in reverse order so that the latest chosen color is considered

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

any hint about how to solve D?

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

    if you understand the definition of beautiful numbers well, then it is pretty easy.

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

      Is this what had to be understood?
      for beautiful numbers,
      b%d == 0 but (b/d)%d != 0 where b is beautiful number
      If yes, I still couldn't get further approach.

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

        yes u got that right

        so now from the definition if x is beautiful number then ans is no

        now we can write x = d^n*t (where t may be prime or composite) ans n > 1 now if t is composite then ans is yes (bcz we can split t in its divisor to write x in different ways) else we have to split d into its divisors ( there is one more case to consider, i leave it to you to consider :P)

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

      Extremely helpful, thank u

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

    how to divide x into multiple of beatiful numbers? first, recursively divide x by d. then check the left number. Now you have one candidate if you get at least 2 d. Then, check the left part y. if y is not a prime, you succeed. if y is a prime and d is also a prime, you fail. Now the only left case is y is a prime and d is not a prime. if x has at least 3 d, you can try split d * y into several parts, so that each part could not be divided by d.

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

Could anyone explain why was output of 1000 10 yes whereas 8 2 is No since 1000 =10^3 8=2^3 ?

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

    1000 = 10 * 10 * 10 = 20 * 50

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

    1000 = 20 * 50 = 10 * 10 * 10 8 = 2 * 2 * 2 = 2 * 4, but 4 is not beautiful

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

    for 1000 10 two possible combinations are [10,10,10] and [20,50]

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

Implementation forces...

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

    I agree this time. B's code is more than A+B+C in usual.

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

      Bruh, B is very easy to implement (just check if there exists 2x2 square where sum of elements is equal to 3).

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

        nice observation, but solving B in a straighforward way is implementation heavy

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

          Part of problem solving is also finding a nice way to implement solution :D.

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

        oh, I didn't think about that. I used a quite complex solution... anyway it survives from system testing...

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

        Oh, dang, nice!

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

GridForces

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

The whole round is not bad,but I thought that D is a little troublesome :(

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

    I feel the same（

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

    f**k the D

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

    Agree, spent half an hour on finding two small bugs in D. Kind of a boring problem.

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

      Looking for four small bugs with four "Wa on #2"

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

      I have also spent about 40 mins,so that I didn't finish my E in time :(

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

    I have to say that I feel not good about D which cost me one hour to solve it.But it's laudable that the pretests are strong and few people FST.

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

With the power of the girl Madoka, I can finally reach Codeforces purple

According to the Google Chrome extension I should go to 1919 rating :-)

Well I should sleep now I don't want to wake up my mother in the middle of the night, I am from Hong Kong. Good night!

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

Thanks for good tasks. Especially for task E:)

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

Me in this contest

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

This is not the first time I notice that building binary jumps is so satisfyingly short in Kotlin:

val pp = (0..L).scan(p) { pr, _ ->
    (0 until n).map { pr[pr[it]] }
}
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what was crux in problem b? any hint?

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

    If any 2x2 square contains 3 ones, then it's NO.

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

Can someone explain the last test case of problem D .

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

    4^3=8^2

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

    We have $$$x = 2 ^ {14}$$$ and $$$d = 2 ^ 2$$$. The possible divisions are $$$x = 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 \cdot 2 ^ 2 = 2 ^ 2 \cdot 2 ^ 3 \cdot 2 ^ 3 \cdot 2 ^ 3 \cdot 2 ^ 3$$$.

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

      Igor_Parfenov But $$$x = 2^2.2^2.2^2.2^2$$$ is not a beautiful number as we can represent it as $$$4.4.4.4$$$

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

      Hey! Thanks I got . I had missed the part that $$$x$$$ can be broken into multiple beautiful numbers.

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

Problems B and C should have been swapped.

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

I think {2^2, 2^2, 2^2, 2^2, 2^3} and {2^2, 2^3, 2^3, 2^3} are the same, because this two "sets" are both equal to set {2^2, 2^3}, but the solution must distinguish those, so for X=2^11 and D=2^2, the answer is Yes...

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

that was the fastest system test i've ever seen

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

Can someone explain the last test case of problem E?

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

A backtracking solution for D passed in 62ms: 149323602. Is it possible to hack it?

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

    Can You explain your solution? I am new to backtracking technique.

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

      I think it's very similar to jqdai0815's solution described here, but without memoization.

      I sort the beautiful divisors in decreasing order (increasing got TLE works too: 149357544), then try to take or skip each divisor recursively while maintaining the product of the taken divisors. A divisor can be taken multiple times. The product should always be a divisor of x (if not, return 0).

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

It was a very nice contest :).

When I realized the solution for problem E, I was all https://www.youtube.com/watch?v=cDu-2h8ZDhI

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

Thanks to problems B and C, and my overwhelmingly poor observation skills, I am going to receive my 7th consecutive rating drop.

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

Solution video for A-D for anyone looking

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

When you realise that ...Total time spent reading statement of problem B > Total time taken for system testing

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

UPD: Oh, it's just the same as solution 1 in the editorial. And I thought it was not the intended solution.

My solution to D:

To avoid the casework, we can simply count the number of factorizations and check if it's greater than $$$1$$$.

We can consider all the beautiful numbers those are the divisor of $$$n$$$, denoted as $$$d_1, d_2, \dots, d_k$$$. And then it's a standard knapsack-like problem.

Let $$$f_{i,j}$$$ be the way that we only consider $$$d_1, \dots, d_i$$$, and the product is $$$j$$$. Like knapsack problem, we have $$$f_{i, j} = f_{i-1, j} + f_{i, j/d_i}$$$. We only need to consider the product $$$j$$$ that is the divisor of $$$n$$$ here. So the time complexity is $$$O(d(n)^2)$$$.

The time complexity is not good. But nobody likes casework, right?

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

RiddleForces

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

This is a test case for D that should fail anyone who used an O(n) algorithm for checking primality as opposed to O(sqrt n)

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

One of the best rounds I have ever seen!

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

I received two messages saying the following:

"Your solution 149270007 for the problem 1647A significantly coincides with solutions timaktimak/149265121, ylc0/149270007."

"Your solution 149280463 for the problem 1647B significantly coincides with solutions ylc0/149280463, timaktimak/149289518."

I am confused as the answers were indeed written by me and that the message says the answer coincides with itself. I would really appreciate it if someone can tell me what is going wrong here.

Edit: I now understand that the message is listing the coinciding solutions, after looking at the solutions. I think it is just a pure coincidence of a similar method, and there were still differences, as well as more differences in q. C. I hope this can be moderated, I have local version history on my IDE avalible if needed.

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

Appeal against plagiarism

I would like to point out that I've received an email from CF System that my submission significantly coincides with another one submitted during the contest by ktk5901.

While the two submissions do look very similar (surprising!), it's purely a coincidence since Problem A is very straightforward and a simple one (not so surprising). There was no intentional or unintentional leakage of either of our solutions.

Hence, would like to appeal against this accusation and request the system to process both submissions without considering it a violation.

Thanks.

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

big fan magaaaaaaaaaaa

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

For Problem A, writing char by char doesn't make it pass the time limit (eventhough O(n/3) implementation) (check my submission here). I think the time limit is tuned to match only some implementation styles.. is it?

EDIT: even writing 2 chars at a time didn't pass the time limit (my code), maybe C printf is too slow?

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

    I am not sure if vfprintf is buffered or not, but if it's not, then it's probably the reason of tle.

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

I tried solving problem D before reading A, B and C. But I failed because problem D is too difficult to consider all situations. Anyway, thanks for such a good round!

→ Reply