SEGDEV-Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Kingvarun

DIFFICULTY:

Easy Medium

PREREQUISITES:

Math , Arrays

PROBLEM:

You need to create a array of N distinct numbers such that the there will be no subarray of size greater than 1 whose sum is divisile is by the length of that subarray.

EXPLANATION:

We can directly use brute force approach to create that N size array, such that above conditions hold.

We simply select N natural numbers starting from 1, but before select we have to check for the every subarray containing the last element that we select such that the sum of that array is not divisible by the size of that subarray,

If we found any subarray that is divisible than we exclude that number and have to check for another number greater than that.

Is this possiblle that we can’t find a number such that the all the subarrays containing that number will not follow the above condition?

No there will always a number which satisfies our condition

Because, let’s assume we have N size array and last value we have to check is X than sum of subarrays starting from i where i ranges from 1 to N-1 and ends at N should not be divisible by their respective sizes.

Assume that the sum of subarray of size N in P

If that P is divisible by N than last numbers can be replaced by any of this numbers X+1, X+2 , … X+N-1, because than the total sum will not able to get divisible by N, and In this N-1 possible numbers, there are also N-2 numbers which we can take such that subarray whose end points are 2 and N will not divisible by N-1 and this will aso happen for N-3 ,N-4 ,....2.

Thus we create a vector and simply push back N natural starting from 1 (not first N natural numbers) and by checking which number satisfies the above given condition.

TIME COMPLEXITY:

O(N ) per test case

SOLUTIONS:

Author's Solution
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int N = 505; 

int a[N];

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << "\n";
}

int32_t main()
{
    IOS;
    iota(a, a+N, 0);
    for(int i = 1; i+1 < N; i += 2)
        swap(a[i], a[i+1]);
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        solve();
    }
    return 0;
}
Tester's Solution
// final check of input files.
#include <bits/stdc++.h>
using namespace std;

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        cerr << res << endl;
        return res;
    }

    string readString(int minl, int maxl, const string &pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

int main() {
    input_checker in;
    int tt = in.readInt(1, 10);
    in.readEoln();
    while (tt--) {
        int n = in.readInt(1, 500);
        in.readEoln();
        vector<int> a(n);
        a[0] = 1;
        for (int i = 1; i < n; i++) {
            a[i] = a[i - 1];
            while (true) {
                a[i]++;
                bool ok = true;
                int sum = a[i];
                int cnt = 1;
                for (int j = i - 1; j >= 0; j--) {
                    sum += a[j];
                    cnt++;
                    if (sum % cnt == 0) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                cout << " ";
            }
            cout << a[i];
        }
        cout << '\n';
    }
    in.readEof();
    return 0;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

int main() {

    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);


        int t;
        cin>>t;
        while(t--)
        {
            ll n,i,p=2,g=0,sum,j;
            cin>>n;
            vector<ll> v;
            v.push_back(1);
        
            for(i=1; i<n; i++)
            {
                p=v[i-1]+1;
                
                while(1)
                {
                    sum=p;
                    for(j=i-1; j>=0; j--)
                    {
                        sum+=v[j];
                        if(sum%(i-j+1)==0)
                        {
                            g=1;
                            break;
                        }

                    }
                    if(g==0)
                    {
                        v.push_back(p);
                        break;
                    }
                    else
                    {
                        g=0;
                        p++;
                    }
                }
            }

            for(i=0 ; i<n ; i++)
            {
                cout<<v[i]<<" ";
            }
            cout<<"\n";
        }
            
             

            
        return  0;

    }
    
  
6 Likes

There is also an O(n) solution for this problem , where adjacent elements are of type 4k + 1 , 4k + 2.
(Solution: 56928296 | CodeChef)

7 Likes

This problem can also be solved in O(N).
Just use this series.

My Solution

Updated proof (previous proof was wrong :sweat:: ):

Let us consider two A.P. one with a = 1 and second with a = 2. Both have d = 4. Our answer consists of alternating terms of this two A.P. Now, without losing generality let’s assume that our subarray of length N is of form : 1, 2, 5, 6, ...

Now let’s consider two cases.

Case 1 (N is even):

  • Sum of such subarray is S = (N* (2N - 1))/2
  • Here S must be an integer. Because 2N-1 is odd, N must be divided by 2.
  • Rewriting sum would give us: S = N/2 * (2*N - 1).
  • Now, if the subarray is not good then N must divide S. N cannot divide first term because N/2 < N. N also can’t divide second term because that term is odd. Hence case 1 is proved.

Case 2 (N is odd):

  • Sum of such subarray is S = (N*(2N-1))/2 + (5 - 2a)/2 Here, a is either 1 or 2.
  • So, S can be either (2N^2-N+3)/2 or (2N^2-N+1)/2
  • Now, to S to be divisibly by N is mut be of form 2kN. Because, numerator must be even.
  • We can not get that form from either of above expressions. Hence, case2 is proved.
6 Likes

Can you please explain why does this work?

My solution to this problem:
3,2,5,4,7,6,…
Simply output x,x-1and increment x by 2.

2 Likes

Did u arrive at this result or u knew it before?

If i knew i would have submitted it very early . actually the way i arrived at the solution was on path of the authors’ approach itself and , so writing out some numbers for the smaller values of n <= 7 , i saw this pattern 1 , 2 , 5 , 6 …And then stress tested it for all possible n (in the given constraints) and it luckily worked :)`

4 Likes

I’ve also used the same series.
My Solution

I can’t really understand the editorial. The second to last paragraph should be explained better, as it is the important part. So suppose we pick a number that makes the subarrays that were divisible, not divisible anymore, as explained in the editorial. How do I know there wasn’t a subarray that was not divisible before but it is now with the new number?

3 Likes

There is also a solution in which we can start with initial array as [7,22] then for n-2 times append last value of array + 7. I have verified by running a loop from 1 to 500 to check if the sum of previous values at a particular index i divided by it’s length does not give int value i.e. not divisible. But still the solution was NOT ACCEPTED.
Can anyone please tell me the reason behind it???

Here, is my code:

T = int(input())
for tc in range(T):
    n = int(input())
    arr = [7,22]
    if n == 1:
        print(3)
    elif n==2:
        print(arr)
    else:
        for i in range(n-2):
            arr.append(arr[-1]+7)
        for x in arr:
            print(x,end=" ")
        print()

My solution in Python 3

cook your dish here

for _ in range(int(input())):
n=int(input())
x=3
for i in range(1,n+1):
if(i%2==0):
print(x-2,end=’ ‘)
else:
print(x,end=’ ')
x=x+1
print()

1 Like

this can be simply done by putting even numbers at odd index and odd numbers at even index
my soln

1 Like

See my solution ,may be that will help you!

Why this solution is giving a wrong answer, can anybody tell me?

void test(){
    int n;
    cin>>n;
    vector<ll>arr(n+1);
    iota(all(arr),0);
    for(int i=1;i<=n;i++)
    {   // If I am doing arr[i]=arr[i-1] here, then it is giving ac. 
        while(true){
            ll sum=arr[i];
            bool flag=true;
            for(int j=i-1;j>0;j--){
                sum+=arr[j];
                if(sum%(i-j+1)==0){
                    arr[i]++;
                    flag=false;
                    break;
                }
            }
            if(flag){
                cout<<arr[i]<<" ";
                break;
            }
        }
    }
    cout<<endl;
}

JJ challenges his friend GG to construct an array A containing N distinct elements such that the following conditions hold:

“”“distinct”""

2 Likes

There is no need of doing any kind of pre-computation. If you dry run the solution for n = 2, 3, 4, 5 then you clearly see there is pattern formation.
You have to just initialize pt1 = 2 and pt2 = 3 and each time add +4 in both the pointer and print both the pointer one by one

ll n; cin >> n;
ll odd = 3;
ll even = 2;
for (ll i = 0; i < n; i++)
{
if (i % 2 == 0) {cout << even << " "; even += 4;}
else {cout << odd << " "; odd += 4;}
}
cout << ed;

Hey, ig in case-1 you are calculating the (n/2)th term of the AP rather than the sum

1 Like

oh, i didn’t noticed that, thank you

why this works??

1 Like

even+odd =odd and not divisible by 2.
for length=3, sum will be (x+x-1+x+2)=3x+1… so we can conclude that for length of n we get sum as nx+y, y is remainder and y!=n so it works. Correct me if something is wrong.