COLORS - Editorial

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

C \geq \left\lceil \frac{N}{\left\lfloor \frac{N}{K}\right\rfloor}\right\rceil

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()
1 Like

This was a really very nice problem.
I somehow managed to get that observation in the contest and solved it, but it was quite hard.

3 Likes

for the input :
1
23 4
my code gives output as:
5
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3
which is wrong. but my code got accepted.

Simple Explanation

#include <bits/stdc++.h>
using namespace std;

#define int     long long int

void solve(){
    int n,k;
    cin>>n>>k;

    int noOfSubset = n/k;
    int leftOutElement = n%k;

    k += ceil(leftOutElement/(noOfSubset*1.0));

    vector<int> v(k), ans(n);
    for (int i = 0; i < k; ++i){ v[i] = i + 1; }
        
    cout<<k<<endl;
    for (int i = 0; i < n; ++i){
        ans[i] = v[i%k];
    }

    for(auto i : ans)
        cout<<i<<" ";
    cout<<endl;        
}

signed main() {
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

There is only problem when there are remain element left out in our array to be output. first if remainder of n%k == 0 then we can simply print our answer.
But when the remainder remain then , calculate the number of subset and try to assign the remaining element to the no of subset . add this value to our k value. just print the answer.
Please to like this post.

I was trying a binary search approach on number of colors. In order to validate whether x number of colors are possible or not, I tired a greedy coloring solution. This didn’t pass the testcases at all! I spent huge time on this question. :cry: