KluydQ's blog

Codeforces Round 1123 (Div. 2)
By KluydQ, history, 6 weeks ago, In English

Hello, Codeforces!

We are glad and excited to invite you to take part in Codeforces Round 1123 (Div. 2), which will take place on Sep/25/2026 17:35 (Moscow time). You will be given 2 hours and 15 minutes to solve 7 problems. Problem F will be divided into subtasks.

Problem A B C D E F1 + F2 G
Score 250 500 1000 1250 1750 1000 + 2000 3000

Problems were authored by KluydQ, Aldk, YF_YUSUF, Dibamboo and Wansur.

We would like to give special thanks to:

UPD: Editorial is available here https://codeforces.me/blog/entry/157126

Congratulations to the winners:

Div. 1:

  1. StarSilk

  2. __baozii__

  3. solar_tree

  4. maspy

  5. Papaulo

Div. 2 (trusted participants):

  1. solar_tree

  2. jisoofan

  3. kaiboy

  4. GoogleBot

  5. HADIA_ABD

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

»
6 weeks ago, hide # |
 
Vote: I like it +30 Vote: I do not like it

First time seeing a 250 points problem.

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

As a participant, my goal is to solve two problems. Good luck to everyone!

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

I didn't see A and B have this low points in a while. I hope I get my color back

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

As a tester, I love Wansur

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

Is 1000 point F1 a typo? If not why isn’t it just non-adjacent subtasks?

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

problem A :

2 + 2 =

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

Div. 3 disguised as Div. 2? 'Cause wym A is only 250

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

is F1 ez as a normal 1000pts prob :)?

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

I don't have a good feeling about this if C and F both have the same amount of pts.

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

No it's 74TrAkToR we are in great danger

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

First time where an author is a pupil ;)

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

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

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

The F1 and A being worth that low scare me

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

As a tester, post contest discussion stream here

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

As a participant, I'll enjoy the contest instead of the mid-autumn festival.

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

Is that your kitty? :)

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

Spelling Mistake: "probmles" — > "problems"

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

fkikfrfoeroreoreoreo49349498934983499935893459345893459854

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

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

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

Why the kitten looks flat ToT

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

I like the cat

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

glhf. Plan to solve 3 atleast...

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

that's a cute cat >.<

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

I will be pupil.

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

Oh, is this kitty yours? I love it

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

Is F1 actually intended to be easier than D? I was a bit surprised to see F1 with a 1000-point score while D has 1250. Could you clarify the intended difficulty/order?

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

Maybe I have to give up the mid-autumn festival.

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +3 Vote: I do not like it 
#include <iostream>
using namespace std;

int main() {
    int A = 250;
    int B = A + A;
    int C = B + B;
    int D = C + A;
    int E = D + B;

    int F1 = C;
    int F2 = C + C;
    int G = F1 + F2;

    cout << "Problem\tScore\n";
    cout << "A\t" << A << "\n";
    cout << "B\t" << B << "\n";
    cout << "C\t" << C << "\n";
    cout << "D\t" << D << "\n";
    cout << "E\t" << E << "\n";
    cout << "F1+F2\t" << F1 << " + " << F2 << "\n";
    cout << "G\t" << G << "\n";

    return 0;
}
→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    #include<iostream>
int main(){int a=250,b=a*2,c=b*2,d=c+a,e=d+b,f=c,g=c*2,h=f+g;std::cout<<"A="<<a<<" B="<<b<<" C="<<c<<" D="<<d<<" E="<<e<<" F="<<f<<"+"<<g<<" G="<<h<<std::endl;}

    idk what to do, just.... waiting... and having fun.

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

crazy score distribution

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

Cat above the tractor but under the sky, is it cat or not ??

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

Tomorrow is Mid-Autumn Festival!!!Hope it will be a good match.

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

As a tester, I really enjoyed the problems!

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

I wish I could take this contest but i'm drowning in work rn

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

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

Problem F1 is only of 1000 points does this means it will be of the same level around C which is also of 1000 points.

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

ragebait points

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

Hope everyone giving this contest will get a huge negative delta and will never recover from that

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

Really hope i am able to solve E in time. GLHF

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

is it rated?

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

wish everyone happy Mid-Autumn Festival！

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

excited for this

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

Is the F1 going to be easier than D ..? What i am able to see from the score or it's something else.!

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

I expect that round will be interesting and balanced good luck to everyone!

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

I hope to become expert in this contest :-)

UPD: yay!!

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

im new to this competitive programming can i attempt this one? im having knowledge in python as i worked in ai and data science and automations (weak in data structures)

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

Problem A:

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

A and B together are only 750, then C jumps straight to 1000 and D is just 250 above that. With 2h15 and F split into F1 and F2, feels like the round actually starts at C. Good luck everyone.

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

i am student

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

As a participant, I don’t know what awaits us there, but I can say that this DIV will be unforgettable.

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

good luck everybody :)

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

hahahaha i am gonna level up to green broooooo

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

cute car

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

i wish the problem problem A be like that :a+b

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

w contest

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

too many cheaters top 40:

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

A bit of a weird contest, but C is a nice problem.

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it +2 Vote: I do not like it

B = https://www.luogu.com.cn/problem/P9143

English Translation of P9143
→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

so many people solved F1 ... How to do it ?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Brute force is enough

    → Reply
    • »
      »
      »
      6 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      no wayyy !!! . I was guessing everything would go to zero, but couldn't prove after how many turns..

      → Reply
      • »
        »
        »
        »
        6 weeks ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        CP is not like MO, we often use "guess" instead of "prove":)

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

        let B be msb currently in the array. suppose c elements have bit B = 1 and n - c elements have bit B = 0.

        pairs with matching bits cancel bit B to 0, producing values strictly < 2^B. the number of such pairs is:

        f(c) = c*(c-1)/2 + (n-c)*(n-c-1)/2 = c^2 - n*c + n*(n-1)/2

        this quadratic minimizes at c = n/2, where its minimum value is:

        f(n/2) = (n^2 - 2n) / 4

        for this minimum to be >= n:

        (n^2 - 2n) / 4 >= n <=> n*(n - 6) >= 0 <=> n >= 6

        because the transformation strictly selects the n smallest values, pairs with bit B = 0 are always chosen before any pair with bit B = 1:

        • for n >= 6: there are always >= n pairs with bit B = 0, so the highest bit is guaranteed to be eliminated in strictly 1 turn.
        • for n = 5: the worst split (c = 2 or 3) leaves only one single 1 in the array, which vanishes on the very next turn (at most 2 turns per bit).

        since a[i] < 2^30 (at most 30 bits), the highest bit strictly decreases every turn, meaning the array is theoretically guaranteed to reach all 0s in at most 30 turns (at most 60 for n = 5).

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

    Try to generate tests and check what happens to the array after you apply the operation a few times.

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

Too large gap between F1 and F2

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

i am done

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

How so many solves on $$$F1$$$?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Personally, I just generated random tests and checked how many times the operation is applied before the array becomes all zeros. The result is intuitive for big n: the bits become 0 very quickly, from the MSB down to the LSB. For n <= 4 the array can cycle (see 0, 0, 1, 1)

    → Reply
»
6 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Watch me TLE on F1

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Good contest, I love C, and definitely will try and upsolve D. First time solve Div2F ;). I don't really like F1 tho because it needs nothing but implementing

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

Thanks for the great round! I enjoyed Problem C.

Was anyone else getting TLE on test 23 for D? It was running about 100ms on my (fairly slow) computer for $$$n=250000$$$, one test case and <1ms for $$$10000$$$ cases with $$$n=20$$$.

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

First contest!!! Now I know I do not deserve this username

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

does anyone have a riguros proof for C?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Isn't it like, we are only considering the distinct prime factors of x, so at max 15 or so factors so that makes the time complexity about O(k * N) or so, where k is at max 15

    → Reply
    • »
      »
      »
      6 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Yeah that's the idea, i'm just asking for a proof that it's correct, it's pretty easy to guess it gets AC :)

      → Reply
      • »
        »
        »
        »
        6 weeks ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I dunno if this counts as proof, but the thought was that, the final value of x would always be a multiple of initial value of x, so doing just the distinct primes works

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

        Assume x > 1. After any operation x > 1 still holds. Look at the final value of x in an optimal sequence of operations. Take any prime factor p of the final value of x. Since p remained as a factor of x, all numbers that we took must have been divisible by p. If we take all values divisible by p, it will also be a valid sequence of operations.

        → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    yeah I did something during contest... the point is that transformation of X -> g can never add a new prime factor, it can only remove it,

    so I realized that in the end we can't pick up two different prime values ... so all values to be picked has to be multiple of one of the prime factor.

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

    i did it dp first if u perf oper btw x , a[i] regardless how many time u repeat the operation with same elemnt x will end to be gcd(x ,a[i]) so it's like if u did it once the optimal is to keep till a[i] = 0 second x always go to some divisor of it (very clear)

    So before anything any a[i]%x == 0 then finish these values then dp[x] = max{sumOfaiDivisbleBy d + dp[d]} where d is divisor of x not equal of x and to solve the problem of taking ai twice u notice that if u are at x then u dont need to take any multiple of x so dp[x] = max{sumOfaiDivisbleBy d -sumOfaiDivisbleByx + dp[d]}

    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    proof-by-AC is enough

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

    this is the mathematical proof for my solution

    let X_0 be a natural number greater than or equal to 2, and a_1, a_2, ..., a_n be natural numbers.

    Define the set of reachable divisors R recursively as: 1, X_0 is in R. 2, If d is in R and g = gcd(d, a_i) > 1, then g is in R.

    The maximum number of coins S_max that can be stolen is: S_max = max over all d in R (excluding 1) of the sum of all a_j such that d divides a_j.

    Proof:

    Upper bound: S_steal <= S_max Every valid operation updates x to gcd(x, a_i), implying x_new divides x_old. By induction, x is in R at every step. Let d_end in R (excluding 1) be the final parameter value before the operation stops (or transitions to x = 1) Any pile j touched when the state is x_k satisfies x_k divides a_j (if cleared) or gcd(a_j, x_k) > 1 Since d_end divides x_k for all active states x_k, any pile j contributing coins must satisfy d_end divides a_j Thus, S_steal is less than or equal to the sum of a_j for all j where d_end divides a_j, which is less than or equal to S_max.

    Lower bound: S_steal >= S_max Let g in R (excluding 1) be a divisor that achieves S_max

    by definition of R, there exists a sequence of piles picks i_1, i_2, ..., i_k such that iteratively applying x to gcd(x, a_i_m) transitions X_0 to d_1 to ... to d_t, call it g Execute one single operation on each of these piles to reach state x = g.

    once x = g, consider any piles j where g divides a_j. Here, gcd(a_j, g) = g > 1. Taking g coins leaves a_j' = a_j — g and updates x to gcd(a_j — g, g) = g Repeating this a_j / g times reduces pile j to 0 coins while maintaining x = g.

    Executing clear for all j where g divides a_j empties these piles, yielding S_steal = sum of a_j for all j where g divides a_j = S_max.

    Combining the bounds give S_steal = S_max

    i think the lemma the other person posted should be enough though

    i need to sleep it's 1am

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

Also really nice F although it's a bit hard on the implementation :p

→ Reply
»
6 weeks ago, hide # |
← Rev. 8  
Vote: I like it 0 Vote: I do not like it

nvm

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

It's possible to solve G by calculate the number of ways to reach $$$i$$$ for all $$$i \le n$$$ with a simple dp then use convolution + CRT to solve the rest part...

my submission

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

B is atleast 1000 rated

It was hard to come up with sorting -> printing -> cleaning -> repeat till u reach the highest frequency of element

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

Abnormally easy contest

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

It's like div2.5 for me :)

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I think this is the best round i have ever participated so far
Huge thanks to authors for this amazing contest

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

Can anyone tell me why the maximum number of transformations is low in F? Can't really seem to prove it, its $$$O(log n)$$$ right?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Consider

    ???
    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +19 Vote: I do not like it

    Well it can be proven that for n>=5 each transformation lowers the amount of active bits by 1. Every xor of 2 elements with the same value for the highest bit will always result in 0 for that bit, which is always smaller than considering two elements with different values over that bit.

    The number of ways to pick elements with the same value for a bit h is C(cnt0,2)+C(cnt1,2) where cnt0=nr of elements where bit h is 0 and cnt1=nr of elements where bit h is 1. This value is smallest when cnt0=cnt1 and if you check for n>=6 the sum C(cnt0,2)+C(cnt1,2) is always at least n, therefore the n smallest xors will have bit h=0. for n=5 you can check by hand :)

    I hope this is clear enough, i'm not that good at explaining things...

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

Amazing F1 good job writer

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

any hints for D

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    My Sol
    → Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Am i the only one who doesn't have to allocate a $$$O(n^2)$$$ array every transformation? Just use a multiset/priority_queue and keep the $$$n$$$ smallest!

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

I got A and B but got stuck on C ....

Does anyone know how to approach C ?

i thought it like sort array according to maximum frequency ? then apply key idea

this is how i did it .....

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//code

int coins = 0;

for(int i = 0;i < n;i++){

while(a[i] > 0 && __gcd(a[i],x) != 1){

int g = __gcd(a[i],x);

 a[i] -= g;

 coins += g;

 x = g;

}

}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

so while loop does calculates till it get 0 or gcd == 1 but i was unable to get the proper solution it still got wrong idk y...

If anyone knows pls let me know>>>>>

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    so if u choose a prime factor u can always finish a stack since a[i] — p is divisible by p too but if u pick a prime factor u cant move anywhere but this is still effective

    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Suppose you perform a steal on $$$a_i$$$, and let $$$g = \gcd(a_i,x) \ne 1$$$. Note we immediately have that $$$a_i$$$ is divisible by $$$g$$$. After this first operation, $$$a_i := a_i-g$$$ and $$$x := g$$$. Now $$$a_i$$$ is still divisible by $$$g=x$$$, meaning $$$\gcd(a_i,x)=g=x$$$. So now you can keep applying the operation to $$$a_i$$$ without $$$x$$$ changing, eventually getting $$$a_i$$$ down to zero. So if you can perform an operation on any element, it always makes sense to keep doing it until that element reaches zero.

    Now you only need to choose which elements to try to steal from. Suppose you pick the elements $$$a_{i_1},a_{i_2},a_{i_3},\dots,a_{i_k}$$$, in that order. To pick those, you must have $$$\gcd(a_{i_1},x) \ne 1$$$, $$$\gcd(\gcd(a_{i_1},x),a_{i,2}) \ne 1$$$, $$$\gcd(\gcd(\gcd(a_{i_1},x),a_{i_2}),a_{i_3}) \ne 1$$$, etc. You can rewrite this as $$$\gcd(a_{i_1},a_{i_2},\dots,a_{i_k},x) \ne 1$$$. In other words, all those values must share a common divisor greater than 1.

    Note that this common divisor must be a factor of $$$x$$$, so to solve this, I found every factor of $$$x$$$ greater than 1. Then for each factor $$$i$$$, I summed up all the array elements divisible by $$$i$$$, and I then took the max of this across all factors. 392035843

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

Intresting contest, wanted to try F2 but time is money

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

D>>F1 in my opinion

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

Amazing contest excellent problems thanks to authors good job guys!

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

is this unrated?

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Did i overcomplicate D?

Spoiler

I'm sorry, i'm not really good with the markdown for math, i hope it's clear.

Amazing contest BTW

edit: it looks like i did

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

Difficulty is all over the place. Genuinely how is $$$F1$$$ an $$$F1$$$? That deserves like a $$$C$$$ at best.

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

I'm in a great mood today, and I really enjoyed focusing on the topic.

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

Big +ve delta, thanks for the contest!!!

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

A pretty natural screw-up found its way into F2.

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

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

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

Where is the editorial ??

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it -9 Vote: I do not like it

good round

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

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

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

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

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

So happy in appearing in my first winner list!

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

I would have made it up there if there was a first solves section...

→ Reply
»
6 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Hello,

I request a manual review of the coincidence flag on my submission 392048627 for problem 2267G in Codeforces Round 1123 (Div. 2).

My solution was written independently. I did not copy from or share code with Nours200, whom I don't know also and I didn't access their solution during the contest.

The submissions use the same underlying DP idea, but the implementations differ. I use calc(), dp, add, and a cumulative recurrence, with bit extraction inside calc(). Submission 392059274 uses buildDp(), g, y, a differently written recurrence, bit preparation outside the function, and an explicit i == 0 case. The function structure, loops, and modular updates also differ.

I believe the overlap comes from the mathematical approach to the problem, including the powers-of-two DP, applying the transformation twice, and the final condition (m & x) == x. Please compare the full source codes and reconsider the flag.

My submission: 392048627 Compared submission: Nours200 / 392059274

Thank you.

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

Hello, I want to ask for a manual review of the coincidence flag on my submission 392063124 for problem 2267D. I came up with my solution to this problem and coded it myself. I didn't copy or receive code from any of the users named in the warning, and I don't know any of them. What I did was store the index of each number and then check the pairs (n,n-1), (n-2,n-3), etc. For every such pair, I checked whether the indices of the two numbers have different parity. If they had the same parity, I printed NO; otherwise, I continued checking the other pairs. I thought about it myself during the contest and coded it myself. It will be great if you could review the coincidence flag manually and compare the full submissions. Submission: 392063124 Problem: 2267D Thanks.

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

Hello, I respectfully request a manual review as I've received a warning that my submission 392055948 for the problem 2267C coincides with submission 392069096.

I want to clarify that I solved and wrote my submission independently and had no communication with these users and I don't know them.

I understand that the implementations are very similar. The solution is basically factoring x and then find sum of elements divisible by each prime factor and store the maximum one. That was how I approached to the solution.

However I've attached a screenshot from my VS Code timeline showing the developement history of the actual source file. It shows that the code was in an incomplete state at 10:05 PM(GMT+6,Dhaka time) on sept,2026 during the contest. and then the remaining logic was added at 10:07 PM, which was submitted at 10:08 PM. ScreenShot

I'm providing this as evidence of my own development process. The solution is so simple and short that it naturally coincides with others. And prime factorization has common template that I used from this published 2 months ago.

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

Hello,

I received a plagiarism/coincidence warning for my submission 392059274 to problem 2267G.

I want to clarify what happened. I wrote the solution myself during the contest. However, my local C++ compiler was not working correctly at the time, so I used an online compiler to compile and run my own code because I needed to check whether my implementation was producing the expected output.

I did not copy the solution from tapandutta46779, and I do not know this user. I also did not use their submission or communicate with them during the contest.

I understand from this warning that using a public online compiler can potentially expose submitted code and cause an unintended coincidence. I was not aware of this risk at the time, and I apologize for using it during the contest.

Could you please review submission 392059274 and the other submission involved in the warning? I would appreciate it if the circumstances could be taken into consideration when reviewing the case.

I will make sure not to use public online compilers during contests in the future. Thank you.

→ Reply