stupid constructive problems

wow thanks for the quick editorial

Very good round (even though I lost rating :cri:)

I am proud to First Solve B today, it's my first time having such great experience.

on D, I did not divide cases, instead I thought about two pointers. I set $$$L=\min$$$ and $$$R=\max$$$, and the total sum as $$$\frac{L+R}{2} \cdot n$$$. And then, I advanced $$$R$$$ and $$$L$$$ until I could find an answer. For the exact method, please see my accepted submission — 182519051. I am yet not sure how this method really works, but it did. Can anyone provide a formal proof on why this works?

Here's a simple solution for D. For example, if $$$n = 5$$$, we use $$$[2, 3, 4, 5/6/7/8/9, 10]$$$. We can add 1 to all numbers to change sum without changing the LHS. To change the value $$$\mod n$$$, we can choose the correct integer in the 4th location. Using this we can get all integers above some value. And the square of max — min is provably larger than the current sum. So it works.

Nice problemset!! got +ve delta :)..stuck on D though!

C was amazing. Took me 40 minutes but made that..

My solution for D: 182515472

Let's assume that the minimum element is $$$x$$$ and the maximum element is $$$y$$$. Then we have a lot of freedom to change the elements in the middle without changing the range. The smallest sum is when the array is $$$[x, x+1, x+2,\ldots, x+n-2, y]$$$ and the largest sum is when the array is $$$[x, y-n+2, \ldots, y-2, y-1, y]$$$. We can achieve any sum between these extremes using a greedy algorithm. Start with the array with the smallest sum, visualize the elements as points on a number line, and move elements to the right one by one, where you move it as far as possible without making the sum exceed the target.

So if we have values for $$$x$$$ and $$$y$$$ such that it is possible, we can construct one possible array with the above approach. Now, how do we choose values of $$$x$$$ and $$$y$$$ for each possible $$$n$$$?

Let's assume we know $$$x$$$. Then we can iterate $$$y=x+n-1, y=x+n, y=x+n+1,\ldots$$$ until one of them is valid. We just test validity by making sure the range squared $$$(y-x)^2$$$ is between the minimum possible sum $$$(n-1)x+y+(n-2)(n-1)/2$$$ and the maximum possible sum $$$(n-1)y+x-(n-2)(n-1)/2$$$.

I assumed that it will always work when $$$x=2n$$$ and I assumed that $$$y(n) \le y(n+1)$$$ so that I can use two pointers in $$$O(n)$$$ time instead of iterating every possible $$$y$$$ for every possible $$$x$$$, which I believe would be $$$O(n^2)$$$.

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

This is my first time i get standing in top 500. As a pupil, i think this contest is easier than the previous div 2 contests. Anyone think so ?

E is a really nice problem

In problem B , for n=4, why answer can not be 1 1 3 2. ScarletS

My solution for D https://mirror.codeforces.com/contest/1758/submission/182529333

Let's say you want to make the sum of all the numbers as (2*n)^2 then on average all the numbers should be 4*n, now you want max — min as 2*n take max as 5*n and min as 3*n, now if you see all the remaining number still averages out to be 4*n, if n is even, distribute the number like 4*n-i,4*n+i and same for odd just 1 number would be 4*n

My solution for C :

we can think of a permutation as follows

• X,2,3..__....,n-1,1 ( '__' denotes there is no element on the xth index)
• here at the first index there is x and at the last index there is 1, and all other indices except xth index are filled with permutation[i] = i , i != x;
• Here only x index has no element in it , and we have not placed n in our list ,
• so we have to place n to the as right as possible.
• so we can just start iterating from (x+1)th index to (n-1)th index and see if n can be placed at that index and this index can be moved to xth index , if yes then we change x to j.
• for example
• n = 12 and k = 2,
• list = {2,empty,3,4,5,6,7,8,9,10,11,1}
• now we can see that for 4th index , you can move 4 to the empty place ,
• list = {2,4,3,empty,5,6,7,8,9,10,11,1}
• and at the empty place you can put n = 12;
• now you can not shift the empty position to the right so just place n over there
• list = {2,4,3,12,5,6,7,8,9,10,11,1}
• Note : You will have to take care of other edge cases as well !
• My submission : 182552063

Four constructive tasks... If you can't come up with normal tasks, why are you doing a contest?

My solution for C

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n, x;
    std::cin >> n >> x;

    std::vector <int> v(n+1);
    std::iota(v.begin(), v.end(), 0ll);
    v[x] = n;
    v[1] = x;
    v[n] = 1;

    int i = x+1, j = x; 
    while(i < n){
        if(v[j]%i == 0 && i%j == 0){
            std::swap(v[i], v[j]);
            j = i;
        }
        i += 1;
    }

    bool ok = true;
    for(int i=1; i<n; i++){
        ok &= (v[i]%i == 0);
    }
    if(!ok){
        std::cout << "-1\n";
        return;
    }

    for(int i=1; i<=n; i++){
        std::cout << v[i] << " ";
    }
    std::cout << "\n";

}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

If p[1] != n and p[1] = k, p[k] = n then try to place n as further as possible If p[1] = n then no need

My approach for task D: Assume we construct our initial sequence as M, M+2, M+4, .., M+2*(N-1). Difference between endpoints = d = 2*(N-1). Now let's define the Deficit as: sum — d*d. deficit = M*N + N*(N-1) - 4(N-1)^2 We can observe that deficit increases with increase in M, and it increases in multiples of N. So we can binary search for that point where deficit first becomes negative. At this point, absolute value of deficit is <= N. So we can cover the deficit by shifting the in-between elements by 1.

The bound in the editorial for F is indeed quite loose. A simple way to improve it:

To remove something we must have added it first so operations are at most 2*(number of added intervals). Case 1 adds one interval, case 2 adds two intervals, however case 2 operations can be at most half of the operations (since they pair with a corresponding case 1 operation). Therefore the described solution will do $$$3n$$$ operations at most.

Can someone please explain why this solution 182516763 works for E?

Welcome to ConstructForces. I love it.

another solution for problem D

1. For even number n: same as official solution, the answer is [n-n/2, n-n/2+1, ... ,n-1, n+1, ... ,n+n/2-1, n, n/2+1].

2. For odd number n: construct y = n*4, answer is [y-n, y-((n-1)/2)-1, ... , y-2, y-1, y, y+1, y+2, ... , y+(n-1)/2+1, y+n]. notice the first and the last is special. for instance: 7: y = 28, answer is [21, 26, 27, 28, 29, 30, 35], the max — min = 14, sum = 196 = 14 * 14.

I really liked problem d Although it took me every single cell in my brain to solve it But it was worth the effort

Why is complexity O(nlogn) instead of O(n) in C?

There's an another quite interesting solution for problem B:

In this situation, $$$XOR = Average = n$$$.

For $$$D$$$, here is another solution.

If $$$n$$$ is odd, we can let $$$[a_1,a_2,\dots, a_n]=[3n,4n-{n-3\over2},\dots,4n-2,4n-1,4n,4n+1,4n+2,\dots,4n+{n-3\over2},5n]$$$

If $$$n$$$ is even, we can let $$$[a_1,a_2,\dots, a_n]=[3n,4n-{n-2\over2},\dots,4n-2,4n-1,4n+1,4n+2,\dots,4n+{n-2\over2},5n]$$$

$$$\displaystyle\sum_{i=1}^na_i=4n^2,\max-\min=5n-3n=2n$$$

182509063

Alternative Solution for D:
Let req = (right — left)^2
For a section of n elements spread over a range of length len (len = max — min) and beginning from 1, we can find the min and max possible values that can be obtained by shifting values in this range.
​ Eg: len = 5, n = 3.
min = [1, 2, 5] = 8, max = [1, 4, 5] = 10.
We run an infinite loop for satisfying the condition min <= req <= max.
It can be easily proved that if this condition is satisfied, we'll always be able to find an appropriate solution for req.
Now, if max < req, then we'll need to 'boost' (add an offset to all elements), as that is the only way of satisfying the equation.

My Solution

what's wrong with my solution for C 182586576 .. i am not able to figure out

This contest was amazing! Thanks to everyone who contributed to its preparation :D

1758C — Almost All Multiples 182522546

Please can anyone help me to figure out why my solution is giving the wrong answer? Thank you in advance.

for question D, the sqrt(sum) question. My solution was like this. My solution for the even is the same but for the odd solution i did as like this: my sequence will be in the form of n/2+1,n+3,n+3,n+2,n+2,n+2,n+2,...,3*n/2+2, its sum is equal to n^2 + 2n + 1
proof: i did some maths adn made sure that 3*n/2+2>=n+3 for all n (>=2 stated in the question)

max-min=n+1
2*(n+3)+(n/2+1+3n/2+2)+(n-4)(n+2)=4n+9+n^2-2n-8=n^2+2n+1
someone pls tell me why am i wrong xd

1758C — Almost All Multiples — implementation(C++) and implementation(Python) are equal, i mean links are the same, can u correct it pls, thanks for blog btw!!

For problem E, I have doubts related to the sample input. in the question for the sample

row=2 col=3   hour=4
1 0 - 1
-1 -1 2

it's mentioned that the following is the configuration. Can anyone tell me how this configuration is reached?

For the first sample, this is a possible configuration for the clocks:

1 0 3
0 3 2

Any help will be appreciated. Thanks.

In D just write numbers from 1 to n ,then increase n by (n-1) ,then see how much more required to get (max-min)^2 ,let it be K so first add K/n in all numbers ,but there is till k%n left but that's not a prblm,just add it to the second last number and it won't create collision and remove distinction as at the beginning we freed upto n-1 spaces by increasing last number (n) by n-1 Xbir

Code of My Solution

Nice B question. Nicely explained, good approach.

Alternative approach to problem E:

Set up nxm bipartite graph, G. There is an edge from ith LHS vertex to jth RHS vertex of weight w iff there is a clock at (i, j) with value w. An edge also exists in the opposite direction with weight -w. Set up UFDS for G as well.

Perform dfs on G instead using the same logic of finding contradicting modulos. If so, just output 0.

Now iterate through all pairs in G, if ith LHS vertex isn't already in the same UFDS set as jth RHS vertex, there are exactly h possible clocks you can now insert at cell (i, j), then union these two sets.

Link: https://mirror.codeforces.com/contest/1758/submission/185844107

A quick solution for D, for n , no matter even or odd , consider the array: 3n+1,3n+1+2,3n+1+4,3n+1+6.....,3n+1+2(n-1), the sum of these elements are 4n^2, the sqrt of which is 2n, but the biggest — smallest element in the array is 3n+1+2(n-1)-3n-1 = 2(n-1), what can we do to modify it? that's simple , we add 1 on the biggest element which is 3n+1+2(n-1) and minus 1 on the smallest element 3n+1, now we get 3n+1+2(n-1)+1 — (3n+1-1) = 2n.

In The Problem C I have this solution can anyone explain why it fails ? "void solve() { ll n,k; cin>>n>>k; if(k!=n) { if(n%k!=0) { cout<<-1<<endl; } else { cout<<k<<" "; for(int i=1;i<n-1;i++) { if(i+1==k)cout<<n<<" "; else cout<<i+1<<" "; } cout<<1<<endl; } } else { cout<<k<<" "; for(int i=1;i<n-1;i++) { if(i+1==k)cout<<n<<" "; else cout<<i+1<<" "; } cout<<1<<endl; } }" Logic behind is that we know that K is to be placed first so the i+1 th place must be occupied by a number sivisible by k , so i just check if the number n is divisible by k then i will place n at K's original position .

Is my solution to C better than the editorial ?