Match Editorials

Match summary

The 2008 TCHS tournament started with Round 1 with 191 competitors. This giving all the posibility to advance with a positive score, which most of the competitors were able to do. For high rated highschoolers the first round was a warm up round. With a pretty easy set of problems 77 of competitors sent solution to all 3 problems but only 51 ended up with corect solution to all 3 problems. Only after 5 minutes solutions started to be submitted, and after 15 minutes some competitors were done with all problems. After a succesful challenge Loner managed to be 1st, fallowed by Zuza on second and gurugan1 on third.

The Problems

Value	250
Submission Rate	183 / 189 (96.83%)
Success Rate	178 / 183 (97.27%)
High Score	LittlePig for 248.49 points (2 mins 13 secs)
Average Score	229.94 (for 178 correct submissions)

A pretty strightforward problem. Take each query in order, and check if the class is available in names, and check if there are any spaces left for that class left. Each time we find a class we decrement the number of spaces available for that class, so each element of spaces will still represent the number of free spaces left. An example of java solution follows:

for (i = 0; i < queries.length; ++i) {
    int available = -1;  // the number of spaces available in class queries[i]
    for (j = 0; j < names.length; ++j)
        if (names[j].equals(queries[i])) {available = spaces[j]; break;} //we found the class
    if (available == -1) {ret[i] = "DOES NOT EXIST"; continue;}; //if available == -1 there is no class queries[i]
    if (available == 0) {ret[i] = "NOT GOOD"; continue;}; // if available == 0 there is no more room in that class
    spaces[j]--; //decrement the number of spaces available in class
    ret[i] = "GOOD";            
    };
return ret;    

Value	500
Submission Rate	186 / 189 (98.41%)
Success Rate	177 / 186 (95.16%)
High Score	mosrecki for 497.69 points (1 mins 56 secs)
Average Score	443.20 (for 177 correct submissions)

Most of the coders used the intuitive greedy solution. It was pretty easy to see by intuition that if you serve the clients in tips orders, from the largest tip to the lowest one, you would get the right answer. Let's prove this solution is really optimal. Each second we pick a customer, take all coins from him, and our rival takes one coin from every other customer which is still present. If we minimize the number of coins our rival gets, we maximize the number of coins we get. The number of coins our rival takes each turn is equal to the number of customers with at least one coin. If we always pick the customer with the maximal amount of coins available, we maximize the number of customers without money after each second. So, our rival gets the smallest possible amount, and we get the biggest.

Value	1000
Submission Rate	77 / 189 (40.74%)
Success Rate	51 / 77 (66.23%)
High Score	Zuza for 983.85 points (3 mins 39 secs)
Average Score	686.43 (for 51 correct submissions)

For some this problem was a classic one, but for others it was something new. For those who had trouble with it or never saw problems like this, I recommend to take a look on Dynamic Programming Tutorial from TopCoder and practice as much as they can, TCHS final will be soon.

Consider the table DP[i][X] with i = 1, N and X = 0, 100000, where N is the number of groups from the problem. DP[i][X] has the meaning what is the number of subsets that are made using only first i groups and such that the greatest common dividor (GCD) of each of those subsets is equal to X. Easy to see that the answer for the problem will be equal to DP[N][1]. If at some point we know DP[i][X], we can go further and count the number of subsets built using the (i + 1)-st group as well. In details, since each subset built using first i groups can be also built using first i+1 groups, we need to add DP[i][X] to element DP[i + 1][X]. If we want to use the (i+1)-st element, the GCD of the new group will be equal to GCD(X, groups[i + 1]), so we need to add DP[i][X] to DP[i + 1][GCD(X, groups[i + 1])] as well.

A simple java solution follows. The reference solution used longs instead of ints, and was taking the modulo at the very end.

    long ret = 0;
    int n, i, j;
    n = groups.length;
    long [][] DP = new long[n+3][100002];
    for (i = 1; i <= n; ++i) {
        DP[i][groups[i-1]]++;
        for (j = 1; j <= 100000; ++j) if (DP[i-1][j] != 0) DP[i][gcd(j, groups[i-1])]+=DP[i-1][j];
        //plus add all
        for (j = 1; j <= 100000; ++j) DP[i][j] += DP[i-1][j];
    };
    ret = DP[n][1];
    
return (int)(ret % 10000003);