JOIN
 Match Editorials
TCHS SRM 38
Tuesday, September 4, 2007

## Match summary

The match started quickly, and after only a few minutes there were coders who had the easy problem and the medium problem done. The problems were pretty easy for most of the coders, but the 1000 problem was fair. ahyangyi won the match with the fastest time on the medium and hard problems (Quelloquialism had the fastest time on the easy problem). One more successful challenge would've brought neal_wu into first position, but he ended up in second. Third place went to spencer.

# The Problems

JoshString
Used as: Division One - Level One:
 Value 250 Submission Rate 47 / 48 (97.92%) Success Rate 31 / 47 (65.96%) High Score Quelloquialism for 248.99 points (1 mins 48 secs) Average Score 231.18 (for 31 correct submissions)

This was a pretty easy task. The solution was to find the required sum and then check if it's a prime number or not. For every letter you had to add (letter - 'a' + 1). Here is the code:

``` int value = 0;
for (int i = 0; i < s.length(); ++i) value += s.charAt(i)-'a'+1;
if (checkPrime(value)==1) return "YES";
return "NO";
```

Where checkPrime is the function that checks if a number is prime or not. To check if a number is prime, it was up to the coder. Here is a code for it:

``` int checkPrime(int value) {
if (value == 2) return 1;
if (value%2 == 0) return 0;
for (int i = 3; i*i <= value; ++i) if (value%i == 0) return 0;
return 1;
};```

A few people failed or got challenged because they returned 2 as being a non-prime number.

JoshSum
Used as: Division One - Level Two:
 Value 500 Submission Rate 40 / 48 (83.33%) Success Rate 36 / 40 (90.00%) High Score ahyangyi for 498.97 points (1 mins 17 secs) Average Score 429.16 (for 36 correct submissions)

This was a pretty easy task for almost every one. If you were used to Fibonacci series you could code it quickly and get a good score on it, as ahyangyi did. The solution was straightforward: find the n-th term of Fibonacci series modulo 10. Here is the code:

```int a1 = 0, a2 = 1;
int ret = 0;
for (int i = 1; i <= n; ++i) {
int aux = 0;
ret+=a2;
aux = a2; a2 = (a2 + a1)%10; a1 = aux;
}
return ret;```
GrandpaField
Used as: Division One - Level Three:
 Value 1000 Submission Rate 17 / 48 (35.42%) Success Rate 9 / 17 (52.94%) High Score ahyangyi for 805.36 points (14 mins 43 secs) Average Score 565.47 (for 9 correct submissions)

The solution intended has the complexity O(N^2 * F^2). The brute force approach wouldn't pass the system test. The section chosen had to contain at most 2 types of fruit. If you choose 2 type of fruits, let's say f1 and f2, then the problem changes to: What is the biggest square section that contain only fruits of type f1 and f2? The brute force for this would TLE, so a good solution was one based on Dynamic Programming.

Let's define DP[i][j][f1][f2] = the biggest square with down-right corner at (i, j) that contain only fruits of type f1 and f2. The recurrence was easy. If at (i, j) the fruit is not of type f1 nor f2 then DP[i][j][f1][f2] = 0, else DP[i][j][f1][f2] = 1 + min(DP[i-1][j][f1][f2], DP[i][j-1][f1][f2], DP[i-1][j-1][f1][f2]). If you don't understand why this is true, I suggest that you take a piece of paper and see it on an example. During the match neal_wu took another approach and solved it with a binary search; you can take a look at his solution too. Here is the code for the intended solution:

```int best = 0; //here will be the solution
//choose 2 fruits
for (int f1 = 1; f1 < 7; ++f1)
for (int f2 = f1 + 1; f2 <= 7; ++f2) {
//solve for f1 and f2
int bestLocal = 0;
int[][] dp = new int[N+2][N+2];
for (i = 0; i <= N; ++i) dp[i][0] = dp[0][i] = 0;

for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j) if (field[i][j] == f1 || field[i][j] == f2) {
dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));
if (dp[i][j] > bestLocal) {bestLocal = dp[i][j]; }

}

if (bestLocal > best) best = bestLocal;
}
return best*best;
} ```

By vlad_D
TopCoder Member