 # ALTDIA - Editorial

Author: Tejas Pandey
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh

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.

# 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)


The definition of Diameter in the context of a tree should have been mentioned in the problem statement.

It is a bit misleading (or maybe I was dumb). I thought not only the diameter, but no two nodes sharing an edge have the same colour too.

6 Likes

Strong agree. I understood diameter to be the longest distance between two leaves of the tree. That’s quite an interesting little problem, but - unfortunately for me - that’s not this problem 1 Like

It is a controversial
question.