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

Автокомментарий: текст был обновлен пользователем KluydQ (предыдущая версия, новая версия, сравнить).

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,