RedLycoris's blog

Codeforces Round 872 (Div. 1 & 2)
By RedLycoris, history, 21 month(s) ago, In English

Hello Codeforces! （你好，代码部队）

We are glad to invite you to participate in Codeforces Round 872 (Div. 1) and Codeforces Round 872 (Div. 2) on May/08/2023 15:05 (Moscow time). Please note the unusual start time.

This round is rated for all the participants. You will be given 5 problems (one of which is divided into two subtasks) and 2 hours to solve them in each division.

Assume you are YuezhengLing, and in this round, your best friend LuoTianYi will give you several problems to solve.

(LuoTianYi is the left one and YuezhengLing is the right one)

We would like to thank:

  1. RedLycoris, CrTsIr, Gyy_cj, SanweiTreap and Gellyfish for writing the problems.

  2. Artyom123 for coordinating the round.

  3. MikeMirzayanov for great Codeforces and Polygon platforms.

  4. He_Ren, orzdevinwang for our red suns testing the round.

  5. Qingyu, zimpha, SeeleVollerei, Crying, rui_er, Kevin114514, Lynkcat, lgswdn, FreshP_0325, mir for red testing the round.

  6. KbltQaQ, LHQing, Falashiro, NemanjaSo2005, geospiza, Kohaku, maoweishou, welleyth, EasonTAO, Rushroom, Gheal, rsj for orange testing the round.

  7. Error_Yuan, fishy15, Lyrically. ntherner, yash_0402, robin_friday for purple testing the round.

  8. LRL65, ayhan37, Zhangxuyang, Koful123, playerr17, AhmedEzzatG for blue testing the round.

  9. zhy137036 for green testing the round.

  10. tibinyte2006 for gray testing the round.

  11. You

     for participating in this round.

UPD: Scoring distribution:

Div.1: 500 – (500+750) – 1750 – 2250 – 3000

Div.2: 500 – 1000 – 1500 – (1000+1250) – 2750

UPD: Editorial is available here

UPD: Winners!

Div 2:

Div 1:

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

Comments Comments (231)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +85 Vote: I do not like it

awa

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    QwQ

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -224 Vote: I do not like it

      People of Codeforces! This is an extremely urgent PSA.

      You are all aware about the strangely incessant efforts of the anime weebs to push anime propaganda upon us in recent times. From images of cute anime waifus, comments containing jokes with anime references, to entire blogs about anime. It must have puzzled you. Some of you must be wondering that what could, after all be the reason for this unholy weeb mass indoctrination.

      Till yesterday, I too was unaware of the dark truth behind this mystery. However, I recieved shocking intel from my contacts in the CIA, and I am compelled to share this information with you, as the fate of the world hangs in the balance right now.

      CLASSIFIED
      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      ovo

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    You bought my participation with that anime picture XD

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    As a tester, I recommend reading all problems. GLHF!

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

hoping for easy A this time so more people can participate otherwise they will just leave :|

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +131 Vote: I do not like it

As the gray tester, I guarantee that taking last place in this round will result in negative delta.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Good luck in your achievement!!!

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    How did you get negative rating???

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +82 Vote: I do not like it

      Submit fail hacks on people in your room some 80 times or more to get negative delta in contests. (Scared the shit out of me last contest when I saw 74 unsuccessful hack attempts on my C submission xD)

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    And the first place will lead to a very positive delta.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    damn you're right

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Why there's no cyan testing?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Good question. Maybe this round is a BIT difficult.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

As a (former) purple tester, I secured last place in testing easily. Anyway, good luck in the round!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +67 Vote: I do not like it

    puts on glasses Theoretically you should not be telling this information to the participants since several individuals may theoretically be able to find out about the topics of the problems of this round by getting the statistics of topics where you're good at or not based on your performances on CF, please don't blame me if this situation will happen

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Maybe he was just pretending to be weak.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Sir but the task of testers is to test the round so that based on their opinions every problem in the final problemset is of appropriate difficulty, and if a person deliberately didn't solve problems on their full strength the quality of the round may worsen

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Actually I tested this round last year when having lunch:P

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lyrically is a cute boy. I met him in Nanjing. He only studied OI for less than a year, but he can easily become a candidate master. This is incredible. From this, we can conclude that he is pretending to be weak (fAKe).

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I advise u to stop fAKing and wear girls’ clothesxD

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That is not possible! You should be my girlfriend!

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No matter what gossip I say. Wishing everyone a good ranking!

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +65 Vote: I do not like it

As a tester, this round might be Chinese-friendly.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What does that mean? Lot of people say there is too much math in chinese rounds.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      I think he means that the unusual contest time is friendly to Chinese, as we don't have to stay up late to participate in this round :)

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, that's true. More contests at this time please!!

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In fact, maybe a Chinese middle school student won't have enough time to the contest.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Don't forget ds.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      maybe have some well-know algorithm or trick in China?

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    So Div.1 D's solution is very similar to NOIP2022 T4?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

gl hf

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Cyan's : Are we a joke to you?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

As a newbie I don't know much about how codeforces ratings work, but which of the two contests can I give and expect a change in my rating? Div1 or div2? Or will both not affect my rating?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Yot can't participate in div 1 because your rating is lower that 1900, but you can freely participate in div 2 and it will affect you'r rating

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

unfit my schedule but still appreciate

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

I really like a sentence from chinese participants:啊？()

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Cute

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What should I say.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

RedLycoris Orz

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +40 Vote: I do not like it

Hello, YuezhengLing and LuoTianYi!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +41 Vote: I do not like it

wow！Nan-bei！！！！（我超 南北组！！！！）

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Lot of people say there is too much math in chinese rounds. Is this true?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    (And many DS.)

    But these are all stereotypes. I think there will be many interesting problems, too.

    Hope to enjoy the contest!

    → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +51 Vote: I do not like it

wow, LuoTianyi and YuezhengLing! what year is it today 我超！南北组！今夕是何年

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Seems a lot of OIers like vocaloid (including me).

    But I don't really like the style of the illustrations...

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    awa

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another Chinese round. Time to lose ratings.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -32 Vote: I do not like it

From the time to the theme,it's not only round by Chinese but also round for Chinese.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

Too much testers. Hoping for an amazing round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +117 Vote: I do not like it

Damn, div 0?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I here?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Please continue this great time!And I love nanbei!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Damn, div 0?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

As YuezhengLing, you gave LuoTianYi a dynamic tree.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

%%%gezhiyuan %%%sanweitreap

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

As a tester, i think this round is a good one.It is friendly to beginners.Good luck to all!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

You

for participating in this round.

You

is very magical.
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

1 up rate for cuteness ._.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Cutest invitation/announcement I have ever seen... <3

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Anime, good.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Announcement so cute, I can't miss this contest at all.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Return to orange again,hope not dropping this time...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Extremely excited for this contest. Hoping for a positive delta

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, this round has beautiful problems, really loved solving them. Good luck!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Points distribution?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

W*c, Vocaloid!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Wish rp++

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, I tested.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    The moon shines, thank the moon.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The moon shines, thank the moon. YueLiangHaoShan, BaiXieYueLiang.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

no way,is it 2023 ? last time i saw them was almost 5 years ago, rating++pls （今夕是何年）

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

wawawawawa!!!!!so cute!!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why unusual start time?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Friendly time for participants.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Can I become CM today?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese round has math problems. Hope to solve at least one of them.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

i think that will be a great round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

as a tester I'm not, but it's a good trick to raise a contribution ( :

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Upvote me to have +ve delta

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best everyone.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

orz

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

My first Div 1 round. Hope for amazing problems)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! Lyrically! btw gl!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it
My copy of the picture in the announcement
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I know that some Chinese people hold this contest. But as a Chinese middle student, I don't think it's a good time to start the contest. Chinese students especially high school students have nearly no time to participate the contest on Mondays. I'm just in Grade 7 but I have too much homework to do. I usually finish my homework after 10:30 p.m.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it might be fit for Chinese oiers

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The round started at 20:05(UTC+8), That's great. But today is Monday. Because of that, I can't participate this contest.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

wtf, div1B have mathematical expectation.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same buddy, I'm too weak in probability :(

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    It's not really about expectation. I mean it is but you don't have to know anything.

    For k = 1 answer is obviously 1, for k = 3 the answer is also 1 (there is one point central point which is the intersection of paths A-B, A-C and B-C; this is the island you are looking for, if you move one step from it you can get closer to one island but further from 2 others).

    So you need to solve only for k = 2. Calculate the sum of path lengths with standard tree dp and divide by number of paths (n-1)*n/2.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i know it. I solved this problem. But B2 is unreal for me

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not sure why are you surprised/complaining then.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Arguing local behavior is not enough to ensure global optimality. One needs to argue that the function is convex (both for B2 as well as here, but here it's easy to see it by taking cases) for that to be enough (which can be done), but I found that the most important part that I almost missed.

      → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +42 Vote: I do not like it

I'll never write div1 again!.. until I can solve d1C-D. div2 on my second account is way better than two hours of complete hell and a decent rating loss, which is what happens 99% of the time

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you for this contest. (Praying that I don't fail systests)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Why does div2C have such a weird test case?

6 6
-1 1 4 5 -1 4

WTF!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to optimize in D1B2

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

Wow, today I experienced the feeling of submitting a solution last minute. Nothing can beat this feeling.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Wrong Answer on Pretest 6.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Amazing problems D1,D2 (B1, B2). Thanks a lot :)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved D1, for odd n answer is 1, how to solve D2,i know what to do but can't optimize it.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Each edge of A- B counts as a sum of exactly C(down[B],k) * C(n — down[B], k), here down[X] is how many vertices lie in subtree X if hanging on vertex 1. (Here I consider that B is strictly deeper than A). Actually, in my solution of D1 I could have changed only 2-3 lines to get D2, but I noticed this only later. С(n,k) — binomial coef.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

In problem $$$B2$$$. Let's calculate for every vertice number of good combinations for it, and then sum them. Look at vertice $$$v$$$. Let $$$a_1, \dots, a_p$$$ be sizes of its subtrees. The combination is good if and only if there is no subtree with more than $$$\frac{k}{2}$$$ vertices in combination. So if $$$v$$$ is not in the combination (if it is, there is a little change) the answer is:

$$$\sum_{0 \le b_i \le min(a_i, \frac{k}{2}), \sum{b_i}=k} {k \choose b_1, \dots, b_p}$$$

How to calculate it?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Consider the set of good vertices for fixed locations of the $$$k$$$ nodes. This set of good islands is always connected and, if there are $$$m$$$ good islands, between them there are $$$m-1$$$ edges. Try to calculate the expected number of edges between the good nodes instead of the expected number of the nodes. Or more specifically, try to calculate how many times each edge will be between two good nodes. The answer will be this plus 1.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Let's find the number of bad combinations with vertex $$$v$$$. Notice, that there should exists only 1 subtree with number of vertices from combination greater than $$$\frac{k}{2}$$$. So let's fix that subtree. Suppose size of this subtree is $$$s$$$. Then the number of bad combinations is $$$\sum_{i=1}^{k} \binom{s}{k+i} \binom{n-s}{k-i}$$$. We fix the number of vertices from combination in that subtree: $$$k+i$$$. Then choose them with $$$\binom{s}{k+i}$$$ ways. And multiply it with $$$\binom{n-s}{k-i}$$$ — number of ways to place other $$$k-i$$$ vertices not in that subtree. We need to calculate this sum for $$$O(n)$$$ sizes. You can rewrite this sum as $$$\sum_{i=k+1}^{s} \binom{i-1}{k} \binom{n-i}{k-1}$$$. Why? Consider the binary array with size $$$n$$$ and $$$k$$$ ones. Then this sum is the number of way to have $$$> \frac{k}{2}$$$ ones in the first $$$s$$$ positions. Let's fix the position of $$$k+1$$$ ones — call it $$$i$$$. Then we need to have $$$k$$$ ones on the left and $$$k-1$$$ on the right. Number of ways to choose left ones is $$$\binom{i-1}{k}$$$, on the right is $$$\binom{n-i}{k-1}$$$. The binomial coefficients do not depend on $$$s$$$, so you can calculate it fast with prefix sums.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Honestlly, I felt like div2. Problem D1 was like regular D problem. It's points should have been more at least 1750. Definitely NOT 1000 points problem.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How? That's way easier than regular D's. It's just counting total number of paths in a tree, and it's a very standard problem.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 3   Vote: I like it -14 Vote: I do not like it

      For K = 2 , it would have been WAY EASIER THAN REGULAR D.

      but when u add K = 3, things become little complex. You have to add prefix Sum DP.

      suppose all the neighbours of node are having subtree of size a1,a2,a3,a4,a5...

      now, we need to find pattern of prefix sum DP where 

      int total = 0;
for(int i = 0 ; i < a.size() ; i++) {
  for(int j = i+1 ; j < a.size() ; j++) {
      for(int k = j+1, j < a.size() ; k++) {
             total += (a[i] * a[j] * a[k] % MOD);
             total %= MOD;
      }
  }
}

      Converting these three for loops into LINEAR TIME was definitely challenging for me, I don't know about others.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        For any odd K the answer is always 1

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          LOL vgtcross, I sense sarcasm in that comment. And no, for k = 1 , it wasn't as difficult as regular D problem xD

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Um... what? For any odd K, including K = 3, the answer is ALWAYS 1. No exeptions. You don't need any of that complicated stuff for D1 since for K = 1 and K = 3 the answer is always 1.

            205099808

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
              ← Rev. 5   Vote: I like it -7 Vote: I do not like it

              For any odd K, answer will be always 1 ,

              I couldn't prove it myself, so I calculated it with program. I hope my program passes. Anyways, Can you please help me understand the proof, why for all odd K, answer is always 1 ? ( actually, I knew how to solve for even K , for even K > 3 , but I was stuck on solving odd K , when K > 3 ) . Alas, my little brain couldn't come up with above answer = 1 when k = odd . vgtcross

              UPDATE : WHEN K is odd, we will always have single center in tree.

              → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for k = 3

        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          well, I could not deduce that, and I honestly dont know how to calculate that. So, what I did is,,, converted these three for loops into one single for loop with suffixSumDp, which was really hard to find. 

          int total = 0;
for(int i = 0 ; i < a.size() ; i++) {
  for(int j = i+1 ; j < a.size() ; j++) {
      for(int k = j+1, j < a.size() ; k++) {
             total += (a[i] * a[j] * a[k] % MOD);
             total %= MOD;
      }
  }
}
          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          for $$$k \equiv 1 \pmod 2$$$ :

          Spoiler
          → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a standard problem that consists of two phases:

  1. add $$$k$$$ for rectangle area ($$$O(N)$$$ times)

  2. after all addition, calculate the sum for rectangle area ($$$O(N)$$$ times)

I know it is can be done in $$$O(N \log N)$$$ by Binary Indexed Tree, but I did not want to think it deeply and wrote lazy propagation code with same time complexity which is TLE due to big constraints ... Is it intended?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually how would one create a BIT to do those in O(N log N) time?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't know, whether div2.C was tricky or i am dumb :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

SpecialCaseForces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I like the tasks, although I'm not able to solve B2/C even after thinking a lot

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Isn't B1 answer just 1 if k = 1 or k = 3 and if k = 2 answer is sum of lenghts of all paths? (by lenght I mean number of verticies)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did not realize that lol. I took each node and determined how many different paths have that specific node as a valid one and summed all that up.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

How to solve d1C? It's the hardest d1C I've seen in real contest.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    For C, I try this: Every non-leaf node which does not have more than 1 child can be compressed into it's descendant. I think if we do this we might be able to pass with dp[node][val], which gives minimum moves to make all leaves in subtree of node equal to val. Because height of tree after compressing is logarithmic. Idk if it will work I fail to implement in time

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No this is wrong, consider this:

      1 2
1 3
3 4
3 5
5 6
5 7
7 8
7 9
...
      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Ahh I see.. Height can still be linear :/

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hi, so the idea i got (and did not have time to implement in contest)

    let dp[u][x] = min number of moves to get x as common xor among all paths from leaves upto u

    then dp[u][x ^ a[i]] = min(dp[u][y] + 1, sum(min(dp[v][x], dp[v][z] + 1)))

    You notice that all the dp values are atmost 1 off from each other, so you store min and the values of the state which achieve this min. Then you can do subtree merging.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Do dfs to solve subtrees.

    When solving a subtree, basically you have the children subtrees that might be solved using OPTIMAL number of changes to some values and OPTIMAL+1 to the rest.

    Merge that by looking at which values appear as optimal the most in the children subtrees.

    Optimize the solution by using small to large merging.

    It's a pretty standard idea tbh.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +42 Vote: I do not like it

Even I got $$$\Delta \approx -70$$$, B2 is an overwhelming problem. This time I was completely defeated. Thank you for good contest!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

I might've finally reached expert!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    After this round, I'm still a pupil.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I am expecting to become a Master excitedly!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone Please explain the solution for Div 2 C / Div 1 A . . .

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose u 1st sitted the person at xi whose xi was greater than 0 then choose this as pivot point and make other people sit accordingly like persons with -1 will sit left to it and persons with -2 will sit right to it while persons with xi>0 are independent to sit at xi.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We have 3 cases to consider:

    1. start at seat 1, then our answer will be number of option 2s + number of distinct option 3s
    2. start at seat m, then our answer will be number of option 1s + number of distinct option 3s.
    3. We start at a seat x that is not 1 or m. In this case, we must fill up the "gaps" to the left and right of the seat x that we start at.

    For the first 2 cases, we see that if we start at 1 we can never pick the left guys, same for if we start at m we can never pick the right guys

    Now we just need to iterate over all possible middle values x, and fill up the guys to the left of x, and the right of x. We take the number of middle values < x and the number of option 1s, and number of middle values > x and number of option 2s

    This can be done by sorting our array of middle values and doing some index checking.

    https://codeforces.net/contest/1825/submission/205103435

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

that n==k case in B2 gave me a mini heart attack for my B1. relief when I understood that it gets handled automatically XD

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Brainless D with only 7s TL

What a trash experience

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    I feel your pain

    Spoiler

    Bro tried everything 😭

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

oof.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -33 Vote: I do not like it

Div2 D testcase == 'heng heng heng aaaaaaaaaa'

^ ^

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice Problems

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Chinese culture export

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Strong pretests, but the successful hacking rate out of all valid attempts is 100%! Fascinating.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice Contest, especially on div2 d1, d2! Btw, I was so unlucky to get in top 100 because of modular mistake on d2 :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Amazing problem Div1B (Div2D). I was struggling for "points" idea, that is, try to find number of configurations that can split two group of points and assign k//2 to each of them, and get stuck on it until the end of the contest (for almost 90 minutes). When system testing, a word "edges" came into my mind, and I only need to change two lines in my code to get accepted.

Gosh!It's so close to get a positive delta in div1. Why I am doing so bad at div1?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I managed to solve D1 but i dont have any idea how to solve D2.

How to solve D2?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Check edutorial. Generally speaking, if you think of a "correct" solution (look at the edges and not the vertices) of D1, it is immediately clear how to convert it to D2:)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2 B problem...

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Put the $$$\min(a_i)$$$ on $$$(0, 0)$$$ and put the $$$\max(a_i)$$$ on $$$(0, 1)$$$ or $$$(1, 0)$$$ depending on $$$n$$$ and $$$m$$$ which is greater, and you are very close to the answer. Just be greedy. Tutorial

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what if the given array is .... a[] = {-1 , -2 , -3 , 10} here putting -3 on (0,0) would give me a max value of 28 but i can get a max value of 38 if i use 10 on (0,0). i guess i'm right ?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You are right, it's my fault. T_T I think it's actually about the maximum difference and the secondary maximum difference in the array, just make the difference between (0, 0) and (0, 1) and the difference between (0, 0) and (1, 0) to be those two maximum difference in an order depending on m and n which is greater. It can be proven that the pair of the secondary maximum difference contains at least one $$$max(a_i)$$$ or $$$min(a_i)$$$

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't think so clearly about that while programming to solve the problem because it's not important to decide which number to place in (0, 0). Actually the important thing while programming is to get the secondary maximum difference

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

This contest did show me the mirror after I became too much confident upon solving 6 problems in the last div4 contest. Was only able to solve A in this one :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can become specialist

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

When will the rating be? Why won't these be preliminary results. Can anyone explain the distribution of points and how they will be calculated?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

round approved

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How is it possible that the guy from the first place on div2 did 3 tasks in the 9-th minute?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I don't think that this is possible too.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    it seems to me that they know all the answers in advance and immediately send[maybe they can be cheaters]

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I think that they will review this. It happens that they suddenly roll back all the ratings of the past rounds and then edit some things then you get back your rating; I think in that time, they review all kinds of things that might make the round unfair, so we'll just wait.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Problem B,C,D have completely different coding style/format. Hex_10EFFB_ is definitely suspicious.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -40 Vote: I do not like it

      I apologise for the fact that more than one person finished the race together. I am willing to be disciplined accordingly and promise that this will not happen again. Sorry！

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -11 Vote: I do not like it

gooooood contestttttttt___akfla

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to digest this fact that, F1shHead who had a rating of 1359 and got a rank of 3984 got -1 delta, whereas I had a rating of 1338 and even got a better rank of 3556 but still got -23 delta. I don't find this appropriate. Can anyone help me figure out what am I missing!?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You get a fixed amount of extra rating during your first six contests. Notice that this contest was their sixth contest, meaning that they got extra rating. You have done more than six contests, you don't get extra rating.

    (This is not how the rating system works exactly, but it's a decent simplification.)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for the clarification. I was just wondering that, in general, does the performance in the first six contests affect the rating in the future contests also?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        immediately, obviously yes, but not in the long run.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible I'm still grading grades. your first six rated contests are grading your grades.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +36 Vote: I do not like it

Chinese: 很符合我对中国场的想象！

It fits my imagination of a Chinese round!

Div1 A is a great classification discussion trash question!

Div1 B is a classic counting garbage problem!

Div1 C is a large code volume classic dsu rubbish problem!

Div1 D is classic Chinese data structure with super large code volume and weak intelligence litter problem!

Div1 E is a waste problem because only one passed it!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    I agree with you. And your English is GREAT!

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    as a person who lost rating due to div1B, i think its one of the best problems i have seen.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +22 Vote: I do not like it

      I think it is a classic problem. If you know the theory of tree centroid, this question should be relatively simple. But if you don't really understand it, it may be a great question for you, but I don't think that makes it a good question for everyone.

      And about Div1 E, it is a traditional CNOI problem. Huge code volume, huge data structure, but only two hours of competition time, so it's not comfortable for CF.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        "I think it is a classic problem."

        I would believe you if you didnt create an alt for shitposting

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Stop showing off your pitiful level, it will only make you look like a loser.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I'm not showing, but criticizing the competition.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

I love not being able to open codeforces in public without looking like a weaboo

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is div 1 and div 2 held separately instead of 1 open?

Most of the problems are identical and for the ones that aren't either a div 1 user will do both in <= 10 mins or a div 2 user will not get that far.

Why is there 2 separate contests then instead of 1 open contest?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

What's the issue with CF. Its opening on phone but not on pc.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I was reminiscing about Luo Tianyi's Vocaloid while solving the contest.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

I'm a little curious about why Yuki__S2008 used inline assembly to solve both problems D1 and D2. However, on the first 3 wrong answers on D1, he or she used normal C++ codes (refer to this submission). Can anyone explain a little?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i suppose his nickname must be like: assembly fun fun fun

    → Reply