Match Editorials

Match summary

In this TCHS match 132 participants took part, 100 out of them correctly solved the easy problem, 72 correctly solved the medium one and 42 correctly solved the hard one. First place went to lyrically from Japan, gnocuil (China) and Zuza (Croatia) were second and third respectively.

The Problems

Value	250
Submission Rate	112 / 125 (89.60%)
Success Rate	100 / 112 (89.29%)
High Score	Zuza for 249.28 points (1 mins 32 secs)
Average Score	227.50 (for 100 correct submissions)

The easiest way to solve this problem was just to brute force over all triples of students, check whether they can work together in a team and to pick the team with the maximal possible summary rating. Such an approach needs O(n^3) operations where n is the number of students. Such a solution easily fits into timelimit because n ≤ 50.

Java implementation of this approach can look as follows.

public class TeamSelection {
    public int selectBestTeam(int[] rating, String[] compatibility) {
		int n = rating.length;
		int ans = -1;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if (compatibility[i].charAt(j) == 'Y' && 
					    compatibility[j].charAt(k) == 'Y' && 
					    compatibility[k].charAt(i) == 'Y') {
						int cur = rating[i] + rating[j] + rating[k];
						ans = Math.max(ans, cur);	
					}
				}
			}
		}
		return ans;
	}
}

Value	500
Submission Rate	110 / 125 (88.00%)
Success Rate	72 / 110 (65.45%)
High Score	DaViDeX for 492.46 points (3 mins 31 secs)
Average Score	398.22 (for 72 correct submissions)

As in most implementation problems to solve this problem one needs only to implement everything from the statement carefully. First of all, you need to split the number into integer and fractional parts. This can be done using string manipulation functions which are included into standard library of programming language.

After it one need to format the integer as described in the statement. To do it you need to process characters fror right to left and insert space after each character which number is divisible by three (characters are numbered from right to left with integer numbers starting with one). This step should carefully implemented to not insert the space before the first character of integer part. Some of coders had made such a mistake and they failed system test or were challenged (for example, on test case "123" their programs returned " 123" instead of "123").

Java implementation of this approach can look as follows.

public class NumberFormatter {
	
	private String insertSpaces(String s) {
		String res = "";
		int len = s.length();
		for (int i = 1; i <= len; i++) {
			res = ("" + s.charAt(len - i)) + res;
			if (i % 3 == 0) {
				res = " " + res;
			}
		}
		return res.trim();
	}

	public String format(String number) {
		int commaPos = number.indexOf(',');
		if (commaPos == -1) {
			return insertSpaces(number);
		} else {
			return insertSpaces(number.substring(0, commaPos)) + '.' + number.substring(commaPos + 1);
		}
	}
}

Value	1000
Submission Rate	68 / 125 (54.40%)
Success Rate	42 / 68 (61.76%)
High Score	niyaznigmatul for 988.30 points (3 mins 6 secs)
Average Score	625.95 (for 42 correct submissions)

First of all let's note that a one-to-one correpondance between decreasing numbers and non-empty subsets of set of digits {0..9} exists. All digits in a decreasing number are different (so they form a subset) and exactly one decreasing number can be formed from each subset (you need arrange elements of it in a decreasing order). So there exists only 2^10 - 1 = 1023 decreasing numbers. They can be easily generated. After it one need to sort them increasingly and return the answer for the problem.

Java implementation of this approach can look as follows.

public class DecreasingNumbers {
	ArrayList<Long> list; 
	void go(int pos, String s) {
		if (pos == -1) {
			if (s.length() > 0) {
				list.add(Long.parseLong(s));
			}
			return;
		}
		go(pos - 1, s + pos);
		go(pos - 1, s);
	}
	public long getNth(int n) {
		list = new ArrayList<Long>();
		go(9, "");
		Collections.sort(list);
		if (n >= list.size()) {
			return -1;
		}
		return list.get(n);
	}	
}