EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2023
ICPC 2023

G. Turning Red

47th Annual hosted by ICPC World Championship AASTMT Problem G Turning Red Time limit: 3 seconds...

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 G
                                            Turning Red
                                      Time limit: 3 seconds
Mei’s parents have spent the last year remodeling their house, but their lighting system is quite complex!
Each room in the house has an LED light, which can be set to red, green, or blue, as seen in Figure G.1.
Figure G.1: The initial state of the lights in Sample Input 1. Buttons and wires not shown.

Throughout the house are various buttons which are each connected to one or more lights. When a button is pressed, any red lights connected to that button become green, any green lights connected to that button become blue, and any blue lights connected to that button become red. Each button can be pressed multiple times. Because the house was built prior to the invention of crossbar wiring, each light is controlled by at most two buttons. Mei’s favorite color is red, so she wants to turn all of the lights red. Her parents, fearing the buttons will wear out, have asked her to minimize the total number of button presses.

Input

The first line of input contains two positive integers l and b, where l (1 ≤ l ≤ 2 · 105 ) is the number of lights and b (0 ≤ b ≤ 2 · l) is the number of buttons. The second line of input is a string of l characters, all either R, G, or B, where the ith character is the initial color of the ith light. The next b lines describe the buttons. Each of these lines begins with an integer k (1 ≤ k ≤ l), the number of lights controlled by this button. Then k distinct integers follow, the lights controlled by this button. The lights are indexed from 1 to l, inclusive. Each light appears at most twice across all buttons.

Output

Output the minimum number of button presses Mei needs to turn all the lights red. If it is impossible for Mei to turn all of the lights red, output impossible.

Sample Tests

Sample 1
Sample Input 
 8 6
 GBRBRRRG
 2 1 4
 1 2
 4 4 5 6 7
 3 5 6 7
 1 8
 1 8


                                 World Finals | ICPC 202
   47th Annual
    ICPC World
  Championship
Sample Output 
8









3 Luxor
hosted by

AASTMT
Sample 2
Sample Input 
4 3
RGBR
2 1 2
2 2 3
2 3 4
Sample Output 
impossible
Sample 3
Sample Input 
4 4
GBRG
2 1 2
2 2 3
2 3 4
1 4
Sample Output 
6
Sample 4
Sample Input 
3 3
RGB
1 1
1 2
1 3
Sample Output 
3
Editorial

Editorial

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

Raw TeX

Key Observations

  • Let $x_i \in \{0,1,2\}$ be the number of times button $i$ is pressed, modulo $3$.

  • For a light controlled by buttons $u$ and $v$, the requirement that it becomes red is one linear equation \[ x_u+x_v \equiv \text{need} \pmod 3. \] If a light is controlled by only one button $u$, we simply get $x_u \equiv \text{need} \pmod 3$.

  • Therefore each connected component of the graph on buttons, where two buttons are adjacent if they control the same 2-button light, can be solved independently.

  • Inside one component, once the value of one button is fixed, every other button value is forced by BFS propagation through the equations.

  • There are only three possible values for the root button, so we can try all three and keep the valid one with minimum total presses.

Algorithm

  1. Convert every initial light color into the residue need required to reach red modulo $3$.

  2. Build the incidence structure between buttons and lights.

  3. Traverse the connected components of the button graph.

  4. For each component, try root values $0,1,2$:

    • propagate all forced values with BFS;

    • reject the choice if some equation becomes inconsistent;

    • otherwise compute the sum of button values in that component.

    • If no root value works for some component, output impossible. Otherwise sum the best component costs. enumerate

      Correctness Proof

      We prove that the algorithm returns the correct answer.

      Lemma 1.

      Within one connected component of the button graph, fixing the value of one button determines every other button value uniquely.

      Proof.

      Whenever a light is controlled by buttons $u$ and $v$, the equation \[ x_u+x_v \equiv \text{need} \pmod 3 \] implies \[ x_v \equiv \text{need}-x_u \pmod 3. \] So knowing one endpoint forces the other. Repeating this along paths determines every button in the component uniquely. □

      Lemma 2.

      For a fixed root value in one component, the BFS propagation finds a valid assignment if and only if such an assignment exists with that root value.

      Proof.

      By Lemma 1, every button value is uniquely forced once the root value is fixed. The BFS computes exactly those forced values. If a contradiction appears, then some light imposes two different values on the same button, so no valid assignment with this root value exists. If no contradiction appears, all encountered equations are satisfied, so the computed assignment is valid. □

      Theorem.

      The algorithm outputs the minimum total number of button presses, or impossible if no solution exists.

      Proof.

      Different connected components share no variables, so the total cost is the sum of independent component costs. For one component, every feasible solution corresponds to exactly one of the three root values modulo $3$. By Lemma 2, for each root value the algorithm either proves infeasibility or constructs the unique valid assignment. Taking the minimum valid cost in each component is therefore optimal, and if some component has no valid root value then no global solution exists. □

      Complexity Analysis

      Each light-button incidence is processed only a constant number of times across all traversals. Therefore the running time is linear in the input size, namely $O(l+b+\text{total incidences})$, and the memory usage is the same order.

      Implementation Notes

      • A light controlled by zero buttons is immediately fatal unless it is already red.

      • The optimal number of presses for one button is always one of $0,1,2$, because three extra presses have no effect.

Implementation

Code

C++ solution used for this page.

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 {

int color_value(char c) {
    if (c == 'R') {
        return 0;
    }
    if (c == 'G') {
        return 1;
    }
    return 2;
}

int mod3(int x) {
    x %= 3;
    if (x < 0) {
        x += 3;
    }
    return x;
}

void solve() {
    int l, b;
    cin >> l >> b;

    string colors;
    cin >> colors;

    vector<vector<int>> lights_of_button(b);
    vector<vector<int>> buttons_of_light(l);
    for (int i = 0; i < b; ++i) {
        int k;
        cin >> k;
        lights_of_button[i].resize(k);
        for (int j = 0; j < k; ++j) {
            int light;
            cin >> light;
            --light;
            lights_of_button[i][j] = light;
            buttons_of_light[light].push_back(i);
        }
    }

    vector<int> need(l);
    for (int i = 0; i < l; ++i) {
        need[i] = mod3(-color_value(colors[i]));
        if (buttons_of_light[i].empty() && need[i] != 0) {
            cout << "impossible\n";
            return;
        }
    }

    vector<char> seen(b, false);
    long long answer = 0;
    vector<int> value(b, -1);
    vector<int> component;
    queue<int> q;

    for (int start = 0; start < b; ++start) {
        if (seen[start]) {
            continue;
        }

        component.clear();
        seen[start] = true;
        q.push(start);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            component.push_back(u);
            for (int light : lights_of_button[u]) {
                if (buttons_of_light[light].size() != 2) {
                    continue;
                }
                int v = buttons_of_light[light][0] ^ buttons_of_light[light][1] ^ u;
                if (!seen[v]) {
                    seen[v] = true;
                    q.push(v);
                }
            }
        }

        long long best_cost = -1;
        vector<int> best_assignment;
        for (int root_value = 0; root_value < 3; ++root_value) {
            for (int node : component) {
                value[node] = -1;
            }
            queue<int> bfs;
            value[start] = root_value;
            bfs.push(start);

            bool ok = true;
            while (!bfs.empty() && ok) {
                int u = bfs.front();
                bfs.pop();
                for (int light : lights_of_button[u]) {
                    int target = need[light];
                    const auto& owners = buttons_of_light[light];
                    if (owners.size() == 1) {
                        if (value[u] != target) {
                            ok = false;
                            break;
                        }
                        continue;
                    }

                    int v = owners[0] ^ owners[1] ^ u;
                    int required = mod3(target - value[u]);
                    if (value[v] == -1) {
                        value[v] = required;
                        bfs.push(v);
                    } else if (value[v] != required) {
                        ok = false;
                        break;
                    }
                }
            }

            if (!ok) {
                continue;
            }

            long long cost = 0;
            for (int node : component) {
                cost += value[node];
            }
            if (best_cost == -1 || cost < best_cost) {
                best_cost = cost;
                best_assignment.clear();
                best_assignment.reserve(component.size());
                for (int node : component) {
                    best_assignment.push_back(value[node]);
                }
            }
        }

        if (best_cost == -1) {
            cout << "impossible\n";
            return;
        }
        answer += best_cost;
        for (int i = 0; i < static_cast<int>(component.size()); ++i) {
            value[component[i]] = best_assignment[i];
        }
    }

    cout << answer << '\n';
}

}  // namespace

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

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2023/G-turning-red/solution.texC++ implementationcompetitive_programming/icpc/2023/G-turning-red/solution.cppStatement textcompetitive_programming/icpc/2023/G-turning-red/statement.txtStatement PDFcompetitive_programming/icpc/2023/G-turning-red/statement.pdfMetadatacompetitive_programming/icpc/2023/G-turning-red/meta.jsonYear packetcompetitive_programming/icpc/2023/contest_problems.pdf