prvocislo's blog

Codeforces Round #945 (Div. 2)
By prvocislo, 7 months ago, In English

Ahoj, Codeforces!

We are excited to invite you to participate in Codeforces Round 945 (Div. 2), which will start on May/17/2024 17:35 (Moscow time).

The problems are authored by TimDee and prvocislo.

This round will be rated for participants whose rating is below $$$2100$$$. Participants with higher ratings are encouraged to participate out of the competition.

You will be given $$$6$$$ problems and $$$2$$$ hours to solve them. The scoring distribution is bellow. One of the problems will be interactive. Please read this blog to get familiar with this type of problems.

We would like to thank everyone, who made this round happen:

Scoring distribution: $$$500-1000-1500-2000-2250-3000$$$

Good luck, have fun and see you on Friday! ✩₊˚

Upd: Congratulations to the Winners!

Div 2:

1) _MyGO_Tomori_

2) Sxy_Limit

3) LofiGirl

4) prins

5) SXWZ-Queenie

Div 1+2:

1) BucketPotato with first AK!

2) gamegame

3) hitonanode

4) abc864197532

5) peti1234

Upd2: Editorial is out!

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

»
7 months ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester, I enjoyed testing this round. Also, satyam343 orz

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

    Can you briefly explain, what testers do?

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

      They just enjoy testing the round, as he had said.

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

        So they solve all problems before the contest? Is this testing? If it is then it's quite cool!

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

          Pretty much. You do the round before it is held and give feedback to problem authors. You can also upsolve and give suggestions and feedback to authors even after testing. Basically helping with problems as it's much easier to make good problems when you have opinion from a lot of people.

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

          It's what you mention — with some goals; broadly, there are two types of testers:
          - those that give the contest and opine on the overall quality (difficulty gradient/topic bias etc)
          - those that scrutinize the problems in detail, evaluating all aspects of the problem; its difficulty, constraints, wording, test-quality, some go the extra mile and test to make sure that poor solutions don't pass (though I believe this falls on part of the setter)
          At times, there is also an overlap of the two; after evaluating the contest as a whole, a tester can also individually scrutinize problems in detail.

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

    satyam343 orz

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

As a loyal tester, I wish you all the best!

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

Hi! As a newbie tester I would encourage everyone to take part in this round and I would like to thank all the people who took part in organizing this round — especially prvocislo ! :D

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

Well done prvocislo, I am looking forward to Friday :-)

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

As a tester, I tasted so you could enjoy. GLHF!

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

As a tester, prvocislo TimDee and satyam343 put a ton of effort into this round. ORZ

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

LET'S GOOOOOOOOOOOOOOOOOOO

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

As a tester, problems are:

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

As a tester, I hope the participants will enjoy solving the problems as much as I did. Also, satyam343 orz.

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

romanticforces

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

Does CF allow someone who cheated (https://mirror.codeforces.com/blog/entry/120675) and never showed remorse for his actions to author contests? What I want is not that he shouldn't author contests ever, what I want is for him to apologize publicly and say that what he did was wrong, and maybe return the 2 TON he got from cheating.

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

    dramaforces

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

    MikeMirzayanov Can you please tell why no action was taken against him despite him cheating in many contests using alt accounts, and he never apologized or showed remorse for his actions?

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

      The perception among the top contestants is generally that using alts is not a bad thing, and I kind of agree with it (although Mike does not given that zh0ukangyang got banned, but that was probably a special case anyway, but I digress). It has a caveat though: You should never, and I repeat never, use two accounts in the same contest (obviously), which he has violated several times, and even worse than that, he has used two accounts in a contest with prizes, therefore effectively taking away one contestant's 2 TON.

      Of course, you could argue: "Well 2 TON is chump change, who the hell cares?", and I agree yes, this sort of mindset does have a place in certain situations, but not in this one. Why? Well for starters zh0ukangyang got banned even though all he did was take 3000 measly internet points from other participants, so it stands to reason that a person who takes 2 TON should have some action taken against him. Also, without all of that stuff, like cheating = bad???? hello??? a person who cheats should not get away scot free, like that's what I believe, maybe other people might believe something different, but yknow I've spoken my piece I guess

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

        Using alts is still cheating anyway, cos you're still taking some rating from other people. If you want to be against cheating, be against it fully.

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

          Yes, that is true. I personally don't have any alts, but I can see a ton of reasons why someone could create alts, the most frequent of which is that "I have only an hour to participate in contest, but I still want to participate". If CF introduced a feature like Atcoder where you can participate unrated, that would be great, and would probably reduce the use of alts by a lot.

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

As a tester, I tested!

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

World Telecommunication Day !

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

as a participant i won't participate if problem C Or D is interactive

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

    as another participant I don't think this is a wise decision. If you don't attempt harder interactive problems you will not improve at them.

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

As a tester, I enjoyed testing this round.

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

As a tester I am afraid to say that I'm no longer a specialist to make this round special

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

Why is the time changed? I remember it started from 17:00 UTC+8

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

As a tester, the problems are of high quality and I would recommend the participants to read all of them.

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

It was my first time testing a round, I really enjoyed it, all the best for it!!!!

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

Hopefully, the problem statements will be short & precise just like the announcement! :)

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

one of the problem will be interactive

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

is it rated?

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

Ok cheater

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

This will be my birthday contest :)

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

    Happy birthday! I hope you will enjoy the round :D

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

As a participant, I wonder why the time has been changed. It would start at 17:05 UTC+8 on May 16th when I registered.

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

    Same, the original time just barely didn't collide with my uni, the new one does >:(

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

Pray for Expect :3

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

Plz.start on 17:05(UTC+08) :<

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

GL&HF&high rating!

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

Thank you all for organizing this. Hope i can manage to solve up to problem C.

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

Lovers made me contest, Tim is fall in love with prvocislo. This contest will be a very romantic

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

Congratulations prvocislo, looking forward to your round :D

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

romantic forces 🤡

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

I wish everyone could reach their destination by this contest.Best of luck all the participants.

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

Today's contest in "Calendar" was scheduled: 15:05. I got ready and saw that: 20:35. Anyway I'm ready!!!

→ Reply
»
7 months ago, # |
  Vote: I like it +25 Vote: I do not like it
  • Codeforces Round 941 (Div. 1)
  • Codeforces Round 942 (Div. 2)
  • Codeforces Round 943 (Div. 3)
  • Codeforces Round 944 (Div. 4)
  • Any guesses?
→ Reply
»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

A > B,C

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

    A for me was in reading the constrain after 2 hours of trying to casework it

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

Receiving clarifications for A about 7-9 mins into the contest after 1 failed attempt to answer the "original" problem is pretty underwhelming.

Bonus points for MASSIVE confusion after the first submission failed on pretest 1.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -25 Vote: I do not like it

.

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

Anyone proved the validity of C?

I thought of a greedy solution, check if it's possible to maximize at indices $$$(3, 5, \dots, n-1)$$$ or $$$(2, 4, \dots, n-2)$$$, then take the case with better score.

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

    I skipped the sequence having a[i]=1

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

    As long as $$$1$$$ is not one of the chosen elements to be local maximums, then such construction will lead to values $$$\geq n+2$$$ for local maximums and $$$\leq n+1$$$ for other values.

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

      I see. This claim seems to assure that my solution is correct (yet slightly redundant as excluding $$$1$$$ is done only at the final comparison). Thank you.

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

    Just choose the case that ignore 1 cuz for example if n=8

    a-> ..8 1 7.. p-> ..1 8 2.. res -> ..9 9 9 ..

    which not valid solution..

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

    If one of them have better score, then the smaller-score one will have the element '1' inside it. The fact is that every elements will be at least n + 1 after the transformation. So if the we try to maximize the position having the element 1, it couldn't be the local maximum.

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

    Take the one with n or if n is on the edge, take the one that is further away from n.

    If you take the one with n, worst case, you have to maximize 1, 2, 3, ... n in order. To 1 let's match up n in ans permutation and to 2 let's match up n — 1 and so on and so on. The minimum sum we can get is n + 1, n + 1, n + 1 ...

    To be sure they are the local maximums, the worst case scenario of the neighbors are that they are n — 1, n — 2, n — 3 ... to n — 1 let's match up 1 in our ans permutation, to n — 2 let's match up 2 to n — 3, 3 ... and we see that our neighbors are n, n, n in the worst case. Since n + 1 > n, this works.

    There is similar logic when n is on the edge.

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

    Since it is even you can always achieve the optimal number of local maximums in an array. The only thing you need to watch out for is to make element N, a local maximum, and if you do that it can be proven that every element that is supposed to be a local maximum will be >= N+1 and every other element < N+1. Just add 1, 2, 3, 4.... to local mins in increasing order so at worse that would be (N-1)+1, (N-2)+2 ... you can see that each is at most N, and do the reverse for local maxs 1+N, 2+(N-1) ... each is >= N+1.

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

good round

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

is it just me or was C kinda tough to implement?

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

    It was very easy to implement, the observation was the difficult part imo.

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

      dang I must've overcomplicated it then

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

        Take a look at my submission, I see your code got very messy. 261386987

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

          Thanks broski. It seems like we had the same greedy strat but this one is much more concise.

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

PTSD

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

Almost toughest Div2. BCD are too hard for their positions and D is the strangest problem of my CP journey...

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

    Lol I thought I was the only one thinking B was odd. Counting prefixes bit-by-bit should be C at least.

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

      I didn't count prefixes. I just split the numbers into bits and found the length of the longest sequence of zeroes in the resulting arrays.

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

        Exactly, just sort the indices of elements with each bit and take the max difference between them, no need for prefixes or binary search or anything similar.

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

        Ah, I see. I must have done dumb things under pressure. XD

        Still, bitworking for B does seem overboard a little bit. Maybe 1250 is a more proper score for it.

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

          I get what you're saying, but nothing compares to having an incorrect russian A statement to me. Wasted 10 mins because of it, more than i spent on B.

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

            That part, I could empathize with (though I escaped it since the English ver did justice). Kinda sorry for your bad luck there.

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

          Same lol, I used Sparse Table and Binary Search. Ig I really over killed it.

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

    Out of curiosity, what makes D so strange in your opinion?

    It feels fairly normal for a CF interactive problem to me.

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

      The interaction and the output format is very weird. What I expected: I can ask $$$l, r$$$ and the answer will be $$$f(l, r)$$$. (I know that's not interesting because $$$f(l, l)=$$$ $$$a_l$$$) And the output should be the array or some natural proterty of that.

      By the way nice problem.

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

      Straightforward thinking leads $$$O(n \log n)$$$ (but maybe with small constant) queries, and try to cut down into $$$O(n)$$$ leads back-to-back wrong ideas.
      And splitting $$$2n$$$ into $$$n+n$$$ feels bad because asking $$$?$$$ $$$1$$$ $$$m \times i$$$ ( $$$1 \le i \le n$$$ , $$$m$$$ is a (fixed) integer) leads easily shortage of one of $$$n$$$. The actual solution is finding maximum and bruteforcing with some upperbounds, but later one costs $$$\le n$$$ queries is very unnatural I feel.

      Maybe the unnatural situation of the problem also calls my feeling.

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

        I think so too, i would say the less number of solves is partly due to the un intuitive solution and setting of the problem

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

        Why does it feel unnatural to try and split the latter $$$n$$$ into checking $$$\frac{n}{k}$$$ options that each require $$$k$$$ queries? Or did I misunderstand something?

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

          When I don't know the solution, fixed $$$k$$$ looks like shackle rather than advantage so I get lost, and I found the fact your figured almost after write my code. (Noticing after is easy but solve from $$$n/k \times k = n$$$ is hard and I feel the solution is just happened to work well or something that)

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

How to solve C?

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

    1.Divide the array into halves based on even and odd index.

    1. Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.

    2. Sort both halves.

    3. Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.

    4. Same as above with array without peaks but with 1 to n/2.

    5. Print

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

Proud of myself by solving C with proving its validity, not by guessing

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

how problem B was solved?

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

got 180 score on A. couldn't solve anything else. bye bye pupil! :sob:sob:sob

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

my hardest div.2 till now

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

Happy to solve B, BS op!

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

can anyone explain the approach for problem-C ?

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

    1.Divide the array into halves based on even and odd index.

    1. Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.

    2. Sort both halves.

    3. Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.

    4. Same as above with array without peaks but with 1 to n/2.

    5. Print

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

please don't give spoiler

in problem D.
we can find max element a_max in n queries 
the ans m will be some multiple of a_max there will be n such possible values of m but don't how to check them all in rest n queries

please tell me if im in correct direction and need some more observations
or im too far from the soln. Thanks!

upd : got AC, we only need check first n / k multiples of a_max

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

    You're going in the correct direction.

    If you want a (somewhat spoiler-ish) hint:

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

Worst A ever!!! A > B

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

A: I guessed we should greedily remove (1, 1) from 2 highest score until there is 0/1 positive score left.

B: I guessed it's binary searchable.

C: I guessed only considering position 2 and 3 is sufficient.

D: What should I guess? XD

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

Author please tell me why interactor not giving maximum element in the array for sample test case 3 for the following code.

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

    Every time it's giving 0 as maximum, but surely it will give some positive

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

    I think that you may need to read something after you give an answer, because the interactor in this problem will return 1 or -1 after you give an answer. I also WA in pretest 1 and got confuse but after I figure it out and read one more thing after giving my answer, I passed the pretest.

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

got TLE for problem B

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

how to solve D?

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

    1. Use n guesses to find largest element in array. Can be done by guessing ? n s*n for s in range n to 1. s is the largest number in array

    2. If m exists m must be a multiple of s. m must also be a maximum of s/k, because anything greater cannot exist as m=s/k, divide array into k equal parts if all elements in array are s.

    3. Can brute force with those 2 observations. n/k solutions to check. Each solution takes at most k queries.

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

    Find the maximum element $$$mx$$$ in $$$a$$$ by making queries $$$(1,n*n), (1,n*(n-1)),\dots$$$. If you get $$$r=n$$$ on query $$$(1,n*b)$$$ then $$$mx=b$$$.

    Now since this maximum element is present in at least one of the $$$k$$$ subarrays, $$$mx$$$ must divide $$$m$$$. Also, if $$$m=b*mx$$$, every subarray must have length at least $$$b$$$. So we only need to check multiples of $$$mx$$$ upto $$$\frac{n}{k}mx$$$. In each candidate for $$$m$$$, just query $$$k$$$ segments starting from position $$$1$$$ and check if these segments cover the array.

    This takes $$$n$$$ queries to find $$$mx$$$ and another $$$n$$$ queries to check all values of $$$m$$$.

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

      Damn, I figured this one out during contest but forgot to replace $$$m$$$ with $$$b \cdot mx$$$ and thought it's $$$O(n^2)$$$ queries :(

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

    you'll need to find the max, it is easy to find in $$$n-1$$$ queries (iterate over multiples of n)

    once, you've got max (call it $$$a_{max}$$$) then iterate over multiples of $$$a_{max}$$$, note that $$$m \leq a_{max} \times n$$$, candidate $$$m$$$ is a multiple of $$$a_{max}$$$

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

Problem C, I've tried some special case line n = 6 Assumpt P = {6 1 4 2 3 5} so optimal Q should be = {1 4 5 3 6 2} but not Q = {1 6 3 5 4 2}

and otherwise with P = {6 3 2 4 1 5} So i come up with solving two case but my idea seems to be wrong somehow idk. Can sb help me with this 261394519

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

It was the most fun Div.2 ever, thank you!

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

Man, this was a hard contest. Took 51 minutes to solve AB.

Also, why is this wrong for C? I did the same idea as everyone else. Calculate max score for odd indices (3, 5, ..., n — 1) and for even indices (2, 4, ..., n — 2) and then take max.

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

-1e9 downvotes loading

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

Mannn.. wasted 20 min on a corner case in problem A. and wasted almost 1 hr on a simple mistake in problem C.. as well as 4 wrong submissions, giving a heavy penalty... But overall the questions were amazing.

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

C is too bad

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

Finally i have reached master

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

    I would also appreciate if anyone could give me some advice on how to grow from here. I am looking for things like something that you felt you had to change in order to go from M to GM and really anything except for just practice.

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

    Can I be your slave? Plz?

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

      Would you be so kind to enlighten me on what that entails?

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

    Nice reaching master in less than 2 years, any advice for us newbies, kiyotaka?

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

My easy solution for A:

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

    how does it always work

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

      There can be at most $$$\frac{p1 + p2 + p3}{2}$$$ draws between 3 players. But if the total score of any two people smaller than $$$\frac{p1 + p2 + p3}{2}$$$ (for example, $$$p1 + p2 < \frac{p1 + p2 + p3}{2}$$$) then there can only be at most $$$p1 + p2$$$ draws between player 3 and (player 1 & player 2).

      I don't know how to explain it more clearly :(

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

        Your explanation was pretty clear! Very nice solution.

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

    You can apply standart algorithm: $$$s=a+b+c$$$ and answer is $$$\left\lfloor \frac{s}{2} \right\rfloor$$$ or $$$s-c$$$ if $$$s-c\leq c$$$

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

    (p2+p3) and (p3+p1) makes no sense since the numbers are sorted (p1+p2) makes sense if C was bigger than(a+b) but how did you come up with (p1+p2+p3)/2 can you please tell ?

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

      (p1+p2+p3)/2 is literally the case when every match ends with a draw.

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

      Oh, I didn't notice that the numbers are sorted. Each game increases $$$(p1+p2+p3)$$$ by $$$2$$$, which means the maximum number of games played is $$$\frac{p1+p2+p3}{2}$$$.

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

        How can we write math variables and equations with special font and symbols in our comment?

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

Terrible problems.

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

The assumption of finding the maximum value of the array in problem D was nice.

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

Terrible contest...

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

Finally I find my lucky contest lol :>

Waiting for another even luckier contest to push me to CM :>

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

I'm newbie in here, can someone explain why in the problem A test case 1 => 3, 4, 5 the answer is 6. If i count manually i just can make the max of draw is 5. With the following operation:

  1. A & C draw so 1, 0, 1
  2. A & C draw so 2, 0, 2
  3. A & C draw so 3, 0, 3
  4. B & C draw so 3, 1, 4
  5. B & C draw so 3, 2, 5
  6. then B win so 3, 4, 5

I cant find if the max draw is 6 T_T

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

    A & C draw $$$2$$$ times, B & C draw $$$3$$$ times, A and B draw $$$1$$$.

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

      Oh! stupid me :) Thx for the answer, very understandable

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

Is it just me who solve A with a naive dp? Can't even come up with any solutions now xD

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

I don't like to guess T_T

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

Sooo fast rating updation!!!

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

Hi all!

Can someone help me figure out what happened with my B? I solved it using C++20 in my machine (the tests where matching) then I submitted my code to CF and got WA on test case 1. I looked at the results on the submission and one test was different from what I got locally.

Then I switched to C++17 on codeforces, submitted my code again and got AC.

What might be the problem? What I think is weird is that I was also using c++20 locally and there was no problems.

AC submission (c++17): 261375967 WA submission (c++20): 261374878

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

    Bro, I got TLE on case 1. Although, running well in my pc. Don't know why!!! Finally, I have managed to get accepted.

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

This C solution seems simpler than the other ones I've seen. Just take some set of nonadjacent (n-2)/2 elements to make as peaks such that none of the taken ones are equal to 1. Then, you can force those positions in the array a to have values >= n + 2, while forcing all other positions to have values <= n + 1, which guarantees that those become peaks.

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

got skill-issued, and somehow increased rating lol

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

How to solve B?

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

A bit tougher than usual Div2, but the problems were amazing.

I felt B > C, especially proving that binary search works in B has taken a lot of time.

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

BUCKETPOTATO ORZ

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

I solved A in like 1hr and B in next 30 min. B without binary seach.

Why do I suck at A kind of problems.

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

That was a hard one, anyway I enjoyed it.

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

Pretest Exactly Maintest WOW!

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

Very nice round!

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

A little difficult, but absolutely a nice contest and high quality problems.

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

'B' was quite tough compared to usual div-2.

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

Great problems!

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

Any approach to solve this problem?I am stuck

You are given a tree of 'N' vertices, rooted at vertex '0'. You assign a random number in the range '[0, M — 1]' to each of the vertices.

Let us define 'heap-like' as the property that: for all vertices 'v' in the subtree of any vertex 'u' of the tree, the random number assigned to vertex 'u' is less than or equal to the random number assigned to vertex 'v'.

Find the probability that the resulting tree is 'heap-like'.

The answer should be found modulo 10^9 + 7. Formally, let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q !≡ 0 (mod M). Output the integer equal to p * (q^-1) mod M. In other words, output such an integer x that 0 <= x < M and x * q ≡ p (mod M).

For Example : Let 'N' = 3, edges = [ [ '0, 1' ], [ '0, 2' ] ], 'M' = 3. Random number assignments that result in a 'heap-like' tree are [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1], [ 0, 0, 2 ], [ 0, 2, 0 ], [ 0, 2, 1 ], [ 0, 1, 2 ], [ 0, 2, 2 ], [ 1, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ], [ 1, 2, 2 ], [ 2, 2, 2 ]. The total number of possible assignments is '27' and the '14' assignments above result in a 'heap-like' tree. Thus, the probability of a heap-like tree is '(14 / 27) % (10^9 + 7) = 185185187'.

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

Hello there! I had a funny little solution for B which involving Segment Trees.

My code : 261728503

Solution :

Hope you understand the solution, if you have any queries feel free to ask, and I'll try to help if possible.

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

I think problem D,E are both clever and interesting.

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

really cool round! Problems have quite short and nifty codes and the ideas are really cool. well done on setting D and E (especially D)

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

This is the first time I am experiencing rating decrement after roll back!!!

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

hello guys, I have participated in code forces round 945 div2 . i have solved a and i have used some bit manipulation notes and took help of gpt i had idea but was unable to get some part of code. and i have solved c on my own. but it showed plag and skipped entire contest and rating decreased from 1359 to 1097. What to do now.

→ Reply