Match summary

What do school boys and girls do during the winter holidays? That's right, they compete in TopCoder High School SRMs! More than 200 competitors took part in HS SRM 26, with Zuza winning the match with a comfortable lead. fatit finished second and reiten rounded out the top three.

The Problems

ThirdBuyDiscount

Used as: Division One - Level One:

Value 250

Submission Rate 191 / 212 (90.09%)

Success Rate 164 / 191 (85.86%)

High Score fpavetic for 248.31 points (2 mins 20 secs)

Average Score 209.83 (for 164 correct submissions)

It should be easy to see that putting the most expensive items into the discount positions (positions with indices divisible by 3) is the optimal strategy. Accordingly, just sort the items by the price, and apply the discount for the n / 3 most expensive ones, with n representing the number of the items.

Java code follows:

public static double minCost(int[] prices, int discount) {
	double ret, k;
	int n, i, j;
	n = prices.length;
	ret = 0;
	k = 0.01 * (100 - discount);
	Arrays.sort(prices);
	for (i = 0; i < n; i++)
		if (i < n / 3) ret += k * prices[n - 1 - i];
		else ret += prices[n - 1 - i];
	return ret;
}

CompressedString

Used as: Division One - Level Two:

Value 500

Submission Rate 144 / 212 (67.92%)

Success Rate 78 / 144 (54.17%)

High Score Burunduk3 for 491.91 points (3 mins 39 secs)

Average Score 369.09 (for 78 correct submissions)

There is a straightforward recursive solution for this problem. If the first character of s is a digit and the second is the opening paranthesis, then find the corresponding closing paranthesis -- the answer is equal to the answer for the substring enclosed by the parantheses, multiplied by the value of the first digit, plus the answer for the remaining part of s (from the position immediately after the closing paranthesis until the end of the string). In the other case, the answer is equal to the answer for the same string without the first character plus 1.

Java code follows:

public int getLength(String s) {
	if (s.length() <= 1) return s.length();
	if (s.charAt(1) != '(') return 1 + getLength(s.substring(1));
	int left = 2, n = 2, stack = 1;
	for (int a = left; a < s.length(); a++) {
		if (s.charAt(a) == ')') stack--;
		if (s.charAt(a) == '(') stack++;
		if (stack == 0) {
			n = a;
			break;
		}
	} return (s.charAt(0)-'0')*getLength(s.substring(2,n))+getLength(s.substring(n+1));
}

CoolNumbers

Used as: Division One - Level Three:

Value 1000

Submission Rate 24 / 212 (11.32%)

Success Rate 12 / 24 (50.00%)

High Score Zuza for 791.81 points (15 mins 26 secs)

Average Score 523.36 (for 12 correct submissions)

Suppose, we have a function f(x) that returns the number of cool numbers between 0 and x, inclusive. The answer for the problem is equal to f(upperBound) - f(lowerBound - 1). Function f(x) uses dynamic programming. Let's introduce a function doit(int step, int last, int len, int match, int done). This goes through the binary representation of x from left to right, constructing a number, and returns the number of the cool numbers that has a constructed prefix. Here step is the number of the remaining digits, last is a value of the previous digit, len is a number of the last consequtive equal digits, match indicates whether the constructed prefix is equal to the corresponding prefix of x, and done indicates whether the constructed prefix contains a group of three consecutive ones or zeroes (i.e. whether the constructing number is already cool).

Java code follows:

static int memo[][][][][] = new int[33][2][4][2][2];
static int s[] = new int[33];
static int n;

public static int doit(int step, int last, int len, int match, int done) {
	int ret, i;
	if (len > 3) len = 3;
	if (len == 3) done = 1;
	if (step < 0) return done;
	if (memo[step][last][len][match][done] >= 0) return memo[step][last][len][match][done];
	ret = 0;
	for (i = 0; i < 2; i++) if (match == 0 || i <= s[step]) {
		if (i == last) {
			if (match == 1 && i == s[step]) ret += doit(step - 1, i, len + 1, 1, done);
			else ret += doit(step - 1, i, len + 1, 0, done);
		}
		else {
			if (match == 1 && i == s[step]) ret += doit(step - 1, i, 1, 1, done);
			else ret += doit(step - 1, i, 1, 0, done);
		}
	}
	return memo[step][last][len][match][done] = ret;
}

public static int f(int x) {
	int ret, i, j, k, y, z;
	if (x < 0) return 0;
	... // fill the array memo by -1
	for (z = x, n = 0; z != 0; z >>= 1) s[n++] = z & 1; // s now contains a binary representation of x
	ret = doit(n - 2, s[n - 1], 1, 1, 0); // count all cool nubers with the same number of digits (in binary) as s
	for (i = n - 2; i > 0; i--) ret += doit(i - 1, 1, 1, 0, 0); // count all other cool numbers less than x
	return ret;
}
	
public static int count(int lowerBound, int upperBound) {
	return f(upperBound) - f(lowerBound - 1);
}

By gevak
TopCoder Member