Match Editorials

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

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.

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;

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;
  }