Sagita_Phoenix's blog

Codeforces Round #983 (Div. 2)
By Sagita_Phoenix, history, 2 weeks ago, In English

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:

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

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

As an author, good luck.

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

As a tester, good luck!

→ Reply
»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it
As a tester
→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bd

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

      dp

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

        greedy

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

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~

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

    all the best bro, mine online round is on 11 nov hope my team will qualify for the offline regionals round

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

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

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

As a tester, good luck

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

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

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

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

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

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

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

As a tester, good luck :)

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

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

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

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

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

you forgot to thank Mike Mirzayanov.

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

OMG Vietnamese round

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

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

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

Good KFC.

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

omg kuroni round

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

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

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

looking forward the result.

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

    bro you ain't a tester, who are you trying to fool.

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

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

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

Mary skelter fan spotted omg

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

Special thanks to KFC was what really hit me <3

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

Is KFC preparing a round?

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

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?

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hope full solve

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    Yo, this guy's my senior at the college and he freakin' wants to be unrated!

    → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

time to celebrate and rank up

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

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?

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    As a anime fan, I'm also curious..

    If this character is from an anime please tell me the name of the anime.

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

    I hope I can officially announce her soon in a future round. ;)

    → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

as a 20yrs fan, kuroni orz

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a compiler, I cant complain.

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wish this contest will be interesting

→ Reply
»
5 days ago, # |
  Vote: I like it -86 Vote: I do not like it

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

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

    unfortunately the world doesn't revolve around India

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

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

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Haa kattue tujhe kya fark padega

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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 !!!

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

          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.

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

    who cares

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

return specialist?

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everybody!

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Goodluck for everyone

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

excited

→ Reply
»
5 days ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

(D) is Mucho Texto

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

B had so many edge cases but atleast i solved it

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

Samples in C are useless

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

time to touch grass

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

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.

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

    how did you solve it?

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

      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;

      ~~~~~

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

      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$$$.

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

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

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

    did you know that function res() does not return?

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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

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

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

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

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF man why is my solution for C wrong?

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

    hope this helps 289278230

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

      What is your solution?

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

        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...

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

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

        try this:

        2
6
1 2 2 3 3 4
7
3 3 4 5 6 7 7
        → Reply
        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          2 and 2 is the output

          which i believe is correct?

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

            correct, nvm

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

              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

              → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 days ago, # |
  Vote: I like it +24 Vote: I do not like it
After doing D
→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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))

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

      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.

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

    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

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

      Implementation

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

      But I saw n was in range 2*(1e5), I thought a N^2 algorithm would result in TLE, Im saying O(N^2) since you're checking for each

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

        It can be done in Nlog(N). Check the implementation above. You can store v[i] + v[i+1] in an array, then to find the first pair with ai + ai+1 > mx, just find the upperbound of mx in this array.

        → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

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

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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)?

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

    It should be something around difference array.

    → Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 2   Vote: I like it +15 Vote: I do not like it

        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.

        → Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

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

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

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        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$$$.

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

      Could we use this to solve? It got me WA

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

        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}$$$.

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

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

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

            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.

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

            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.

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

              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.

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

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

      → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

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

    Can u tell me how to improve speed solving greedy problems? That's only stopping me from Expert

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

      Write out some cases and see the pattern. That's quite a good strategy actually.

      → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Greedy is hard. Especially the proof part.

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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:(

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

    How many you solved finally?

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

      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.

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

        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 :(

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

    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)

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

      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

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

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

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

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

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

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 ;)

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Sum of $$$d_i$$$ is always $$$0$$$, so there always exists a solution for an input.

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

    it took me much time to arrive at this solution but the implementation is very simple 289836310

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.

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

    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.

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

      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.

      → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    no

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

      Why?

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

        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.

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

        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 ).

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

        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?

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

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you guys and Code Mely for the amazing contest!

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please anyone can explain me 3rd question

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

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

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

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

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

      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]

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

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.

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

it 's unrated.

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

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.

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

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

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

    you can also replace the biggest with the smallest

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

    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

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

    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?

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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!!

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to stop being stupid?

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

finally got expert :)

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone teach me problem E?

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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')

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

    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.

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

      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.

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

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

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

    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)

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much for the contest.

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

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

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

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

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

    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.

    → Reply