Free Marks

Author: hopeiess
Preparation: hopeiess
Solution: hopeiess
Subtask 1, Y is positive
output Y/X, Y%X
Subtask 2, Y can be positive or negative
fun fact: c++ handles division by rounding to 0
so -8/3=-2, -8%3=-2
to handle this:
if Y is positive, output the same thing
if Y is negative, output -((-Y)+X-1)/X,(X-((-Y)%X))%X

Touch Grass

Author: s22l19
Preparation: s22l19
Solution:
Loop $i$ from $2$ to $N$ and keep calculating the sum of previous elements.
Average can be calculated by $sum_{1…i-1}/(i-1)$.
Therefore, if $A_i \cdot (i-1) > sum_{1…i-1}$, the plant is “T”, or else it is “G”.

Snoring Snorlax

Author: yck
Preparation: yck
Solution: yck
Find the time and loudness by accessing the first 2 and last 2 characters of the 4 digit number.
One can do this by calculating X/100,X%100.
After that we need to find the sleep and eating continuous time segments.
One can do this by maintaining current action, and current acting time.

Concert Ticketing

Author: Animal Migration
Preparation: Animal Migration

Part I: handling the piece name, input and output
For input, use getline or getchar function to handle the "s. For every letter of the start of a word (or say there’s a space or " before it), make it uppercase, else lowercase. When outputting, remember there isn’t a comma at the end of the line, so handle it using ifs.

Part II: handling the ticking system
Make a queue/array for every piece to store its buyers (i.e. array of queue or 2D array). Decrease $A[i]$ by 1 when buying piece $i$, and check whether a piece’s $A[i]$ is 0 before “buying” it.
Combine everything and that’s it! If you know how to handle one of the parts, you can get marks from subtasks!

Bytephone Keyboard

Author: Animal Migration
Preparation: Animal Migration


Brief idea: Convert every word in the dictionary into corresponding 3-key combination, for every query, count the number of occurrences of that word’s 3-key combination in the dictionary. To find the frequency of triples quickly, use map,int>, map,int>, or combining the 3 numbers into 1 by some math (instead of using map, use can use an array to store, and the ans is upper_bound - lower_bound). To find the 3-key combination, you can do binary search as the characters for each key are unique.

Fall

Author: s22l19
Preparation: s22l19
Solution:

Subtask 1:
Do case handling, check whether the only obstacle is above the portal.

Subtask 2:
Run the whole thing by dropping yourself from top to portal. Small number of queries allows you to do so without TLE.

Subtask 3:
Important observation:
For each column, what only matter is the top obstacle.

What you need to check for each query is whether the portal is below or above the topmost obstacle in that column.
The topmost obstacle can be precomputed. Therefore you can do $O(N)$ for each adding of obstacle and $O(1)$ for each query.
Overall time complexity: $O(N^2)$

Subtask 4:
(Actually not quite related to full solution)
Note that you can loop through each segment of obstacles for each query to check whether it blocks or not.

Subtask 5:
You need to optimize the solution in subtask 3 so that each obstacle do not need $O(N^2)$ update.
There are many solutions for this problem.
Solution 1, $O(NlogN)$ :
Slide through the leftmost column to the rightmost column, and insert/erase segments of obstacles in a set. For each column, store the minimum height of obstacle.
Solution 2, $O(NlogN)$ :
Use segment tree to store the minimum height of obstacle of each column by doing range update and point queries.

Actually there are a lot more $O(N)$ and $O(NlogN)$ solutions, feel free to explore more!

Fun extended problem:
If the starting point is not the top row but instead given X distinct starting point, can you solve this problem?