April 28, 2020 Single Round Match 782 Editorials
GoblinRabblemaster
Let’s see what happens in the first turns:
| Number of Rabblemasters | Number of Ordinary goblins | Total damage |
| 1 | 1 | 1 |
| 2 | 3 | 9 |
| 3 | 6 | 33 |
| 4 | 10 | 52 |
We keep the number of Rabblemasters and ordinary Goblins we have at each turn. Also, we keep track of the total damage.
Python code:
def totalDamage(self, T):
n_masters = 0
n_goblins = 0
damage = 0
for _ in range(T):
n_masters += 1
n_goblins += n_masters
damage += (n_masters - 1) * (n_masters + n_goblins) + n_goblins
return damage
Java code:
public long totalDamage(int T) {
long rabblemasters = 0;
long ordinary = 0;
long total_damage = 0;
for (int t=0; t<T; ++t) {
// you cast a new Goblin Rabblemaster
rabblemasters += 1;
// each Goblin Rabblemaster, including the new one,
// adds one ordinary Goblin
ordinary += rabblemasters;
// calculate the number of attacking creatures:
// all except for the new Rabblemaster
long attacking = (rabblemasters-1) + ordinary;
// add the damage dealt by Rabblemasters this turn
total_damage += (rabblemasters-1) * (2+(attacking-1));
// add the damage dealt by ordinary Goblins this turn
total_damage += ordinary;
}
return total_damage;
}
TrivialWordSearch
If the size of w is 2, there is no solution: regardless of how you fill the grid, there will be always multiple occurrences of w.
If the size of w is more than 1 and all of the letters are equal, again there is no solution.
Otherwise, we have a solution. Let’s see. For example for “abc”, this works:
abc
aaa
aaa
So, we put w in the first row, fill the other cells with an arbitrary character, say the first character of w. But there can be one problem. Let’s check “aab”:
aab
aaa
aaa
To avoid this exception case, if all of the letters except the last letter is equal, we fill the other rows with the last letter instead of the first letter:
aab
bbb
bbb
The below solution uses the character with the minimum frequency.
def construct(self, s):
l = len(s)
if l == 1:
return [s]
if s == s[0] * l:
return []
if l == 2:
return [s, s[::-1]]
letter_frequencies = {}
for i in s:
letter_frequencies[i] = 0
for i in s:
letter_frequencies[i] += 1
minimum = min(letter_frequencies.values())
for key, value in letter_frequencies.items():
if value == minimum:
to_use = key
break
if not to_use:
return []
return [s] + [to_use * l] * (l-1)
Another solution
public String[] construct(String w) {
String[] answer = new String[w.length()];
answer[0] = w;
if (w.length() == 1) return answer;
for (int i=0; i<w.length(); ++i) {
char fill = w.charAt(i);
for (int r=1; r<w.length(); ++r) {
answer[r] = "";
for (int j=0; j<w.length(); ++j) answer[r] += fill;
}
int c = countOccurrences(w,answer);
if (isPalindrome(w) && (c==1 || c==2)) return answer;
if (!isPalindrome(w) && c==1) return answer;
}
return new String[0];
}
EmptyTheBox
For penalty tokens with value > 2 * D, there is no way to delete them. Add them to the answer and set T = min(T, 2 * D).
For each 2 <= j <= 2 * D we can easily calculate the probability of the number we rolled equals to j, call it rollprob[j].
T is so small now, we can use a simple O(3^T * D) solution. dp[tokensInBag] is what is the answer if we have only the tokens present in the tokensInBag. Iterate over all of the possible rolls and subsets that we can remove (i. e. the sum of tokens in the subset is equal to the current roll) and find the best option.
(A faster solution can be implemented by precalculating all possible subsets of tokens for each power. The limits were intentionally set low so that O(4^T * D) solutions would pass, too.)
int totalValue(int T, int subset) {
int sum = 0;
for (int t=0; t<T; ++t) if ((subset & 1<<t) != 0) sum += t+1;
return sum;
}
public double minExpectedPenalty(int D, int T) {
// handle the tokens that cannot be removed
int cannotBeRemoved = 0;
while (T > 2*D) { cannotBeRemoved += T; --T; }
// be lazy to do math and precalculate the roll probabilities
double[] rollprob = new double[2*D+1];
for (int a=1; a<=D; ++a) for (int b=1; b<=D; ++b) rollprob[a+b] += 1./(D*D);
// for each subset of remaining tokens, calculate the answer via dp
double[] dp = new double[1<<T];
for (int tokensInBag=0; tokensInBag<(1<<T); ++tokensInBag) {
// iterate over all possible outcomes of the roll
for (int roll=2; roll<=2*D; ++roll) {
// iterate over all sets of tokens we can take and pick the best
// this can be heavily optimized by pre-sorting the subsets into groups by sum
// but constraints are such that you don't have to do that
double best = totalValue(T,tokensInBag);
for (int subset=1; subset<(1<<T); ++subset) {
if ((tokensInBag & subset) == subset) if (totalValue(T,subset) == roll) best = Math.min( best, dp[tokensInBag ^ subset] );
}
dp[tokensInBag] += rollprob[roll] * best;
}
}
Python code:
def minExpectedPenalty(self, D, T):
excess = 0
for x in xrange(2*D + 1, T+1):
excess += x
masks = {0:{0}, 1:{1}}
for roll in xrange(2, 2*D+1):
row = set()
for take in xrange(1, 1 + roll):
for p in masks[roll - take]:
if not(p & (1 << (take-1))):
row.add(p ^ (1 << (take-1)))
masks[roll] = row
# do dp
N = min(2 * D, T)
dp = [0] * (1 << N)
for state in xrange(1 << N):
text = bin(state)[2:]
for i in xrange(len(text)):
if text[~i] == '1':
dp[state] += i + 1
for state in xrange(1 << N):
eq = 0
for roll in xrange(2, 2*D + 1):
# roll D+1 occurs numerator D
# roll 2 occurs numerator 1
numer = D - abs(D+1 - roll)
odds = numer / float(D*D)
bns = float('inf')
# Lets try to remove sum of roll
for mask in masks[roll]:
if mask & state == mask:
state2 = state ^ mask
cand = dp[state2]
if cand < bns:
bns = cand
if bns == float('inf'):
bns = dp[state]
eq += odds * bns
dp[state] = min(dp[state], eq)
return dp[-1] + excess
RankingStudents
Ignore the second rule. The problem becomes simple. Sort vertices by f and check if it satisfies.
Merging the first and second rule leads to: “for each valid i, f[a[i]] < f[b[i]]”.
So, let’s relax the values of f[]. That is, reach a stable state where the above condition holds. For n times we will do the following:
for(int j = 0; j < a.length; j++)
f[a[j]] = Integer.min(f[a[j]], f[b[j]] - 1);
If the graph has a cycle the answer is -1, f[] can’t be relaxed ever. Otherwise, we reach a stable state. We can do this part in O(n) instead of O(n^2) using topological sort.
Now, if we sort the vertices by increasing the value of (the new) f, the first rule will be satisfied too. Now, check if the first rule is satisfied.
public String rankingPossible(int n, int [] f, int [] a, int [] b){
int [] g = f.clone();
for(int i = 0; i < n; i++){
for(int j = 0; j < a.length; j++) f[a[j]] = Integer.min(f[a[j]], f[b[j]] - 1);
}
int [] h = f.clone();
for(int j = 0; j < a.length; j++) f[a[j]] = Integer.min(f[a[j]], f[b[j]] - 1);
for(int j = 0; j < n; j++) if(f[j] != h[j]) return "Impossible"; // Negative cycle
ArrayList<Long> toSort = new ArrayList<>();
for(int i = 0; i < n; i++){
long x = (1 << 30) + f[i];
toSort.add((x << 20) + i);
}
Collections.sort(toSort);
int [] where = new int[n];
for(int i = 0; i < n; i++){
int student = (int)(toSort.get(i) & ((1L << 20) - 1));
where[student] = i;
if(i > g[student]) return "Impossible";
}
return "Possible";
}
PaintItBlack
Consider we have no odd cycle. The graph is bipartite. Consider u be in the first part. In the first move, we change the color of a vertex in the second part. In the second move, we change the color of a vertex in the first part. So, if n is odd, it’s impossible to find such a walk.
Consider n is even, we can always find such a walk. Find a spanning tree. Start from the root. For each vertex like v, when you entered the vertex start from the first child. For each child like u, add u to the answer. Then, call the function on u. In the end, if the size of the subtree of u is odd, u will be black, white otherwise. If it’s white, add v to the answer and u to the answer again. Anyway, go up to the v (add v to the answer).
After all, the root will be black. You can prove with complete (strong) induction that if we call the function on the root of a tree with an odd number of vertices remains white (while others are black) and if we call the function on the root of a tree with an even number of vertices all of the tree become black.
Now, what about when n is odd and we have an odd cycle? Consider a cycle of length 3. Vertex 1 is white and others black. We want to make all black. We are currently at 1.
This is the sequence we will traverse: 2, 1, 2, 3, 1, 3, 1. As you see, all of the vertices are black after that.
For a cycle of length n: 2, 1, 2, 3, 4, 3, 4, 5, 4, 5, …, n – 1, n, 1, n, 1.
This way we can change the color of a single vertex without changing the color of other vertices.
So, if there is an odd cycle and n is odd, once we reach a vertex in the mentioned cycle we change the color of it (using the process above) and then continue. The color of the root will change after the process finishes.
Note that the first part costs at most 3n moves and the second part costs at most 2n moves. For calculating the cost of the first part, note that we see each edge going to a vertex with an odd number of vertices in it two times. We see each edge going to a vertex with an even number of vertices in it four times. The upper bound of the number of vertices with even size of subtree is n / 2.
Here is the implementation:
boolean odd;
int [] par;
boolean [][] adj;
int [] vis;
int [] color;
ArrayList<Integer> walk;
public PaintItBlack(){
}
public void init(int n){
odd = false;
par = new int[n];
adj = new boolean[n][n];
vis = new int[n];
color = new int[n];
walk = new ArrayList<>();
}
public void dfs(int s, int p, int n, int col){
vis[s] = col;
par[s] = p;
for(int v = 0; v < n; v++) if(adj[s][v] && v != p){
if(vis[v] == 0){
walk.add(v);
color[v] ^= 1;
dfs(v, s, n, 3 - col);
} else if(vis[v] == vis[s] && n % 2 == 1 && !odd){
odd = true;
int curr = par[s];
while(curr != v){
walk.add(curr);
color[curr] ^= 1;
curr = par[curr];
}
walk.add(v); walk.add(s);
color[v] ^= 1; color[s] ^= 1;
}
}
if(p != -1){
if(color[s] == 0){
walk.add(p);
walk.add(s);
color[s] ^= 1;
color[p] ^= 1;
}
walk.add(p);
color[p] ^= 1;
}
}
public int[] findWalk(int n, int u, int [] a, int [] b){
init(n);
for(int i = 0; i < a.length; i++) adj[a[i]][b[i]] = adj[b[i]][a[i]] = true;
walk.add(u);
dfs(u, -1, n, 1);
if(color[u] == 1){
int[] ret = new int[walk.size()];
for(int i = 0; i < walk.size(); i++) ret[i] = walk.get(i);
return ret;
}
return new int[0];
}
Guest Blogger
