KluydQ's blog

Codeforces Round 1123 (Div. 2) Editorial
By KluydQ, history, 15 hours ago, translation, In English

Thanks a lot for participating!

2267A - Turn Into a Palindrome

Solution
Implementation
Did you like the problem?

2267B - Fashionable Array

Solution
Implementation
Did you like the problem?

2267C - GCD Treasury

Solution
Implementation
Did you like the problem?

2267D - Backrooms Hill

Solution
Implementation
Did you like the problem?

2267E - Clean Substrings

Solution
Implementation
Did you like the problem?

2267F1 - XOR Transformations (Easy Version)

Solution
Implementation
Did you like the problem?

2267F2 - XOR Transformations (Hard Version)

Solution
Implementation
Did you like the problem?

2267G - New LRT

Solution
Implementation
Did you like the problem?
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
15 hours 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
»
15 hours ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

ORZ round. But in my opinion, C is harder than D.

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

    Same, didn't even prove my approach for C, just went ahead with intuition.

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

Was able to do A and B

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

i should have worked on D instead of C...

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

F1 let me know that brute force is sometimes the solution

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

you didn't link the editorial in the original blog post

→ Reply
»
14 hours ago, hide # |
← Rev. 2  
Vote: I like it +23 Vote: I do not like it

I feel like the problems in this round, except for G (which I couldn't solve), weren't that good.

Also, the extension from F1 to F2 is essentially an existing problem (https://qoj.ac/problem/2995), with an even better time complexity.

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

    It has the same time complexity, isn’t it? Moreover, the crux of the problem was to understand that there is not more that $$$\log(A)$$$ transformations. Because of the fact that we need to do transformations +-9 times gives you greater time complexity.

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

I had a simpler solution for D.

Let's assume the array has an even length. Visually, if we "unfold" the hill and place it's elements in order it's gonna put all the outermost pairs A[i] and A[n-1-i] next to each other. This means that if we sort the initial array, in every pair A[2k] and A[2k+1] there must be one at an even position and one at an odd position, as one of them is gonna go to the left side and one to the right side, and their positions will have opposite parity. If the array has an odd length, we can just skip over the first element and solve for the rest of the array.

All you have to do in the implementation is sort the array and go through every pair where A[2k], A[2k+1] and check that their parities don't match. Fits in 15 lines.

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

    Solved the same way using union find, I am still not able to understand how to come up with the solution given in the editorial.

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

shouldn't the Time Complexity of $$${C}$$$ be $$${O(n\cdot\sqrt[3]{x}+\sqrt{x})}$$$ ?

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

No idea how my solution worked on F1, but I'm not complaining

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

C was much harder than D

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

    C was simple: if gcd(v[i],x)>1 then we can take full of v[i] as v[i] will continously decresed by the gcd and it will remain same through this process...and if u think internally gcd will always be one of the divisor of x..and each divisor will give answer independently...so bruteforcing over each divisor individually and try to take as much as elements which are divisable as sum....ans will be the maximum sum

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

      we can make use of this basic gcd proposition- gcd(ai,g)=gcd(ai-g,g)

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

        most beautiful thing of this problem is that any divisor ultimately triggers its prime factors...so indeed we need to brute for each of the prime factors only

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

          yes ofc, see, anyways g will always remain one of the prime factor of x i am just stating that the gcd will not gonna change even after decreasing ai

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

Also, my post-contest discussion stream for all problems is here

→ Reply
»
12 hours ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

This round Felt like a div 3, especially F1 was really easy for a div 2.

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

I don't think it was quite intended for F2, but I solved it by dividing the intial array in many other arrays, each corresponding to a specific bitmask. From what I understand, it allows for my solution to have complexity $$$\frac{n^2}{const}$$$, instead of just $$$n^2$$$, where const can go > 2048. I also think it is highly amortized estimation.

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

E is so peak orz

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

In C instead of divisors, we can use prime divisors only ( this will give better time complexity) , check my code 392022818

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

F2=F1+Luogu P5283

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

For problem E, there is a more tedious solution (and with higher complexity)

Firstly, the contribution of a substring is the number of runs / 2, floored.

When a bit at s[x] (0-indexed) flips and s[x-1] == s[x+1], all substrings containing [x-1, x+1] will get a ±2 in number of runs depending on whether s[x-1] == s[x], which increases the answer by ± x * (n-x-1)

Then for substrings whose right or left boundary is x (inclusive of x), we need to find the number of bits that are equal to s[x-1] and s[x+1] on the left and right respectively, and call it cnt. This can be handled using a Fenwick/Segment Tree.

  • If s[x-1] == s[x], cnt will be the number of substrings with odd runs. Hence, this increases the answer by cnt
  • If s[x-1] != s[x], cnt will be the number of substrings with even runs. Hence, this increases the answer by -cnt

This logic applies similarly for the right side.

The initial calculation of the string can be viewed as inverting bits on a string that is originally filled with '0'

This is for when one could not make the observation over how we can separately handle cnt0 * cnt1 to be the number of odd sums. i would say E is a great problem.

392056887

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

Alternative solution to E: For a fixed string s, assume it starts with "1". The number of required operations will be the number of "10" substrings. This way, we don't have to deal with roundings. We can use segment tree to calculate the answer.

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

A at 250 and F1 at 1000 on the same round is a weird scoreboard. F1 did not feel 4 times harder than A.

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

Alternate Solution for C:

Notice that we need to find a subarray with $$$\gcd(x, a_{i_1}, a_{i_2}, \dots) \gt 1$$$ and the sum $$$(a_{i_1} + a_{i_2} + \dots)$$$ should be maximum. Now this $$$\gcd$$$ of a maximum sum array and $$$x$$$ will always be a multiple of a prime factor of $$$x$$$. So just do prime factorization of $$$x$$$ and for each prime factor of $$$x$$$, let's say $$$p$$$, iterate over the array and find the sum of the elements that are a multiple of $$$p$$$.

The distinct number of primes for $$$x \le 3 \cdot 10^5$$$ is not more than $$$7$$$, because $$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \gt 5 \cdot 10^5$$$. So overall Time complexity is $$$\mathcal{O}(\sqrt{x} + N)$$$.

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

    any idea why this implementation gives TLE?: I think it should fit within the constraints

    /*
Created on: 2026-09-25 21:10:58
Author: Shivam
*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using st = string;
template<typename T>
using V = vector<T>;
template<typename T>
using MSET = multiset<T>;
template<typename T, typename U>
using P = pair<T, U>;
template<typename T, typename U>
using UM = unordered_map<T, U>;

#define eb emplace_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define F first
#define S second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define sz(x) ((ll)(x).size())
#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
#define loop(i, start, end) for(ll i = start; i <= end; ++i)
#define rloop(i, end, start) for(ll i = end; i >= start; --i)

inline ll msb(ll n) {return 63 - __builtin_clzll(n);}
inline ll setbits(ll n) {return __builtin_popcountll(n);}
inline ll trailzeroes(ll n) {return __builtin_ctzll(n);}

const ll LOG = 63;
const ll MOD = 1000000007LL;

void solve() {
    ll n, x; cin >> n >> x;
    V<ll> a(n + 1, 0);
    ll M = 3e5 + 5;
    V<ll> freq(M + 1, 0);

    loop(i, 1, n){
        cin >> a[i];
        if (a[i] <= M) {
            freq[a[i]] += a[i];
        }
    }
    V<ll> divisors;
    for (ll i = 1; i <= x / 2; i++) {
        if (x % i == 0) {
            divisors.eb(x / i);
        }
    }
    ll ans = LLONG_MIN;

    for (ll d : divisors) {
        ll sm = 0;
        for (ll m = d; m <= M; m += d) {
            sm += freq[m];
        }
        ans = max(ans, sm);
    }
    if (ans == LLONG_MIN) {
        cout << "0\n";
        return;
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll tt = 1;
    cin >> tt;
    while (tt--) solve();

    return 0;
}
    → Reply
    • »
      »
      »
      32 minutes ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      You are trying to find all divisors that too in O(x), you can find prime factors in O(sqrt(x)) and then proceed to simply check for divisibility by a single loop, my code for reference:

      392023418

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

I can't prove why this works but here's a greedy approach (for problem D) that also construct such valid array configuration. Firstly we can divide the elements into odd and even indexed, and sort it. The main idea is to arrange the hill from the left by going back and forth between the odd and the even array (i.e. odd-even-odd..).

And if while doing so the placement isn't valid, we will place the element from the right (if it can't be placed in the left side of the hill, it has to be a part of the right side). After that we keep building from the left (if placement is valid). We can't build such valid configuration if placing the element in the right side won't work too.

Here's my solution 392111475

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

    Here is a proof:

    The left-most and right-most current blank on the two sides must by of one of the two types: T1 is where both blanks are of odd index or both blanks are of even index, and T2 means one blank is of odd index and the other is of even index. For convenience we call the two cases of T1 as T1O and T1E.

    And we notice a few properties 1. Deaths (where it immediately can't build) can only happen on T1. Where both parity fails. In case of T2 you put it on the side with correct parity (your case where the left side can't be placed happens here). 2. T1 always changes into T2 when a new element is put into it, and vice versa (because placing an element changes the parity of the blank on one side).

    When you finish then there is a valid configuration, which is trivial (you just constructed it). Now let's see why a case being stuck is not possible to avoid. First we would see that T1 always changes to T2 and T2 always changes to T1, so the time they appear won't change regardless of your actions (put on which side). Also in case of placing an element into T2, the board would force you to put it on exactly one side as the other side won't work (wrong parity), therefore the transition into T1O or T1E is also forced and not depending on your action. Therefore regarding the states of T1O, T1E, and T2, there is only one possibility regardless of your action. Your action only changes the direction where you put the numbers in, which does not affect death (since only T1O and T1E matters which does not depend on direction).

    (I feel like there could've been a D2 that requires the count or requires a minimum cost construction in some way instead of keeping that C)

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

Here's my solution for D:

solution
code
→ Reply