T241 - Cube Volume and Surface Area

If the side length of the cube is $L$, its volume is $L^3$ and its surface area is $6L^2$.

T242 - Three Kingdoms Challenge

Note that $D=(A-B)+(B-C)=A-C$. If you try to do the first few cases by hand, you will realise:

• $N=6$: 2
• $N=7$: 3
• $N=8$: 3
• $N=9$: 2
• $N=10$: 3

Indeed, the pattern is true: if $N$ is divisible by 3, the answer is 2. Otherwise, the answer is 3. This is because any three consecutive numbers sum to a multiple of 3. Challenge: can you construct the $A, B, C$ that gives the minimal $D$?

T243 - Square Grid

For R queries, the answer is sum from $N\cdot(X-1)+1$ to $N\cdot(X-1)+N$.
The formula for sum from $A$ to $B$ is $(B-A+1)\cdot(A+B)/2$.
For L queries, note that the sequence is an arithmetic sequence.
The formula for sum of arithmetic sequence is $N\cdot(2A+d\cdot(N-1))/2$, where $A$ is the first term and $d$ is difference of terms.
Pay attention to the constraint on $N$, long long is needed.
Time complexity : $O(Q)$

T244 - Fair Partition

Subtask 1

We can naively loop over all possible values of $j$ and calculate each range by considering the max or min of each subarray. We would have 2 nested for loops so the time complexity is $O(N^2)$ which would pass subtask 1.

Subtask 2

We could still loop over all possible values of $j$ but we can't calculate the range by brute force. Instead, we can do some precomputation: we can calculate the max and min for each prefix and suffix. (Note that $\max a[1..j] = \max(\max a[1..j-1], a[j])$ so we can reuse the previous values.) With this trick, we can speed up the calculation of the ranges to just a simple subtraction, and the overall time complexity would be $O(N)$ so it would pass subtask 2.

T245 - The World

Subtask 1

The World Value of all subarrays are zero. Print $0$ if $L = 0$, otherwise print the total number of unordered distinct pairs, which is $\binom{n}{2} = \frac{n(n-1)}{2}$.

Subtask 3

The World Value of a subarray $a$ of length $n$ is: $$W(a) = 1 \cdot (n-1) + 2 \cdot (n-2) + \dots + (n-1) \cdot 1 = \frac{n(n+1)(n+2)}{6}$$ With this formula, the answer can be calculated by brute force.

Subtask 2

By brute force, for all $O(n^2)$ subarrays, use $O(n^2)$ time to calculate its world value and check if its within $[L, R]$.
Time Complexity: $O(n^4)$

Subtask 4, 5

Optimisation 1 - $O(N)$ computation of $W$

Say you know the value of $W(a[l..r])$, in order to use this to find $W(a[l..r+1])$, let us compute the difference. $$W(a[l..r+1]) - W(a[l..r]) = \sum_{i=l}^r {(r+1-i)a_i a_{r+1}} = (\sum_{i=l}^r {(r+1-i)a_i}) a_{r+1}$$ $\sum_{i=l}^r {(r+1-i)a_i}$ can be computed in $O(1)$, using two partial sums: $$P[k+1] = \sum_{i=0}^k {a_i}$$ $$P2[k+1] = \sum_{i=0}^k {(n-i)a_i}$$ Then, $$\sum_{i=l}^r {(r+1-i)a_i} = P2[r+1] - P2[l] - (n - r - 1) \cdot (P[r+1] - P[l])$$ Therfore, $W$ is computed in $O(n)$, improving runtime to $O(n^3)$.

Optimisation 2 - amortised $O(1)$ computation of $W$

Instead of recalculating $W$ every time, if we can iterate $r$ while keeping $l$ the same, we can reuse previous values of $W$.
This achieves $O(1)$ time for every subarray.

Combining

Using both optimisations, we achieve a time complexity of $O(N^2)$

Subtask 6-7

Optimisation 3 - 2 pointers method

As $r$ increases and $l$ kept constant, $W(a[l..r])$ is non-decreasing, as all $a_i$ is non-negative. To utilise this fact, we keep two pointers, $l$ and $r$. While iterating $l$ from $0$ to $n-2$, we maintain $W(a[l..r) \gt L$. Meanwhile, increase counter if $W(a[l..r) = L$. Now, only $O(n)$ subarrays need to be checked, each using $O(1)$ time. Time complexity: $O(1)$.

Full Solution

Improve on the subtask 6-7 idea. Maintain instead three pointers, $l$, $r_L$, and $r_R$, so that for each $l$, the number of valid subarrays is $r_R - r_L$.

T246 - Maze Runner

Subtask 1 (10%)

Assume $N = 1$ (Since the solution for $M = 1$ will be very similar), we can maintain $mx$, the maximum number such that $mx < Y$ and $(1, mx)$ is blocked, and $mn$, the minimum number such that $mn > Y$ and $(1, mn)$ is blocked.

Type 1 query:

Output 1 if $mx \le C_i \le mn$, else return 0.
Time complexity: $O(1)$

Type 2 query:

Update $mx$ and $mn$.
Time complexity: $O(1)$
Overall time complexity: $O(Q)$

Subtask 2 (15%)

Treat the entire maze as a graph.

Type 1 query:

Perform BFS / DFS from $(X, Y)$ to check whether the player can move to $(R_i, C_i)$.
Time complexity: $O(NM)$

Type 2 query:

Update the graph.
Time complexity: $O(1)$
Overall time complexity: $O(NMQ)$

Subtask 3 (25%)

Maintain connectivity online while blocking cells is hard!
Observation 1: Notice that we can actually do all queries in reverse order and the answers to the queries will simply be in reverse order. This way, we should first block all $(R_i, C_i)$ in type 2 queries, then unblock them as we handle the queries in reverse order. We can perform BFS starting from $(X, Y)$ at the beginning, since in the new version of problem, once a cell becomes reachable, it will continue to be reachable in later query.

Type 1 query:

Check whether $(R_i, C_i)$ is visited by BFS.
Time complexity: $O(1)$

Type 2 query:

Push $(R_i, C_i)$ into the queue if one of its neightbouring cells is reachable and continue BFS. Since BFS won't revisit the same cells and there are only $NM$ cells, the amortized time complexity is $O(NM)$.
Overall time complexity: $O(NM + Q)$

Subtask 4 (30%)

We need not to worry about maintaining the graph online. Since there are too many cells to maintain, we need a smarter approach. Notice that all cells between some interval $(R, l)$ to $(R, r)$ are reachable to each others if none of them is blocked.
Observation 2: We can merge all of them into some larger cell intervals based on all type 2 queries, so the number of large cells we need to maintain is $O(N + Q)$. That way, we can simply perform BFS / DSU on these large cell and handle each type 1 query. To check whether two cell intervals are neightbour, we can store them in arrays of std::set and use std::set.lower_bound.
Overall time complexity: $O((N + Q) log (N + Q))$

Solution

Combine both idea from subtask 3 and 4, we can update the state of cell intervals in type 2 queries and perform BFS / DSU.
p.s. If you are solving with BFS, be extra careful to never revisit any cell intervals, or else you may TLE.
Overall time complexity: $O((N + Q) log (N + Q))$

Notes from GL

Illustrations drew by myself on paint.net
Originally, type 1 query is to find the number of reachable cells from any given $(R_i, C_i)$, which can be solved by DSU with something similar to union by size, but Snuny said DSU is out syl, so I have to remake the whole task and solve this with BFS and set ONLY!!!
Thank you Snuny for doubling my workload 🙃
Also congrat Kodi for being the only AC for this task, well deserved champ

T247 - Game of Creation

Subtask 1

By playing the simulator, you shuold be able to realise that the answer is always $1$ for all $|x_i| = |y_i|$, i.e. cells on the diagonal.

Subtask 2

You can hard-code the answer with the simulator. To simplify, note that you only need to look at values in the upper-right quandrant.

Subtask 3

Simulate the game by running 128 iterations (not 100 - why?).

Subtask 4

Observe in the simulator. What happens? Only one cell is living. Remember to handle $\max(|x_i|, |y_i|)=1$. This hints the full solution - why powers of two?

Subtask 5

Speed up the simulation in subtask 3 by only considering the neighbouring cells of the cells that recently turned living in the last iteration. Run this for 1024 iterations.

Subtask 6

First note that there are a lot of symmetry in the grid. Consider $p=2^{\lfloor \log_2 x \rfloor}$, the largest power of 2 smaller than or equal to x. If $(x, y)$ is in the upper right quandrant of the subgrid of $(0,0)$ to $(2p-1, 2p-1)$, we can consider its relative position in the bottom left quandrant. In picture:

We can always reduce the grid to a smaller subgrid when the cell is in the top-right quandrant, which by design of this subtask, $\min(x,y) \lt 1024$ after reduction.

Full solution

Find some symmetries and we are done. One way to do it:

We need to flip the blue and green rectangles vertically.