April 9, 2022 Single Round Match 827 Editorials
HouseOfCards
This problem is about noticing patterns and counting them quickly.
If the bottom floor has N blocks of cards, there will be a total of N floors in the pyramid. From bottom to top, these will contain N, N-1, N-2, …, 3, 2, 1 blocks. As N <= 10^5, we can afford to iterate over all floors and count the number of cards on each of them separately.
Additionally, there’s a row of horizontal cards between each pair of consecutive floors. The longest of these has N-1 cards, the next one has N-2, and so on all the way down to 1. We can count these using another cycle – or using the same cycle as above, but skipping the first iteration.
We can also solve the problem for much larger values of N than the statement required. The extra step we need for that is to realize that we are summing up a very simple arithmetic sequence, and so we can replace the for-cycle with a closed-form formula for the sum of the sequence. The resulting formula for the number of cards in an N-story house of cards is 2*N + 3*N*(N-1)/2.
public long count(int N) {
long answer = 0;
for (int n=1; n<N; ++n) {
answer += 2*n; // blocks on floor n, counting from the top
answer += n; // horizontal cards below them
}
answer += 2*N; // blocks on the bottom floor
return answer;
}
ContestTraining
If we have integer variables that are large enough, there is a more convenient solution than the one described below. This solution is included at the very end of this problem’s analysis. But before we get there, we’ll show how to solve the problem using just 64-bit integer variables.
For any D we can compute the number of problems T(D) Ela will solve during the first D days. This can be done in constant time as follows:
- Ela’s schedule is periodic with period heavyDays + lightDays.
- Thus, D days contain F = (D div (heavyDays + lightDays)) full periods and then E = (D modulo (heavyDays + lightDays)) extra days.
- Each full period contains heavyDays heavy and lightDays light days.
- If E <= heavyDays, all E extra days are heavy. Otherwise, there are heavyDays heavy and (E-heavyDays) light days among the extra days.
- Now we know the total number HD of heavy days and the total number LD of light days among the first D days.
- The total number of problems solved is therefore HD * heavyProblems + LD * lightProblems.
Once we have a function that counts the total number T(D) of problems solved for a given D, we can answer each query efficiently using binary search: the answer is the smallest x such that T(x) is greater or equal to the query.
In languages that have integer variables with fixed ranges we need to be a bit careful so that we don’t run into an integer overflow. But this isn’t hard to do. The only thing we can do wrong is starting the binary search with an upper bound that is too large, which will cause the value computed by T() to overflow.
We can get rid of this problem by determining the upper bound for the search dynamically: by repeatedly doubling it. Initially we will start with lo=0. We know that in lo=0 days Ela has solved 0 problems, which is strictly less than our query. We now need to find some value hi such that T(hi) >= our query. We will do this by looking at hi=1, hi=2, hi=4, hi=8, and so on.
Whenever we double the value hi, the value T(hi) will at most double. This is because the interval of 2*hi days can be broken into the first hi days and the second hi days. In the first hi days Ela will solve exactly T(hi) problems, in the next hi days she will solve at most T(hi) problems, so in total T(2*hi) <= 2*T(hi). Hence, the first time we’ll get a value that is >= our query, the value will be less than twice our query, which is still small enough to not cause an overflow.
(The reason why the second block of hi days contains at most as many problems as the first block is that the first block starts with heavy days and thus it contains as many heavy days as possible.)
long countProblems(long heavyDays, long lightDays,
long heavyProblems, long lightProblems,
long totalDays)
{
long fullBlocks = totalDays / (heavyDays + lightDays);
long lastBlock = totalDays % (heavyDays + lightDays);
long seenHeavyDays = heavyDays * fullBlocks;
long seenLightDays = lightDays * fullBlocks;
if (lastBlock <= heavyDays) {
seenHeavyDays += lastBlock;
} else {
seenHeavyDays += heavyDays;
seenLightDays += lastBlock - heavyDays;
}
return seenHeavyDays * heavyProblems + seenLightDays * lightProblems;
}
public long solve1(long heavyDays, long lightDays,
long heavyProblems, long lightProblems,
long query)
{
long lo = 0, hi = 1;
while (true) {
long probs = countProblems(heavyDays, lightDays,
heavyProblems, lightProblems, hi);
if (probs >= query) break;
hi *= 2;
}
while (hi - lo > 1) {
long med = (hi + lo) / 2;
long probs = countProblems(heavyDays, lightDays,
heavyProblems, lightProblems, med);
if (probs >= query) hi = med; else lo = med;
}
return hi;
}
public long[] practice(long heavyDays, long lightDays,
long heavyProblems, long lightProblems,
long[] queries)
{
long[] answer = new long[queries.length];
for (int q=0; q<queries.length; ++q) {
answer[q] = solve1(heavyDays, lightDays,
heavyProblems, lightProblems, queries[q]);
}
return answer;
}
The problem is also solvable more conveniently if we can use bigger integers. (In C++ it is sufficient to use 128-bit integer variables such as __int128_t, in Java we can use BigInteger, and Python handles it natively.) We can compute the total number of tasks in one period, divide the query by that amount to find out the number of full periods, and if there is any remainder, we can then do the same for heavy days and then light days. (The existence of this approach is what made the problem only worth 200 points in div1.)
Finally, it is also possible to implement this alternate solution completely in 64-bit integers, we just need to add some extra overflow checks. (“If we can tell that the number of problems solved in one period overflows, there are no full periods.” and so on.)
CoinFlipping
The final state of any cell is determined by its initial state and the total number of times it has been flipped. If the cell is empty, it will remain empty. If it has a coin and the total number of flips was even, the coin will be in the same state as in the beginning. And if the total number of flips is odd, the coin will be showing its opposite side.
Thus, the order in which we make the flips does not matter, only the number of flips of each row/column matters. Additionally, we see that flipping the same row/column twice has no effect at all: the second flip negates the first one. Thus, we can produce any reachable configuration by flipping each row and each column at most once.
There are at most 12 rows, so there are at most 2^12 = 4096 different options which rows to flip and which ones to leave unflipped. We can iterate over all these options and consider each of them separately.
Once we decided which rows to flip, the only decision left is to decide which columns to flip. And here comes the main observation of this solution: at this point, the columns are completely independent – flipping or not flipping one of them doesn’t change the others. So, for each column separately we can simply compute its current number H of heads and the current number T of tails it contains. (Note that “current” means “after we flipped the subset of rows we are currently examining”. I.e., these numbers depend on which rows have been flipped.)
If a column has H >= T, the better-or-equal option is to leave this column as is and take the heads it currently contains. If T > H, we should flip the column to turn the tails into heads and vice versa.
This gives us a solution that runs in O(2^R * R * C): plenty fast for the given constraints.
public int mostHeads(String[] layout) {
int R = layout.length, C = layout[0].length();
char[][] board = new char[R][C];
for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
board[r][c] = layout[r].charAt(c);
}
int answer = 0;
for (int flipRows=0; flipRows<(1<<R); ++flipRows) {
int current = 0;
for (int c=0; c<C; ++c) {
int heads = 0, tails = 0;
for (int r=0; r<R; ++r) {
if (board[r][c] == '.') continue;
boolean isHeads = (board[r][c] == 'H');
if ((flipRows & 1<<r) != 0) isHeads = !isHeads;
if (isHeads) ++heads; else ++tails;
}
current += Math.max( heads, tails );
}
answer = Math.max( answer, current );
}
return answer;
}
CoinFlipping2
Division 1 got to solve a somewhat harder version of the same coin-flipping problem. The first three paragraphs of the analysis of the previous problem still apply, so we’ll just copy them here. Feel free to skip them if you just read the previous solution.
The final state of any cell is determined by its initial state and the total number of times it has been flipped. If the cell is empty, it will remain empty. If it has a coin and the total number of flips was even, the coin will be in the same state as in the beginning. And if the total number of flips is odd, the coin will be showing its opposite side.
Thus, the order in which we make the flips does not matter, only the number of flips of each row/column matters. Additionally, we see that flipping the same row/column twice has no effect at all: the second flip negates the first one. Thus, we can produce any reachable configuration by flipping each row and each column at most once.
There are at most 12 rows, so there are at most 2^12 = 4096 different options which rows to flip and which ones to leave unflipped. We can iterate over all these options and consider each of them separately.
New content starts here:
Once we decided which rows to flip, the only decision left is to decide which columns to flip. And here comes the main observation of this solution: at this point, the columns are completely independent – flipping or not flipping one of them doesn’t change the others. The question is whether we can do these flips in a way that will leave us with exactly the desired total number of heads.
We can solve this question efficiently by looking at it as a subset-sum-style problem. Remember that we already fixed which rows to flip. Given that those flips have been made, we can look at each column c and compute the numbers heads and tails of the heads and tails it currently contains. If we leave this column as is, it will contribute heads heads to the total. If we flip it, it will contribute tails heads instead.
We can now iterate over all columns from left to right and for each c we can compute the set of all totals of heads that can be produced from the first c columns. For c=0 we can only have 0 heads. When we add another column, we take all previous totals and add heads and tails to each of them to get the new totals. Note that all these totals are small: the maximum number of heads in c columns is just R*c.
Once we have processed all columns, we know whether the desired total is reachable. If it is, we can reconstruct one set of column flips that produces it simply by going backwards: if the last column where we haven’t made a decision yet is column c and we need X heads from the undecided columns, we take a look whether X-heads heads can be produced from the first c-1 columns. If yes, we can leave column c as is and look for X-heads heads from the previous columns, if not, we must flip it and look for X-tails more heads.
A single run of the dynamic programming takes O(RC^2) time: the slowest part is the actual DP where we C times iterate over a set of O(RC) values. Thus, the full solution runs in O(2^R * R * C^2) time.
int[] IMPOSSIBLE;
char flipped(char c) { return c=='H' ? 'T' : (c == 'T' ? 'H' : '.'); }
int[] flatten(ArrayList<Integer> data) {
int[] answer = new int[data.size()];
int i = 0;
for (int x : data) answer[i++] = x;
return answer;
}
int[] dp(int[] heads, int[] tails, int desiredCount) {
int N = heads.length;
boolean[][] possible = new boolean[N+1][12*N+1];
possible[0][0] = true;
for (int n=0; n<N; ++n) {
for (int x=0; x<=12*n; ++x) {
if (possible[n][x]) {
possible[n+1][x+heads[n]] = true;
possible[n+1][x+tails[n]] = true;
}
}
}
if (!possible[N][desiredCount]) return IMPOSSIBLE;
ArrayList<Integer> toggle = new ArrayList<Integer>();
int remains = desiredCount;
for (int n=N-1; n>=0; --n) {
if (remains >= heads[n] && possible[n][remains - heads[n]]) {
remains -= heads[n];
} else {
toggle.add(n);
remains -= tails[n];
}
}
return flatten(toggle);
}
public int[] correctHeads(String[] layout, int desiredCount) {
int R = layout.length, C = layout[0].length();
char[][] board = new char[R][C];
for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
board[r][c] = layout[r].charAt(c);
}
int[] heads = new int[C];
int[] tails = new int[C];
IMPOSSIBLE = new int[] {-1};
for (int flipRows=0; flipRows<(1<<R); ++flipRows) {
for (int c=0; c<C; ++c) {
heads[c] = 0;
tails[c] = 0;
for (int r=0; r<R; ++r) {
if (board[r][c] == '.') continue;
boolean isHeads = (board[r][c] == 'H');
if ((flipRows & 1<<r) != 0) isHeads = !isHeads;
if (isHeads) ++heads[c]; else ++tails[c];
}
}
int[] columnSolution = dp(heads, tails, desiredCount);
if (Arrays.equals(columnSolution, IMPOSSIBLE)) continue;
ArrayList<Integer> answer = new ArrayList<Integer>();
for (int r=0; r<R; ++r) if ((flipRows & 1<<r) != 0) answer.add(r);
for (int c : columnSolution) answer.add( R+c );
return flatten(answer);
}
return IMPOSSIBLE;
}
RainbowConnection
We present a solution with an implementation that doesn’t need any “heavy artillery”. But in order to get this simple implementation, we are going to have to make some observations about the mathematical properties of the process we are simulating.
If we assign the values 1, 2, 3, 4, 5, 6, 0 to the seven colors of the rainbow (in ROYGBIV order), we see that the kids are just counting in base-7. In each step each kid looks at its left neighbor and adds their value to its own.
Let’s denote the value after i steps for kid j as x[i][j].
Ignoring all “modulo N” for indices and “modulo 7” for the actual values, we can write that:
- x[1][j] = x[0][j] + x[0][j-1]
- x[2][j] = x[1][j] + x[1][j-1] = ( x[0][j] + x[0][j-1] ) + ( x[0][j-1] + x[0][j-2] ) = 1*x[0][j] + 2*x[0][j-1] + 1*x[0][j-2]
- x[3][j] = 1*x[0][j] + 3*x[0][j-1] + 3*x[0][j-2] + x[0][j-3]
- in general, x[i][j] = sum of choose(i,k) * x[0][j-k] over k=0..i
In general, this tells us that the final values can be computed by cyclically summing up the initial values weighted by appropriate binomial coefficients. This observation on its own is way too slow, but it will soon become very useful.
Remember that we just need to compute the values x[i][j] modulo 7. What happens when i is a power of 7?
If i is a power of 7, almost all binomial coefficients choose(i,k) are divisible by 7, hence we can treat them as zeros. The only one or two non-zero coefficients are choose(i,0) = choose(i,i) = 1.
(For i=1 this is obvious, for i=7 this follows from 7 itself being prime, and for i=7^k for k>1 it follows for example from Lucas’s theorem.)
Thus, for any situation and any k>=0 we can efficiently compute the new situation we’ll see after 7^k steps: x[7^k][j] = x[0][j] + x[0][j-7^k].
This allows us to simulate the entire process in O(N*log S) time by breaking it into O(log S) blocks of steps, each being 7^k steps long for some k.
public int[] paint(String C, long S) {
int N = C.length();
int[] color = new int[N];
for (int n=0; n<N; ++n) {
color[n] = (1 + ("ROYGBIV".indexOf( C.charAt(n) ))) % 7;
}
long stepSize = 1;
while (S > 0) {
while (S % 7 != 0) {
int[] newColor = new int[N];
int delta = (int)((-stepSize) % N);
for (int n=0; n<N; ++n) {
newColor[n] = color[n];
newColor[n] += color[ (n+N+delta)%N ];
newColor[n] %= 7;
}
color = newColor;
S -= 1;
}
S /= 7;
stepSize *= 7;
}
int[] answer = new int[7];
for (int x : color) { --x; if (x == -1) x = 6; ++answer[x]; }
return answer;
}
misof
