Hi Codeforces.

On friday I participated in the round 1A of the GCJ but I could not pass the third problem. Even the easy set test. Here are my two codes.

PROBLEM

Easy case LINK. Full case LINK.

In the easy one, I just did what the editorial said. However, I got WA repeatedly (15 submissions).

For the full set, my idea is the following. First rest from P the perimeter of all the rectangles and now I have P'. Now, each rectangle i add to the answer 0 if it is not cut, or a number in range [ L[i], R[i] ] where L[i] = 2 * min (W[i], H[i]) and R[i] = 2 * hypot (W[i], H[i]) if is cut. The idea is to choose a subset of the rectangles whom will be cut and the sum of additional perimeters must not exceed P'.

Now, each subset j generates an interval [ L_subset[j], R_subset[j] ]. However, these intervals will always start (left side value) with at most 250 * 100 (maximum side length and maximum quantity of rectangles). Therefore, I did a DP where DP[i] is the maximum right side of an interval for the left side be exactly i.

Start DP[i] = -INF
DP[0] = 0
FOR i in range(0, N):
	FOR leftside in range(0,25001)
		DP[leftside] = max (DP[leftside] , DP[leftside – L[i] ] + R[i] ) 

Now, for each DP[i] for i <= P' I checked if DP[i] >= P', then the answer is P as this could be reached. Otherwise, the answer is max DP[i] for i <= P' plus the sum of perimeters of all rectangles.

The complexity of this idea is 100 * 100 * 250. Could give TLE, I don't know because the system always gave me WA.

I spend all the weekend tring to find out why my codes gave me WA, now I need your help. Many thanks

Hi, I would like to know if there is some algorithm to solve the following problem, or maybe it is NP.

Given a bipartite graph of at most 200 nodes in each side, I need to color the minimum number of nodes so each node is colored or has a colored neighbor. The colored nodes could be in any side.

Thanks for your answers.

Hi, I need help to understand why my code is giving me WA in the following problem Kingdom Roadmap.

Basically the problem ask the following: Given a tree of size N, what's the minimum number of additional edges (and which ones) so the tree becomes a biconected graph (there is no bridge). Notice that an existing edge could be repeated

I will explain my idea part by part, so I hope someone could find my mistake.

The case with N == 2 This is a special case, just print "1\n1 2\n"

N>2 then the tree will have L leaves with L<N

The key observation of my idea is that each leaf of the tree must be connected by at least one of the new edges. Why? because in the contrary case the edges between the leaf and his parent becomes a bridge. So, a lower bound of the answer will be (L + 1) / 2 (integer division).

When we join two leaves u and v with and edge, all the edges in the path from u to v are no longer bridges. Is there some way to match leaves with just (L + 1) / 2 edges and solve the problem?

I think it's posible.

1 Find a node which isn't a leaf and has the following property: If we use this node as the root of the tree, then the maximum quantity of leaves in the subtrees of his neighbors is <= L/2. This node is kind of a "centroid" of leaves.

At the beginning I wasn't sure if there is always a node which has the previos property but I couldn't prove it. I tried to send a code in which if there isn't a "centroid" the program enters in a infinite loop, but the judge still gives WA and not TLE.

2 Using the centroid as a root of the tree, I assign a different color for each of his neighbors and propagate that color to their respective subtrees.

The fact that I used for my solution is that the path between two leaves of different colors must contain the centroid/root. So, if we match each of the leaves with another one that has different color, all the paths from each leaf to the root will no longer be bridges, so the problem is solved. Now, how to assign the necessary edges?

3 Put all the leaves in a vector and sort them by their color. So, all the leaves with the same color will be next to each other. (First assume that L%2 == 0).

if the vector is Leaves then, all the leaves in position i, with i < L / 2, and i + L / 2 must have different color. Why? Because we choose the leaf-centroid as the root, and because of its definition the number of leaves with the same color must be <= L/2. So, in the sorted vector, the positions i and i + L / 2 must be different, otherwise there should be L / 2 + 1 leaves with the same color, which is a contradiction.

4 The only remaining case is when L%2==1

In this case we can match all the edges, we will have 1 unmatched edge. But we could match this edge with the root of the tree removing all the remaining edges that were still bridges. But which leaf?

After sorting, I just add the first leaf in the vector at the end, because the first node and the one in de middle have different color.

This is my code, I tried to add comments for better understanding. Hope someone could find my mistake, I sure it is something that, if is not the base idea, will make me feel stupid when I find it.

Thank you.

Hi, I've been trying to solve the following problem Blanket

but my code just get RTE and I don't know why, could someone help me to find my bug?

Here is my code Code