PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N (which is even) and K, find an array A of length N such that:
- Half the elements of A are even and the other half are odd.
- The sum of the elements of A is K.
- 1 \leq A_i\leq 10^5
EXPLANATION:
We want \frac{N}{2} elements each to be odd and even; and they should all be positive.
So, the smallest array we can create is A = [1, 1, 1, 1, \ldots, 1, 2, 2,2, \ldots, 2] containing \frac{N}{2} each of ones and twos.
If the sum of this array is \gt K, then we certainly can’t have a sum of K; so the answer is -1.
Now, let’s see how we can modify this array to obtain K as the sum.
The current sum of the array is \frac{N}{2} + 2\cdot\frac{N}{2} = \frac{3N}{2}.
That means we still need to add in K - \frac{3N}{2} more.
Let Y = K - \frac{3N}{2}.
To maintain the parity condition, we can only increase each element by an even number.
In particular, this means that if Y is odd, we can’t make a sum of K since we need to add an odd number to the sum which is impossible while also maintaining the parity condition; so the answer would be -1.
This leaves us with the case when Y is even. Note also the constraint 1 \leq A_i \leq 10^5 that we need to satisfy.
- Iterate i from 1 to N.
- At index i, figure out how much to add to A_i: this is the minimum of Y and 99998 (since we start with either 1 or 2, and can’t exceed 10^5 anywhere).
Add this value to A_i and subtract it from Y.
In the end, if Y = 0 we’re done, and the resulting array can be printed; otherwise no answer exists and we print -1.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
vector<int> a(n, 1);
for (int i = 0; i < n; ++i) {
if (i >= n/2) ++a[i];
k -= a[i];
}
if (k < 0 or k%2 == 1) cout << -1 << '\n';
else {
for (int i = 0; i < n; ++i) {
int take = min(k, 99998);
k -= take;
a[i] += take;
}
if (k > 0) cout << -1 << '\n';
else {
for (int i = 0; i < n; ++i) cout << a[i] << ' ';
cout << '\n';
}
}
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
if 3*n//2 > k: print(-1)
elif k%2 != (3*n//2)%2: print(-1)
else:
a = [1, 2] * (n//2)
rem = k - 3*n//2
for i in range(n):
have = (100000 - a[i]) // 2
take = min(have, rem // 2)
rem -= 2*take
a[i] += 2*take
if rem > 0: print(-1)
else: print(*a)
