Artyom123's blog

Codeforces Round 924 (Div. 2)
By Artyom123, history, 10 months ago, In English

Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 924 (Div. 2), which will start on Feb/11/2024 12:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.

The problems were authored and prepared by vaaven, silvvasil, Alexdat2000, teraqqq and me.

The round is based on Moscow Olympiad for school students.

We would like to thank

Score distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 2750$$$

UPD: Editorial

UPD2: Congratulations to the winners!

Div. 2

  1. hmmmmm

  2. satellite.

  3. RomkaRS

  4. Alx

  5. hirayuu_cf

Div. 1

  1. SSRS_

  2. maspy

  3. kotatsugame

  4. 74TrAkToR

  5. SSerxhs

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

»
10 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Good luck to everyone. I hope to reach expert in this contest.

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

contemplating taking this contest at 1:35 AM :)

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

The start time is good for Chinese.

Today is Spring festival eve.Happy new year!

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

GOOD LUCK!!!

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

bed time for pacific programmers

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

    bed time for pacific programmers

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

      sleeping time for pacific programmers

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

Hope to maintain my specialist rating.

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

Best of luck everyone

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

Best Of Luck!

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

Hope that Delayforces won't come again

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

Good!

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

need to run out of college class to attend the contest

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

div 2 too hard for me

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

Thanks for making the contest!

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

Good luck! May the force be with us!

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

As a tester for this round, this round is great, please participate!

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

Good start time.

I can participate in contest instead of going to school :)

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

as a tester, i can confirm that the problems are problems

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

    as a tester, i too can confirm that the problems are indeed problems

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

      as a participant, it will be amazing to solve problems which are problems xD.

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

Hope to become master after this.

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

As a taster, the contest was delicious and I ate the problems

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

Nah I'd Win (I will most definitely lose)

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

    (JJK Special joke, hope you get it) First problem: Divide this element into two...

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

      Lol, problem A actually involves dividing into two parts ... cut midway

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

    lmao

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

bad start time, I've school ig I'm gonna be "sick"

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

lets see if i can become specialist

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

Bad time contest for New York contestant

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

The round is based on an official russian competition. I don't know why the authors decided to support the existing system by organizing official events, but I encourage other users to avoid this mistake. Many other competitions are more worthy of your problem ideas and participation.

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

    bro look at your profile picture, i can find it googling "cute авы стим аниме", you can't be taken seriously XDD just go chill somewhere, no need to litter here

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

i hope i could back some rating this contest in which I lost 923 div 3, but div 3 was a fantastic contest

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

Hope to get a negative deltaa so that div 3 becomes rated for me.

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

    Come to my level and you can enjoy smurfing in Div 4 too then

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

Rankup time...

6 contests in a row!

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

Good luck!!!

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

chinese new year : (

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

GOOD LUCK!

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

Happy Chinese New Year! Good Luck!

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

Good start time for Asians

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

Good luck!!!

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

Skipping classes for this contest (my second contest)

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

This is my first comments. Happy new year!!! Please take care of me.

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

Today is a special day for the Chinese (the second day of the Chinese New Year) and it's also a good start time for the Chinese.I think it may be a wonderful contest.

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

Let's skip class and reach specialist.

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

Good start time,I need to work a lot!(After 1 week the semifinal of Olympiad will start)

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

3:05 PM ist Great timing...

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

Will Reach CM after this round

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

Good time. Today is Sunday + I'm free at this time

Good luck for everyone

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

Guess the rating of Problem

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

This will be a fantastic contest

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

good start time, i don't have to sleep

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

Good time, hope i solve A fast

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

Fantastic

Because my mind is more active at 17:35 (UTC+8)

I'm Chinese

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

Good luck!

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

I will have a negative delta but I will participate anyway

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

Happy Chinese new year!Good luck to everyone.

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

Any ways the start time is good for India. Sunday afternoon :)

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

I wish I will have positive delta during Chinese New Year!

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

I hope be expert in this contest!

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

First CF Contest

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

My first contest. Good luck everyone! Happy Chinese New Year!

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it
Me after the contest :
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach expert with this round

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

Judgement failed?

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

glad to see another Mathforces round.

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

nice math contest

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

I am considering whether to die or not,because I only complete question A.

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

    B is just sliding window.

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

      Emm...Are you wanting A cute new student who has only studied for one year to realize that?

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

        Well atleast now you know the name of one more topic that you must learn. Pretty useful, unlike some of these questions that just require math

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

      was there system testing this round ? cuz the results were declared so fast

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

        yes, It completed in like 5 mins

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

          do u have any idea why it was so fast though, the last div3 took atleast an hour

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

            There are less tests than usual in problems A and B.

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

MATHFORCES :((

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

Did they assume us mathematicians?

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

is $$$D$$$ binary search?

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

    Yes. Observe that as you increase the number of squads, the amount lost by b only increases by a fixed amount(b), while the amount gained from adding a new squad, decreases as you add more. Therefore, we should find the amount of squads at which adding a new squad gives less than b. Since the amount given by a new squad decreases monotonically, we can use binary search.

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

      yeah bro I mind solved it but didn't have time to implement , wasted a lot of time in $$$C$$$

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

      Though binary search may work, it isn't actually needed to solve it.

      You can just realize that the number of pairs for a group with $$$c_i$$$ members only increases till the number of groups becomes $$$c_i$$$, so you can just recalculate it for each $$$1 \leq \text{squad size} \leq c_i$$$. This runs in $$$O(n + \sum {c_i})$$$ which is fast enough for the constraints.

      Code — 245818007

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

        ExplodingFreeze why your solution passes time complexity,

        N : 10^5

        max(c): 10^5

        O(N*max(C)) = TLE right? please explain if i missed something

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

          You actually don't have to recalculate every time (I see that he used the pop_back function for the optimisation), so the solution is only O(N+C)

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

          See the last line of the input section — "It is guaranteed that the sum of the values $$$c_1 + c_2 + \cdots + c_n$$$ over all test cases does not exceed $$$2\cdot10^5$$$."

          So $$$O(n + \sum{c})$$$ is by definition fast enough.

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

      This is a convex function, which can more easily be solved with ternary search.

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

    kind of, I get AC with a ternary search for the amount of groups we are doing, run time is O(n * log (max C))

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

Hint for C please

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

      thanks

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

      Yeah, I considered those cases, but still unable to come up with solution. What I came up with after doing some calculations is to find number of even factors of (x-n) and (x+n-2) such that size of one unit of repetition is atleast n. Is this approach correct?

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

        for even a factor i you have k = i / 2 + 1 in first case k >= x and in second case k > x

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

          my code got accepted just by changing condition from factor>=n to factor/2+1>=n. still couldn't understand why...

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

            That's because factor is 2k-2

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

              thanks! I was putting constraints on (2k-2) instead of k lol

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

Good contest, interesting problems. Thanks to the authors.

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

how to C

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

How to solve D?

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

    notice that sum of c[i] <= 200000 => number of different c[i] is at most sqrt(200000) => simply iterate over all possible num of squads in O(max(c[i]) * sqrt(200000))

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

    Suppose a group with $$$c_i$$$ members is divided into $$$k$$$ pairs, then it is optimal to split it into groups of size $$$\lfloor \frac{c_i}{k} \rfloor$$$ and $$$\lceil \frac{c_i}{k} \rceil$$$ to maximize the number of pairs. You can trivially calculate the number of groups of each size and the number of pairs for a given $$$c_i $$$ and $$$k$$$.

    Then just realize that the number of pairs for a group with $$$c_i$$$ members only increases till the number of groups becomes $$$c_i$$$. So if you iterate on squad size in increasing order, you can just recalculate it for each $$$1 \leq \text{squad size} \leq c_i$$$ and then maintain the last value in a common sum. This runs in $$$O(n + \sum {c_i})$$$ which is fast enough for the constraints.

    Code — 245818007

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

How to solve problem B? what is wrong with my solution: https://codeforces.net/contest/1928/submission/245837687

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

bad F.

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

Problem D: binary search on answer(no. of squads) because the target function has only one extreme large value

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

    i think it's ternary search

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

      I didn't wrote this algo but I read a code when hacking. I think this algo is right, because it's a quadratic function which has only $$$\le 2$$$ max value. But I prefer the $$$\Theta(\sum c_i)$$$ solution better :).

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

    but how do we decide whether to increase lower bound or upper bound during binary search i was thinking of BS but above confusion made me quit it

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

      with binary search you can check whether it is increasing or decreasing

      ternary search is easier though as someone said

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

    I applied binary search but I think I will get FST soon :(

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

    How did you check if the answer from bin sh can be obtained?

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

    U actually did ternary search :|

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

    I am not certain of it. It can definitely have 2 maximums of equal value.

    I did solve it with binary search on f(m)<f(m+1) but I was not certain if it is monotonic until max. I did see 2 equal maximums f(max)==f(max+1)

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

      You are right, 2 adjacent maximums are possible, I didn't mean to be precise on my og comment

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

first time ever that I couldn't solve A, I still have no idea

extremely frustrating actually

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

Very dramatic that hmmmmm solved problem F in the last minute(may win a prize in some contests) and became the only AK. Congratulations!

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

    Thanks!

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

    Very dramatic that 74 solved F in the last 10 minutes. Maybe he is (re-)learning to setting problems.

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

      bro that joke got me dying never joke again pls

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

Really tough B

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

I found D easier than C.

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

If the round is based on some olympiad, I guess it's understandable that the authors didn't have the time to fine-tune the TLs for codeforces, but still repeatedly getting TLs in F with $$$\mathcal{O}(n\log n)$$$ was pretty frustrating

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

    STFU BUNDLE OF STICKS

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

      Had to google what that was (in this context), haven't laughed that hard in a while, thank you lol

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

approach for B? I tried sliding window, got WA on pretest 3.

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

Good start time, i dont need to stay up late

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

Anyone else spend a long time without realizing that the triangle numbers start from "0" in E? I spent like 1 hour trying to think about how to calculate both exact length and sum before realizing right at the end that only min length was required T_T.

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

    Can you please elaborate how you mapped E to triangles and how to solve it ? It seems very interesting as the problem does not seem to be about geometry superficially.

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

      Triangular numbers are of the form n*(n+1)/2 where n is a natural number.

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

I want hint for B

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

    sort arr
    i used window slide and check if arr[right] — arr[left] < n

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

    If put all the numbers in a numerical axis, what can you do?

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

    Maximum number of unique integers that can all be converted to a certain integer and this certain integer shouldn't exceed min(all(unique_integers)+n. The term unique is significant as it's evident from the test case 7,1,4,1 like u can only convert one of two '1's to a certain integer which is 5 here. Cuz for another '1' u need to again add 4 which is not possible in case of permutation.

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

I got WA2 on problem E. What is incorrect in this solution?

$$$x \; mod \; y$$$ subtracts $$$y$$$ from $$$x$$$, so it makes sence to work with multiples of $$$y$$$. Look at this sequence: $$$a_1 \cdot y + p, a_2 \cdot y + p, \dots$$$, where $$$p = x \; mod \; y$$$. Then either $$$a_i = 0$$$ or $$$a_i = a_{i-1} + 1$$$, so this is a sequence of arithmetic progressions.

What is the sum of sequence? It is $$$\sum_i{(a_i \cdot y + p)} = y \cdot \sum_i{a_i} + n \cdot p = s$$$. This gives $$$sum = \frac{s - n \cdot p}{y}$$$. Check that this is an integer number.

Now our problem is to find sequence of arithmetic progression with given length $$$n$$$ and sum $$$sum$$$. We can find minimal length instead, and after it append zeros at the end. Let's first $$$a_1 = 0$$$. This is a simple $$$dp$$$. We iterate over length of additional progression. There are $$$\sqrt{n}$$$ of them, so it takes $$$O(n \cdot \sqrt{n})$$$ time.

How about $$$a_1 = \frac{x}{y}$$$? Let's just iterate over all prefixes-progressions and find the best one prefix.

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

    Did you test your code on this?

    2
1 1 1 1
1 1 1 2

    Some solutions will fail when $$$y=1$$$.

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

    Oh, no. The problem was following:

    if (a && b) print("NO");

    instead of

    if (a || b) print("NO");
    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anybody knows greedy doesn't work here?

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

      Greedy for making sequence of arithmetic progressions? If taking maximal progression, then no.

      $$$12 = 0 + 1 + 2 + 3 + 4 + 0 + 1 + 0 + 1$$$ — greedy.

      $$$12 = 0 + 1 + 2 + 3 + 0 + 1 + 2 + 3$$$ — dp.

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

Nither good nor bad timing in india but would be better if delayed

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

B problem implementation triki but logic easy.

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

Why anyone would just cheat to get better rank? For real I don't know how you doin that and u think u are good but the fact that u r cheating

Problem C is not that easy to get 3k accept

Fu*k youtube channels and telegram and anyone that take anything from them

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

    they will most likely get plagged and the round will get skipped for them negatives included

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

    why don't you cheat?

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

How to solve the problem c? I got TLE with this solution: https://codeforces.net/contest/1928/submission/245842512 anyone please explain.

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

    Notice that the position where x appear is x and 2k — x adding 2k — 2

    so what you need to do is calc the number of k satisfy n % (2k — 2) = x or n % (2k — 2) = 2k — x

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

      yeah, I have observed this though could not implement it efficiently, can u explain the time complexity pls

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

      I understood the part where we need to find all divisors for n — x, but why do we need to check the n + x — 2. Can you help me please?

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

        Case $$$1$$$: $$$n\mod (2k — 2) = x$$$.

        This means there exists some $$$y$$$ such that, $$$(2k - 2) * y + x = n$$$ $$$\rightarrow$$$ $$$(2k - 2)*y = (n - x)$$$. So, if we find divisors of $$$(n - x)$$$, we can find the candidate values for $$$k$$$.

        Case $$$2$$$: $$$n\mod (2k - 2) = (2k - x)$$$.

        This means there exists some $$$y$$$ such that, $$$(2k - 2) * y + (2k - x) = n$$$. Subtract $$$2$$$ from both sides, $$$(2k - 2) * y + (2k - 2) = n + x - 2 \ $$$ $$$\rightarrow$$$ $$$(2k - 2)(y + 1) = n + x - 2$$$. So, if we find divisors of $$$(n + x - 2)$$$, we can find the candidate values for $$$k$$$.

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

I have applied Binary search on 1928D - Lonely Mountain Dungeons and got Accepted, but I think my solution can be hacked. Try it.

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

B should be difficult but not as much difficult, because then there is almost no difference between a lot of users. If you wanted to make B this much difficult then make A also a little more difficult.

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

Bad start time , i need to eat dinner with my family during the spring festival.

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

Well balanced round although a bit mathy.

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

GOOD ROUND !!

On my way to Specialist

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

anyone can give me a countertest of this submission for problem B??

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

I wonder if this is an intended solution for E, or is this hackable.

https://codeforces.net/contest/1928/submission/245851958 (hacked)

https://codeforces.net/contest/1928/submission/245926933

The problem can be reduced to constructing an array of length n of sum z where

  • the starting element is fixed
  • each other element is either zero, or one larger than the previous element

The strategy is to greedily increase, except for the following scenarios

  • The remaining budget (the target sum z minus current array sum) is a triangular number and the remaining space (target array length n minus the current array length) is at least one more than the size of the triangle.
  • The remaining budget (the target sum z minus current array sum) is a triangular number plus one and the remaining space (target array length n minus the current array length) is at least three more than the size of the triangle.
  • The remaining budget (the target sum z minus current array sum) is a triangular number plus three and the remaining space (target array length n minus the current array length) is at least four more than the size of the triangle.

In other words, the only times you do not go greedy is when the constructed array ends in

[..,0,1,2,3,4...,n,(and maybe a few more zeroes)]

or

[..,0,1,2,3,4...,n,0,1,(and maybe a few more zeroes)]

or

[..,0,1,2,3,4...,n,0,1,2,(and maybe a few more zeroes)]

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

    I tried this exact same logic, but it didn't work. I wonder why though...

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

    I found that maybe 0,1,2,3,4,0,1,0,1 is worse than 0,1,2,3,0,1,2,3

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

      The greedy algorithm I have described covers this case, it knows it can end with 0,1,2,3 and so it will not increment.

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

Very tricky E!

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

Welcome to Mathforces dot com

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

Can someone explain in for testcase 3 in D why the answer

1 1 5 5 16

is 525? I calculate 530 when I use 10 squads. I even did a brute force of the squads and get the following

1 0 2 315 3 415 4 465 5 490 6 505 7 515 8 525 9 525 10 530 11 530 12 530 13 530 14 525 15 525 16 525

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

    Disregard that. I think the issue is with the formula I was using.

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

Can anyone tell me if the penalty applies only for solved problems? If I have submited 3 wrong answers for a problem but I fail to ultimately solve the problem, will my overall points still be reduced by 150? Thank you.

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

    Yes u get a penalty of a wrong answer only after solving the problem

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

    they told me no , but i have almost 150 points reduced lol

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

i really dont know why i have this much penalty and it effects my rating alot , ill appreciate any help or explainations

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

If the contest starts at an unusual time, at least mention it in bold. I overlooked the start time and missed the contest :(

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

Can anyone explain why A returns JUDGEMENT FAILED verdict in the beginning of the contest?

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

    that is server issue, not our fault I believe

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

    Because there were no pretests. Fortunately, it was fixed much sooner than I expected.

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

      Why round with all math problems?

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

        It happens. Anyway we inserted B (which was proposed for Pinely Round 3 (Div. 1 + Div. 2), then unused) precisely because it is not a math problem.

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

          By doing so you did a great thing. That's funny, because right after I read the problems I said "Problems are too mathematical, although problem B is an exception and it's really nice". I feel really sorry for contestants who come to solve programming challenges, but get the contest full of math.

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

very classic problems. dislike

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

Bad start time, I need to have dinner.

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

D could be solved with brute-force, by fixing the number of squads, and iterating over the races with population higher than the fixed value.

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

    It is $$$O(s \sqrt{s})$$$ actually, or something like that

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

      Actually, I think it works in $$$O(N \log N)$$$ where $$$N = 2.10^5$$$ as $$$\sum_{k=1}^{N} \frac{N}{k}$$$ is $$$O(N \log N)$$$, and the sum of values of $$$c_i$$$ is bounded by $$$N$$$ in all test cases. I don't have exact proof but it passed in 31 ms, and I don't think $$$O(N \sqrt{N})$$$ is that fast.

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

        I guess it is just because of the weak tests. It is exact $$$\mathcal{O}(n\sqrt{\sum c_i})$$$.

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

Even though I(my main acc) have +delta for this contest, I think it is mathforces. It's not all bad, I have some new math experience. But I think it is better, more satisfied to do algo contest.

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

first participated,but bad experience

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

Can anyone tell, whats wrong in my code for B?. Its failing on test 4 https://codeforces.net/contest/1928/submission/245858210

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

Can anyone tell why my code for problem B fails so hard on test case 3?

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

    One quick observation: when you update your answer, you should use max instead. This way, you get the best answer (largest possible interval) and not the most recent one.

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

      Well I get the largest possible interval anyways because r-l only gets smaller in the code I wrote. The only possibility is that my approach does not yield the optimal answer, and I'd like to know why that is.

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

        Makes sense. Indeed, your algo doesn't get the optimal answer sometimes. A good strategy to prove this is to find a good counterexample.

        What you are doing is you make the interval to consider smaller based on which difference in values of either the right or left end is bigger. Let's try to find a correct answer that exploits this.

        Try for example: [1 2 3 501 502]

        The optimal subarray is [1 2 3]. Notice that your algo disregards 1 at the first iteration, so that's a valid counterexample.

        A hint to solve the problem: assume that we have a set of (distinct) values and we want to make them equal using a permutation. Try to find what condition we need to have in order to make all the values of this subset equal.

        Let me know if you need more help! :)

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

          Thanks for helping me find a counter example to my code. I managed to get AC just by switching the implementation from l=0 r=n to l=0 r=0, and it indeed gives a correct answer. Thank you once again :D

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

I had good contest but the ratings was too bad and I got positive rate only for 14

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

can someone hack this solution? -> https://codeforces.net/contest/1928/submission/245838079 this solution uses unordered map and i think it can be hacked?

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

    or maybe it's impossible to hack because d(n) is very small

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

Square_root_forces

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

i wish there was at least a reminder that we could put even so the start time is bad anyways so

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

I don't really believe this solution for problem E is correct, but for some reason it passed all the tests:

  • Brute force the largest index i before we take element modulo y.

  • For the rest of the array (after index i) try to distribute sum across the elements greedily (it gets WA11 without the next step).

  • Before doing the greedy thingie, try to remove prefix of length L (L is from 0 to 10) and pick the way with the least number of elements required.

Am I right that this solution doesn't look correct?

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

Finally able to do a Div2B with no penalties

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

Bad time.missed the round due to different timing.

CF needs to bring some UI changes on contests page.

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

Problem C video Solution here: https://youtu.be/AM6pz2H6JzQ?si=K5JXdOWcbTSiVyRV

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

Can someone help me understand why my solution isn't working for A problem: https://codeforces.net/contest/1928/submission/245856620

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

    actually, your code gives wrong answer for a test case like this: 8 4 you can use another two variables (for example x,y) for the input ,then:

    a=min(x,y)
b=max(x,y)
    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks man, I can't believe I overlooked such a simple thing.

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

One of the most interesting contest I've ever written, Thanks)

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

Thanks to the round, finally an Expert

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

A really good contest, even though the contest inspired by olympiads are generally more mathematical than usual but this one had a great balance. Great work by authors!!

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

.

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

Honestly I don't think this contest should be regarded as mathematical, as least the first five problems (which I solved during contest). I'm only a junior 2 student that had only learnt junior high school math and a little of senior high school math, and I have no MO background. I believe lots of people have an age larger than mine, so imo they have math knowledge better than me, st they shouldn't think this is a "math" round.

I've faced many times that people say that "... round is full of math", but I usually cannot understand (once was a round I VPed when I'm in primary school)

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

Can anyone plz explain y is there TLE for my solution of problem D. https://codeforces.net/contest/1928/submission/245999184 Link of my soln also the code is given below. This is my code for a single testcase:

void solve(){ ll n,b,x,mx_e=LLONG_MIN; cin>>n>>b>>x; vectorrace(n); rep(i,0,n) { cin>>race[i]; mx_e=max(mx_e,race[i]); }

vector<ll>army_str(mx_e+1,0);
rep(i,0,mx_e) army_str[i+1]-=(i*x);

ll to_p;
rep(c,0,n) {
    rep(k,1,mx_e+1) {
        ll x=race[c]/k, y=race[c]%k;

        if(race[c]<k) {
            to_p = ((race[c]*(race[c]-1))/2)*b;
            army_str[k]+= to_p;
        }
        else if(y==0) {
            to_p = ((k*(k-1))/2)*x*x*b;
            army_str[k]+= to_p;
        }
        else {
            ll v=k-y;
            to_p = ((y*(y-1))/2)*(x+1)*(x+1)*b + ((v*(v-1))/2)*x*x*b + y*v*x*(x+1)*b;
            army_str[k]+= to_p;
        }
    }
}

ll mx=LLONG_MIN;
rep(i,0,mx_e+1) mx = max(mx,army_str[i]);
cout<<mx<<"\n";

}

→ Reply