Malaysian Computing Olympiad 2022
Solution Presentation
Totally Fair Split
Idea by: Jun Xing
Prepared by: Jun Xing
Abridged Problem Statement
Given N numbers, flip the sign of at most one element such that the sum of the largest N / 2 elements is maximized.
Subtask 1-3
Flip the sign of each number, sort the array, and take the sum of the largest n/2. Subtask 1 - 3 only differs by your implementation. e.g. are you using O(N2) to sort instead of O(N log N)?
Subtask 4: |a_i| <= 50
The number of distinct a_i’s are small, instead of flipping through each of them and test, you only need to try to flip the distinct a_i’s.
Subtask 5-6:
Observation: Just flip the smallest number! It doesn’t matter if the smallest number is positive or not.
If it is positive, it will never make it to the largest n/2 numbers to begin with because it means all numbers are positive.
If it is negative, then it is obviously better to flip the smallest negative number instead of a larger one (if -x < -y, x > y)
So that’s all: flip the smallest number (which can be found with a sort), then sort it and sum the largest N/2 number. O(N log N)
Subtask 6 is just to catch if you are aware of C++ integer type limitation.
Subtask 5-6:
You can still try flipping every number, but calculate the difference the flip makes instead of summing over n/2 numbers.
Sort the array such that a[i] is the i-th smallest number (1-indexed).
First, calculate the answer if Evirir doesn’t flip any sign, let it be ans. Call the first and second halves of the sorted array P1 and P2 respectively. Suppose we flip x. Then:
x is in P1 if x <= a[n/2].
(If there are multiple numbers equal to a[n/2] and x=a[n/2], x can be either in P1 or P2, for convenience let it be in P1)
Statistics: Totally Fair Split
Average score: 93.06
Portals
Idea by: Jun Xing
Prepared by: Shao Qian
Abridged Problem Statement
Given a weighted tree where each edge has weight 1, you can reduce an edge’s weight to 0. For each vertex i,
Or equivalently…
…you can reduce an edge’s weight by 1. For each vertex…
Subtask 1: n<=5000, the tree is a single path
Denote the path as v1->v2->...->vn
Let’s fix node vi and we are removing (vj,vj+1)
Case 1 : j>=i�Only the nodes to the right of vj are affected,each of their distances with v gets -1, thus the total reduction is n-j
�Case 2 : j<i
Only the nodes to the left of vj are affected,each of their distances with v gets -1,so the total reduction is j-1
For every node try each every edge in O(1)
Total complexity : O(n^2)
Subtask 2: The tree is a single path (line graph)
Observation : for a fixed node,the edge to be removed will always be one of the neighbouring edges�Proof : this is left to the reader as an exercise
Each node only has two or one neighbouring edges, we can use back subtask 1’s solution and try the 2 possible candidates edges for each node
Total complexity : O(n)
Subtask 3 : n<=5000
For a fixed node v, We can compute the sum of distances from v to all other nodes with a single dfs
Do one dfs with (v,u) not reduced and do another one with (v,u) reduced. the total reduction is their difference, we can try each neighbouring edge in O(n) (2 dfs’s) and take the edge that gives the best answer
For each edge it is a candidate for its two endpoint therefore each edge will do 4 dfs’s in total
Total complexity : O(n^2)
Subtask 4 : no further constraints
Lets first root the tree at node 1. Define sub(v) as the number of nodes in the subtree of v
For a fixed node v and we choose to reduce (v,u) there are two cases�Case 1 : u is a child of v�Only the nodes in the subtree of v are affected namely each of their distances with v gets -1. The total reduction is simply sub(u)
Case 2 : u = p(v)�we want the subtree size of u if the tree was instead rooted at v and this is equivalent to n-sub(v) (the number of nodes outside of subtree of v)
Precompute sub(v) for all v with one dfs then for each node try each neighbouring edge in O(1) and take the best answer�Total complexity : O(n)
Statistics: Portals
Average score: 28.33
Counting Boxes
Idea by: Wei Xin
Prepared by: Wei Xin
Abridged Problem Statement
Call a 3 * 3 subgrid a box if the surrounding eight cells are coloured black, and the center cell white.
Given a grid of size N * M, each cell is to be coloured black or white. K cells have fixed colouring of either black or white.
Consider all possible colouring of such grid (without changing the K fixed cells), what is the total number of boxes?
Abridged Problem Statement
In all subtasks, N * M <= 1010, K <= min(N * M, 105)
Subtask 1: K = N * M
Subtask 2: N * M <= 20
Subtask 3: Special pattern
Subtask 4: N * M <= 106, K = 0
Subtask 5: N * M <= 106
Subtask 6: N * M <= 1010, K = 0
Subtask 7: No additional constraints
Subtask 1: N * M = K
All cells are fixed, just need to iterate through all 3 * 3 subgrid and check if they are a box.
Note that by the constraint of K <= 105, N * M <= 105
This can be done in O(N * M)
Subtask 2: N * M <= 20
Iterate through all possible combinations of the colouring and count each of them as per subtask 1. There are no more than 220 ~= 106 possible colourings, which is not that large. O(N * M * 2N*M) should pass (though you might to optimise for constant factor)
Subtask 3: Special pattern
To recap, the patterns are as follows
The only possible 3 * 3 subgrid to form a box is the fixed left 3 * 3 subgrid, therefore each colouring only contribute one box. We just need to count the number of possible colouring. The number of uncoloured cells are
N * M - (9 + M - 3) = N * M - (M + 6)
Therefore the total number of boxes is 2N * M - (M + 6). Even with normal exponentiation this runs in O(N * M) (by the constraint of the pattern and K, this is basically O(K))
Subtask 4: N * M <= 106, K = 0 (no fixed cells)
Subtask 3 suggests that there may be some way to calculate by considering a fixed 3 * 3 subgrid.
Suppose you fix a 3 * 3 subgrid, how can this subgrid contribute to the total sum? It must be that this 3 * 3 subgrid is coloured to form a box, we do not need to care about others/they can be coloured however they want!
This is the key insight needed! For a 3 * 3 subgrid that is fixed to be a box, how many ways are there to colour the other cells? This is clearly 2(N * M) - 9 (the - 9 comes from the fixed 9 cells of the 3 * 3 subgrid, which forms a box)
Moreover, it doesn’t matter which subgrid is chosen, their contribution is the same! The answer is therefore (N - 2) * (M - 2) * 2(N * M) - 9. This can be calculated in O(N * M)
Subtask 5: N * M <= 106
Now we simply need to take care what happens if there are some fixed cells. If we think carefully about it, this is not too hard to handle.
When you consider a 3 * 3 subgrid, simply make sure that the fixed cells does not make this subgrid impossible to be a box (i.e. if the center is fixed to be black, or the side is fixed to be white).
So we simply need to iterate through all 3 * 3 subgrid and calculate how they contribute if they can be a box. Each 3 * 3 subgrid will contribute 2(N * M) - (K + 9 - C) where C is the number of originally fixed cells in that 3 * 3 subgrid. Essentially, we are fixing the cells in this subgrid in addition to the K fixed cells, though we need to take care of the overlap.
Subtask 5: N * M <= 106
Solution so far: Calculate 2(N * M) - (K + 9 - C) where C = number of originally fixed cells in the 3 * 3 subgrid.
Though if you are still naively calculating the exponentiation by simply repeatedly multiplying 2 in O(N * M) for each subgrid, you will still TLE.
One easy observation is that 0 <= C <= 9 by definition, so we can actually precompute naively 2(N * M) - (K + 9 - C) for each possible C, and when iterating subgrid, we calculate the C and just take the corresponding precomputed value.
This runs in O(N * M)
Subtask 6: N * M <= 1010, K = 0
This is the same as subtask 4, except calculating 2(N * M) naively will TLE. We need a faster way to calculate exponentiation.
Luckily this is actually a well-known problem, we can solve this with exponentiation by squaring. Essentially, realise that
ab =
(ab/2)2 , if b is even
(a(b-1)/2)2 * a, if b is odd
Therefore by calculating ab/2 or a(b-1)/2, we can easily calculate ab (just square the result and multiply by a if needed), halving the exponent each time.
With this, you can calculate ab in O(log b), translating back to our subtask 4 solution and we have a solution in O(log (N * M))
Subtask 7: No additional constraints
This is very similar to subtask 5, except the grid is so large that we cannot possible iterate through them all.
The last observation needed: most of the 3 * 3 subgrids have C = 0 (they are unaffected). In fact, each fixed cells only contribute C to the adjacent 8 3 * 3 subgrids and itself. There are only O(K) affected subgrids.
Therefore we need only iterate through the affected subgrids and calculate their answer manually (with fast exponentiation, of course). The remaining unaffected subgrids is easy to deal with. This runs in O(K * log(N * M)) or even O(K).
We are (finally) done!
Statistics: Counting Boxes
Average score: 17.92
Superpermutation
Idea by: Zi Song
Prepared by: Zi Song, Jun Xing
Problem Statement
A sequence of numbers a_{1}, a_{2}, ......, a_{n} is called a permutation of {1,2,3,...,n} if each integer from 1 to n appears exactly once in the sequence.
A sequence of numbers a_{1}, a_{2}, ..., a_{n(n+1)/2} is called a superpermutation if it can be partitioned into n contiguous blocks such that for all 1 <= i <= n, there exist a block which is a permutation of {1,2,...,i}.
Given a superpermutation a_{1}, a_{2}, ..., a_{N(N+1)/2}, find the number of ways modulo 10^9 + 7 to partition it into N contiguous blocks such that for all 1 <= i <= n, there exist a block which is a permutation of {1,2,...,i}.
�1 <= N <= 500
Subtask 1: N <= 6
Trying all possible 2^(N(N+1)/2 - 1) partitions works (you can do better, but this is enough).
For each gap between adjacent numbers, choose whether to add a line between them as a block boundary. Then check whether it is valid. O(N^2 * 2^(N(N+1)/2-1)).
1 2 3 | 2 1 | 1
1 2 | 3 | 2 | 1 1
Subtask 6: N <= 500
Fun fact: This problem was proposed long ago but originally not chosen for MCO 2022. We had another problem, but a lot of problems arose (brute force with pragmas ran much faster than intended sol).
So 4 hours before MCO, Zi Song and Jun Xing who are in the U.S. prepared this problem from scratch to replace the problem.
We had partial solutions during the problem selection process, but we mostly just spammed constraints on N for different complexities lul.
Examples of suboptimal solutions: dp[l][r][# of blocks], dp[r][# of blocks]
Other subtasks…?
Subtask 6: N <= 500
Claim: If a partition consists of only permutation blocks, then it has to be valid.
Proof:
If a partition is valid, then it contains only permutation blocks as well due to the length. Note that 1+2+...+n = n(n+1)/2 = length of a
Therefore, “a partition is valid” is equivalent to “a partition contains only permutation blocks.”
Problem becomes: How many ways are there to split a into blocks such that each block is a permutation? Note that there are no other conditions!
Subtask 6: N <= 500
Problem: How many ways are there to split a into blocks such that each block is a permutation?
This can be done with a very simple DP (dynamic programming).
Let dp[i] be the number of ways to partition the first i elements into permutation blocks. Then
dp[i] = sum of dp[j - 1] where j<=i and a[j...i] is a permutation
Base case: dp[0] = 1
You only need to check for at most n values of j’s since the longest possible permutation has length n. Specifically, check for j with i-n+1 <= j <= i.
One way to check whether a subarray of length m is a permutation is by checking 3 conditions: (1) No duplicates; (2) 1 is (the minimum) of the subarray; (3) m is the maximum number of the subarray. The only way to satisfy all conditions with a sequence of length m is by having a permutation of length m.
There are O(n^2) states (note that the length of a is n(n+1)/2), each state takes O(n) time to compute. Complexity: O(n^3)
Statistics: Superpermutation
Average score: 5.83
Portals 2
Idea by: Jun Xing
Prepared by: Jun Xing
Abridged Problem Statement
Given n portals in a line each facing left or right (D[i] for i-th portal), Evirir starts from the leftmost portal and can teleport to a portal at any time, but must continue flying in the direction the portal is facing.
If Evirir can fly at most K meters, what is the minimum number of teleports needed to visit all portals? With that many teleports, what is the minimum distance he needs to fly?
Subtask 1: N <= 3000, D = R…RL…L
Subtask 2: N <= 200,000, D = R…RL…L
Subtask 3: N <= 20
Subtask 4: N <= 500
Subtask 5: N <= 3000
Tiny detail
Tiny detail:
Observation for all subtasks
Even though you may teleport even when you are not at a portal, it is never optimal to do so - you can teleport the moment you reach the portal you visited last instead.
Therefore, the paths flown on by Evirir can be modelled as line segments between portals, where each line segment is one flight without teleporting.
Goal: Find min teleports such that (total length of the line segments) <= K
Subproblem: When is a set of line segments valid, i.e. possible to be flown on by Evirir with the direction conditions? Example: Sample 3 needs 2 teleports.
Subtask 2: N <= 200,000, D = R…RL…L
With D = R…RL…L:
For all line segments between two portals, it is always possible to fly on them because one of these is always true: the line segment’s…
No reason to intersect line segments - a set of non-intersecting line segments is always possible and optimal.
R … R R … R R L L L … L
Subtask 2: N <= 200,000, D = R…RL…L
Problem becomes: Among the n - 1 line segments between adjacent portals, find the maximum number of line segments such that total length <= K.
Simply greedily take the shortest lines. Sort all n - 1 segments by length, take as many as possible with total length <= K. O(n log n).
I wonder why nobody solved subtask <= 2 (they’re one of the easiest subtasks in the contest)…
Subtask 3: N <= 20
Now, when is a set of line segments valid?
For a line segment, it is possible to fly over it if and only if it is not a “LR segment.”
A set of line segments is valid if there is no LR segment.
L
L
R
R
L
R
R
L
Impossible!
Subtask 3: N <= 20
Is there ever a need to have intersecting line segments?
L R L R
No! Look at the leftmost and rightmost endpoints of any two intersecting segments:
L L L … L R … R
Conclusion: We can always model the flight as a set of non-intersecting line segments!
L … R L … L R … L L R … R
Subtask 3: N <= 20
Try every 2^(n-1) subsets of segments between adjacent villages, check whether it is valid (no LR segments), then take the best subset.
You can do this by using bitmasks.
O(n * 2^n).
Subtask 4: N <= 500
We use dynamic programming (DP) to solve this.
We can instead solve:
then take the minimum X with min distance <= K.
Subtask 4: N <= 500
Let dp[i][j] be the minimum distance to visit the first i portals with j segments. Then
dp[i][j] = min(dp[k-1][j-1] + A[i] - A[k])
for all k <= i with (D[k], D[i]) != (L, R) because we cannot have LR segments.
Base case: dp[0][0] = 0
Answer:
There are O(n^2) states, where each state takes O(n) time to compute.
Complexity: O(n^3)
Subtask 5: N <= 5000
Solution 1: Optimize the transition
dp[i][j] = min(dp[k-1][j-1] + A[i] - A[k]) for all k <= i with (D[k], D[i]) != (L, R)
= A[i] + min(dp[k-1][j-1] - A[k]) for all k <= i with (D[k], D[i]) != (L, R)
Bolded part only depends on j (which is constant) and k. We can maintain a prefix min on the bolded part.
Let
Then
dp[i][j] = A[i] + pre[i][j][1] if D[i] = R
= A[i] + min(pre[i][j][0], pre[i][j][1]) if D[i] = L
Subtask 5: N <= 5000
Solution 2: Drawing lines from left to right
We “draw” the line segments as we go from left to right. Let the current line segment be “open” if we started drawing it but haven’t ended it.
Let dp[i][j][k] be the minimum distance for the first i portals with j segments and:
Subtask 5: N <= 5000
Let dp[i][j][k] be the minimum distance for the first i portals with j segments and:
Base case: dp[0][0][2] = 0
// amin(x, y) is set x = min(x, y)
c = 1 if D[i] == ‘L’, 0 otherwise
// Continuing an open line segment
for k in 0..1
amin(dp[i][j][k], dp[i - 1][j][k] + a[i] - a[i - 1]);
// Opening a line segment
amin(dp[i][j][c], dp[i - 1][j][2]);
// Closing a line segment starting with R
amin(dp[i][j][2], dp[i - 1][j - 1][0] + a[i] - a[i - 1]);
// Closing a line segment starting with L: d[i] must not be 'R'
if (d[i] != 'R')
amin(dp[i][j][2], dp[i - 1][j - 1][1] + a[i] - a[i - 1]);
// Opening and closing immediately (creating a point)
amin(dp[i][j][2], dp[i - 1][j - 1][2]);
Statistics: Portals 2
Average score: 1.5