JOIN
Get Time
high_school  Match Editorials
TCHS SRM 62
Saturday, November 22, 2008

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

TeamSelection rate it discuss it
Used as: Division One - Level One:
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;
	}
}

NumberFormatter rate it discuss it
Used as: Division One - Level Two:
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);
		}
	}
}

DecreasingNumbers rate it discuss it
Used as: Division One - Level Three:
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);
	}	
}

Author
By FedorTsarev
TopCoder Member