I agree. Please don't use approximate problems where the test case generation method is not disclosed. It makes it almost impossible to test our solutions locally. This problem in particular had a large space of inputs and we were supposed to simply guess how the test cases were generated from such a large pool of possibilities? In particular, some approaches which worked really well on my local test cases made almost no difference or scored worse on the official test cases. In some of the recent Hackerearth contests this issue did not show up anymore, so I thought it was finally solved, but now it's back again. I guess it all depends on the experience of the problem setter, but I think the tester should also push for disclosing the test case generation method.

Sqrt decomposition.

• For big groups  > sqrt(N).

Use standard algorithm (2 DFSs) for finding perimeter of a tree in O(N).

• For small groups  < sqrt(N)

Choose a root, compute levels and ladders, Then check the distance of each pair in so the total complexity would be , where n_i is the size of this group. (You can also use Tarjan LCA to avoid extra log)

NlogN solution.
For each color keep track of the 2 farthest nodes and whenever u find a node whose distance to one of the 2 farthest nodes of that color is more than the distance between those 2 nodes , update the farthest pair of nodes for that color.
Code

I solved it with centroid decomposition.

There are two cases:

1. If the diameter pass through the centroid, then we only need the deepest node of every color in each of the branchs

2. Otherwise, calculate recursively for each of the subtrees that are hanging on the centroid

Suppose that we fix some subset of f's, say f_s1, f_s2, ..., f_sk, and we want to choose some permutation p such that all a[i] + p[i] belongs to {s₁, s₂, ..., s_k}.

In other words p[i] can be equal j iff .

It is a matching problem, between the domain of p and its counterdomain. Say D = {0, 1, ..., n - 1} and C = {0, 1, ..., n - 1}, and the edge between i and j exists iff p[i] can be equal to j.

Now let us go back to the original problem. We sort f, say f_s1 ≤ f_s2 ≤ ... and for k = 1, 2, ... we check if we can find a permutation p for the subset {f_s1, f_s2, ..., f_sk}. If so then the answer to the original problem is f_sk.

Binary Search on answer
We want to check an answer <= 'X' is possible or not.
Lets make a bipartite graphs with 'N' nodes from [0 , n — 1] on each side.
Now the weight of edge from i on left side to j on right side will be f[i + a[j]]. if this weight is less than 'X' then add this edge to list of edges.
Now find maximum bipartite matching.
If matching == 'N' then return true else return false.
Code

Consider that we had to remove edges instead of Nodes. In that case it is a standard problem of finding the min-cut which is equal to the Max-Flow.
Now we need to remove nodes instead of edges , so we keep 2 copies of each node say V1 and V2. Now for every edge (U -> V) in input , add edges in our graph from U2 to V1 and since its undirected , edge from V2 to U1 as well , give it weight infinity. And then for all nodes from 1 to N , add an edge from V1 to V2 with weight = the cost of removing that node. And then just find the maxflow from A1 to B2. Code

+1. It seems that once the contest ends, the scores for the approximation problem are not shown anymore (neither for old submissions, nor for new ones). You only get if the solution was Accepted on each test case or not, but not the score which measures the quality of the solution on each test case (which is the most important thing).

@organizers: Can you please fix this issue with the approximation problem? It's really annoying (both for upsolving and for looking at the best submissions of the other competitors).