Gellyfish's blog

Codeforces Round 901 (Div. 1, Div. 2)
By Gellyfish, 3 years 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?
»
3 years ago, hide # |
 
Vote: I like it +68 Vote: I do not like it

orz

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

Hi

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

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

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

StO

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

Do Gr-app Dream of Electric Jellyfish?

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

orz njwrz for providing user solutions for all the problems!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

OMG 5000 D1G, so heavy round...

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Unfortunately conflicts with ICPC North America Qualifier :(

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Honored to be a tester!QwQ

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

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

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

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

→ Reply
»
3 years ago, hide # |
 
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 Gellyfish

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +11 Vote: I do not like it

.

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

Hope my rating can be risen!

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

Look at the score distribution, so weird...

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

omg 2 festivals round

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

Will try my best to reach the specialist.

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

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

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

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

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

    What is LeetCode?

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

    -- deleted because my memory sucks--

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

hello.

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

21h35 -> 00h35 in VN x_x

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

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

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

rated?

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

hopefully atleast +6 this time

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

Happy the National Day of China!!!

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

Grandmaster when?

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

Happy Chinese National Day:D

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

My first Div1.

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

scary score distribution. 1250 to 2000 jump

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

LOL CLown1331 is actually a real clown

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

hope to get positive delta :)

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

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

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

tourist vs Benq Round

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

I don't have any fun in it

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

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

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

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

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

this comment is deleted

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

Thank you for giving me an unhappy holiday :(

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

Casting an ancient Roman curse on the round author

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

That was indeed a llong round.

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

mathforces

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

Where is testers for specialists??:))

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

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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

How to solve D1B?

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

orzdevinwang :)

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

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

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

How to solve C.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +20 Vote: I do not like it

I cannot clutch B I am going to kms

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

What's the casework solution of D1A?

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

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

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
Vote: I like it -45 Vote: I do not like it

Is there any hopes of this contest getting unrated?

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

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

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

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

what a bad contest

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

what type of problem is d1b :sob:

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

Let's discuss the solutions.

How to solve D?

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

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

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

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

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

Questions were tricky rather than difficult.

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Expert, here i come

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

RIP

RIP

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

Where does D1C probability dp formula come from?

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

Todays Contest was Awesome Thank You Gellyfish and everyone who made this round possible .

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

Speedforces :o

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

Here is a Video Editorial for Div2 B/Div1 A

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

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

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

Again a devastating Round!!!.. for me

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

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

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

c question was pure gold in div 1.

→ Reply