FelixArg's blog

By FelixArg, history, 22 months ago, translation, In English

Hello, Codeforces!

It's been a long journey, and I'm finally pleased to invite you to participate in our Codeforces Round 955 (Div. 2, with prizes from NEAR!), which will take place on Jun/25/2024 17:35 (Moscow time).

This round will be rated for all participants with a rating is below 2100. Participants with higher ratings can participate out of competition.

During the round, you will need to solve 6 problems. You will have 2 hours to solve them.

The problems for the round were prepared by nik1998, egor4444ik, iamdimonis and me.

We sincerely thank everyone who provided invaluable assistance in preparing this round:

We are pleased to announce that NEAR has supported the round!

NEAR was founded in 2017 by Illia Polosukhin, one of the creators of Transformers, and Alex Skidanov as an attempt to build an artificial system capable of solving competitive programming problems. You can read more about that attempt here.

Ultimately, NEAR pivoted into building a blockchain protocol, which it launched in 2020.

This year, NEAR started NEAR.AI, a new lab with a mission to build AI systems that are open and available to everyone, instead of being controlled by a few mega-corporations.

One of the areas of focus is making models capable of reasoning reliably, and for that, competitive programming problems provide a great environment. To help us build it, we invite all the Russian-speaking members of the Codeforces community with a rating of Specialist or higher (1400+) to help us annotate step-by-step explanations of solutions to competitive programming problems. We want to annotate a very large set of problems of all difficulty levels, and pay relatively high rewards in NEAR per annotation. Don't speak Russian but speak English? Stay tuned here, we will be launching the same project for English-speaking people very soon, and will likely sponsor another round when it happens.

The round also features prizes in NEAR. Participants who rank in the top 16 will receive Ⓝ 16 each. The next 32 participants in the overall ranking (including unofficial participants) will receive Ⓝ 8 each. The following 64 participants will receive Ⓝ 4 each; the subsequent 128 participants will receive Ⓝ 2 each, and finally, the next 256 participants will receive Ⓝ 1 each.

Additionally, 64 random participants from the top 4096 in the overall ranking will each receive Ⓝ 4.

Score distribution: $$$500\,—\,1000\,—\,1000\,—\,1750\,—\,2500\,—\,3000$$$

Wishing everyone good luck and high ratings!

UPD: Let's continue the series of announcements with a photo of the authors :)

UPD 2: Editorial!

UPD 3: Congratulations to the winners!

Div 1:

  1. tourist

  2. jiangly

  3. SSerxhs

  4. kizen

  5. potato167

Div 2:

  1. lunchbox

  2. _JiaY19_

  3. gxy001

  4. _DongY19_

  5. Muelsyse_sep005

UPD 4: Wonderful video analysis of A-E tasks. Thank you, Shayan!

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

| Write comment?
»
22 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

Just curious, are the prizes based on full ranking or just official/Div.2 ranking only?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +69 Vote: I do not like it

    Prizes will be distributed among all participants of the round (including unofficial participants)

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it +27 Vote: I do not like it

      Why not just wait for a combined round instead of awarding div1 participants for solving div2 problems.

      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it +11 Vote: I do not like it
        My answer
      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it +45 Vote: I do not like it

        Even if div1 participants were excluded from prize list, they would have made an alt and took the prizes anyways so ig it doesn’t matter

        • »
          »
          »
          »
          »
          22 months ago, hide # ^ |
           
          Vote: I like it +7 Vote: I do not like it

          You could just say "official participants" to reduce the number of alts but that's not my issue with this. If you're going to give prizes to div1 the contest should be at least a bit challenging for them. It's their money I guess.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Could someone please explain what's Ⓝ in the prizes?

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is anyone going to pull a rainboy?

»
22 months ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Hello everyone, hope to reach CM in this round

»
22 months ago, hide # |
 
Vote: I like it +36 Vote: I do not like it

As a tester vodacbaoan is genius

»
22 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

December 2023: "AlphaCode 2 is worth a gazillion specialists, competitive programming is done for!"

Fast-forward to present day six months later: "Sup nerds, wanna annotate some problems?"

»
22 months ago, hide # |
 
Vote: I like it +67 Vote: I do not like it

This round will be rated for all participants with a rating of 2100 or below.

I am 2100 and I can’t register officially :(

»
22 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Hey Authors

I'm curious to know all your ages/experience? since it's great to find people with 2-3 years of experience building contests!!

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a tester problems are really interesting and challenging!

»
22 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

As a tester, I literally tested just now because the coordinator invited me to test a few hours ago.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I will come back after a long time not participating in contests

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

OMG! Another FelixArg round.

»
22 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

The expression on the face of boys explain how dangerous their mind is.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is meant by blue testing, purple testing, etc...?

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i remember you guys removed 24-word seed restore in the default web wallet and my near coins were gone, very funny. then someone told me i have to paste it in the url to restore it. please be careful about backwards-compatibility, would hate for the new ai to suddenly vanish. looking forward to nearcrowd round 2!

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

weird score distribution, I've never seen 1000 point div2c

thinking speedforce, unless upsolve D of course.

»
22 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

64 random participants from the top 4096 in the overall ranking will each receive Ⓝ 4, that means we have a 1.5625% chances of becoming rich! All the Best!!

»
22 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

interesting score ditribution

»
22 months ago, hide # |
Rev. 2  
Vote: I like it -8 Vote: I do not like it

Can someone help me ? How am i supposed to change my compiler from c++14 to c++20 (in my own laptop) ?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    You have to download and setup a newer version of GCC. Here is one of the places you can download it, under Release versions. Then you have to do the usual, adding it to system path.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

is there any penalty?

»
22 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Me after solving D : (^_^) Checking standings afterwards : (o_o)

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +6 Vote: I do not like it

nice tasks, 2k submissions on D wow

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +4 Vote: I do not like it

    thx to cheaters actually :)

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    I'd say it was not that hard of a problem, albeit a bit scary looking. Once you realize that you only need to get the difference of zeroes and ones in each kxk matrix to get the impact of an operation then it becomes a fairly simple number theory problem

»
22 months ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

B > C

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Animated Video editorial for problems [A-C]:

https://youtu.be/-btzjr-u4dM

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +16 Vote: I do not like it

problem D must have something to do with 2D prefix and maybe some gcd yes? I believe

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

C<<<B

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    how to solve C? i tried queue, greedy, pretest 2 fall

    • »
      »
      »
      22 months ago, hide # ^ |
      Rev. 4  
      Vote: I like it 0 Vote: I do not like it
      actually greedy but with two-pointer
  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    indeed spent 1 hours to solve B and C under 10min

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +5 Vote: I do not like it
meme E
»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone tell how to solve D?

My thought process for D : Find net difference between two types of mountains, this will give the value to increase. Now in each kxk submatrix, find difference between the number of two types of mountains : this will give the amount we can increase or decrease. And then I couldn't proceed further.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    That's correct. Then you can use GCD to figure out whether you can sum the list of kxk difference into mountain_diff.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The difference should be a linear combination of the amount you can increase by each of the k*k matrices. Hence, it should be divisible by their gcd.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    same, my approach was to first calculate sum of ones and zeros and get difference between them , now create prefix 2d array to store count/(difference between them) of ones and zeros in a matrix then for all possible matrix if dimension kxk save difference between one,zero in an array so now my problem boils down to classic Coin Change DP(with infinite coins of each arr[i]),but it takes O(sizeofArray*Sum) probably TLE

    any hints please ??

  • »
    »
    22 months ago, hide # ^ |
    Rev. 5  
    Vote: I like it 0 Vote: I do not like it

    Suppose the difference of the numbers of each type of mountain is $$$k_1,\dots,k_\ell$$$. Recall from number theory that the only numbers we can form as a $$$\mathbb{Z}$$$-linear combination of integers $$$k_1,\dots,k_\ell$$$ (i.e. $$$c_1k_1+\cdots+c_\ell k_\ell$$$ for integers $$$c_i$$$) are multiples of $$$\gcd(k_1,\dots,k_\ell)$$$. Therefore, if the difference is some multiple of the $$$\gcd$$$ of all the $$$k_1,\dots,k_\ell$$$, then there is some series of moves we can do to get the difference to zero (plus some edge cases where some/all of the $$$k_i$$$'s are zero).

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I was knowing ax + by = c has solutions only if c is divisible by gcd(a,b) but was not knowing this is true for any number of variables.

      • »
        »
        »
        »
        22 months ago, hide # ^ |
        Rev. 2  
        Vote: I like it +5 Vote: I do not like it

        If you have $$$a_1x_1+a_2x_2=c$$$ iff $$$\gcd(a_1,a_2) \mid c$$$, then you can write (for some $$$v$$$)

        $$$ a_1x_2 + a_2x_2 + a_3x_3 = (a_1x_2 + a_2x_2) + a_3x_3 = v\gcd(a_1,a_2) + a_3x_3 = d $$$
        $$$ \iff \gcd(\gcd(a_1,a_2),a_3) = \gcd(a_1,a_2,a_3) \mid d, $$$

        and you can continue by induction :)

        • »
          »
          »
          »
          »
          22 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I didn't know this. If it's so simple to know if a sum can be obtained by some combination, then why don't we use this property in subset sum problem or coin change problem?

          • »
            »
            »
            »
            »
            »
            22 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            It's simple because every item can be used for any integer number of times, but it's not the case for subset sum problem.

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, hide # ^ |
               
              Vote: I like it +3 Vote: I do not like it

              This will only hold when the coefficients can be any integer (including negative) ?

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, hide # ^ |
                 
                Vote: I like it +4 Vote: I do not like it

                Yes. For example, with $$$2,3$$$ you can form $$$1$$$ with negative coefficients as $$$1(3)+(-1)2$$$ but clearly not with positive (the result would be greater or equal to 2!)

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, hide # ^ |
                Rev. 2  
                Vote: I like it +1 Vote: I do not like it

                It would hold if the coefficients can be any integer. But the reverse direction may not be true (i.e. it's possible to get all multiple of $$$gcd(a_1, a_2, \ldots, a_n)$$$ even if some of the value can't be used for any integer number of times).

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Is there a name for that theorem or is it just a common concept?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    You can find the net difference in all $$$K \times K$$$ submatrices and let gcd of these differences be $$$G$$$. It can be proven that you can only change the total height difference by some multiple of $$$G$$$, therefore you only need to check if the height difference is divisible by $$$G$$$.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to do B?? Spent more than an hour and couldn't solve it.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    After a while, the value of x just starts to loop in between 1 and y-1 . So just find out the position at the end making use of some %

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Tried something similar to that.

      I tried to convert x to 1. If it was possible then I gave x + k%(y-1) as answer and if not then returned x only.

      Submission : 267370934

      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        At First , we need to ensure that x<y ,only after that x can become 1.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So you've really decided to use the $$$3 \cdot n + 1$$$ problem in a contest? I'm really salty right now if you didn't notice.

»
22 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

even though i couldn't solve it, i feel that C is much easier than B. From the One's I've read, A-C. I can say that the problems were very interesting and I think i would enjoying upsolving them.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The trick to B is to try to simulate the operations and output the x values as it changes, then it becomes apparent that it starts looping between 1 and y-1 when x reaches a value equal to y or less. And to get to that point you just perform as many operations as you need to get x to the next multiple of y but you don't actually need to add 1 every time just find the next multiple of y and do all the ops at once

»
22 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

B was very hard for people who aren't that good at math. :(

»
22 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Why are all the A's getting hacked..?

»
22 months ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

Thanks for the contest. I got my lesson. I wont give any contest from now on which has the word TrAkToR in its description.

»
22 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Why so many hacks on A? (observing those on page 1 of standings)

»
22 months ago, hide # |
Rev. 8  
Vote: I like it +15 Vote: I do not like it

A: If the sign of (x-y) changed, then (x-y) must be 0 at some time, so answer is NO. Otherwise, the answer is YES.

B: If x<y, then the value of x will change among {1, 2, ..., y-1} periodically, so the answer will depend on k%(y-1). Otherwise, after (y-x%y) operations x will become (x+y-x%y)/y, which is not greater than (x/y)+1. Because y>=2 this can happen not more than log(x) times until x<y, so we can simulate the process in O(log(x)).

C: Let dp[i] be the anwser for first to i-th cards. We can binary search for the largest j such that sum(j+1, i)>=l, if sum(j+1, i)<=r we have dp[i]=max(dp[i-1], dp[j]+1), otherwise dp[i]=dp[i-1].

D: Let the balance of heights B=(sum of snowy heights)-(sum of not-snowy heights). If B==0 initially the answer is YES. If we let c[i][j]=1 when (i, j) is snowy, c[i][j]=-1 otherwise, then when we do operation on a k*k square, the change of balance will be sum(i,j)(c[i][j]) where (i,j) is in the square. So we can calculate the sum of c[i][j] over all k*k submatrices using 2D prefix-sum, and by the bezout's theorem, the change of balance can be any multiple of GCD of these sums. In order to make B=0, the initial value of B must be the multiple of GCD.

E: First think about case for n=2**d. If k>=d the answer is n*(n+1)/2, and if k==d-1 the answer is (n-1)*n/2, let's assume k<=d-2. We can see the answer is sum(1<=r<=k+1)((2**r-1)*(2**r)/2 * C(d-r-1,k+1-r)). Denote this as f(d, k).

Proof

Now think about arbitrary n. We can split [0, n) into several intervals with length of 2**j, where n has the j-th bit. If we let L=floor(n/2**(j+1))*(2**(j+1)), R=L+2**j, the answer on interval [L, R) will be f(j, k-popcount(L)). If popcount(R-1)>k, there will be no valid interval containing both R-1 and R, so we can add this to the answer and consider for [R, n) seperately. Otherwise, when popcount(R-1)<=k, we can see that for any R<=x<n we have popcount(x)<=k, so we can add (n-L)*(n-L+1)/2 to the answer.

F: Let L be the minimum i such that a[i]>a[i+1], R be the maximum i such that a[i-1]>a[i]. Then at least we need to sort subarray [L, R]. Let X=min(L<=i<=R)(a[i]), Y=max(L<=i<=R)(a[i]), if there are any L1<L such that a[L1]>X or any R1>R such that a[R1]<Y, then we also need to sort them. To find L,R we can maintain a set S={1<=i<n: a[i]>a[i-1]} which can be modified in O(log(n)) each operation. To find X,Y we can use a segment tree, and to find L1, R1 we can use binary search on a[i].

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    how to solve F?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +16 Vote: I do not like it

    C is greedy $$$O(n)$$$, you don't need a binary search.

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it +10 Vote: I do not like it

      yes but bs solution is easier to understand why it works.

      also easy to implement without considering different cases. check his solution 267340021

      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        The greedy isn't too hard to prove either. At any step, you chose a valid interval with minimum right side index. That is correct because you end up with more possibilities for the rest of the problem than with any other valid leftmost interval (since its right index would be larger).

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Who can prove D?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    Bézout's identity

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    I just thought about Linear Diophantine equation, and the condition of it to be solvable is in CP-algorithm :v.

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I am just not studying number theory, haha. I just thought about knapsack.

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    If d[i][j] is the positive difference between the number of snowy caps and bare caps in the k*k submatrix whose top left corner is (i,j), then you can change the total difference in sum of heights, by c * gcd(d[i][j]), where c is any integer. (bezouts identity).

    So just compute this gcd and check if it divides the positive difference between the sum of snowy heights and the sum of bare heights.

    Can obviously be done in linear time by precomputing the rectangles.

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +6 Vote: I do not like it

Wrote a overcomplicated DP + Segment Tree solution for C. D was a good problem.

»
22 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

In fact, I think that question C is much less difficult than question B, and I was thwarted by question B for forty minutes but passed C in ten minutes.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone teach me how to past B problem?

  • »
    »
    22 months ago, hide # ^ |
    Rev. 3  
    Vote: I like it +3 Vote: I do not like it

    When $$$x$$$ will become less than $$$y$$$, there will be a cycle: $$$x$$$, $$$x+1$$$, ..., $$$y-1$$$, $$$1$$$, $$$2$$$, ..., $$$x-1$$$, $$$x$$$, which cost $$$y-1$$$ moves, so you just take $$$k$$$ modulo $$$y-1$$$ after $$$x$$$ will become less than $$$y$$$.

»
22 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

Lol, i just read F and isn't it just much much easier, than D and E? It took me like five minutes to come up with the solution.

»
22 months ago, hide # |
Rev. 3  
Vote: I like it -16 Vote: I do not like it

Can anybody please help me understand the problem with my code for problem C(Boring days) ~~~~~

signed main() { ll t; cin >> t; while(t--) { ll n,l,r; cin >> n >> l >> r;

vector<ll> a;
  for(ll i=0;i<n;i++) {
    ll x;
    cin >> x;
    a.push_back(x);
  }

  ll i = 0;
  ll j = 0;
  ll sum = 0;
  ll count = 0;

  while(j<n){
    sum+=a[j];
    if(sum<l){
      j++;
    }
    else if(sum<=r and sum>=l){
      count+=1;
      i = j+1;
      j++;
      sum = 0;
    }
    else if(sum>r){
      while(sum>r){
        sum-=a[i];
        i++;
      }
      if(sum<=r and sum>=l){
        count+=1;
        i = j+1;
        j++;
        sum = 0;
      }
      else{
        i = j+1;
        j++;
        sum = 0;
      }
    }


  }

  cout << count << endl;

}

}

~~~~~

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it -25 Vote: I do not like it

    bro, your final else block is the problem, its the same as if block

    include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    signed main() { ll t; cin >> t; while(t--) { ll n,l,r; cin >> n >> l >> r;

    vector a; for(ll i=0;i<n;i++) { ll x; cin >> x; a.push_back(x); }

    ll i = 0; ll j = 0; ll sum = 0; ll count = 0;

    while(j<n){ sum+=a[j]; if(sum<l){ j++; } else if(sum<=r and sum>=l){ count+=1; i = j+1; j++; sum = 0; } else if(sum>r){ while(sum>r){ sum-=a[i]; i++; } if(sum<=r and sum>=l){ count+=1; i = j+1; j++; sum = 0; } else{ j++; //only change } }

    }

    cout << count << endl; }

    }

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      267411889 check this, cuz the copy paste was horrible

      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Thanks , but can you explain why that was wrong in which test case it will fail

        • »
          »
          »
          »
          »
          22 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          well you else block is basically (sum < l) right? and in that condition you need to j++, i.e., only move the front pointer as the sum is already smaller than l.

          For example, 6 9 10 1 3 3 5 4 8 the original code will fail this test case and give 0, instead of 1. because it will not go to the pair i=5,j=4(which sums up to l) but would rather go to i=4,j=4

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

267409135 Can anyone tell me why is this not working? Like is my logic completely wrong or is there some edge case that the code misses?

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +7 Vote: I do not like it

Hello everyone, I need somebody to hack my friend's code: https://mirror.codeforces.com/contest/1982/submission/267413232

I am so sure that His code will overflow since he just used 32bits integer (int / i32). Hurry up! Don't let him discover it! Just hack the submission!

PS: His computer's battery has run out and I submitted his code after contest. But why it AC!!!!! I cannot accept it!!!!!

Thanks!


Update:

Sorry, his code is correct. Just sum up all the "-1" and "+1" will not exceed i32. My bad! Actually, he cannot submit his code since the battery problem, I want to easy him that his code maybe cannot pass the test (So that he will not lose this big chance to increase his rating). Okay...... Now he will be definitely very sad and regretful.

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +39 Vote: I do not like it

Is filling "TON wallet" field (and "Secret Code") with account id from mynearwallet in settings enough for getting reward in NEAR cryptocurrency for current round? Or what should I do to get it?

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I did surprisingly well in this round. This was a really fun one, questions were not very straightforward, I liked it a lot.

»
22 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

My rating is 1110.I participated in this contest. But my rating not changed.Why?

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Till now i was happy that i became specialist but all of a sudden ratings changes is disappeared, can i know what's the reason behind it?

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    They are probably running plagiarism checks and they will need to recalculate the ratings so it's kind of messy right now

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      But why they released earlier and now making such messy but i don't think that this happened before

      • »
        »
        »
        »
        22 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        This happens sometimes but usually the plagiarism checks are ran for multiple contests at once (And then you have the message that "the ratings for a few contests are temporarily rolled back") but I assume they wanted to do a single contest plagiarism check here because of the contest having prizes

        • »
          »
          »
          »
          »
          22 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          In that case then they have check plagiarism for both today's contest and recent div 3 contest.

          • »
            »
            »
            »
            »
            »
            22 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Maybe, not sure how exactly it works but I'm assuming that the plagiarism check has to be ran manually and now they are doing it for this contest because of the prizes

»
22 months ago, hide # |
Rev. 2  
Vote: I like it -23 Vote: I do not like it

Subject: Issue with Judgement in Problem C

Hi,

I encountered a possible error in the judgement of my submission for Problem C during Codeforces Round 955 (Div. 2). It seems there was a bug during the judging process.

Details:

My Submission During Contest: Submission 267358679 My Submission After Contest: Submission 267429867 During the contest, in the 2nd pretest, 6th test case, my submission was judged incorrectly. The actual output should be 0, but it was judged as 1, resulting in a wrong submission.

After the contest, I resubmitted the same solution, and it was judged correctly with the output being 0.

I would appreciate it if the issue could be reviewed and corrected as it affected my contest standing unfairly.

Thank you for your attention.

Best regards, Deshik conan45

»
22 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

I have one question for the cf community, why to give the score distribution beforehand, people can initially guess the difficulty of the contest, isn't it non exciting it would be more fun if we are not known that and may be we can keep it constant in every contest

»
22 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

FelixArg , My solution for D shouldn't have passed the test cases, but it did.

  • I knew the current difference between type1Sum, and type0Sum. ( let's call it RequiredDifference )

  • I knew for each of the sub-rectangle of size k*k, what are achievable differences. Lets call them (d1, d2, d3 ... dk).

I knew that I had to do a1 * d1 + a2 * d2 + a3 * d3 + ... ak * dk = RequiredDifference

I didn't know how that gcd ( d1 , d2 ... dk ) | requiredDiff .

But I knew, for ax + by = z , then gcd(x, y) | z. So I used this two variable equation property and passed test cases. Refer to my solution.

The test cases were weak for D. Ideally my solution shouldn't pass. It was later hacked by djm03178 .

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

So many people here are saying that B was a lot difficult than C. I did B in 20 mins, but it took me almost a day and more than 10 attempts to finally get AC on C. I had actually figured it in some time but it was giving TLE again and again. Don't know if I am too dumb or too smart lol!!

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +2 Vote: I do not like it

Exposing Cheating in Competitive Programming Cheating undermines the spirit of competitive programming. The Telegram channel selling Codeforces solutions, with Gautam_Himanshu implicated in using these solutions to unfairly boost their ranking. This not only disadvantages honest participants but also erodes the platform's credibility. The community must stay vigilant, report suspicious activities, and promote ethical practices. By addressing such issues, we can ensure a fair and rewarding environment for all. Let's work together to uphold the values of integrity and fair play in competitive programming. Report any evidence of cheating to maintain our community's standards.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Creating: .cfuser.near.

Transaction to create the account was sent, but the account is not on chain yet. Please refresh the page. If the problem persists, please reach out to the admins

Can you please help me?

»
22 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Even though I ate negative delta the problems were very good, I enjoyed the round so much.

»
22 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Hey folks! Here's an attempt of an explanation of problems A to D of this context with Tourist's codes https://www.youtube.com/watch?v=3fPvRAowuqU. Would be glad if you find it informative!

»
22 months ago, hide # |
 
Vote: I like it +34 Vote: I do not like it

How do I redeem the 1N prize? Sorry, this is the first time I've won something in an online contest, so I don't know how to redeem stuff. Thanks in advance for the reply!

  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I have the same question. And how do I determine if I have won a prize(because of unofficial participation)? Should it be a message, or other forms?

    • »
      »
      »
      22 months ago, hide # ^ |
       
      Vote: I like it +8 Vote: I do not like it

      I saw your rank, I think you are also eligible for the reward. They said unofficial participators will also be able to claim rewards. Ranking under 496 (including 496th rank) should be enough. I saw something in the settings->Wallet section (but it is only visible in Russian language). But I still don't know how to claim it. If you find out, please let me know too :D

      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        OK,thank you, maybe you have noticed, the form for filling out the award information has been sent out by the system about 5 days ago.(You can see it in "talks" page, which is near the position of your profile)

        I wrote this in case that you missed it. Please note that the DDL is 7.8 24:00 :)

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Dear Codeforces Team,

I recently received a notification regarding a significant coincidence between my solution for problem 1982B (solution ID: 267384934) and the solutions submitted by Muhammad_Tawfiq (solution ID: 267384934) and Antartic_Nafeez (solution ID: 267386858). I take such matters very seriously and would like to address this situation promptly.

Firstly, I would like to clarify that my intention has always been to adhere to the rules and maintain the integrity of the competition. I assure you that I have not intentionally shared my code with anyone nor copied from other contestants.

To provide more context:

  1. Code Review: I have thoroughly reviewed my code and confirmed that it is my own work. However, I understand that similar solutions can sometimes arise due to common approaches to solving the problem.

  2. Use of Public Platforms: I have not used public platforms like ideone.com with default (public) settings to share my code. All my code is developed locally or on private, secure platforms.

  3. Potential Common Source: If there was any unintentional similarity due to a common source or widely known algorithm published before the competition, I am more than willing to provide details of my references and thought process.

I request a thorough review of this case and am ready to cooperate fully by providing any additional information or evidence required. My goal is to clear up any misunderstandings and continue participating in Codeforces competitions fairly.

Thank you for your attention to this matter.

Best regards,

[Muhammad_Tawfiq]

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello Codeforces,This is in regard to plagiarism being put on one of my solutions. I want assure you that no such incident has been done by me the only common issue can be a code template i use for some questions .You can check all my previous contests and submissions.This was the first time i used this template seeing many other use a template of their own.If unintenionally I have made a mistake I apologize and assure that i wont be using templates as well from now on

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

seems everyone has received plagiarism message

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How long do the rollbacks take? I need to submit my resume with a screenshot of rating as proof in 4 hours:(

»
22 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it
/*
*    Author: Arjit Khare
*    Created: Friday, 28.06.2024 12:30 AM (GMT+5:30)
*    linkedin: https://www.linkedin.com/in/arjitkhare/    
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        // freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    #endif
    int t;
    cin>>t;
    while(t--){
        int n, m, k;
        cin>>n>>m>>k;
        vector<vector<int>> land(n, vector<int>(m));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin>>land[i][j];
            }
        }
        vector<string> s(n);
        for(int i = 0; i < n; i++)
        {
            cin>>s[i];
        }
        //{snow, nonSnow}
        vector<vector<int>> snow(n, vector<int>(m));
        vector<vector<int>> nonSnow(n, vector<int>(m));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(i == 0)
                {
                    if(j == 0)
                    {
                        snow[i][j] = 1*(s[i][j] == '0');
                        nonSnow[i][j] = 1*(s[i][j] == '1');
                    }
                    else
                    {
                        snow[i][j] = snow[i][j-1] + 1*(s[i][j] == '0');
                        nonSnow[i][j] = nonSnow[i][j-1] + 1*(s[i][j] == '1');
                    }
                }
                else if(j == 0)
                {
                    snow[i][j] = snow[i-1][j] + 1*(s[i][j] == '0');
                    nonSnow[i][j] = nonSnow[i-1][j] + 1*(s[i][j] == '1');
                }
                else
                {
                    snow[i][j] = snow[i-1][j] + snow[i][j-1] - snow[i-1][j-1] + 1*(s[i][j] == '0');
                    nonSnow[i][j] = nonSnow[i-1][j] + nonSnow[i][j-1] - nonSnow[i-1][j-1] + 1*(s[i][j] == '1');
                }
            }
        }
        // set<int> nums;
        int common = 0;
        for(int i = k-1; i < n; i++)
        {
            for(int j = k-1; j < m; j++)
            {
                int curr;
                if(i == k-1)
                {
                    if(j == k-1)
                    {
                        curr = snow[i][j] - nonSnow[i][j];
                    }
                    else
                    {
                        curr = (snow[i][j] - snow[i][j-k]) - (nonSnow[i][j] - nonSnow[i][j-k]);
                    }
                }
                else if(j == k-1)
                {
                    curr = (snow[i][j] - snow[i-k][j]) - (nonSnow[i][j] - nonSnow[i-k][j]);
                }
                else
                {
                    curr = (snow[i][j] - snow[i][j-k] - snow[i][j-k] + snow[i-k][j-k]) -
                           (nonSnow[i][j] - nonSnow[i][j-k] - nonSnow[i][j-k] + nonSnow[i-k][j-k]);
                }
                // cout<<curr<<" "<<endl;
                common = __gcd(common, abs(curr));
            }
        }
        int total = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(s[i][j] == '0') total -= land[i][j];
                else total += land[i][j];
            }
        }
        if((common == 0 && total == 0) || (common > 0 && total % common == 0))
        {
            cout<<"YES"<<endl;
        }
        else cout<<"NO"<<endl;
    }
    return 0;
}

Can anyone please!!! tell me what did I do wrong here in question D. please!!! I am disgusted

»
22 months ago, hide # |
Rev. 2  
Vote: I like it +6 Vote: I do not like it

It is showing "Amount to claim: 0." in the prize link, what's the problem? How can I resolve the issue?

Update: Fixed

»
22 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

Can I know how to claim the prize because I got 4 NEAR but when I enter the form link and make cf near account nothing happens can someone explain how to claim the reward please?

»
22 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Why I tried to connect NEAR account via here and clicking "Connect your account with NEAR ecosystem", only to get a text which reads, "500: Internal Server Error" in the url "https://acade.studio/cf/[account name]/[some UUIDs]"?

Also, I tried other guy's account on my computer, which can normally connects NEAR.

  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The link works either if you have rating 1400+ or if you won prizes during the round.

    If you did win prizes, send me a DM, I will help debug.

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

All

»
21 month(s) ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

Near Prizes-

I got 4 Near as a prize and I did sign up on Acade Studio as well as claimed the prize. However it is not showing up on the Acade Studio built-in wallet balance, and on MyNearWallet, it says it requires a deposit with NEAR to be able to do transactions. What can I do, or will the prize be given after some time? I did claim the prize almost a week back.

  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Do you remember what account did you withdraw the prize to?

    Also can you confirm that the amount to claim on the CF page shows up as 0?