B. Schedule

47th Annual hosted by ICPC World Championship AASTMT Problem B Schedule Time limit: 2 seconds The Instit...

Updated May 21, 2026

Track ICPC

Year 2023

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

  47th Annual                                                                             hosted by
  ICPC World
Championship                                                                              AASTMT

                                          Problem B
                                            Schedule
                                    Time limit: 2 seconds
The Institute for Creative Product Combinations (ICPC) tries to find unusual and innovative ways to
unite seemingly unrelated products or technologies, opening up new markets and creating new jobs. (For
instance, their most recent success was the “hairbachi,” a hair-dryer with a hibachi grill top attachment
for preparing on-the-go hot meals.) The company employs n teams of size 2 to research individual
products, then members of the different teams get together to explore ways of combining products.
During the pandemic, the ICPC management organized everyone’s schedule in such a way that there
were never more than n people in the office at the same time, and things ran so smoothly that they
continued the process once things began to return to normal. Here is the scheme they used. Label the
teams with integers 1 through n and the two people on the ith team as (i, 1) and (i, 2) for each i from 1
to n. Each week, exactly one person from each team is allowed in the office, while the other has to stay
away. The employees (i, 1) and (i, 2) know each other well and collaborate productively regardless of
being isolated from each other, so members of the same team do not need to meet in person in the office.
However, isolation between members from different teams is still a concern.
Each pair of teams i and j for i 6= j has to collaborate occasionally. For a given number w of weeks and
for fixed team members (i, a) and (j, b), let w1 < w2 < . . . < wk be the weeks in which these two team
members meet in the office. The isolation of those two people is the maximum of

{w1 , w2 − w1 , w3 − w2 , . . . , wk − wk−1 , w + 1 − wk },

or infinity if those two people never meet. The isolation of the whole company is the maximum isolation across all choices of i, j, a, and b. You have been tasked to find a weekly schedule that minimizes the isolation of the whole company over a given number w of weeks.

Input

The input consists of a single line containing two integers n (2 ≤ n ≤ 104 ) and w (1 ≤ w ≤ 52), where n is the number of teams and w is the number of weeks that need to be scheduled.

Output

Output a line containing either an integer representing the minimum isolation achievable for n teams or the word infinity if no schedule guarantees that every pair of individuals on different teams can meet. If the isolation is finite, it is followed by w lines representing a schedule that achieves this isolation. The j th line of the schedule is a string of length n containing only the symbols 1 and 2, where the ith symbol indicates which of the two members from team i comes into the office on week j.

                               World Finals | ICPC 2023 Luxor
 47th Annual                                                       hosted by
  ICPC World
Championship                                                       AASTMT

Sample Tests

Sample 1

Sample Input

2 6

Sample Output

Sample 2

Sample Input

2 1

Sample Output

infinity

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

If a schedule has isolation $k$, then during every block of $k$ consecutive weeks each pair of people from different teams meets at least once.
So it is enough to build a schedule of length $k$ where every such pair meets at least once. By repeating those $k$ weeks forever, we get the same isolation for any larger horizon.
A team's schedule over $k$ weeks is a binary string of length $k$: bit $0$ means member $1$ comes in, bit $1$ means member $2$ comes in.
Two teams are compatible exactly when the four bit pairs $00,01,10,11$ all occur somewhere. Then every cross-team pair of employees meets at least once.
If we take strings of length $k$ that start with $0$ and contain exactly $\lceil k/2\rceil$ ones, then any two distinct such strings are compatible. There are \[ \binom{k-1}{\lceil k/2\rceil} \] such strings, and this is also the maximum possible number of pairwise compatible team strings.

Algorithm

For $k=1,2,\dots,w$, find the first $k$ such that $\binom{k-1}{\lceil k/2\rceil} \ge n$.
If no such $k$ exists, output infinity.
Otherwise enumerate any $n$ distinct binary strings of length $k$ that start with $0$ and have exactly $\lceil k/2\rceil$ ones.
Assign one string to each team.
Output the first $w$ weeks by repeating these strings periodically with period $k$.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

If a schedule has isolation $k$, then the first $k$ weeks already contain at least one meeting for every pair of people from different teams.

Proof.

If some pair did not meet in the first $k$ weeks, then the initial gap before their first meeting would be at least $k+1$, contradicting isolation $k$. □

Lemma 2.

Any two distinct binary strings of length $k$ that start with $0$ and contain exactly $\lceil k/2\rceil$ ones are compatible.

Proof.

Both strings start with $0$, so $00$ occurs in the first position. Since the strings are distinct but have the same number of ones, there must be one position where they differ as $01$ and another where they differ as $10$.

Among the last $k-1$ positions, each string has $\lceil k/2\rceil$ ones. Because $2\lceil k/2\rceil > k-1$, the two sets of one-positions must intersect, so $11$ also occurs. Therefore all four bit pairs occur, and the two teams are compatible. □

Lemma 3.

No schedule block of length $k$ can contain more than $\binom{k-1}{\lceil k/2\rceil}$ pairwise compatible team strings.

Proof.

By flipping all bits of a team string if necessary, we may assume every string starts with $0$ without changing compatibility.

Now remove the first bit. If one suffix were contained in another, then one of the pairs $01$ or $10$ would never occur, so the family of suffixes is an antichain in the Boolean lattice on $k-1$ elements. Sperner's theorem gives the extremal size, and the standard complement-pair refinement in the odd case reduces the bound exactly to $\binom{k-1}{\lceil k/2\rceil}$. □

Theorem.

The algorithm outputs an optimal schedule whenever the answer is finite, and outputs infinity otherwise.

Proof.

Let $k$ be the first value found by the algorithm. By Lemma 2, the constructed $k$-week pattern makes every pair of teams compatible, so every pair of employees from different teams meets at least once in that block. Repeating the block makes each such pair meet at least once in every consecutive block of $k$ weeks, so the isolation is at most $k$.

Conversely, if some schedule achieved smaller isolation, then by Lemma 1 its first block of that smaller length would already contain $n$ pairwise compatible team strings, contradicting Lemma 3 and the minimality of $k$. If no $k \le w$ satisfies the binomial bound, then no finite-isolation schedule exists. □

Complexity Analysis

Trying all $k \le w$ is $O(w)$. Generating the first $n$ valid patterns takes $O(nk)$ time, and printing the repeated schedule takes $O(nw)$ time. The memory usage is $O(nk)$.

Implementation Notes

Binomial coefficients are computed with 64-bit arithmetic and capped at $n$, because larger values are irrelevant.
Enumeration is done by backtracking with the first bit fixed to $0$.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

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

namespace {

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long capped_choose(int n, int k, long long cap) {
    if (k < 0 || k > n) {
        return 0;
    }
    k = min(k, n - k);
    long long result = 1;
    for (int i = 1; i <= k; ++i) {
        long long num = n - k + i;
        long long g = gcd_ll(num, static_cast<long long>(i));
        num /= g;
        long long den = i / g;
        result /= gcd_ll(result, den);
        if (result > cap / num) {
            return cap;
        }
        result *= num;
    }
    return min(result, cap);
}

void generate_patterns(int k, int need_ones, int n, int pos, string& current,
                       vector<string>& patterns) {
    if (static_cast<int>(patterns.size()) == n) {
        return;
    }
    if (pos == k) {
        if (need_ones == 0) {
            patterns.push_back(current);
        }
        return;
    }

    int remaining = k - pos;
    if (need_ones > remaining) {
        return;
    }

    if (need_ones < remaining) {
        current[pos] = '0';
        generate_patterns(k, need_ones, n, pos + 1, current, patterns);
    }
    if (need_ones > 0) {
        current[pos] = '1';
        generate_patterns(k, need_ones - 1, n, pos + 1, current, patterns);
    }
}

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

    int best = -1;
    for (int k = 1; k <= w; ++k) {
        int ones = (k + 1) / 2;
        if (capped_choose(k - 1, ones, n) >= n) {
            best = k;
            break;
        }
    }

    if (best == -1) {
        cout << "infinity\n";
        return;
    }

    int ones = (best + 1) / 2;
    vector<string> patterns;
    string current(best, '0');
    generate_patterns(best, ones, n, 1, current, patterns);

    cout << best << '\n';
    for (int week = 0; week < w; ++week) {
        string schedule;
        schedule.reserve(n);
        for (int team = 0; team < n; ++team) {
            schedule.push_back(patterns[team][week % best] == '0' ? '1' : '2');
        }
        cout << schedule << '\n';
    }
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2023/B-schedule/solution.texC++ implementationcompetitive_programming/icpc/2023/B-schedule/solution.cppStatement textcompetitive_programming/icpc/2023/B-schedule/statement.txtStatement PDFcompetitive_programming/icpc/2023/B-schedule/statement.pdfMetadatacompetitive_programming/icpc/2023/B-schedule/meta.jsonYear packetcompetitive_programming/icpc/2023/contest_problems.pdf

B. Schedule

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets