ALTDIA - Editorial

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.

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 :frowning:

1 Like

It is a controversial
question.