The first problem in today’s TopCoder Single Round Match was on bijections:
Formally, a relation is a set of ordered pairs of elements. The teacher gave Weiwei one such relation. You are also given a description of this relation: int[]sdomain and range. For each valid i, the relation contains the ordered pair (domain[i],range[i]).
Let X be the set of elements that appear at least once in domain. Similarly, let Y be the set of elements that appear at least once in range. We say that an element x of X is paired to an element y of Y if the relation contains the ordered pair (x, y).
We will say that our relation is a bijection if each element of X is paired to exactly one element of Y, and each element of Y is paired to exactly one element of X.
That is, given a list of pairs, determine whether an element appears in more than one pair (there are no identical pairs). We can use Java’s HashMap to store these pairs, and when we’re adding a pair we can check if either of the elements has already been added in another pair.
import java.util.*;
public class RelationClassifier {
public String isBijection(int[] domain, int[] range) {
HashMap<Integer, Integer> relations = new HashMap<Integer, Integer>();
for (int i=0; i<domain.length; i++) {
if (relations.containsKey(domain[i])) return "Not";
else if (relations.containsValue(range[i])) return "Not";
else relations.put(domain[i], range[i]);
}
return "Bijection";
}
}
The second problem looked quite interesting, but I couldn’t get a solution in time. You’re playing a game where you have one shot that will eliminate any points (on a plane) that lie on the x and y-axes . Before you take the shot, though, you’re allowed to rotate all the points (together) and move them together in any direction — any number of times. The aim is to eliminate as many points as possible.