PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mehul_g2874
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N and K, construct a permutation of \{1, 2, \ldots, N\} such that exactly K adjacent pairs of elements have an odd sum.
EXPLANATION:
For P_i + P_{i+1} to be odd, the only thing that really matters is the parity of P_i and P_{i+1}, not their actual values.
In particular, this sum is odd if and only if one of the two numbers is even and the other is odd.
So, our task is really to construct a binary string S of length N such that:
- S contains exactly \left\lfloor\frac{N}{2} \right\rfloor zeros (the positions of the even elements in [1, N].
- Every other position contains 1 (the positions of the odd elements).
- There are exactly K adjacent pairs of characters that are not equal (and hence will have odd sum).
If we can find such a binary string, all that needs to be done is to place the even elements at 0's and odd elements at 1's, in some order.
There are likely several constructions now, here’s one.
Consider the binary string 1010\ldots 10 that consists of 10 repeated several times.
If it’s repeated y times, it’ll have 2y-1 adjacent pairs of unequal elements.
So, we can do the following:
- Find the largest y such that 2y-1 \leq K, and create y repeated occurrences of 10.
Now, we either have 2y-1 = K or 2y-1 = K-1 (since each extra copy of 10 adds two to the count). - If 2y-1 = K, we don’t want to have any more adjacent equal elements.
So, place any remaining ones just before the last character, and any remaining zeros at the end of the string.
Essentially, we go from 1010\ldots 10 to 1010\ldots 10111\ldots 11000\ldots 00, i.e, the last 1 and 0 both get ‘extended’. - If 2y-1 = K-1, we want one more index.
For this, simply place a 1 at the end of the string, then once again distribute the remaining zeros and ones as above.
We go from 1010\ldots 10 to 1010\ldots 101000\ldots 00111\ldots 11.
Now, just replace zeros with distinct even numbers and ones with distinct odd numbers to obtain the answer.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k; cin >> n >> k;
vector <int> odd, even;
for (int i = 1; i <= n; i++){
if (i & 1) odd.push_back(i);
else even.push_back(i);
}
cout << odd.back() << " ";
odd.pop_back();
int done = 0;
int mv = 1;
while (done < k - 1){
done++;
mv ^= 1;
if (mv == 1){
cout << odd.back() << " ";
odd.pop_back();
} else {
cout << even.back() << " ";
even.pop_back();
}
}
if (!mv) swap(odd, even);
for (auto x : odd) cout << x << " ";
for (auto x : even) cout << x << " ";
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
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() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
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;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
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);
}
};
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
int T = input.readInt(1, 1000); input.readEoln();
int NN = 0;
while(T-- > 0) {
int N = input.readInt(1, (int)1e5); input.readSpace();
int K = input.readInt(1, (int)N - 1); input.readEoln();
for(int i = 1 ; i <= K ; ++i) cout << i << " ";
for(int i = K + 2 ; i <= N ; i += 2) cout << i << " ";
for(int i = K + 1 ; i <= N ; i += 2) cout << i << " ";
cout << '\n';
}
input.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = [1, 0] * (k//2)
have = 2*(k//2) - 1
if have == k-1:
a += [0]*(n//2 - k//2)
a += [1]*((n+1)//2 - k//2)
else:
a += [1]*((n+1)//2 - k//2)
a += [0]*(n//2 - k//2)
odd, even = 1, 2
for i in range(n):
if a[i] == 1:
a[i] = odd
odd += 2
else:
a[i] = even
even += 2
print(*a)