RedLycoris's blog

Codeforces Round 872 (Div. 1 & 2)
By RedLycoris, history, 19 months 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 Atomic-Jellyfish 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, themoon, Crying, rui_er, Kevin114514, Lynkcat, lgswdn, FreshP_0325, Umi for red testing the round.

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

  7. Error_Yuan, fishy15, Lyrically. valeriu, yash_0402, smokebellew for purple testing the round.

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

  9. zhy137036 for green testing the round.

  10. tibinyte 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?
»
18 months ago, # |
  Vote: I like it +85 Vote: I do not like it

awa

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

    QwQ

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

      ovo

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

    You bought my participation with that anime picture XD

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

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

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

    Good luck in your achievement!!!

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

    How did you get negative rating???

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

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

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

    damn you're right

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

Why there's no cyan testing?

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

    Good question. Maybe this round is a BIT difficult.

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

      Maybe he was just pretending to be weak.

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

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

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

      I advise u to stop fAKing and wear girls’ clothesxD

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

        That is not possible! You should be my girlfriend!

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

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

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

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

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

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

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

      Don't forget ds.

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

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

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

gl hf

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

Cyan's : Are we a joke to you?

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

orz

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

unfit my schedule but still appreciate

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

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

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

Cute

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

What should I say.

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

RedLycoris Orz

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

Hello, YuezhengLing and LuoTianYi!

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

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

→ Reply
»
18 months 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
  • »
    »
    18 months 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
»
18 months ago, # |
← Rev. 3   Vote: I like it +51 Vote: I do not like it

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

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

    awa

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

Yet another Chinese round. Time to lose ratings.

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

Too much testers. Hoping for an amazing round.

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

Damn, div 0?

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

Why am I here?

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

Please continue this great time!And I love nanbei!

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

Damn, div 0?

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

As YuezhengLing, you gave LuoTianYi a dynamic tree.

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

%%%gezhiyuan %%%sanweitreap

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

You

for participating in this round.

You

is very magical.
→ Reply
»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

1 up rate for cuteness ._.

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

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

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

Anime, good.

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

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

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

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

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

Extremely excited for this contest. Hoping for a positive delta

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

Points distribution?

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

W*c, Vocaloid!

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

Wish rp++

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

As a tester, I tested.

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

    The moon shines, thank the moon.

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

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

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

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

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

Why unusual start time?

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

Friendly time for participants.

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

Can I become CM today?

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

i think that will be a great round.

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

Upvote me to have +ve delta

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

All the best everyone.

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

orz

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

My first Div 1 round. Hope for amazing problems)

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

Wow! Lyrically! btw gl!

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

Good luck!

→ Reply
»
18 months ago, # |
  Vote: I like it +33 Vote: I do not like it
My copy of the picture in the announcement
→ Reply
»
18 months 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
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it might be fit for Chinese oiers

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

wtf, div1B have mathematical expectation.

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

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

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

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

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

How to optimize in D1B2

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

Wrong Answer on Pretest 6.

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

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

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

        For any odd K the answer is always 1

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

        for k = 3

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

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

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

SpecialCaseForces

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

    It is

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

I might've finally reached expert!

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

I am expecting to become a Master excitedly!

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

Brainless D with only 7s TL

What a trash experience

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

    I feel your pain

    Spoiler

    Bro tried everything 😭

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

oof.

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

Div2 D testcase == 'heng heng heng aaaaaaaaaa'

^ ^

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

Nice Problems

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

Chinese culture export

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

How to solve div2 B problem...

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

I hope I can become specialist

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

round approved

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

    I don't think that this is possible too.

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

gooooood contestttttttt___akfla

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

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

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

    I agree with you. And your English is GREAT!

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

      I'm not showing, but criticizing the competition.

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

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

    → Reply