Where am I?

Note that he himself also counts as a person
Therefore, the answer is N-A-1

Task validator

We can write 3 if statements.

if(score==100) printf("Accepted");
else if(score>0) printf("Partial Score");
else printf("Wrong Answer");

Real Trivial Task

Observe the task,you have to compare the first and second, the second and third...
Therefore, we have to compare the $i^{th}$ and the $(i+1)^{th} $ element, where $0 \leq i \le N-1$.
Noted that abs(a-b)==1returns TRUE if a and b are consecutive integers (no matter the order).
Therefore, if(abs(s[i]-s[i+1]))ct++ will solve the problem.

Snail at the Bottom

Use a for loop simulate the process day by day.
Remember to check whether the current height is already >= H before dropping C metres.
Also, remember to set C to be 0 if it drops below 0. (This happens when C is larger than current height)

Buying Stocks

Subtask $1$: Array $a$ is decreasing

The stock is always decreasing in value, Alice cannot earn money.
Output $0$

Subtask $2$: Array $a$ is increasing

The stock is always increasing in value, Alice should buy as soon as possible(day $1$), and sell as late as possible(day $n$)
Output $a_n-a_1$

Subtask $3$: $n \le 5000$

Lets say Alice buys at $i$ and sells at $j$.
She will earn $a_j-a_i$, we want to maximize this.
Simply exhaust $i$ and $j$ and find the maximum value.
Time complexity: $O(n^2)$.

Subtask $4$: There exists an optimal way of operating such that Alice sells when the stock is the most expensive

Find the maximum and its position, that is where Alice will sell.
Then Alice will obviously buy at the smallest value of stock before she sells.
We just need to find the minimum value before the maximum.
Time complexity: $O(n)$.

Subtask $5$: No Additional Constraints

Exhaust where Alice sells, then she should buy at the minimum value before selling
We can precompute all such values in $O(n)$ with prefix minimum.
Specifically, we loop $i$ from $1$ to $n$, maintain the minimum value of $1$ to $i$, and find the answer if we sell at $i+1$.
Time complexity: $O(n)$, easy $100$ points!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h>
using namespace std;
int n,a,mn,ans;
int main(){
    cin>>n>>mn;
    for(int i=2; i<=n; i++){
        cin>>a;
        ans=max(ans,a-mn);
        mn=min(mn,a);
    }
    cout<<ans;
}

Balls

Subtask 1 (7 pts) (R + Y + B = 1)

The constraints implies that either R, Y or B is 1, and others are 0.
As you can take any ball on the first move, just output the colour that has 1 ball.
You can use if-else statements to handle it. Expected Score: 7

Subtask 2 (9 pts) (R = 0, N <= 20)

There are only yellow / blue balls.
By trying different combinations, you’ll find out that only Y -> B or Y or B works.
When Y > 1 or B > 1, it’s impossible to get back to where you start, so it’s impossible to get more than 1 of the same kind.
Just case handling. Expected Score: 9 (Cumulative: 16)

Graph Modelling

To help us better think, we can turn the transitions between different colours into a graph, like this:
An arrow means that it’s possible to transit from current move to next move. For example, there is an arrow from yellow to blue, that means it’s possible to pick yellow in the current move, then pick blue in the next move.

Subtask 3 (13 pts) (B = 0)

Observe that we can keep repeat red and yellow without passing through blue.
Observation 1.1: In general case, we can use the pattern RYRYRY… to clear the same amount of red and yellow balls.
However, when R ≠ Y, there might still be a solution:
- When Y = R + 1, we can pick Y first, then RYRYRY…
- When R = Y + 1, we can pick R first, then YRYRYR…

Subtask 4 (23 pts) (Y >= R >= B)

We can extend the idea of subtask 3. First, consider the case Y = R.
Run observation 1.1 until R = B. As both Y and R reduces by the same amount and Y = R. Therefore, Y = R = B after running it.
Observation 2: When R = Y = B, we can run (RYB) or something similar to clear everything.
We then solved the case Y = R. How about Y = R + 1? We can simply take a Y first, then do the same thing.
For Y >= R + 2, the answer is -1.
We can also discover condition 1: R >= Y – 1 must hold when you start at yellow in order to have a valid sequence. (Refer to powerpoint for more details)

Subtask 5 (19 pts) (R >= Y + B)

This time, we have a lot of red. As we want to clear R, we can use observation 1.1 again.
After running, the current R is still larger than or equal to B.
We can apply something similar to observation 1.1 and clear R and B.
Observation 1.2: In general case, we can use the pattern RBRBRB… to clear the same amount of red and blue balls.
After running, there are R – Y – B red left and no more blue and yellow.
There are few cases of R – Y – B:
- If R – Y – B = 0 then we done.
- Otherwise if R – Y – B = 1 then we output 1 more R then done.
- Otherwise if R – Y – B > 1 then there is no solution.
We can also discover condition 2: R <= Y + B + 1 must hold when you start at red in order to have a valid sequence. (Refer to powerpoint for more details)

Subtask 6 (12 pts) (N <= 20)

Naively brute forcing all combinations takes too much time. O(3^N) ~ 10^9 operations.
To optimize it, we can run depth-first search. Notice that each colour at most connect to two different colours (According to the graph).
Therefore, the time complexity is O(2^N), which can pass.

Subtask 7 (17 pts) (No Additional Constraints)

Let's list out all the findings:
- Condition 1.1: R >= Y – 1 must hold when you start at yellow in order to have a valid sequence.
- Condition 1.2: R >= B – 1 must hold when you start at blue in order to have a valid sequence. (Refer to powerpoint for more details)
- Condition 2: R <= Y + B + 1 must hold when you start at red in order to have a valid sequence.
- Observation 1.1: In general case, we can use the pattern RYRYRY… to clear the same amount of red and yellow balls.
- Observation 1.2: In general case, we can use the pattern RBRBRB… to clear the same amount of red and blue balls.
- Observation 2: When R = Y = B, we can run R times (RYB) or smthing similar to clear everything.
Generalize the conditions:
- Condition 1.1: R >= Y must hold when you start at red in order to have a valid sequence.
- Condition 1.2: R >= B must hold when you start at red in order to have a valid sequence.
- Condition 2: R <= Y + B + 1 must hold when you start at red in order to have a valid sequence.
We can pick the starting path optimally if the above conditions aren't satisfied yet.
if after picking the starting path still not satisfy all conditions, then no solution.
Otherwise, we always have a general way to generate the sequence, combining all observations:
We make RYB cycles until R = Y + B. Then, we run Y times obs. 1.1 and B times obs. 1.2.
Congrats if u can follow then AC.