PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, construct an array A of length N such that:
- -1000 \leq A_i \leq 1000
- For each 1 \leq i \lt j \leq N, the sum A_i + A_{i+1} + \ldots + A_j is not divisible by j-i+1. That is, the subarray sum is not divisible by its length.
EXPLANATION:
The simplest way to ensure that one number (say x) is not divisible by another number (say y) is to see whether 0 \lt x \lt y. If x is smaller then y, of course y can’t be a factor of x.
Let’s try to use this idea.
Consider the array A = [1, 0, 1, 0, \ldots], with alternating zeros and ones.
Since A contains only ones and zeros, the sum of any subarray cannot exceed its length.
Also, any subarray of length \gt 1 contains at least one zero and at least one 1.
This means any such subarray has a strictly positive sum, while also having a sum that’s strictly less than its length.
This is exactly what we wanted!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
#include <iostream>
using namespace std;
int main() {
int t; cin>>t;
while(t--){
int n; cin>>n; n++;
while(--n){
cout<<(n&1)<<" ";
}
cout<<"\n";
}
return 0;
}
Editorialist's code (Python)
a = [0, 1]*300
for _ in range(int(input())):
n = int(input())
print(*a[:n])