Gellyfish's blog

Codeforces Round 901 (Div. 1, Div. 2)
By Gellyfish, 15 months ago, In English

Hello, Codeforces!

I'm pleased to invite you to Codeforces Round 901 (Div. 1) and Codeforces Round 901 (Div. 2). It starts on Sep/30/2023 17:35 (Moscow time). It also means, the National Day of China arrives during the round. Wish you a nice vacation! 🎉🎉🎉

For both divisions, you will have 3 hours to solve 7 problems.

I would like to thank:

Especially, I would like to thank errorgorn for his great contribution to the round, njwrz for providing user solutions for all the problems, Kevin114514 for making the announcement and tutorial more readable.

Finally and most importantly, I would like to thank PersistentLife for helping me with everything patiently all the time. This round can't happen without him.

The main character of the problems will be Jellyfish, a sweet little girl. 🍏🍏🍏

Score distribution:

  • Div.1: $$$500$$$ − $$$1250$$$ − $$$1500$$$ − $$$2250$$$ − $$$3000$$$ − $$$4000$$$ − $$$5000$$$

  • Div.2: $$$500$$$ − $$$1000$$$ − $$$1000$$$ − $$$1250$$$ − $$$2000$$$ − $$$2250$$$ − $$$3000$$$

Good Luck & Have Fun! 🔥🔥🔥

UPD1: Editorial is out.

UPD2: Congratulations to the winners!

Div.1
Div.2
first solves in Div.1
first solves in Div.2
  • Vote: I like it
  • +178
  • Vote: I do not like it

Comments Comments (203)
| Write comment?
»
15 months ago, # |
  Vote: I like it +68 Vote: I do not like it

orz

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

Hi

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

fun fact about Div $$$1$$$. $$$5000 + 4000 > 500 + 1250 + 1500 + 2250 + 3000$$$

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

StO

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

As a tester, I enjoyed the round and found some very nice problems! I recommend you to participate.

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

As a tester, I have no clue how come we have seven problems for each division now.

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

Do Gr-app Dream of Electric Jellyfish?

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

Wow, the round have many tester including thenymphsofdelphi — one of the Vietnamese strongest coder. So the round must be good.

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

orz njwrz for providing user solutions for all the problems!

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

As a tester, I really love some of the problems in this round!

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

thankyou codeforces for giving java 21 support , it was launched just a week ago and is now available to submit on codeforces

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

As a tester,I really enjoyed the problems in this round. And div.1 G is a difficult and interesting problem, hope someone can solve it in the contest!

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

As a tester, I can say that the problems are very educational and I really enjoyed them! Hope you have fun practicing and good luck to all!

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

OMG 5000 D1G, so heavy round...

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

Hope to reach expert on this round. Good luck to everybody participating!

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

Unfortunately conflicts with ICPC North America Qualifier :(

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

    Looks like it should be fine, NAQ only starts 25 min after the round ends :)

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

Exciting, it'll be hard to wait 3 days, hope to get at least +5. GL & HF

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

Honored to be a tester!QwQ

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

As a tester, I recommend the Round to upgrade your rating ^_^

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

As a participant, I predict that this contest will be perfect!

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

As a tester，I found many good problems in this round. Wish you good luck~ sto Atomic-Jellyfish

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

As a tester, I had fun with the problems and I hope you do too!

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

.

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

Hope my rating can be risen!

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

Look at the score distribution, so weird...

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

omg 2 festivals round

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

Woah, a 3-hour round. I, personally, will not be able to focus for that long :sob:

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

Will try my best to reach the specialist.

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

Only one author for all problems? .... Oh, he is Atomic-Jellyfish, it's okay.

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

Hopefully I will make optimal use of the 3 hours, but not go to problem C or D and feel hopeless

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

Clashing with LeetCode Biweekly Contest :(. PLease try to schedule these at some different times in future.

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

    wdym, I think Leetcode should reschedule theirs, not the other way

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

      LC contests are always at the same time. I will give LC contest because they arent mathforces af

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

        But Codeforces contests are almost always held at the same time as well. I don't see any logic in your statement. Maybe you should get your priorities straight with a grain of reasoning.

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

          I can predict when will there be a LC contest 1 year from now.

          Can you do the same for CF contest? Can you tell me whether there would be a CF contest at 5th Jan 2024.

          Try to get my point instead of just arguing for the sake of argument.

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

            No, but at least I know most of them will be held at the same hour of day. I know rescheduling is a hard decision. But how does the schedule being predictable account for deciding that one contest should reschedule in favor for another? Tell me. You're saying you have a point. Tell me where your point lies.

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

        I too prefer contests where I dont need to think and just regurgitate my data structures and algorithms knowledge.

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

    What is LeetCode?

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

    -- deleted because my memory sucks--

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

hello.

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

21h35 -> 00h35 in VN x_x

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

Yeaah！festival round! hope i can increase my rating! Orz

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

rated?

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

hopefully atleast +6 this time

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

If you think that person who did pupil testing is a pupil, then you are a CLown1331

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

This round is very special! It has 7 problems and 3h to solve problems.

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

I just broke up because I declined my girlfriend's invitation to go out tonight so I could participate in Codeforces contest :D

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

Can't wait to solve 4 problems in Div2 for the first time. I hope i reach specialist today. Good luck everyone.

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

This may be my first time to take part in div1. Hope I can be a master. QAQ

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

Happy the National Day of China!!!

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

Grandmaster when?

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

Happy Chinese National Day:D

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

My first Div1.

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

I'm so excited about this one,Im going to fight for C today really hard.

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

scary score distribution. 1250 to 2000 jump

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

LOL CLown1331 is actually a real clown

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

hope to get positive delta :)

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

I'm using Chrone on Mac. The digits in equations are in sans-serif font, which makes it really annoying to see some of the eqautions. Does anybody experienced this before or have an idea how to resolve it? It seems it only happens in CodeForces, and with other browsers like Safari this does not happen.

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

    Try m1.codeforces.com (usually refresh will work when I see this (but I don't use chrome :( idk if it will also work on chrome

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

      I want to try, but there's no way to take a look at a problem statement until the contest start...

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

        sad :( maybe you can try to save the page before mathjax works. read the words between $s may help(?

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

Why are two starting letters Black in MagicalFlower handle? :O

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

tourist vs Benq Round

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

I don't have any fun in it

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

    This is the first contest during which I went to its announcement ._.

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

I'll never ever take part in Chinese contests again. Ծ_Ծ

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

I think that I willn't participate in Chinese rounds after this.

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

    It's a really good opportunity to learn something well known in china, ain't it

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

this comment is deleted

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

    It is better to ask when the contest is finished

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

Thank you for giving me an unhappy holiday :(

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

How many math questions do you need?

Problem Setter: Yes

P.S: (just my opinion) Didn't enjoy much, where I could think of using algorithms for mid-rated problems rather than checking my mathematical ability :(

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

Casting an ancient Roman curse on the round author

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

That was indeed a llong round.

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

Who in their right mind would think Div2B is 1000 rated, and is the same difficulty as Div2C? Have the authors actually lost touch with lower rated contestants? There has to be more pupil and specialist testing for future contests.

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

How do you solve div1C? I could probably have done it if output format was modulo a prime instead of double but now I don't know

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

mathforces

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

Where is testers for specialists??:))

→ Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it
Graph Representation of Test Case 2

In problem Div1C/Div2F, in test case 2, how is the answer 0.625?

Except node 5, every other node has possibility 1 for successful mission.

If at node 1, and Asuka select v2 = 5, v1 can be 2,3,4. One of these 3 roads will get destroyed and with remaining roads we can always reach 7.

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

    Jellyfish will not know Asuka's choice before making her choice.

    I also got stuck in the same place as you, but I asked for clarification and this was the response.

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

    I think Jellyfish picks before Asuka, so she cannot mirror her choice.

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

    ohhh, got confused becoz of this statement

    Jellyfish knows that Asuka will choose a road randomly. Now, Jellyfish wants to know, if she chooses the roads optimally, what is the maximum probability of the mission being successful.

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

How to solve D1B?

→ Reply
»
15 months ago, # |
← Rev. 7   Vote: I like it +10 Vote: I do not like it

How to do D2F? I know it is tree dp, but how to calculate the probability at each vertex?

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

orzdevinwang :)

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

Can someone who solved all problems in Div.2, explain the problems?

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

If I don't get FST, It will be my best performance ever.

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

How to solve C.

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

Refreshing when actual problems, for my level, start from B :) .

Thanks for the contest!

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

I cannot clutch B I am going to kms

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

What's the casework solution of D1A?

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

i dont think i've been this afraid of systests in years

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

The server was down for the last few minutes (403 Forbidden) :(

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

What is the intended solution for B? I did something fishy and got AC but with 1980 ms (so high chance I fail systest) I ran normal BFS and realise around 2000 states in total which should be fast enough, if not because of a map, so I did some preprocessing to reduce a b c d and m into 8 bit numbers (since bit combinations of at a particular position of (a,b,m) will give the same result of (c,d) after some operations), then I use a global array to store distances to pass.

Also if not because of the editorial of this: https://mirror.codeforces.com/contest/1866/problem/M I wont have solved D

As expected, I failed systest... (rip IGM dreams)

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

    I do the exact same thing and it ran in ~900ms without anything special. I'd guess this is the intended solution, not sure why yours performs worse.

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

    I did the same and got a lot of TLE.

    Than i started to memorize the solutions for the possible (a,b,c,d,m) tuples among the test cases -> pretests passsed with 670 ms xd

    So there are several identical testcases in a test

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

    I did the same thing, though I sorted the testcases in such a way, that I only run a single BFS for the same 8bit number. And then un-sorted testcases into initial order. It passed in 170ms.

    I also used a vector instead of a map to keep the distances.

    Awesome problem!

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

Is there any hopes of this contest getting unrated?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +42 Vote: I do not like it 
    if(delta>0)cout<<"unrated";
else cout<<"rated";
    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2 Hours spending on Problem E but kept getting WA!!!

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

I actually think Div.1 E is too standard. It equals to asking the number of Cartesian tree with $$$n$$$ nodes and the sum of subtree size $$$\geq lim$$$. I suspect that there is an original problem for that.

Also, I think Div.1 B is too hard for its place. Observing the standings, I think it's better to swap B and C.

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

Div.1 A = Div.2 B but Div.1 B = Div.2 E What's this?

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

    Fr it threw me off so much. After struggling with B and C for so much time, I open the div 2 standings to see my friends, and all of them have solved 2D, that too fast!!!

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

Worst contest ever. Need to practice more and more..

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

How to calculate the probability for transition from $$$u \rightarrow v$$$ in Div1C?

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

Could not submit D becuase the code length limit exceeded. When I finally minimized the code it was two minutes after the content had ended. That's my fault but. Please. Increase. Code. Length. Limit.

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

Although they drove me mad...

but 1B and 1C are very VERY interesting problem with fantastic trick! (for me)

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

    Could you explain the idea of 1C?

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

      my english is poor. so u can look at my code f[i][j] = there's i roads and you successfully chose the j-th

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

what a bad contest

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

what type of problem is d1b :sob:

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

Let's discuss the solutions.

How to solve D?

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

    I compressed the array into pair of <value, freq> ex 0 0 2 3 5 becomes (0, 2) (2, 1) (3, 1) (5, 1) then used 1d dp.

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

Though there are 7 tasks, so heavy to treat D1ABC...
I guess we can have two Div1 rounds from this problemset.

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

div2 A,B were cool C got on my nerves it's the kind of math i don't like.

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

Is there any legitimate solution for D1D besides "idk ternary search should work to optimize this dp" (I dont like waiting for editorial so that is why I ask)

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

    Write the math and you realise the answer is sum(Si/mi) * 2 — n. Si is the sum of m0.. mi Then a simple DP follows

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

      Sir what simple dp, simplest dp requirrs m^2*n (fix mi, fix Si for each i). How do you do better than this

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

        $$$s_i+m_i*(n-i) \leqslant m$$$

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

          😳 😳 😳 😭 😭 😭 how could i be so blind 😭

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

        I made a claim that mi is increasing. Then the number of transitions become mnlogm

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

          funniest thing is I knew that but didnt think to do the $$$* (n - i) $$$ part 😭

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

    idk divide and conquer DP should be able to optimize this.

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

As a participant, I didn't have fun with the problems

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

Div1 A to Div1 B C was such a huge difficulty jump :/

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

    Div 1's A was Div 2's B.

    Don't know why this was done, but that might contribute to the difficulty spike since it's like if a Div 2 contest went from a B to a E.

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

      Don't know about Div2 E, but I wasn't able to solve Div2 B, rather I solved D and C. .So, for me B preceding E, rather than C or D is very correct. :_)

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

Questions were tricky rather than difficult.

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

Div1 D seems very similar to a problem from SEERC22: https://mirror.codeforces.com/gym/104114/problem/M.

EDIT: the same "local improvement" approach doesn't work in the new problem, nvm

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

Expert, here i come

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

Can someone tell me how to solve "B" that is B. Jellyfish and Game?

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

    I can't prove it, but if they play 4 times the moves will start to repeat, so I simulated 5 and if the number was even I simulated one more.

    225979586

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

RIP

RIP

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

It seems that problem D in div 2 can be done in $$$O(n \log n)$$$ with slope optimization or Lichao segment tree.

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

Where does D1C probability dp formula come from?

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

I have solved 4 problems for the first time in div 2 !(yeee)

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

"Note that the sum of n over all test cases is not bounded." what does this mean in Div2 A problem?

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

    In many tasks you will see statement like "sum of n over all test cases <= 200000" but here there is no guarantee (max n could be max n per test case * max test case)

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

Todays Contest was Awesome Thank You Atomic-Jellyfish and everyone who made this round possible .

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

I dedicate my success in today's round to my two senpais: alinp and BarbutaRobert! Btw I hope TimDee didn't cheat today!

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

how the equation m×|S|−n come out in the problem Div2C? Can anyone explain this? There is no any additional comments about this in Editorial.

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

    Let us assume that $$$\frac{m}{\text{gcd}(n, m)}$$$ is a power of $$$2$$$ . So we can say that $$$\frac{n}{m}$$$ can be finitely represented as some binary representation like $$$\sum_{i \in S} \frac{1}{2^i}$$$.Each individual people is going to get $$$\frac{n}{m}$$$ weight of apples and he will get this weight in denominations of $$$\frac{1}{2^i}$$$ . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces . For an apple of weight $$$1$$$ we can get $$$2^x$$$ pieces each weighting $$$\frac{1}{2^x}$$$ and this will cost $$$2^x - 1$$$ cuts. For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces each weighting $$$\frac{1}{2^i}$$$ and it can be done using $$$\frac{m}{2^i}$$$ number of apples having initial weight of $$$1$$$ and for each apples it will cost $$$2^i - 1$$$ cuts . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we would need exactly $$$\frac{m}{2^i}(2^i - 1)$$$ cuts . Total number of cuts will be $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right)$$$ . We know that $$$\frac{n}{m} = \sum_{i \in S} \frac{1}{2^i}$$$, then $$$n = m \sum_{i \in S} \frac{1}{2^i}$$$.So, the expression $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right) = \sum_{i \in S} \left(m - \frac{m}{2^i}\right) = \sum_{i \in S} m - \sum_{i \in S} \frac{m}{2^i} = m|S| - n$$$.

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

Speedforces :o

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

Here is a Video Editorial for Div2 B/Div1 A

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

Странный раунд, но в принципе задачи нетипичные для дивов, было даже интересно решать)

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

In Div1C, How do we calculate the probability transition formula for the cases where the out degree is even. For odd it will be just $$$1/n$$$

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

Thanks to tourist, we found out that the tests in Div1D were not maximally strong.

In my dynamic programming I search for the best value only in the heuristically selected range [previousBest - 5, previousBest + 11]. This got me OK verdict. However, there is a test, where my solution is not optimal enough!

Input:

10 2633

My output:

23.00521162478544

Actual answer, when heuristic is turned off:

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

    Just wanted the researched data to be public. It appears that searching [previousBest - 12, previousBest + 1] is almost always enough, with just a few exceptions:

    (6, 1754):	-26
(7, 1641):	-23
(7, 2485):	-13
(8, 451):	-14
(8, 2972):	-17
(9, 1091):	-22
(9, 1759):	-13
(10, 1173):	-19
(10, 2623):	-56
(11, 1602):	-15
(11, 2616):	-36
(12, 1077):	-17
(12, 2588):	-15
(13, 677):	-16
(13, 2015):	-27
(14, 1153):	-23
(15, 1957):	-33
(16, 2523):	-22
(18, 1219):	-14
(19, 1819):	-20
(20, 2245):	-15
(20, 2709):	-26
(22, 1866):	-20
(23, 1052):	-15
(23, 2628):	-24
(24, 1412):	-16
(25, 1894):	-19
(26, 2539):	-23

    The listed exceptions are "(n, m — n): shift_from_previousBest"

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

    I just tried to hack my AC solution using the test you provided here and it worked.

    So I could have FSTed :O

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

Chinese rounds are great you have to admit, the only thing we need is getting more foreign coders to test

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

The test in Div2 E is too weak. See this: https://mirror.codeforces.com/contest/1875/submission/226052852

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

Again a devastating Round!!!.. for me

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

Never felt more devastated! Completed 4 ques in 1:10, hoping for a very good increase. But TLE in D system test 18. Changed just a map to unordered map and it passed :( I didn't even need an ordered map, didn't know it would have such high penalty :(

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

write a wrong solution to 1C and hacked by znstz2018 a good contest but not that good for a retired

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

bruh, div1a is div2b and div1b is div2e :skull:

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

Is it just me or was this div2 a lot easier than usual?

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

i used ideone and i didn't know about the public thing and you can clearly see that he is the one copying from me because this is the code template i use and you can find it in most of my submissions

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

c question was pure gold in div 1.

→ Reply