Match summary

As the TCHS 2007 online rounds were close to the end, students from the Delta region were given a chance to prove that they deserved a trip to Purdue in May. Each of the 15 participating students only needed to get a positive score to qualify, and 14 of them were successful. They were led by Loner from The First Middle School of Wuhu. With the help of six successful challenges, Loner was able to overcome ahyangyi, from Affiliated Middle School to Anhui Normal University, who came in second, and wintokk, from Zhongshan No. 1 Middle School, came in third.

The Problems

AdvertisingAgency

Used as: Division One - Level One:

Value 250

Submission Rate 14 / 15 (93.33%)

Success Rate 14 / 14 (100.00%)

High Score tranquilliser for 249.25 points (1 mins 33 secs)

Average Score 246.00 (for 14 correct submissions)

This problem was straightforward -- for each request we can find out whether it will be accepted or rejected, and count the number of rejected requests. The request is rejected if some request before it has the same billboard number. The code follows:

    public int numberOfRejections(int[] requests) {
        int r = 0;
        for (int i = 0; i < requests.length; i++) {
            boolean ok = true;
            for (int j = 0; j < i; j++) {
                if (requests[i] == requests[j]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                r++;
            }
        }
        return r;
    }

DigramAnalysis

Used as: Division One - Level Two:

Value 500

Submission Rate 14 / 15 (93.33%)

Success Rate 5 / 14 (35.71%)

High Score Loner for 476.43 points (6 mins 22 secs)

Average Score 454.98 (for 5 correct submissions)

The solution to this problem is quite technical. For each word let us find all the digrams that occur in it. After that for each digram let us count the number of words it occurs in. Finally we select the digram that occurs in most words.

One interesting moment was not stated in the statement directly, but should have been derived from it. Let all the words in the input text have length equal to 1. In this case no digram appears in any word — it appears in zero words, that is. In this case digram "aa" is the earliest lexicographically digram among equally frequent (or, more exactly, infrequent) digrams, so it must be returned.

The code follows:

    public String mostFrequent(String[] chunks) {
        String text = "";
        for (String ch : chunks) {
            text += ch;
        }

        Map freq = new TreeMap();

        String[] words = text.split("[ ]+", -1);
        for (String w : words) {
            Set<String> ss = new HashSet<String>();
            for (int i = 0; i < w.length() - 1; i++) {
                String dig = "" + w.charAt(i) + w.charAt(i + 1);
                ss.add(dig);
            }
            for (String dig : ss) {
                if (!freq.containsKey(dig)) {
                    freq.put(dig, 0);
                }
                freq.put(dig, freq.get(dig) + 1);
            }
        }

        String ans = "aa";
        int best = 0;
        for (String dig : freq.keySet()) {
            if (freq.get(dig) > best) {
                ans = dig;
                best = freq.get(dig);
            }
        }

        return ans;
    }

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 are encouraged to review the Algorithm Tutorials section to power up their skills, as well as their programming language library tutorials.

MoreBlack

Used as: Division One - Level Three:

Value 1000

Submission Rate 11 / 15 (73.33%)

Success Rate 9 / 11 (81.82%)

High Score ahyangyi for 955.31 points (6 mins 12 secs)

Average Score 652.45 (for 9 correct submissions)

Before reading this writeup the reader is recommended to make himself familiar with the basic terminology on graphs. The Graph & Data Structures tutorial is a good place to start with, and you should also review the Graph Wikipedia article.

Let us consider the given board as a graph, with the existing squares as vertices. Connect two vertices by an edge if the corresponding squares have a common border. The constructed graph is clearly bipartite. The requirement that no two existing squares with a common side should have the same color means that we must color one part of the graph white and another part black. Since the number of black squares must be maximized, the larger part must be colored black, and the smaller one must be colored white.

Note that we can color each connected component separately. Let us find connected components, each of which is a bipartite graph by itself. For each component we determine which part is greater, and color it black.

There is one more optimization criteria — the answer must be lexicographically minimal. The only case when we have a choice as to which part to color black is when parts in a component have the same number of squares. To get the lexicographically smallest solution let us scan the board line after line, identifying connected components. If we find the new component with parts of the same size, we color black the square that was scanned first in the component.

By andrewzta
TopCoder Member