Artyom123's blog

By Artyom123, history, 13 days 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

»
13 days ago, # |
  Vote: I like it -6 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

contemplating taking this contest at 1:35 AM :)

»
13 days 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!

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

GOOD LUCK!!!

»
13 days ago, # |
  Vote: I like it +5 Vote: I do not like it

bed time for pacific programmers

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    bed time for pacific programmers

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sleeping time for pacific programmers

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to maintain my specialist rating.

»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Best of luck everyone

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Of Luck!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that Delayforces won't come again

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good!

»
13 days ago, # |
  Vote: I like it +4 Vote: I do not like it

need to run out of college class to attend the contest

»
13 days ago, # |
  Vote: I like it -6 Vote: I do not like it

div 2 too hard for me

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for making the contest!

»
13 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Good luck! May the force be with us!

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
13 days 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 :)

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    13 days 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

    • »
      »
      »
      13 days 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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become master after this.

»
13 days ago, # |
  Vote: I like it +75 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

lets see if i can become specialist

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad time contest for New York contestant

»
12 days 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.

  • »
    »
    12 days 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

»
12 days 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

»
12 days 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.

  • »
    »
    12 days 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

»
12 days ago, # |
  Vote: I like it +27 Vote: I do not like it

Rankup time...

6 contests in a row!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!!!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

chinese new year : (

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

GOOD LUCK!

»
11 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Happy Chinese New Year! Good Luck!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good start time for Asians

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!!!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Skipping classes for this contest (my second contest)

»
11 days 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.

»
11 days 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.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Let's skip class and reach specialist.

»
11 days 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)

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

3:05 PM ist Great timing...

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will Reach CM after this round

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Guess the rating of Problem

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This will be a fantastic contest

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good start time, i don't have to sleep

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Good time, hope i solve A fast

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I will have a negative delta but I will participate anyway

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Happy Chinese new year!Good luck to everyone.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope be expert in this contest!

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

First CF Contest

»
11 days ago, # |
  Vote: I like it -12 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it
Me after the contest :
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach expert with this round

»
11 days ago, # |
  Vote: I like it +59 Vote: I do not like it

Judgement failed?

»
11 days ago, # |
  Vote: I like it +22 Vote: I do not like it

glad to see another Mathforces round.

»
11 days ago, # |
  Vote: I like it +12 Vote: I do not like it

nice math contest

»
11 days 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.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    B is just sliding window.

    Unless
    • »
      »
      »
      11 days 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?

      • »
        »
        »
        »
        11 days 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

    • »
      »
      »
      10 days 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

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

        yes, It completed in like 5 mins

        • »
          »
          »
          »
          »
          10 days 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

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

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

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

MATHFORCES :((

»
11 days ago, # |
  Vote: I like it +23 Vote: I do not like it

Did they assume us mathematicians?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is $$$D$$$ binary search?

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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$$$

    • »
      »
      »
      11 days 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

      • »
        »
        »
        »
        10 days 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

        • »
          »
          »
          »
          »
          10 days 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)

        • »
          »
          »
          »
          »
          7 days 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.

    • »
      »
      »
      11 days 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.

  • »
    »
    11 days 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))

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for C please

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    hint
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

    • »
      »
      »
      11 days 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?

      • »
        »
        »
        »
        11 days 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

        • »
          »
          »
          »
          »
          11 days 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...

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's because factor is 2k-2

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest, interesting problems. Thanks to the authors.

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

how to C

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    11 days 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))

  • »
    »
    11 days 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

»
11 days 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.com/contest/1928/submission/245837687

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

bad F.

»
11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    i think it's ternary search

    • »
      »
      »
      11 days 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 :).

  • »
    »
    11 days 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

    • »
      »
      »
      11 days 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

  • »
    »
    11 days 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 :(

  • »
    »
    11 days 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?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U actually did ternary search :|

  • »
    »
    10 days 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)

    • »
      »
      »
      10 days 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

»
11 days 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

»
11 days 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!

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks!

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      bro that joke got me dying never joke again pls

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Really tough B

»
11 days ago, # |
  Vote: I like it +11 Vote: I do not like it

I found D easier than C.

»
11 days 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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    STFU BUNDLE OF STICKS

    • »
      »
      »
      10 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good start time, i dont need to stay up late

»
11 days 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.

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want hint for B

  • »
    »
    11 days 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

  • »
    »
    11 days 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?

  • »
    »
    11 days 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.

»
11 days 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.

  • »
    »
    11 days 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$$$.

  • »
    »
    11 days 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");
    
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anybody knows greedy doesn't work here?

    • »
      »
      »
      11 days 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.

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

B problem implementation triki but logic easy.

»
11 days 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

  • »
    »
    11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    why don't you cheat?

»
11 days 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.com/contest/1928/submission/245842512 anyone please explain.

  • »
    »
    11 days 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

    • »
      »
      »
      11 days 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

    • »
      »
      »
      11 days 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?

      • »
        »
        »
        »
        10 days 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$$$.

»
11 days 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.

»
11 days 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.

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Well balanced round although a bit mathy.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GOOD ROUND !!

On my way to Specialist

»
11 days 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
»
11 days 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.com/contest/1928/submission/245851958 (hacked)

https://codeforces.com/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)]

  • »
    »
    11 days 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...

  • »
    »
    11 days 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

    • »
      »
      »
      11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very tricky E!

»
11 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Welcome to Mathforces dot com

»
11 days 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

  • »
    »
    11 days 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.

»
11 days 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.

  • »
    »
    11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 days 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

»
11 days 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 :(

»
11 days 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?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that is server issue, not our fault I believe

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Why round with all math problems?

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days 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.

»
11 days ago, # |
  Vote: I like it +11 Vote: I do not like it

very classic problems. dislike

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Bad start time, I need to have dinner.

»
11 days 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.

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

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

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days 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})$$$.

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

first participated,but bad experience

»
11 days 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.com/contest/1928/submission/245858210

»
11 days 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?

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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.

      • »
        »
        »
        »
        10 days 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! :)

        • »
          »
          »
          »
          »
          10 days 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

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days 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

»
10 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Square_root_forces

»
10 days 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

»
10 days 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?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally able to do a Div2B with no penalties

»
10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 days 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.com/contest/1928/submission/245856620

  • »
    »
    10 days 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)
    
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks to the round, finally an Expert

»
10 days 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!!

»
10 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

.

»
10 days 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)

»
9 days 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.com/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";

}