Блог пользователя Sagita_Phoenix

Автор Sagita_Phoenix, история, 4 недели назад, По-английски

Hello Codeforces!

$$$\newline$$$

From AkiLotus

It's been a while, today AkiLotus and I are delighted to invite you to participate in Codeforces Round 983 (Div. 2). This round will be rated for all participants with a rating lower than 2100.

Our round will start on Nov/01/2024 17:35 (Moscow time). You will be given 6 problems and 120 minutes to solve them.

This contest is a collaboration between AkiLotus, his friends and Code Mely, a Vietnamese community and an individual passionate about Computer Science. Reach out to us here.

Special thanks to:

$$$\newline$$$

Score distribution: $$$500 - 750 - 1250 - 1750 - 2250 - 3000$$$

Happy coding! Our chicken nuggets and Fubao bless you.

UPD1: Editorial is published.

UPD2: Congratulations to the winners!

Div. 1 + Div. 2:

  1. Nachia
  2. arvindf232
  3. peti1234
  4. turmax
  5. superguymj
  6. Rubikun
  7. ksun48
  8. potato167
  9. BurnedChicken
  10. Vincella

Div. 2 (official):

  1. Vincella
  2. SUPERLWR-beta
  3. BlackLily
  4. leolin0214
  5. TAIYANGFENG
  6. xiaowangba
  7. piasticOuO
  8. Nikephoros2Phocas
  9. SkyWave2024
  10. zsj6315

First solves:

  • Проголосовать: нравится
  • +429
  • Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

As an author, good luck.

»
3 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

As a tester, good luck!

»
3 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
As a tester
»
3 недели назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Oops! I'll be at ICPC2024 Nanjing Ragional when the contest is scheduled. Hope I will be able to achieve Cu for my first ICPC contest, and good luck to everyone participating codeforces or ICPC~

»
3 недели назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

As a taster, i tasted and the problems were indeed quite tasty

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

As a tester, good luck

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

As a tester, I hope you all enjoy this round and perform well to achieve the rank you truly deserve.

»
3 недели назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

As a tester, don't eat KFC before the contest if you can't tolerate spicy food.

»
3 недели назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

As a sauce preparer, I can confirm that the nuggets are very tasty!

»
3 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

As a tester, good luck :)

»
3 недели назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

As an author, I'm honored to bring you the score distribution for this round. Good luck.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That announce was made 8days ago mean 10day before contest. Seems like they are prepared...(Excited)

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

you forgot to thank Mike Mirzayanov.

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

OMG Vietnamese round

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

While saving Cats and Dogs, We kept celebrating with Chickens Pigs and Goats. Hypocrite Humans.

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Good KFC.

»
3 недели назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

omg kuroni round

»
3 недели назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Damn.. did you guyz really forgot to thank our lord and saviour MikeMirzayanov...

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

looking forward the result.

»
3 недели назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

As a contestant, how can I become a tester $$$??$$$

»
3 недели назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Mary skelter fan spotted omg

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Special thanks to KFC was what really hit me <3

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is KFC preparing a round?

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Guys, my exam is starting in a month (I gave a practical exam today).

I have all of my syllabus to read.

Should I do this contest?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope full solve

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the team loves chicken nuggets more than their code :D

»
3 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Pray that i solve atleast 1 problem(s) this time :')

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

time to celebrate and rank up

»
3 недели назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

If we write down all the red letters we get the word : Kangokutou Which is a term that is often used in Japanese literature and media to refer to isolated islands designated for imprisoning criminals, similar to the concept of Alcatraz Island in the United States. It may also appear in fictional works to evoke themes of isolation, confinement, and punishment SOS?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OMG This looks like a Halloween edition !!!!! :)

»
3 недели назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

As a tester, I'm curious about AkiLotus's profile character

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

as a 20yrs fan, kuroni orz

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a compiler, I cant complain.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wish this contest will be interesting

»
3 недели назад, # |
  Проголосовать: нравится -86 Проголосовать: не нравится

I am writing to request that MikeMirzayanov postpone the contest, as it is Diwali in many regions of India today.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    unfortunately the world doesn't revolve around India

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    I am from India. And I am embarrassed seeing these kind of immature comments from people from India.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

      Haa kattue tujhe kya fark padega

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        I am Hindu. And I am embarrassed seeing these kind of immature comments from people from our Religion.

        Btw, Belated Happy Diwali to you toooo !!!

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          Happy Diwali, but what was so embarrassing when someone ask to postpone the contest?, this year during eid one guy asked to postpone the contest, and it was indeed postponed, but when I asked, I get hate from my own people.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    who cares

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

return specialist?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everybody!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Goodluck for everyone

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

(D) is Mucho Texto

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B had so many edge cases but atleast i solved it

»
3 недели назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Samples in C are useless

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's a trend ig, it's always been like this.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't get this. Care to explain yourself?

    I do believe the samples have covered most of the general idea of the problem, like what is being done in each operation and how the final criterion is visualized.

    If anything, I think I haven't yet explained too deep into how an operation sequence is invalid, but that should be the work of the Notes section, not the samples.

    And furthermore, I believe samples' purposes only stop at illustrating what the problem asks, not giving any insight of how to solve it (though the 4th sample was there as sort of a sanity check for you guys when coding).

    • »
      »
      »
      5 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sorry for the late reply. I didn't like that in all the examples you can just sort the array and replace some prefix of the numbers with the largest number in the array. Because of this, the tests seemed monotonous to me.

      • »
        »
        »
        »
        5 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Pretty sorry for the experience, but I still don't believe that is something possibly faultable. Again, the testset only needs to illustrate the exact specs of the problem's components (operation, validity, etc.), not hinting or distinguishing right and wrong approaches.

»
3 недели назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

time to touch grass

»
3 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Ofcourse it is on us to read statement carefully, but it would have been so nice if the fact that we are given an identity permutation was clearly stated in Problem B. No way a problem with such a trivial solution has taken so much time for so many people to AC.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how did you solve it?

    • »
      »
      »
      3 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      my solution I think its simple ~~~~~

      int n,k;
          cin>>n>>k;
          if(n==1){
              if(k==1){
                  cout<<1<<endl;
                  cout<<1<<endl;
              }
              else cout<<-1<<endl;
              return;
          }
          if(k==n){
              cout<<-1<<endl;
              return;
          }
          if(k==1){
              cout<<-1<<endl;
              return;
          }
          if(k%2){
              cout<<5<<endl;
              if(k==n-1){
                  cout<<-1<<endl;
                  return;
              }
              cout<<1<<' '<<2<<' '<<k<<' '<<k+1<<' '<< n<<endl; 
              return;
          }
          cout<<3<<"\n";
          cout<<1<<' ';
          cout<<k<<' ';
          cout<<k+1<<endl;
      

      ~~~~~

    • »
      »
      »
      3 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      since given array is identity permutation we can simply split the array into three parts $$$[1,..,k-1], [k], [k+1,...,n]$$$. Since everything in first subarray is smaller than $$$k$$$, its median is also smaler than $$$k$$$. Similarly median of the third subarray is greater than $$$k$$$. Now, for median of medians part we have only three numbers with one each on either side of $$$k$$$.
      Only edge case is that size of subarrays should be odd.
      $$$[k]$$$ is already odd.
      If $$$[1,...,k-1]$$$ is of even length then $$$[k+2,...,n]$$$ must also have even length (otherwise $$$even +1 + odd = even \neq parity(n)$$$. So just split them further into $$$[1]$$$ and $$$[2,...,k-1]$$$. Similarly split $$$[k+1,...,n]$$$ into $$$[k+1]$$$ and $$$[k+2,...,n]$$$ if need be.

      So you either split into $$$3$$$ subarrays or $$$5$$$ subarrays always. In both cases we have equal number of medians less than $$$k$$$ and greater than $$$k$$$, so overall median is still $$$k$$$.

»
3 недели назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

D is solvable with $$$n-3$$$ queries. We have to find the array $$$p$$$. After the first positive value $$$p$$$ is strictly increasing.

Iterating from $$$n-2$$$ to $$$1$$$ we can find $$$p_{n-1}$$$.

$$$p_{n-1}=i$$$ if the $$$(n-1, i)$$$ path doesn't cross $$$0$$$ for the first time.

After that we can do the same for $$$p_{n-2}$$$ iterating from $$$p_{n-1}-1$$$. And so on. Using the observation that node $$$1$$$ has exactly $$$2$$$ adjacent nodes we can save one more query.

Here is my solution: 289236088

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is E really just a knowledge check on how to solve a system of equations for the specific matrix? Or is there an easy solution?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    just get the relation between v[i] and v[i+2] for all i and make them all non-negative by adding minimum value. then check whether it's valid

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

WAforces, I'm feeling -3 intel for making 4WAs in B and 1 WA in C

»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

ABC was SpeedForces for me, but D was a great problem... too bad I couldn't solve it lol

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hope this helps 289278230

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is your solution?

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        Step_1: sort array a

        Step_2: binary search a[i] + a[i+1] in a. Called the result j for example (it infers the array a[i] a[i+1]... a[j] fits the problem requirement, every triplet will fit x+y>z etc.)

        result = n - max(step_2)
        

        UPD: seriously my code is simpler, just read it. It's 4-5 liner code only...

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      int n; cin >> n;
        vi v = inp(n);
        sort(all(v));
        dbg(v);
        int i = n - 1;
        while (i > 0 && v[i - 1] + v[i] > v[n - 1]) i--;
        int j = 2;
        while (j < n && v[0] + v[1] > v[j]) j++;
        cout << min(i, n - j) << endl;
      

      could u tell why this approach fails? cant check the failing testcase

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        try this:

        2
        6
        1 2 2 3 3 4
        7
        3 3 4 5 6 7 7
        
        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          2 and 2 is the output

          which i believe is correct?

          • »
            »
            »
            »
            »
            »
            3 недели назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            correct, nvm

            • »
              »
              »
              »
              »
              »
              »
              3 недели назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              i figured out that my code fails if there is a x + y <= z pattern in middle of array where i or j dont reach

              1 1 1 3 4 5 9 10 11 22 30

              i stops at 11 and j stops at 3 so res is 8 but correct res is 7 considering the correct seq to be 5 9 10 11 and changing the rest of the values

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D gives correct answer on my compiler, but wrong answer on CF

»
3 недели назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
After doing D
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was there an easy solution for C? I tried to memoize with both start and end index of sorted lengths and got TLE

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, Try to check for every position in a sorted array, If this was the minimum, how much are valid ?, it can be done in O(N*Log2(N))

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Damn for C I boiled down to that all numbers revolve around median of the sorted array, so any number i.e. greater than median + 2 and any number smaller than median — 1 would be modified. Something like this, was not able to get it right for the sample test cases and time got over. Might be I was overthinking.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    My approach:

    It is sufficient to ensure that a1 + a2 > mx, where a1 and a2 are the two smallest elements of the array, and mx is the largest.

    We can change the maximum element of the array. So, sort the array and iterate from the end. Let's stay mx1 = largest element, mx2 = second largest and so on...

    For each mxi, we find the number of operations required such that a1 + a2 > mxi. To do that, we find the first pair ai and ai+1 such that ai + ai+1 > mx, and number of operations is simply i - 1, as we must change all elements smaller than ai.

    The answer is min(op1, op2, ...), where opi = minimum number of operations for mxi

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

I think maybe I can't go to sleep tonight.

I practice very hard for two months, and I finally make it.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in B i thought there's actually an array given in the input :(

»
3 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve E? Also Is it possible to construct the answer(operations) array from the final element (if we know the element which will be equal after the operations are done)?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    It should be something around difference array.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 3
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What these operations can do is change any 2 elements by either of [+1, +1], [-1, -1], [+1. -1], [-1, +1] these operations. From these it will always be possible to make all the elements equal since n is odd. Is this correct? Can you explain Hint 3, I didn't get it.

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

        Sorry for the late reply (I went to sleep after posting the commnt :()

        Actually you only need the operation [+1,+1] or [-1,-1]. Let's define $$$inc(i,x) $$$ means that let $$$i,i+1$$$ both increase $$$x$$$ and $$$dec(i,x)$$$ for the same.

        Consider element $$$i $$$ and $$$i +1$$$,

        • If $$$a_i < a_{i +1}$$$, do $$$dec (i,a_i)$$$ so that $$$a_i = 0$$$.

        • Otherwise, do $$$inc(i+1, a_i)$$$ and now $$$a_i < a_{i +1}$$$.

        Keep doing it until there are only two non-zero number in the array and decrease them By there min so only one of them left.

        Now we have $$$n-1$$$ zeros and using $$$inc(i,\text{left_number})$$$ to make them equal.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    The answer to your second question is yes. It is easy to construct the array of operations given the final state, since we just need to solve the linear system

    $$$ \begin{bmatrix} 2 & 1 & 0 & \cdots & 0 & 1\\ 1 & 2 & 1 & 0 & \cdots & 0 \\ 0 & 1 & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 1 & 0 \\ 0 & \cdots & 0 & 1 & 2 & 1 \\ 1 & 0 & \cdots & 0 & 1 & 2 \\ \end{bmatrix} x=Mx=s-a $$$

    where $$$x_i$$$ is the number of times you applied the operation with index $$$i$$$, $$$a$$$ is the input and $$$s$$$ is a vector with the final state (in the problem all the entries of $$$s$$$ are the same however this method applies for every $$$s$$$). It is trivial to see that the $$$k$$$-th row of $$$M^{-1}$$$ is a cyclic shift by k of the upper row of $$$M^{-1}$$$, so you can solve this system easily with convolution/fft.

    However, for the problem itself there are way simpler solutions.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain a little detailed how to use FFT to solve such equations?

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

        Sure, for vector $$$v$$$, denote by $$$w_{v,i}$$$ the vector $$$v$$$ cyclically shifted by integer $$$i$$$.

        We know that

        $$$ M^{-1}= \begin{bmatrix} w_{v,0} \\ w_{v,1} \\ \vdots \\ w_{v,n-1} \end{bmatrix}. $$$

        To solve the system, just multiply $$$M^{-1}$$$ by $$$u=s-a$$$. Of course, you can't do this naively because it would be $$$\mathcal{O}(N^{2})$$$. However, notice that on the vector

        $$$ M^{-1}(s-a)= \begin{bmatrix} w_{v,0} \\ w_{v,1} \\ \vdots \\ w_{v,n-1} \end{bmatrix} u= \begin{bmatrix} w_{v,0} \cdot u \\ w_{v,1} \cdot u \\ \vdots \\ w_{v,n-1} \cdot u \end{bmatrix} (\star) $$$

        every single entry is the dot product of a certain cyclic shift of $$$v$$$ and $$$u$$$. If you consider a vector $$$r=\begin{bmatrix} v,v\end{bmatrix}$$$ then $$$(\star)$$$ is just some of the entries of the convolution of $$$r$$$ and $$$u$$$.

    • »
      »
      »
      3 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Could we use this to solve? It got me WA

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The link you gave is for tridiagonal matrices, $$$M$$$ is not tridiagonal because of the "corner entries" $$$M_{0,n-1}$$$ and $$$M_{0,n-1}$$$.

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Take a look at the Variants section, there is a solution for the matrix which is the same as in this problem.

          • »
            »
            »
            »
            »
            »
            3 недели назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Yes, you can solve with it, but you'll need to store the intermediate results as fractions instead of doing double division and then do a little bit of reconstruction on top of that to get the integer answer.

          • »
            »
            »
            »
            »
            »
            3 недели назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Then yes, you can solve it with that. I used fft because I am more used to it, but I would expect that there is a linear solution like the one described there.

            • »
              »
              »
              »
              »
              »
              »
              3 недели назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              It got me WA on test 6 however, though I copy pasted the whole function from wiki. It's hard to deal with precision here. Maybe FFT is more reliable in this situation.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for sharing. Will go through these concepts to get better at it.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

ACs on problem D rose drastically at the end._.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

damn i am not skilled at greedy problems at all...

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyone who also used a[N] instead of a[2N] on Problem A to declare the array? Just wasted almost 0.5h on it and the unstable mindset finally results in the thorough collapse:(

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How many you solved finally?

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      only ABC, and the "pretests accepted" solution of C is even submitted on the very last time of the round (only 10+ minutes left). I think at least I could solve 3~4 problems much quicker without this annoying bug:( But it's totally my own fault I have to admit, and nothing to accuse about the authors and the statements.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        misread the question thought a[i] = a[j] only allowed if i <= j. Thought about the problem like this for half an hour. What a waste :(

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I make other mistake of overthinking the problem. Also cost 0.5h

    After all the fog clears, it's just res_min = cnt1&1, res_max = min(cnt0, cnt1)

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      lol I've discovered the fun fact that it's exactly how CF Div.2 AB features. The solution is as easy as you could hardly believe, but if you fell into the trap of overthinking then it would just be rather complex or even impossible to solve

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Might someday we will brave enough to rainboy the contest (doing problem in E-D-C-B-A order)

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Very true. It's very hard to remain calm and "think simple" during contests. I always overcomplicate under pressure

»
3 недели назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

My E solution

Consider the difference array.

Let $$$d[i] = a[i] - a[(i-1) \mod n]$$$ (0-indexed).

We can see that the sum of $$$d[i]$$$ does not change. Thus, if the sum of $$$d[i]$$$ is not zero, there is no solution. Otherwise, we can always construct a solution.

Our target is to make $$$d[i] = 0$$$ for all $$$0 \leq i < n$$$.

An operation for $$$i$$$ (denoted as $$$\text{op}(i)$$$) is equivalent to: $$$d[i-1]++, d[i]++, d[i+1]--, d[i+2]--$$$ (mod $$$n$$$).

Merging operations:

$$$ \text{op}(i) + \text{op}(i+2) \implies d[i-1]++, d[i]++, d[i+3]--, d[i+4]-- $$$

Since $$$n$$$ is ODD, $$$\text{op}(i) + \text{op}(i+2) + \ldots + \text{op}(i-1)$$$ results in $$$d[i-1]++, d[i+1]--$$$.

Next, make $$$d[i-1]++, d[i+1]--$$$, then perform $$$d[i+1]++, d[i+3]--$$$, etc. to achieve $$$d[i]--, d[i-1]++$$$.

The implementation is painful. Can't finishit in the contest ;)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the problem with me??? Every contest its one thing or the other.

Sometimes I am able to find out the solution of a problem but unable to implement it quickly. I figured out some solution for D. But I was unable to implement it properly in 40 mins. I was juggling between different approaches. How do I calm my mind and implement the solution first properly? Is it just the lack of practice and nervousness that gets to me or is there something wrong with my time management?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's lack of confidence if you lose your focus on your own algorithm without a clear WA/TLE verdict.

    Practice daily to gain confidence. Confidence isn't grow by words mate.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had the same problem as you, and there is no trick. Just compete in more contests. Today i had solution for D in like 5 mins, but had no idea how to implement it, but i didnt panic and figured it out quite quickly after writing down some simple code. It all comes with experience, you cant speed it up.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am unable to put my mind to focus..Its just that it keeps wandering here and there.

      I am really demotivated right now because it is happening repeatedly with me now. I find some solution during contest, it doesn't work. Just after the contest (when my brain knows the contest is over, there's no time limit) I submit it and get an AC within 10 mins. But in the last 30 mins of the contest ending, I am just unable to even debug my code properly.

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

почему гениальные идеи приходят когда я сру

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D can any other node except root have degree more than 2?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    no

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why?

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        cuz everything else is path thus they need to be a straight line, thus a degree of at max 2 for every node except 0.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        1. Each node that was initially adjacent to the node 0 will be the end of some path. 2. A path is a tree whose vertices can be listed in the order v1,v2,…,vk such that the edges are (vi,vi+1) (1≤i<k ).

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If we remove root node 0 and all adjacent edges, this tree will turn into a forest consisting of only paths.

        think this through — can you figure out now?

»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

missed problem D cause i swaped 2 variables in my code bruh

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you guys and Code Mely for the amazing contest!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please anyone can explain me 3rd question

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

E has a cute trick. Write W[i] = V[i] + V[i+1]. https://codeforces.me/contest/2032/submission/289289897

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    So now we have an operation $$$[+1, +3, +3, +1]$$$, how is it easier?

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      A[i+1] + W[i] + W[i+1] = T differences, W[i+2] = W[i] + A[i+1] — A[i+2]. Say W[0] = w. Use above eqn to fill out W. Each W[i] = aw+b will have a=1. Sum all rows to find the real W[0] ("extra = ..." in the code)

      Now from W solve for V, its easier to solve the n equations W[i] = V[i] + V[i+1]

»
3 недели назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The problems were mostly good ,the issue with D is it just gives away the solution because there are so many limitations(conditions) so you just implement it, and the difference between D and E is too huge.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Special thanks to everyone for They breathe oxygen. and seriously for you.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it 's unrated.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why is the result for this test case for problem C 1 and not 2?

1 1 1 2 Even if we replace the middle 1 with 2, then we get 1 2 1 2, and the triple 1 2 1 is degenerate.

»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

what is wrong with this solution for C? :

always check the two smallest numbers and if thier sum <= biggest number then replace the samllest with the biggest

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    you can also replace the biggest with the smallest

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Consider 1 7 1 1 1 1 1 1 10. Your code replaces all thr ones with 10, but you can also replace the 10 with 1

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    consider the case

    1, 1, 1, 1, 10.

    Is it better to replace the first 3 ones with a 10? or the last 10 with a one?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For E, one can add $$$1$$$ to $$$a_i$$$ and $$$a_{i+1}$$$ equivalently by applying $$$\frac{n+1}{2}$$$ operations on $$$i+1,i+3,\dots,i-2,i$$$, and what remains is simple.

P.S. cf logout my account automatically before the contest start, so I thought I hadn't registered. MISS THE CHANCE TO BECOME MASTER AGAIN!!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to stop being stupid?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

finally got expert :)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone teach me problem E?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain this. At problem C there is this part in test case 3 test line 13 and its like this : 4 1 1 2 3 The correct answer by the judge is 2 but if we remove 2 than that would mean no triplet. Can someone see to this or am I tripping. (the error : wrong answer 13th numbers differ — expected: '2', found: '1')

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you need to replace, not remove. So after replace 1 1 to 3 3, we will get 4 3 3 2 3 which is the most optimal operation that satisfy the condition.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Makes sense. I forgot that when I was making the solution on the paper I thought of it for one moment as removing since it would make it simpler and got carried out on it.

»
3 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

top1codeforces is clearly using GPT. Why is he still getting first solves credits on A?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Interesting. I actually didn't diagnose every code (relying on the submission order to credit), and I also didn't know how to distinguish LLM-generated code from regular ones. Would love some enlightenment, and if feeling solid enough, I could change it accordingly.

    (Might take a day or two however, it's midnight in my place right now)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Mistook the operation ai += aj in C and got WA forever...

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I really enjoyed problem D, the first interactive problem I have ever solved during a contest

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
int n; cin >> n;
  vi v = inp(n);
  sort(all(v));
  dbg(v);
  int i = n - 1;
  while (i > 0 && v[i - 1] + v[i] > v[n - 1]) i--;
  int j = 2;
  while (j < n && v[0] + v[1] > v[j]) j++;
  cout << min(i, n - j) << endl;

why exactly does this approach fail for C ? cant really see the testcase

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you very much for the contest.

»
3 недели назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

My hack on problem F got Unexpected verdict, AkiLotus can you fix it please?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Apparently a tester solution also failed your hack. I'm trying to work on it, thank you for pointing out.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    The fix is done. I don't know if the hack could be redone though (I never saw such happen before), but I believe you could hack that solution again.

»
2 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hi! I have received a message from the system that my submission 289199140 for 2032B - Medians coincides with 289209093. What should I do about this?

This was a relatively easy problem, and I won't be surprised if 10 other people have written the exact same code as mine. Will I be considered a cheater for this by CF now? How can I erase this suspiciousness on me?

This is the first time, I have received such a message. I hope this was the right place to post this comment.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I believe in the email/system message you received there is a link towards a blog that should be the receiving end for your appeal. (I see that you've already commented there, so perhaps be patient)

    Normally that was just a warning. Your solution wasn't skipped, which is seemingly (as far as I understand) an indicate that you are the first in the duplicating chain, thus not being disqualified. But to be certain, just prove to the admin (or at least tell them to take a look at the case) that you neither cheat nor leak your codes for other to cheat.

    Disclaimer for subsequent users: Usually we problemsetters don't involve in disqualifying you (I just provided the above advice based on my own understanding of the system). Do not ping me or any other of our team for similar request (coz we would also be clueless), please notify the right person.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi MikeMirzayanov,

I'm writing this comment after recieving a message from the system that my solution 289214062 to problem 2032B - Medians coincides with lur100 solution 289274678.

After reviewing the profile of lur100 it's clear that this account is fake. This the standard solution for this problem (the author's solution: 289291698), the style of writing have some similarties as I don't use any templates or defines, and also have some differences like the tap size and writing if else, and it can be seen the differences between the styles with other submissions, for example: the solution of problem A in the same contest 289192610 vs 289197212.

If you also look at the submissions timing, while I was struggling with C and solved D, he was struggling with B and made two wrong submissions before the correct one.

Here is also some examples of a div.3 contest he participated and solved 2 problems while I participated virtually ans solved 7 problems, 283727862 vs 282258566 and 283728577 vs 282253457.

I have a friend whos account got blocked after he got this type of messages, and I don't want my 5-years profile to get blocked because of some misunderstanding and a fake account.

  • »
    »
    2 недели назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    MikeMirzayanov

    I've the same thing here , with

    Your solution 287793251 for the problem 2033E significantly coincides with solutions Harsh3304/287746817, Lean_Coding/287760531, Aditya__iit/287771991, MathModel/287793251
    

    though my code is also close to author's one.

    And I pointed out my thoughts

    Here

    I hope this being taken in consideration , I don't want to ping many times but no response so far.

    Moreover it's the same as 74TrAkToR's Submission

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First of all, I want to clarify that I completed this round entirely independently and did not use any online editors or share my code. I am also very surprised to find that my solution to Problem B matches that of another user.

I can provide the following evidence to clarify this situation:

Regarding my solution approach, I had a clear strategy from the start:

First, I considered invalid cases where n > 1 and either k = 1 or k = n, as these cases cause k to be a boundary and thus cannot be a median under any circumstances. For valid cases, I proceeded by analyzing k based on its parity. If k is even, I can treat k itself as an individual element in the array b, with two subarrays on its left and right, both of odd lengths, ensuring k can serve as a median. If k is odd, it requires at least three elements (an odd number) on either side to make k a median. The optimal approach here is to take the smallest odd number (3) so that k remains the median, with one side larger than k and the other smaller. Finally, I considered the special case when n = 1, which is straightforward. However, during my first submission, I missed handling this particular edge case due to insufficient local testing, causing an error on the first test case. I only corrected it and achieved the correct solution on my second submission. If this similarity were anything but coincidence, I believe it would have helped me avoid errors on Problem D, where I spent a long time stuck. I submitted twice unsuccessfully and only corrected my mistake on the following day after realizing I had misunderstood the problem requirements. Had I seen or copied another user’s code, I believe I would not have struggled as much with Problem D and would have solved it correctly during the competition.

Additionally, I have local files with modification timestamps, which include my code and test cases used locally.

I sincerely hope that the officials will review my case carefully and restore my account’s integrity. Thank you very much.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have also received a message from the system indicating that my solution, 289213653, for problem 2032B, coincides with the proven solution, 289197769 Of course I completed this round on my own. First of all, my solution is similar to the author's and represents the easiest way to implement the idea. Additionally, I have submitted the problem three times, each time changing my code. The first submission was made before the proven submission. The second and third submissions were made after it. Moreover, the proven and I solved different problems at different times. In summary, I hope the officials will consider my case and restore the integrity of my account. Thank you.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi MikeMirzayanov Codeforces Round 983 (Div. 2) Problem A Submission id — 289192116 Problem B Submission id — 289214425 Problem C Submission id — 289265297

My problem A and B logic is same as authors solution just their is change in implementation. As logic was trivial their can be multiple implementation similar to mine. Earlier I had different logic with problem C in which I was applying binary search on min number of operations, you can also check by submission id 289242175. After that I had observation that rather than applying binary search on min number of operations we need to do it on longest length of subarray so I stick to that binary search logic. So my approach for binary search on longest length of subarray was correct many others can have thought of same logic but their implementation differs yet I received warning, your solution 289265297 for the problem 2032C significantly coincides with them.

Please look into matter and resolve my issue, as I participated contest individually.

»
13 дней назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Recently I realized that my participation and solutions in this round were skipped due to the coincidence in my solution to problem 2032B - Medians with another contestant. I checked his solution and clearly the solutions match. I don't have access to his credentials and I don't even know him. I don't know or use ideone.com and I don't use AI code assistants in competitive programming. I think that in this specific problem this coincidence is not strange, maybe we followed the same reasoning, I don't know.

I hope this misunderstanding is resolved and my rating returns