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

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

Was able to do A and B

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

F1 let me know that brute force is sometimes the solution

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

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.

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.

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

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

C was much harder than D

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

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

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.

E is so peak orz

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

F2=F1+Luogu P5283

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

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.

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

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

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

Here's my solution for D:

If pos[i] % 2 == l, then just set l = 1 - l then continue to $$$i-1$$$
Else if pos[i] % 2 == r then just set r = 1 - r, then continue $$$i-1$$$
Else, its NO

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    f = [0] * (n + 1)
    for i in range(n): f[a[i]] = i % 2
    l, r = 1 - f[n], 1 - f[n]
    ans = 'YES'
    for i in range(n - 1, 0, -1):
        if f[i] == l:
            l = 1 - l
        elif f[i] == r:
            r = 1 - r
        else:
            ans = 'NO'
            break
    print(ans)

I'm glad to solve five problems in this contest,but I only got 14 points which disappoint me.555

in $$$F1$$$ I can prove that it takes at most 30 operations for $$$N \ge 6$$$ and twice for $$$N = 5$$$ but how to prove the following :

Moreover, it can be observed that the number of transformations until the array becomes zero does not exceed 9

.

Alternate solution for D: Maintain two arrays a(where index parity even) and b(index parity odd), now see the consecutive numbers in each array lets say n=15 and if a has (4,5),(7,8) and b has (2,3),(10,11) so for array to be a valid hill we should be able to arrange these pairs in such a way that the parity of groups alternate and the largest element n sits in the middle of these sequence , eg sorting these bracket bases gives us the sequence of layers: 2 (Odd), 4 (Even), 7 (Even), 10 (Odd) , its of the form A2 B2 A1 B1 A1 B2 A2 here B1 would be the largest element that is n and A2,B2 are elements from consecutive pairs of array a and b and these pairs should alternate , as in our example 4,7 belong to same array a so we can't make this array a hill , if all consecutive sequence when sorted in increasing order of first pair element alternates so we can say hill can be formed

void solve(){
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    vector<int>odd,even;
    if(n==1){
        cout<<"yes\n";
        return;
    }
    vector<pair<int,int>>allpairs;
    vector<int>a,b;
    for(int i=0;i<n;i++){
        if(i%2==0)a.push_back(v[i]);
        else b.push_back(v[i]);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int m1=a.size();
    int m2=b.size();
    for(int i=1;i<m1;i++){
        if(a[i]==a[i-1]+1)allpairs.push_back({a[i-1],1});
    }
    for(int i=1;i<m2;i++){
        if(b[i]==b[i-1]+1)allpairs.push_back({b[i-1],2});
    }
    if(a.back()>b.back()){
        allpairs.push_back({a.back(),1});
    }
    else allpairs.push_back({b.back(),2});

    sort(allpairs.begin(),allpairs.end());
    int m=allpairs.size();
    for(int i=1;i<m;i++){
        if(allpairs[i].second==allpairs[i-1].second){
            cout<<"no\n";
            return;
        }
    }
    cout<<"yes\n";
    
}

submission link : https://codeforces.me/contest/2267/submission/392107745

I didn't catch 2267B...

In problem D, I wrote that takeout even based indexs(0 based indexing) and odd based indexes. now for even based, sort them and place them smallest on 1st left index, 2nd smallest on 1st right index, 3rd smallest on 2nd left index and so on. now for odd based indexes, we will make our final array of two types, first start the smallest of odd based from right with same rule as even and 2nd will be start from left. and we check these two array if they are valid or not. My reasoning for this is suppose of even cases we will have almost about n/2 elements, now if their sorted order alternate difference is exactly two then possibly then the possible answer array is just one which can be manually checked by any logic, suppose difference is greater than 2, then by pegion-hole, one pair must be their whose difference must be 1 (as we have distinct numbers from 1 to n), therefore they cannot on same slope of hill, so best way to arrange this left-right-left-right, although it got an AC, i still have doubts in this solution, can anyone provide why this is getting accepted with this logic with more intutive proof or solution or loigc>>

C is really an elegant problem. I felt proud of myself after solving it.

In Problem C, it can be shown that the optimal strategy is to select the largest possible sum of all elements divisible by at least one of the prime factors of $$$x$$$. This allows the problem to be solved in $$$O(\sqrt{x} + n \cdot p(x))$$$ time per test case, where $$$p(x)$$$ is the number of unique prime factors of $$$x$$$ (at most 6 in the worst case). Here is my solution, which ran in a maximum of 109 ms: 392038880

I think I have O[ n * ( log{A}+log{n} ) ] time + O(n) space for F2,
392224499

How would the solution change for Problem E if instead of changing a substring at at time we were allowed to change only a single character at a time? What better algorithm than brute forcing could be used?

help me debug 2267F2

http://codeforces.me/contest/2267/submission/392104010

Hi, regarding the plagiarism check message I received for problems 2267A and 2267B (my handle: shalok1212, flagged alongside yuvraj178):

2267A — Turn Into a Palindrome: My submission: 392009239, Sep 25, 20:17 (UTC+5:30) yuvraj178's submission: 392031925, Sep 25, 20:47 (UTC+5:30)

My submission is 30 minutes earlier and was solved independently.

2267B — Fashionable Array: yuvraj178's first attempt: 392032573, Sep 25, 20:48 (UTC+5:30) — Skipped My submission: 392053701, Sep 25, 21:33 (UTC+5:30) — Skipped yuvraj178's second attempt (the one flagged as matching mine): 392056281, Sep 25, 21:39 (UTC+5:30) — Skipped

For 2267B, yuvraj178 had already made an unsuccessful attempt at 20:48, before my submission at 21:33. His second, successful submission came 6 minutes after mine, and that is the one flagged as matching my code.

I wrote both solutions independently and did not share my code publicly (no ideone/pastebin, no public repo). Given the submission order above, I'd request the coordinators to review the timeline and reconsider the violation on my account.

Thanks for looking into this.

It appears that in G you can skip the last step with FFTMod and it somehow passes :)

Does anyone have another problem with the same idea as G?

An alternative approach for F2.

Instead of generating XOR values for all possible pairs—which requires $$$O(n^2)$$$ time—we can sort the array and group the elements conceptually like a Trie. This allows us to easily identify contiguous sub-segments that share a common binary prefix down to the $$$i$$$-th bit.

Since the smallest XOR values arise from pairs with the longest common binary prefix, we can iterate a target bit $$$i$$$ from $$$0$$$ up to the most significant bit (MSB). For each $$$i$$$, we generate pairs of elements that share a prefix down to bit $$$i+1$$$ but differ exactly at the $$$i$$$-th bit.

Suppose we have the array $$$[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]$$$.

• For $$$i = 0$$$: We first iterate over pairs differing only at the $$$0$$$-th bit: $$$(0, 1)$$$, $$$(2, 3)$$$, $$$(4, 5)$$$, $$$(6, 7) \dots (14, 15)$$$.
• For $$$i = 1$$$: We reduce the length of the common prefix. We now take all pairs $$$(x, y)$$$ such that $$$\forall x \in A$$$ and $$$\forall y \in B$$$, where:
  • $$$A = \lbrace 0, 1 \rbrace$$$ and $$$B = \lbrace 2, 3 \rbrace$$$
  • $$$A = \lbrace 4, 5 \rbrace$$$ and $$$B = \lbrace 6, 7 \rbrace$$$
  • $$$\dots$$$
  • $$$A = \lbrace 12, 13 \rbrace$$$ and $$$B = \lbrace 14, 15 \rbrace$$$
• For $$$i = 2$$$: We reduce the prefix size again, taking pairs where:
  • $$$A = \lbrace 0, 1, 2, 3 \rbrace$$$ and $$$B = \lbrace 4, 5, 6, 7 \rbrace$$$
  • $$$A = \lbrace 8, 9, 10, 11 \rbrace$$$ and $$$B = \lbrace 12, 13, 14, 15 \rbrace$$$
• For $$$i = 3$$$: We reduce the prefix size once more, taking pairs where:
  • $$$A = \lbrace 0, 1, 2, 3, 4, 5, 6, 7 \rbrace$$$ and $$$B = \lbrace 8, 9, 10, 11, 12, 13, 14, 15 \rbrace$$$

Naturally, we do not need to evaluate all possible pairs as the common prefix size decreases. Since we process the sets in strictly increasing order of their highest differing bit, we can terminate the generation process as soon as our pool of candidate XOR elements reaches or exceeds size $$$n$$$. We then sort the collected elements and retain only the $$$n$$$ smallest.

Suppose $$$n = 2^x$$$. As we decrease the size of the common binary prefix, the number of generated elements before termination can be analyzed as the sum of the $$$i$$$ terms:

This mathematical bound limits the total number of generated elements, ensuring the algorithm terminates well before exceeding time (TLE) or memory (MLE) limits.

My submission — Code

C the most worst problem lol

I found more intuitional solution for D lol. It's just greedy with two pointers. My submission:

C felt like the main bottleneck of the round: its key observation was less immediate than D’s, even though D came later. Was this ordering intentional?

For F1, how to prove the <=9 bound?

Soln of problem D:-

I solved this problem using set where i take take two diff set and and put the same parity index to it and then construct the ans array from front till i get n and then from back using upper bound

My solution to $$$E$$$ is different , it uses the fact that each 01 substring contributes $$$Cnt_0 * length$$$ where $$$Cnt_0$$$ is count of $$$0s$$$ upto start of the substring and $$$length$$$ is count of elements after first element of the substring . Vice versa works for $$$10$$$ substrings