Match summary

Students from the Gamma region were the first to get into TCHS 2007 tournament, and they were first to qualify for the onsite event. Round 3 was the first round in Gamma that could actually leave somebody with a positive score behind, as 35 students competed for 25 onsite spots.

This time the problems were a bit harder than in previous rounds, although the easy problem proved to be really easy with everyone submitting it and only one solution failing. However, the medium and hard problems gave students the opportunity to show their skills and prove that they deserved an onsite spot at Purdue later this spring.

The leading position on the scoreboard was occupied by reiten from UPML. He was followed by Burunduk3 and Burunduk2 (in this order) from Saint-Petersburg Phys-Math Lyceum #30. Another interesting fact is that nobody managed to get a positive score during the challenge phase. Although several coders actually had successful challenges, all of them managed to get at least twice as many unsuccessful ones.

The Problems

BrokenKeyboardRepair

Used as: Division One - Level One:

Value 250

Submission Rate 34 / 34 (100.00%)

Success Rate 33 / 34 (97.06%)

High Score Curiouser for 249.72 points (0 mins 57 secs)

Average Score 246.37 (for 33 correct submissions)

The problem could be actually restated as follows: find the number of different letters in a word. A straightforward approach here is successful. For each letter in a word check whether it occurred before, and if it did not, increase the answer by one. The code follows.

    public int minimalNumberOfKeys(String word) {
        int r = 0;
        for (int i = 0; i < word.length(); i++) {
            boolean first = true;
            for (int j = 0; j < i; j++) {
                if (word.charAt(i) == word.charAt(j)) {
                    first = false;
                }
            }
            if (first) {
                r++;
            }
        }
        return r;
    }

ColorfulDisks

Used as: Division One - Level Two:

Value 500

Submission Rate 29 / 34 (85.29%)

Success Rate 25 / 29 (86.21%)

High Score Burunduk2 for 477.06 points (6 mins 17 secs)

Average Score 333.09 (for 25 correct submissions)

For each radius let us create a set of all colors such that a disk with this radius exists. After we build a pyramid, exactly one disk of each size will be visible from above, so we need to find all colors that appear in each of the sets. The code follows.

    public String[] singleColor(String[] disks) {
        int n = disks.length;
        Set<String> colors = new TreeSet<String>();
        Map<Integer, Set<String>> cbyr = new HashMap<Integer, Set<String>>();
        for (int i = 0; i < n; i++) {
            Scanner s = new Scanner(disks[i]);
            String color = s.next();
            int r = s.nextInt();
            colors.add(color);
            if (!cbyr.containsKey(r)) {
                cbyr.put(r, new HashSet<String>());
            }
            cbyr.get(r).add(color);
        }

        ArrayList<String> a = new ArrayList<String>();
        for (String s : colors) {
            boolean ok = true;
            for (int r : cbyr.keySet()) {
                if (!cbyr.get(r).contains(s)) {
                    ok = false;
                }
            }
            if (ok) {
                a.add(s);
            }
        }
        return a.toArray(new String[a.size()]);
    }

Note that extensive use of library data structures could make this problem a bit easier. Coders who do not feel comfortable with using library data structures should check out TopCoder's Algorithm Tutorials section to power up their skills, as well as their programming language library tutorials.

Provinces

Used as: Division One - Level Three:

Value 1000

Submission Rate 10 / 34 (29.41%)

Success Rate 8 / 10 (80.00%)

High Score reiten for 688.39 points (21 mins 15 secs)

Average Score 520.60 (for 8 correct submissions)

First, note that if a province contains cities with numbers x and y, it contains all cities with numbers between x and y as well. Indeed, if it's not the case, and the city z such that x < z < y belongs to another province, one can get from x to z and from z to y by main roads. This contradicts the constraint in the problem statement which says that there must be no provinces A and B such that we can get both from A to B and from B to A.

Therefore each province must contain a continuous range of cities. Since all provinces must have the same number of cities, the number of provinces must be a divisor of n. Therefore the division to provinces is uniquely identified by a single number k of provinces, and k must divide n.

Let us see what can prevent us from constructing k provinces. Clearly the roads that go from a city x with a smaller number to a city y with a greater number do not play any role, since we can get from x to y by main roads. Therefore we must only consider roads from x to y such that x > y. For each city y let us find the number m[y] — the greatest number of the city such that there is the road from it to y.

Let us consider the division of cities to k provinces, and number provinces from 1 to k in such a way that provinces with smaller numbers contain cities with smaller numbers. So the first province would contain cities 1, 2, ..., n/k, the second one would contain n/k+1, n/k+2, ..., 2n/k, etc.

If the division is invalid, there must be two provinces A and B such that both paths from A to B and from B to A exist. Let A < B, consider the path from B to A, and take the first road on it that goes from a province with greater number to a province with smaller number. Let this road go from city x to city y. From definition of m[y] we deduce that x ≤ m[y]. Therefore if the division to provinces is invalid, there exists a city y such that m[y] belongs to a province other than that of y. Conversely, if there exists such a city, the division to provinces is invalid since these two provinces would contradict the problem statement.

Therefore it is necessary and satisfactory for the division to be valid that for all cities m[x] belongs to the same province as x. The code follows.

    public int maximalNumber(int n, String[] roads) {
        String r = "";
        for (String s : roads) {
            r += s;
        }
        Scanner s = new Scanner(r);
        s.useDelimiter("[ ,]+");

        int[] m = new int[n];
        for (int i = 0; i < n; i++) {
            m[i] = i;
        }
        while (s.hasNextInt()) {
            int a = s.nextInt() - 1;
            int b = s.nextInt() - 1;
            if (a > b) {
                m[b] = Math.max(m[b], a);
            }
        }

        int best = 1;
        for (int d = 1; d <= n; d++) {
            if (n % d != 0) {
                continue;
            }
            boolean ok = true;
            for (int i = 0; i < n; i++) {
                int j = (i + d) / d * d;
                if (m[i] >= j) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                best = n / d;
                break;
            }
        }
        return best;
    }

By andrewzta
TopCoder Member