PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Tejas Pandey
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh
DIFFICULTY:
To be calculated
PREREQUISITES:
Trees, greedy algorithms
PROBLEM:
Chef has B black nodes and W white nodes. Help him construct a tree using these nodes such that it has at least one diameter that alternates between colors, and the diameter is minimized.
EXPLANATION:
Hint
Excluding a few corner cases, it’s always possible to achieve diameter 3.
Full solution
This is a problem which one can gain insight into by working a few small cases out on paper. You will quickly notice that, except a handful of cases where the answer is -1, it’s always possible to create a tree of diameter 3 that has an alternating diameter.
It turns out that this is indeed the full solution. The cases can be split as follows:
- If B + W = 1, the tree consists of only one node. There’s only one such tree, and it has an alternating diameter so in this case, simply print this tree
- If B + W > 1 but either B = 0 or W = 0, the answer is -1. This is because any tree with at least 2 nodes has a diameter of at least 2, and since every node will have the same color, it’s impossible to find a tree with alternating colors on its diameter.
- If B = W = 1, there’s again only one type of tree possible, and it’s easy to see that it indeed works.
- Finally, we have the case when B + W \gt 1, both B \gt 0 and W \gt 0, and either B \gt 1 or W \gt 1. Many constructions work in this case, here’s an example:
- Without loss of generality, let W > 1 (if not, swap what we do with B and W). Assign the color B to nodes 1, 2, \ldots, B and the color W to nodes B+1, B+2, \ldots, B+W. Now, for each 2 \leq i \leq B+W, join node i to node 1, forming a ‘star’ tree. This tree has diameter 3, and since there are at least 2 white nodes, an alternating diameter as well, going
white - black - white
via the central node.
- Without loss of generality, let W > 1 (if not, swap what we do with B and W). Assign the color B to nodes 1, 2, \ldots, B and the color W to nodes B+1, B+2, \ldots, B+W. Now, for each 2 \leq i \leq B+W, join node i to node 1, forming a ‘star’ tree. This tree has diameter 3, and since there are at least 2 white nodes, an alternating diameter as well, going
TIME COMPLEXITY:
\mathcal{O}(B + W) per test.
CODE:
Setter (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
assert(t <= 100);
while(t--) {
int a, b;
cin >> a >> b;
assert(a > -1 && a <= 1000);
assert(b > -1 && b <= 1000);
assert(a + b > 0 && a + b <= 1000);
if((!a || !b) && (a + b) > 1) {
cout << "-1\n";
continue;
}
for(int i = 1; i <= a; i++) cout << "B";
for(int i = 1; i <= b; i++) cout << "W";
cout << "\n";
int n = a + b;
if(b == 1)
for(int i = 1; i < n; i++) cout << i << " " << n << "\n";
else
for(int i = 2; i <= n; i++) cout << i << " 1\n";
}
}
Editorialist (Python)
for _ in range(int(input())):
b, w = map(int, input().split())
if b+w == 1:
if b == 1:
print('B')
else:
print('W')
elif b == 0 or w == 0:
print(-1)
else:
print('B'*b + 'W'*w)
for i in range(1, b+w):
if b == 1:
print(1, i+1)
else:
print(i, b+w)