|
Match Editorials |
Monday, November 27, 2006
Match summary
In total there were 278 submissions for HS SRM 21 by 148 members. Continuing his impressive performance, Zuza enjoyed another HS SRM win with 1708.72 points. He was followed by fatit, who has just turned red, with 1649.62 points after the system test. Burunduk3also did an excellent job with 1596.72 points. After the system test refused a few submissions, 27 members ended up passing all three problems successfully.This set of problems was reasonably easy, and the high number of submissions made this set especially exciting. Congratulations to the great number of gifted high schoolers from all over the world who performed better than they have before.
PostOffice
Used as: Division One - Level One:
This problem was the easiest one, with 129 members' solutions passing the system tests. Two tasks should be accomplished here:
Value 250 Submission Rate 129 / 137 (94.16%) Success Rate 99 / 129 (76.74%) High Score fatit for 248.41 points (2 mins 16 secs) Average Score 220.63 (for 99 correct submissions)
1. Remove all the spaces from both addresses.
2. Perform a case-insensitive string comparison.
If two strings are equal, simply return -1. Otherwise, return the leftmost 0-based position at which they differ. Pay attention, though -- one tricky case is that either parameter can be an empty string here.
Here is tomekkulczynski's code:
char down(char x)
{
if(x>='A' && x<='Z') return x-'A'+'a';
return x;
}
int matchAddress(string a, string b)
{
string A,B;
int i;
for(i=0; i<a.size(); i++) if(a[i] != ' ') A+=down(a[i]);
for(i=0; i<b.size(); i++) if(b[i] != ' ') B+=down(b[i]);
if(A == B) return -1;
for(i=0; A[i]==B[i]; i++);
return i;
}
FixedPoint
Used as: Division One - Level Two:
A fixed point is a point that does not change upon application of a map, system of differential equations, etc. One of the oldest fixed-point theorems - Brouwer's - was developed in 1910. By 1928, John von Neumann was using it to prove the existence of a "minimax" solution to two-agent games (which translates itself mathematically into the existence of a saddlepoint). For this problem, you are not required to know much about such fixed point theorem, but only to solve the following set of equations:
Value 500 Submission Rate 97 / 137 (70.80%) Success Rate 87 / 97 (89.69%) High Score Xixas for 480.09 points (5 mins 49 secs) Average Score 357.61 (for 87 correct submissions)
(scale * cos(rotate) - 1) * x - scale * sin(rotate) * y = -translate[0] * cos(rotate) + translate[1] * sin(rotate)
scale * sin(rotate) * x + (scale * cos(rotate) - 1) * y = -translate[0] * sin(rotate) - translate[1] * cos(rotate)
Step 1: To get a clear view, we define four new variables a A, B, C and D.
A = (scale * cos(rotate) - 1)
B = scale * sin(rotate)
C = -translate[0] * cos(rotate) + translate[1] * sin(rotate)
D = -translate[0] * sin(rotate) - translate[1] * cos(rotate)
Step 2: These two equations are becoming:
A * x - B * y = C (1)
B * x + A * y = D (2)
Step 3: To calculate the answer of x, we do:
(1) * A: A * A * x - A * B * y = A * C
(2) * B: B * B * x + A * B * y = B * D
Step 4: Equation(1)'s left side + Equation(2)'s left side = Equation(1)'s right side + Equation(2)'s right side
A * A * x + B * B * x = A * C + B * D
Step 5: x = ( A * C + B * D ) / ( A * A + B * B )
The sample method can be applied to calculate the answer of y:
(1) * B : A * B * x - B * B * y = B * C
(2) * A : A * B * x + A * A * y = A * D
(2) * A - (1) * B
A * A * y + B * B * y = A * D - B * C
y = ( A * D - B * C ) / ( A * A + B * B )
Here is my code:
double A = (scale * cos(rotate) - 1); double B = scale * sin(rotate); double C = -translate[0] * cos(rotate) + translate[1] * sin(rotate); double D = -translate[0] * sin(rotate) - translate[1] * cos(rotate); vector <double> ans; ans.push_back(( A * C + B * D ) / ( A * A + B * B )); ans.push_back(( A * D - B * C ) / ( A * A + B * B )); return ans;
ElectiveSystem
Used as: Division One - Level Three:
Value 1000 Submission Rate 52 / 137 (37.96%) Success Rate 28 / 52 (53.85%) High Score Zuza for 955.23 points (6 mins 12 secs) Average Score 712.26 (for 28 correct submissions)
This is a normal Dynamic Programming problem. We define S[i] as the sum of goodness
for the first i time units. dp[i][j] means the maximum value for the first i time
unites if we log in j times within it, but with a limit of D time units for each login.
The equation of state is:
dp[i][j] = max{ dp[i-D][j-1] + S[i]-S[i-D], dp[i-1][j] } (here i-D will be replaced by 0
if (i-D<0))
The above equation consists of two aspects:
- The i-th time unit is not a part of any login. Well, we can ignore the existence of the i-th time unit. Under such circumstances, maximum of dp[i][j] equals to the maximum value of first i-1 time units divided into j logins: dp[i][j]=dp[i-1][j].
- The i-th time unit is in one of the j logins, suppose it is numbered as the j-th login. Since all the goodness are positive, the longer you log in, the larger goodness you will get. We can assume that j-th login be a consecutive period from i-D+1 to i, and under such condition, dp[i][j] = dp[i-D][j-1] + sum(i-D+1, i-D+2, ..., i) = dp[i-D][j-1] + S[i]-S[i-D]. (In case of i-D+1<0, all the time units before i should be picked up, so 0 will be used instead of i-D.)
n = 0;
for (int i = 0;i < s.size();i ++)
for (int j = 0;j < s[i].length();j ++)
{
n ++;
a[n] = s[i][j] - 'a' + 1;
}
memset(S , 0 , sizeof(S));
for (int i = 1;i <= n;i ++)
S[i] = S[i - 1] + a[i];
memset(dp , 0 , sizeof(dp));
int ret = 0;
for (int i = 1;i <= n;i ++)
for (int j = 1;j <= K;j ++)
{
int t = i - D;
if (t < 0) t = 0;
dp[i][j] = max(dp[i][j] , dp[t][j - 1] + S[i] - S[t]);
dp[i][j] = max(dp[i][j] , dp[i - 1][j]);
ret = max(ret , dp[i][j]);
}
return ret;
