PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Sahil Tiwari
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
2598
PREREQUISITES:
Observation
PROBLEM:
Given integers N and K, construct a circular array of size N such that every subarray of size K contains distinct elements, while minimizing the maximum element.
EXPLANATION:
Obviously, we need at least K colors.
A natural-seeming starting point is to then attempt to repeat these K colors, to form [1, 2, 3, \ldots, K, 1, 2, \ldots, K, 1, 2, \ldots].
This will allow you to form \left\lfloor \frac{N}{K}\right\rfloor ‘blocks’ of [1, 2, \ldots, K], and will leave the last few elements uncolored — specifically, the last N\%K elements will be uncolored.
Using N\%K more colors gives us a valid array, of course, and we’ve used K + N\%K colors. Can we do any better?
Turns out, we can!
The idea is not too hard: as before, let’s place \left\lfloor \frac{N}{K}\right\rfloor blocks of [1, 2, \ldots, K].
This leaves us with N\%K uncolored elements. Instead of placing them all at the end of the array, let’s instead distribute them equally (as much as possible) to the ends of all the blocks.
For example, if there are 21 blocks and 118 uncolored elements, give 6 elements each to the first 13 blocks and 5 elements each to the remaining ones.
In particular, each block will receive either \left\lceil \frac{N\%K}{B}\right\rceil or \left\lfloor \frac{N\%K}{B}\right\rfloor uncolored elements, where B is the number of blocks.
Now notice that the resulting array can be colored quite easily using \left\lceil \frac{N\%K}{B}\right\rceil extra colors, giving us a solution using K + \left\lceil \frac{N\%K}{B}\right\rceil colors.
Constructing this coloring is fairly straightforward: as noted above, each block of uncolored elements has either size y or y-1, where y = \left\lceil \frac{N\%K}{B}\right\rceil. So,
- Color a block of size y with colors K+1, K+2, \ldots, K+y
- Color a block of size y-1 with colors K+1, K+2, \ldots, K+y-1
That is, the final coloring will look like [1, 2, 3, \ldots, K, K+1, \ldots, K+y, 1, 2, \ldots, K+y, 1, \ldots, K+y, \ldots, 1, 2, \ldots, K+y-1, 1, 2, \ldots, K+y-1]
It turns out that this is also optimal.
Proof
Suppose we are able to use C colors to color the array.
Let M be the maximum frequency of one of the colors; w.l.o.g say color 1.
Then, obviously, it must hold that M\cdot C \geq N.
Further, there are at least K-1 other elements between any two occurrences of 1.
This gives us a minimum of M\cdot(K-1) + M = M\cdot K elements in the array, i.e, M\cdot K \leq N.
This tells us that M \leq \left\lfloor \frac{N}{K}\right\rfloor.
Now, recall that we have M\cdot C \geq N. We’d like to minimize C, so of course M should be as large as possible.
In other words, we choose M = \left\lfloor \frac{N}{K}\right\rfloor.
This tells us that
must hold.
The smallest C that satisfies this equation is indeed K + \left\lceil \frac{N\%K}{\left\lfloor \frac{N}{K}\right\rfloor}\right\rceil: this can be verified algebraically.
Of course, to solve the problem you don’t need to solve this algebraically: you can, for example, run a loop on C or binary search to find the first time C\cdot \left\lfloor \frac{N}{K}\right\rfloor \geq N.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
// Code by Sahil Tiwari (still_me)
#include <bits/stdc++.h>
#define still_me main
#define print(a) for(auto TEMPORARY: a) cout<<TEMPORARY<<" ";
#define tt int TESTCASE;cin>>TESTCASE;while(TESTCASE--)
using namespace std;
const int mod = 1e9+7;
const int inf = 1e18;
void solve() {
int n , k;
cin>>n>>k;
int m = n/k;
int ans = (n+m-1) / m;
cout<<ans<<endl;
vector<vector<int>> a(m);
int c = 1;
while(n) {
for(int i=0;i<m && n;i++) {
a[i].push_back(c);
n--;
}
c++;
}
for(auto i: a){
print(i);
}
}
signed still_me()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
tt{
solve();
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#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() && 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, 1e4);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 5e5);
in.readSpace();
int k = in.readInt(1, n);
in.readEoln();
sn += n;
int x = k;
while (n / k * x < n) {
x++;
}
cout << x << endl;
int t = n - n / k * k;
int c = 0;
for (int i = 0; i < n; i++) {
cout << c + 1 << " \n"[i == n - 1];
if (c >= k) {
t--;
}
c++;
if (c == x || (c >= k && t == 0)) {
c = 0;
}
}
}
assert(sn <= 5e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
cols = k + (n%k + n//k - 1)//(n // k)
print(cols)
ans = [[i for i in range(1, k+1)] for _ in range(n//k)]
n -= k * (n // k)
for col in range(k+1, cols+1):
for list in ans:
if n > 0:
list.append(col)
n -= 1
for list in ans:
print(*list, end = ' ')
print()
