Editorial for Yet Another Contest 4 P3 - Canadian Cactus Competition

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Note that there may be multiple valid schemes of assigning values, with one such scheme being mentioned below.

Subtask 1

In this subtask, the beauty of the graph can only be $0$ ~0~ or $1$ ~1~. For the beauty of the graph to be $1$ ~1~, every edge must connect a node with a value of $0$ ~0~ and a node with a value of $1$ ~1~. This corresponds to a $2$ ~2~-colouring of the graph. Hence, all we need to do is to check if the graph is bipartite.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Subtask 2

Let $B = 2^k-1$ ~B = 2^k-1~. Since we are only dealing with $k$ ~k~ bits, the maximum possible beauty of the graph is $2^k-1$ ~2^k-1~. For the graph to have a beauty of $2^k-1$ ~2^k-1~, every edge must have a colour of $2^k-1$ ~2^k-1~. If we consider the $(k-1)$ ~(k-1)~-th bit (the most significant bit), then every edge must connect a node with a value that contains this bit and node with a value that doesn't contain this bit. Hence, the graph must be bipartite. Therefore, if the graph is bipartite, we can generate a $2$ ~2~-colouring, set all nodes of one colour to have a value of $0$ ~0~, and set all nodes of the other colour to have a value of $2^k-1$ ~2^k-1~.

Otherwise, the beauty of the graph cannot have the $(k-1)$ ~(k-1)~-th bit set, so the maximum possible beauty of the graph is $2^{k-1}-1$ ~2^{k-1}-1~. It turns out that this beauty is always achievable, with the following construction:

First, consider any spanning tree of the graph, and find its $2$ ~2~-colouring. For all nodes of one colour, we will set their values to $2^{k-1}$ ~2^{k-1}~, and for all nodes of the other colour, we will set their values to $0$ ~0~. As long as we do not modify the $(k-1)$ ~(k-1)~-th bit any further, then the colours of all edges in the spanning tree will have the $(k-1)$ ~(k-1)~-th bit set, and hence be greater than $2^{k-1}-1$ ~2^{k-1}-1~.

Then, consider the edges not part of the spanning tree. Due to the properties of a cactus graph, these edges must form an acyclic subgraph (can you work out the details why?). We can generate a $2$ ~2~-colouring of this subgraph. For all nodes of one colour, we will increase their value by $2^{k-1}-1$ ~2^{k-1}-1~. Then, all edges in this subgraph must have the $i$ ~i~-th bit set for $0 \le i < k-1$ ~0 \le i < k-1~, which is sufficient to guarantee that their value is not less than $2^{k-1}-1$ ~2^{k-1}-1~.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Subtask 3

Let $k$ ~k~ be the largest integer such that $2^k \le B$ ~2^k \le B~. Then, since we are only dealing with $(k+1)$ ~(k+1)~ bits, the maximum possible beauty of the graph is $2^{k+1}-1$ ~2^{k+1}-1~. For the same reason as in subtask $2$ ~2~, this is possible if and only if the graph is bipartite. If the graph is bipartite, we can construct a solution by generating a $2$ ~2~-colouring of the graph, setting all nodes of one colour to have a value of $2^k$ ~2^k~, and setting all nodes of the other colour to have a value of $2^k-1$ ~2^k-1~.

Otherwise, the beauty of the graph cannot have the $k$ ~k~-th bit set, so the maximum possible beauty of the graph is $2^k-1$ ~2^k-1~. It turns out that this beauty is always achievable. To do this, generate a $3$ ~3~-colouring of the graph (this is guaranteed to exist). Then, set all nodes of the first colour to have a value of $0$ ~0~, all nodes of the second colour to have a value of $2^k$ ~2^k~, and all nodes of the third colour to have a value of $2^k-1$ ~2^k-1~.

To generate a $3$ ~3~-colouring of the graph, it suffices to perform a DFS or BFS over the graph. When we visit a node for the first time, we will set its colour to be any colour such that no adjacent node has already been visited and assigned that colour. The details of the proof of why this works is left as an exercise to the reader (hint: use the block graph to show that when a node is visited, at most two of its neighbours have already been visited).

To simplify implementation, we note that if we always choose the largest available colour when processing a node for the first time, then if the graph is bipartite, we will automatically find a $2$ ~2~-colouring. Thus, we can handle both cases at the same time without needing to check whether the graph is bipartite.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.