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.