Questions can be found at CCC 2019 Senior
Problem S1: Flipper
Problem Formulation:
In this problem, we are asked to find the final state of a (2 x 2) grid shown in figure 1, after several vertical and horizontal flips.
We are given the initial state of the grid and a string S consists of letter H and V where H denotes a horizontal flip and V denotes a vertical flip.
Solution:
Since the grid is always 2x2, we can just follow the commands given in the string. We iterate through the string character by character. If we encounter H we swap the two rows, and if we encounter V we swap the two columns.
Pseudo Code:
Solution 1: Flipper
Data: grid ={{a11,a12},{a21,a22}}, S={s1,s2,...sn}
Result: grid
for i ←1, 2, ... ... n do
if S[i] =H then
swap(a11,a21), swap(a12,a22)
else
swap(a11,a21), swap(a21, a22)
return grid
Asymptotic big-O complexity:
Running time: O(n)
Additional space complexity: O(1)
Problem S2: Pretty Average Prime
Problem Formulation:
In this problem we are given a positive integer N >3 and N<106. We are asked to find two prime numbers A, B such that N=(A+B)/2. We have do this for T number of N’s in a single run.
Solution:
If we simplify the condition, we get A+B = 2N. There is a conjecture called Goldbach’s conjecture which tells us that every even integer greater than 2 can be expressed as the sum of two prime numbers. Therefore, for the given number N we can always find two prime numbers so that A+B=2N.
To find those two primes we need to check with all the primes under 2N. By using sieve of Eratosthenes, we can pre-calculate and store those primes, under 2*106 since N<106. Now we will iterate through the primes pi and check if 2N-pi is also a prime or not. If we keep an boolean array like isPrime[x] is true if x is a prime then we can check if 2N-pi is prime or not in O(1).
Pseudo Code:
Solution 2: Pretty Average Prime
Data: T, N={n1, n2, ... ... nt }
Result: A, B
primes[] ← Sieve()
isPrimes[] ← Sieve()
for i ← 1, 2, .... T do
for p ← primes[1,2,.....] do
if (isPrime [2ni-p] = true) then
A ← p, B← 2N-p
break
print( A, B)
Asymptotic big-O complexity:
Running time: O(max(ni) *log( log(max(ni)) +T*(max(ni ))
Additional space complexity: O(max(N))
Problem S3: Arithmetic Square
Problem Formulation:
We are provided with a 3x3 grid. Each element of the grid is either an integer number or ‘X’ denoting this element is missing. We are asked to fill in those missing elements such that each row and column of the grid is an arithmetic series. An arithmetic series is a series of numbers where the difference of two consecutive numbers is always the same.
An example is shown in figure 2.
Solution:
Here each of the arithmetic series is of length 3. Let’s say, {a, b, c} are in arithmetic series. Here each of these 3 numbers can be generated by the other 2 numbers using the following relations:
a = 2b-c
b = (a+c)/2
c = 2b-a
Since some of the elements of the grid are given, we may find all the missing elements. We can claim that, if more than 5 elements are already given, then using only those relations we can fill in the missing elements. For exactly 4 or 5 elements are given we can find the missing elements using those relations except one case where those 4 or 5 elements lie exactly in 1 row and 1 column. Two of these scenarios are shown in figure 3. For 4 element scenarios using the above relations, we convert it to 5 element scenarios.
Now let’s say row x and column y has been filled. From here, we can find the difference d for row (x+1)mod 3 and (x+2) mod 3 and fill the whole grid.
If all the elements are missing, we can fill the grid with 0 which is a valid grid.
If an only 1 element is given, then we can fill the grid with that element which is also a valid grid where the common difference for all rows and columns is zero.
For the given 3 elements we find some other elements except the case where those 3 elements will lie on individual rows and columns. An example is shown in figure 4.
For the left scenario in figure 4, we can fill the middle missing element with the fixed value from immediate left, right, up, or down. Then applying those 3 relations mentioned earlier we can fill the whole grid. For the right scenario in figure 4, we can fill the middle column or middle row with the center value. Then applying those 3 relations will fill the grid.
Another scenario with 3 elements is all the given 3 elements are on the same row or same column. In that case, we can just copy that row to other rows or that column to other columns.
Now we are left with the case of 2 fixed elements. If they are on the same row or same column then we fill that row or column and copy it to other rows or columns.
If the 2 fixed elements are in different rows and columns, then we can fill one column or one row with the same value fixed value on that row or column. To decide on fixing a row or column, we need to give priority to adjacency. To make it more clear let’s observe figure 5. For the left scenario, we fill column 1 or 2 with the fixed value of the respective column, and for the right scenario will the row 1 or 2 with the fixed value of the respective row.
Asymptotic big-O complexity:
Running time: O(c*9) c is also a constant
Additional space complexity: O(1)
<code>
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<string>> grid;
vector<vector<int>> result;
vector<pair<int, int>> fixed;
string miss = "X";
int INF = 1e9;
void Input()
{
grid = vector<vector<string>>(3, vector<string>(3, ""));
result = vector<vector<int>>(3, vector<int>(3));
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> grid[i][j];
if (grid[i][j] != miss)
{
result[i][j] = stoi(grid[i][j]);
fixed.push_back({i, j});
}
else
result[i][j] = INF;
}
}
}
bool rowFixer(int idx)
{
int &a = result[idx][0], &b = result[idx][1], &c = result[idx][2];
if (b == INF && a < INF && c < INF)
{
b = (a + c) / 2;
return true;
}
if (a == INF && b < INF && c < INF)
{
a = 2 * b - c;
return true;
}
if (c == INF && a < INF && b < INF)
{
c = 2 * b - a;
return true;
}
return a < INF && b < INF && c < INF && a - b == b - c;
}
bool colFixer(int idx)
{
int &a = result[0][idx], &b = result[1][idx], &c = result[2][idx];
if (b == INF && a < INF && c < INF)
{
b = (a + c) / 2;
return true;
}
if (a == INF && b < INF && c < INF)
{
a = 2 * b - c;
return true;
}
if (c == INF && a < INF && b < INF)
{
c = 2 * b - a;
return true;
}
return a < INF && b < INF && c < INF && a - b == b - c;
}
bool fix()
{
set<int> colFixed, rowFixed;
for (int i = 0; i < 9; i++)
{
for (int it = 0; it < 3; it++)
{
if (rowFixer(it))
rowFixed.insert(it);
if (colFixer(it))
colFixed.insert(it);
}
}
if (colFixed.size() == 3 || rowFixed.size() == 3)
return true;
return false;
}
bool run()
{
if (fix())
{
return print();
}
if (fixed.size() == 0 || fixed.size() == 1)
{
int d = (fixed.size() == 1 ? result[fixed[0].first][fixed[0].second] : 0);
result[0][0] = d, result[0][2] = d, result[2][0] = d, result[2][2] = d;
fix();
return print();
}
if (fixed.size() == 2)
{
int x0 = fixed[0].first, y0 = fixed[0].second, x1 = fixed[1].first, y1 = fixed[1].second;
if (x0 != x1 && y0 != y1)
{
if (abs(x0 - x1) < abs(y0 - y1))
{
result[x0][(y0 + 1) % 3] = result[x0][y0], result[x0][(y0 + 2) % 3] = result[x0][y0];
result[x1][(y1 + 1) % 3] = result[x1][y1], result[x1][(y1 + 2) % 3] = result[x1][y1];
}
else
{
result[(x0 + 1) % 3][y0] = result[x0][y0], result[(x0 + 2) % 3][y0] = result[x0][y0];
result[(x1 + 1) % 3][y1] = result[x1][y1], result[(x1 + 2) % 3][y1] = result[x1][y1];
}
}
else
{
for (int i = 0; i < 3; i++)
{
if (rowFixer(i))
{
result[(i + 1) % 3] = result[i];
result[(i + 2) % 3] = result[i];
break;
}
if (colFixer(i))
{
for (int j = 0; j < 3; j++)
result[j][(i + 1) % 3] = result[j][i], result[j][(i + 2) % 3] = result[j][i];
break;
}
}
}
assert(fix());
return print();
}
if (fixed.size() == 3)
{
int x0 = fixed[0].first, y0 = fixed[0].second;
int x1 = fixed[1].first, y1 = fixed[1].second;
int x2 = fixed[2].first, y2 = fixed[2].second;
if (x0 != x1 && x1 != x2 && x2 != x0 && y0 != y1 && y1 != y2 && y2 != y0)
{
if (result[1][1] < INF)
result[1][0] = result[1][1];
else if (result[0][1] < INF)
result[1][1] = result[0][1];
else if (result[1][0] < INF)
result[1][1] = result[1][0];
else if (result[2][1] < INF)
result[1][1] = result[2][1];
else if (result[1][2] < INF)
result[1][1] = result[1][2];
fix();
return print();
}
else if ((x0 == x1 && x1 == x2) || (y0 == y1 && y1 == y2))
{
for (int i = 0; i < 3; i++)
{
if (rowFixer(i))
{
result[(i + 1) % 3] = result[i];
result[(i + 2) % 3] = result[i];
break;
}
if (colFixer(i))
{
for (int j = 0; j < 3; j++)
result[j][(i + 1) % 3] = result[j][i], result[j][(i + 2) % 3] = result[j][i];
break;
}
}
}
if (fix())
{
return print();
}
}
for (int i = 0; i < 3; i++)
{
set<int> col, row;
for (int j = 0; j < 3; j++)
{
if (rowFixer(j))
row.insert(j);
if (colFixer(j))
col.insert(j);
}
assert(col.size() == 1 && row.size() == 1);
if (rowFixer(i))
{
for (int j = 0; j < 3; j++)
{
if (result[(i + 1) % 3][j] < INF)
{
int d = result[i][j] - result[(i + 1) % 3][j];
result[(i + 1) % 3][(j + 1) % 3] = result[i][(j + 1) % 3] - d;
assert(fix());
return print();
}
if (result[(i + 2) % 3][j] < INF)
{
int d = result[i][j] - result[(i + 2) % 3][j];
result[(i + 2) % 3][(j + 1) % 3] = result[i][(j + 1) % 3] - d;
assert(fix());
return print();
}
}
}
}
return false;
}
bool print()
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
cout << result[i][j] << ' ';
cout << endl;
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (grid[i][j] != miss)
assert(stoi(grid[i][j]) == result[i][j]);
assert(result[i][j] < INF && result[i][j] > -INF);
}
}
return true;
}
};
int main()
{
Solution sol;
sol.Input();
assert(sol.run());
return 0;
}
</code>
Problem S4: Tourism
Problem Formulation:
In this problem, an array A of N integers and an integer K are given. We must segmentize the array in exactly ceiling(N/K) non-overlapping segments where each segment can have at most k integers. The segmentation should be in such a way that the sum of maximum integer from every segment is maximized. It will be clear if we observe figure 5.
Solution:
Here we can see, if N≡0(mod)k then all the segment size should be exactly k. Otherwise, minimum length of a segment can be r=N mod k i.e the reminder of N after dividing it by k.
Now we can formulate a dynamic programming approach to find the maximum sum of maximums of each segment. Let’s say DP[i] denotes the maximum sum by dividing the first i numbers into ceiling(i/k) segments. Then
for p = k-r, p>r, p-=1
DP[d*k+j]=max(DP[d*k+j-p]+max(A[d*k+j-p+1,...d*k+j))
d = 1, 2,3 ... floor(n/k) and j=r, r+1, .... k
We are claiming that starting from d*
The run time complexity of this approach is O(Nk), by using sparse table to find the range maximums. But this runs time will not pass the time limit. We need to make it around at least O(nlogn). Let's see a simulation in figure 6. Here DP[1,..3] = prefix max. using this segment, we update next segment of size k. Since N=11 and k=3 so r = N mod k = 2, the minimum segment size is 2. That's why no segment of size less than r can start at index 4. So, we don’t need to update that position. DP[5] = max(DP[2]+ max(A[3,4,5]), DP[3]+max(A[4,5])
DP[6] = DP[3]+max(A[4,5,6]). Using this segment, we update the next segment of size k. This way DP[N] is updated and that’s the result. In figure 6, the maximum value of DP[N=11] = 41. So result is 41 in this case.
The run time complexity of this approach is O(Nk) as already mentioned. To optimize it we use the observation that we update the next segment based on the previous segment DP values. So, we can always pre-calculate the values.
Now max(A[d*k+j-p+1,...d*k+j)) can be broken in two parts,
A[d*k+j-p,.... d*k] which is in the previous segment and A[d*k+1,... d*k+j]
which is in the next segment. So, we can write DP[d*k+j]=max(max(A[d*k+j-p,...d*k]+DP[d*k+j-p]),
max(A[d*k+1,..d*k+j])+DP[d*k+j-p]))
For max(A[d*k+1,..d*k+j]) we pre-calculate prefix max.
For max(A[d*k+j-p,...d*k]+DP[d*k+j-p] we pre-calculate suffix max.
It will be clearer if you see the C++ code implementation.
Pseudo Code:
Solution 4: Tourism
Data: n, k, A ={a1, a2, a3, ... an}
Result: maxSum
DP[1,...N] = {}
prefixMax[1..N]={}
sufixMax[1....N]={}
sufixSumMax[1....N]={}
sufixDPMax[1....N]={}
minSegSize = N mod k
for i ←{1,2, ...., k} do
prefixMax[i]=max(A[i], prefixMax[i-1])
DP[i]=prefixMax[i]
for i← {k, k-1, ... 1} do
sufixmax[i] = max(sufixmax[i+1], A[i])
sufixDPMax[i] = max(sfixDPMax[i+1], DP[i])
sufixSumMax[i] = max(sufixMax[i]+DP[i-1], sufixSumMax[i+1])
for d ←{2,.... N/k} do
for i ←{k*d+1,.... k*d+k-1} do
prefixMax[i]=max(A[i], prefixMax[i-1])
for i← {k*(d+1), .... k*d+1} do
sufixmax[i] = max(sufixmax[i+1], A[i])
it = k*(d-1)+minSegSize
for j ←{it+1, ...., k*d} do
DP[j]=max(prefixMax[j]+sufixDPMax[it], sufixSumMax[it+1])
it +=1 if (j-it==k) else 0
for i← {k*(d+1), .... k*d+1} do
sufixDPMax[i] = max(sufixDPMax[i+1], DP[i])
sufixSumMax[i] = max(sufixMax[i]+DP[i-1], sufixSumMax[i+1])
maxSum =DP[N]
Asymptotic big-O complexity:
Running time: O(N)
Additional space complexity: O(N)
<code>
#include <bits/stdc++.h>
using namespace std;
void Solution()
{
int N, K;
cin >> N >> K;
vector<int> atr(N);
for (int i = 0; i < N; i++)
cin >> atr[i];
int day = (N + K - 1) / K;
int minVisit = N % K;
if (minVisit == 0)
minVisit = K;
vector<int> prefixMax(N, 0), suffixMax(N, 0);
vector<long long> DP(N, 0), revDpMax(N, 0), revSumMax(N, 0);
for (int i = 0; i < K; i++)
{
if (i > 0)
prefixMax[i] = max(prefixMax[i - 1], atr[i]);
else
prefixMax[i] = atr[i];
DP[i] = prefixMax[i];
}
for (int i = K - 1; i >= 0; i--)
{
if (i < K - 1)
suffixMax[i] = max(suffixMax[i + 1], atr[i]);
else
suffixMax[i] = atr[i];
revSumMax[i] = max(suffixMax[i] + (i > 0 ? DP[i - 1] : 0), (i < K - 1 ? revSumMax[i + 1] : 0));
revDpMax[i] = max(DP[i], (i < K - 1 ? revDpMax[i + 1] : 0));
}
for (int d = 1; d < day; d++)
{
for (int i = K * d; i < min(N, K * (d + 1)); i++)
{
if (i > K * d)
prefixMax[i] = max(prefixMax[i - 1], atr[i]);
else
prefixMax[i] = atr[i];
}
for (int i = min(N, K * (d + 1)) - 1; i >= K * d; i--)
{
if (i < min(N, K * (d + 1)) - 1)
suffixMax[i] = max(suffixMax[i + 1], atr[i]);
else
suffixMax[i] = atr[i];
}
int it = K * (d - 1) + minVisit - 1;
for (int i = it + K; i - it <= K && it < K * d && i < N; i++)
{
DP[i] = max(prefixMax[i] + revDpMax[it], revSumMax[it + 1]);
it += (i - it == K);
}
for (int i = min(N, K * (d + 1)) - 1; i >= K * d; i--)
{
revSumMax[i] = max(suffixMax[i] + (i > 0 ? DP[i - 1] : 0), (i < min(N, K * (d + 1)) - 1 ? revSumMax[i + 1] : 0));
revDpMax[i] = max(DP[i], (i < min(N, K * (d + 1)) - 1 ? revDpMax[i + 1] : 0));
}
}
cout << DP[N - 1] << endl;
}
int main()
{
Solution();
return 0;
}
</code>
Problem S5: Triangle: The Data Structure
Problem Formulation:
In this problem we are provided with M*(M+1)/2 integers in triangular shape and another integer K denoting a query for K sized triangle. A triangle of size M consists of M rows, with the ith row containing i elements. An example is shown in figure 7. We are asked to find the sum of maximum numbers for every K sized triangle in the given triangle.
Solution:
In figure 7, the given triangle size is M=4. If K = 2, then we have (M-K+1)*(M-K+2)/2=6 number of K=2 sized triangles. We must find the maximum value of each K=2 sized triangle and print the sum of those maximum values. The possible 6 triangles are shown in figure 8.
To solve this problem, we can use the Dynamic programming approach. From figure 9, we can see each l sized triangle is consisting of 3, l-1 sized triangles. So, we have some overlapping sub-problems. But this approach will cause O(M2K) runtime complexity because we must know all the max values of every triangle with size 1, 2, ... K.
To optimize we have an observation that is every number of a triangle with l size can be covered with 3 overlapping triangles of 2*l/3 size from 3 corners of the l sized triangle.
An example is shown in figure 9. So instead of searching every triangle of size 1, 2, ... K we recursively compute for log1.5(k) numbers of triangles to find the max of a triangle with size K. But this will also cause O(M2log1.5(k)) extra memory. We can remove this extra memory overhead by doing iterative dynamic programming. Let’s define DP[i][j] keeps the maximum of a triangle whose top is at (i,j) position i.e ith row jth column when we calculate for triangles of size l.
For the base case (l=1) DP[i][j] = grid[i][j] where grid[][] is the given large triangle.
To find the maximum of triangles of size K , we repeatedly find the sub-triangle size by K = 2*K/3 and store them then ascending order in an array Ks[].
Now we iterate the array Ks and on each iteration, we update all DP[i][j] for the current size of triangles. The formula looks like this:
DP[i][j] = max(DP[i][j], DP[i+s][j], DP[i+s][j+s])
Where s = currentTriangleSize - previsousTriangleSize
When we know the maximums of each triangle of size K we simply take the sum.
Pseudo Code:
Solution 5: Tourism
Data: M, K, grid ={{a11}, {a21, a22}, ... {an1,an2,..ann}}
Result: maxSum
DP[][] ←{{0},...{0,0,...0}}
Ks ←{}
tempK ← K
while tempK>1 do
Ks.append(K)
tempK = 2*tempK/3
Ks.append(1)
reverse(Ks)
for it ← {2,3,.... len(Ks)} do
s = Ks[i]-Ks[i-1]
for i ←{1,2,3..... M-K+1} do
for j ← {1,2,..... i} do
DP[i][j] = max(DP[i][j], DP[i+s][j], DP[i+s][j+s])
maxSum ← 0
for i ←{1,2,3..... M-K+1} do
for j ← {1,2,..... i} do
maxSum+=DP[i][j]
print(maxSum)
Asymptotic big-O complexity:
Running time: O(M2log1.5(K))
Additional space complexity: O(M2)
<code>
#include <bits/stdc++.h>
using namespace std;
int value[3000][3000];
void Solution()
{
int N, K;
cin >> N >> K;
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= i; j++)
{
cin >> value[i][j];
}
}
vector<int> ks;
ks.push_back(K);
int k = K;
while (k > 2)
{
k = (2 * k + 2) / 3;
ks.push_back(k);
}
ks.push_back(2);
ks.push_back(1);
reverse(ks.begin(), ks.end());
for (int k = 1; k < (int)ks.size() && ks[k] <= K; k++)
{
int s = ks[k] - ks[k - 1];
for (int i = 0; i + ks[k] <= N; i++)
{
for (int j = 0; j <= i; j++)
{
value[i][j] = max({value[i][j], value[i + s][j],
value[i + s][j + s]});
}
}
}
long long ans = 0;
for (int i = 0; i + K <= N; i++)
{
for (int j = 0; j <= i; j++)
ans += value[i][j];
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
Solution();
return 0;
}
</code>
.png)
