January 27, 2022 Rookie SRM 9 Editorial
TaroBalls
The trick here is to realize that if there’s the same number of each color ball, it’s a loss, otherwise, we can win. This makes it very easy to solve:
public String getWinner(int R, int B) {
if (R == B) return "Friend";
return "Taro";
}
EllysExpression
We get the maximum value of the expression by adding all the largest values, and by subtracting all of the smallest values. So, if we sort the list, we can then add and subtract values based upon how many plus and minus signs we are to use. Note that, because there is no operator at the start of the expression, that’s essentially one more “plus” sign that we get to use.
public int getMax(int[] numbers, int numPluses, int numMinuses) {
Arrays.sort(numbers);
int ret = numbers[numbers.length - 1];
for (int i = numbers.length - 2; i >= 0; i--)
ret += numPluses-- > 0 ? numbers[i] : -numbers[i];
return ret;
}
GoodSubstrings
Here, we want to use dynamic programming to go from left to right, to determine the most optimal way of filling in the ? values. Note that we always want to create the longest lengths of consecutive characters possible, since they create the most good substrings.
final int MAXN = 505;
int [][][] memo = new int[MAXN][MAXN][26];
String s;
int dp(int i, int lastEqual, int last) {
int res = memo[i][lastEqual][last];
if (res != -1)
return res;
res = 0;
if (i == s.length()) {
res = lastEqual * (lastEqual + 1) / 2;
} else {
char ch = s.charAt(i);
if (ch == '.') {
for (int cur = 0; cur < 26; cur++) {
if (cur == last) {
res = Math.max(res, dp(i + 1, lastEqual + 1, last));
} else {
res = Math.max(res, dp(i + 1, 1, cur) + lastEqual * (lastEqual + 1) / 2);
}
}
} else {
if (ch - 'a' == last) {
res = Math.max(res, dp(i + 1, lastEqual + 1, last));
} else {
res = Math.max(res, dp(i + 1, 1, ch - 'a') + lastEqual * (lastEqual + 1) / 2);
}
}
}
memo[i][lastEqual][last] = res;
return res;
}
public int maxGoodSubstrings(String _s) {
s = _s;
for (int i = 0; i < MAXN; i++)
for (int j = 0; j < MAXN; j++)
for (int last = 0; last < 26; last++)
memo[i][j][last] = -1;
int ans = 0;
if (s.charAt(0) == '.') {
for (int cur = 0; cur < 26; cur++) {
ans = Math.max(ans, dp(1, 1, cur));
}
} else {
ans = Math.max(ans, dp(1, 1, s.charAt(0) - 'a'));
}
return ans;
}
KassanErinn
Guest Blogger
