CCC '24 S4 - Painting Roads - DMOJ: Modern Online Judge

CCC '24 S4 - Painting Roads

Points: 12 (partial)

Time limit: 3.0s

Memory limit: 1G

Author:

zhouzixiang2004

Problem type

Canadian Computing Competition: 2024 Stage 1, Senior #4

Alanna, the mayor of Kitchener, has successfully improved the city's road plan. However, a travelling salesperson from the city of RedBlue complained that the roads are not colourful enough. Alanna's second job is to paint some of the roads.

Kitchener's road plan can be represented as a collection of $N$ $N$ intersections with $M$ $M$ roads, where the $i^{\text{th}}$ $i^{th}$ road connects intersections $u_i$ $u_{i}$ and $v_i$ $v_{i}$ . All roads are initially grey. Alanna would like to paint some of the roads in red or blue such that the following condition is satisfied:

Whenever there is a grey road that connects $u_i$ $u_{i}$ and $v_i$ $v_{i}$ , there is also a path of roads from $u_i$ $u_{i}$ to $v_i$ $v_{i}$ such that the roads on the path alternate between red and blue, without any of the roads on this path being grey.

To lower the city's annual spending, Alanna would like to minimize the number of painted roads. Can you help Alanna design a plan that meets all the requirements?

Input Specification

The first line contains two integers $N$ $N$ and $M$ $M$ $(1 \le N, M \le 2 \cdot 10^5)$ $(1 \leq N, M \leq 2 \cdot 10^{5})$ .

The $i^{\text{th}}$ $i^{th}$ of the next $M$ $M$ lines contains two integers $u_i$ $u_{i}$ and $v_i$ $v_{i}$ , meaning that there exists a road from intersection $u_i$ $u_{i}$ to intersection $v_i$ $v_{i}$ $(1 \le u_i, v_i \le N, u_i \neq v_i)$ $(1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i})$ .

There is at most one road between any unordered pair of intersections.

The following table shows how the available 15 marks are distributed:

Marks	Additional Constraints
2	There is a road connecting intersection $i$ $i$ with intersection $i + 1$ $i + 1$ for all $1 \le i < N$ $1 \leq i < N$ (and possibly other roads).
3	We can reach any intersection from any other intersection, and $N = M$ $N = M$ .
3	No road belongs to two or more simple cycles (see Definition below).
7	None

Definition: if we denote a road between intersections $u$ $u$ and $v$ $v$ as $u \leftrightarrow v$ $u \leftrightarrow v$ , then a simple cycle is a sequence $w_1 \leftrightarrow w_2 \leftrightarrow \dots \leftrightarrow w_k \leftrightarrow w_1$ $w_{1} \leftrightarrow w_{2} \leftrightarrow \dots \leftrightarrow w_{k} \leftrightarrow w_{1}$ where $k \ge 3$ $k \geq 3$ and all $w_i$ $w_{i}$ are distinct.

Output Specification

Output a string of $M$ $M$ characters, representing the paint plan. The $i^{\text{th}}$ $i^{th}$ character should be R if the $i^{\text{th}}$ $i^{th}$ road is to be painted red, B if $i^{\text{th}}$ $i^{th}$ road is to be painted blue, or G (for "grey") if the $i^{\text{th}}$ $i^{th}$ road is to be left unpainted.

Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.

Sample Input 1

Copy

Output for Sample Input 1

Copy

RGGRGRB

Explanation of Output for Sample Input 1

A diagram of the intersections along with a valid paint plan that minimizes the number of painted roads is shown below. Note that the colours are shown on each road as R (red), B (blue), or G (grey).

$\text{[math]}$

All the unpainted roads satisfy the condition:

The $2^{\text{nd}}$ $2^{nd}$ road, labelled $\text{G}_2$ $G_{2}$ , connects intersection $2$ $2$ with intersection $4$ $4$ . The path through intersections $2, 1, 4$ $2, 1, 4$ alternates red, blue.
The $3^{\text{rd}}$ $3^{rd}$ road, labelled $\text{G}_3$ $G_{3}$ , connects intersection $5$ $5$ with intersection $2$ $2$ . The path through intersections $5, 4, 1, 2$ $5, 4, 1, 2$ alternates red, blue, red.
The $5^{\text{th}}$ $5^{th}$ road, labelled $\text{G}_5$ $G_{5}$ , connects intersection $4$ $4$ with intersection $3$ $3$ . The path through intersections $4, 1, 3$ $4, 1, 3$ alternates blue, red.

Sample Input 2

Copy

4 2
1 2
3 4

Output for Sample Input 2

Copy

BB

Explanation of Output for Sample Input 2

Note that it is possible for Kitchener to be disconnected.

Comments

0

LordFurno commented 36 days ago

I think the CCC grader is bugged. I get full points when submitting here, but on the CCC grader, I get wrong answer.

0
gangwucanada commented 55 days ago ← edit 3 →
What if the graph like this:

Copy
1 / | \ 2 3 4 4 3 1 2 1 3 1 4

How can we color the edges to make alternative colors on all paths?

I think it is impossible to satisfy the following paths:

2->3

2->4

3->4

1

Superhero commented 54 days ago

Pretty sure you only need a path from A to B alternating between red and blue only when there's a grey edge from A to B... the graph will still be valid if you color all the edges red/blue

If you make even one of the edges grey, then you wouldn't be able to satisfy the requirements (since there's only one path between any two nodes in this graph)