RI November Course stage 2 test editorial
Scoreboard
Q1: What’s the Time?
10 minutes past 1200
Output the time N minutes after 0000, in the 24 hour clock.
Subtask 1
1 <= N <= 59, ie. N is less than an hour.
Just output “00” + N, or “000” + N if N < 10.
(Eg. If N=1, we print 0001; if N=59, we print 0059)
10 free marks!
Subtask 2
1 <= N <= 1339, ie. N is less than a day.
To find the current hour, divide N by 60.
To find the current minute, find the remainder when N is divided by 60.
Remember to print leading zeroes when current hour < 10 (eg. 0111)!
Subtask 3
1 <= N <= 10^6, ie. N is more than a day.
Find the number of hours by dividing N by 60. Now, modulo number of hours by 24 to find the current hour.
Current minutes can be found as per Subtask 2.
Subtask 4
Q2: Coin Journey
to the west
2. Coin journey
Abridged statement:
You have an array.
For every query, find the smallest index i such that sum from 1 to i is greater or equal to the number given in the query
st1&2
Notice that Q and N are small enough that a O(QN) solution is allowed to pass
So for every query,
We simulate the process. Upon reaching somewhere such that the total sum is greater or equal to the query number, we output that index and go on to the next query.
Remember to use long long for EVERY variable
30 free marks!
st3
This subtask says that the array given is all positive.
This means that as we move further into higher indices, our net gain always becomes greater.
We define another array, ss, which stores the sum of all integers from 1 to i for every index i.
We notice that if(ss[i] >= x) is true, then index i fulfills the criteria.
st3
st3
Since ss is always increasing,
If an index fulfills the condition, then index+1 must also fulfill the condition
Thus we binary search for the first index that has ss[index] >= the query number.
If even ss[n] < the query number, then output -1
st4
This subtask is similar to subtask 3, but the array elements can now be negative
Now, we define another array, called mx. The value of the ith index of mx will be the max of ss array from index 1 to i.
Now, we do the same thing as what we did in st3, but using the mx array.
It’s easy to see that mx is monotonic as the maximum of a range that envelopes that another range is always greater than the other range.
Code:
https://ideone.com/edn6AZ��Number of ACs: 3
Q3: Green Beans Mayhem
NOT sorry for the braincells you lost from doing this problem
3. Green Beans Mayhem - Abridged Problem Statement
You have an increasing arithmetic sequence A of length N with the difference of any two adjacent elements is an integer D.��One of the numbers is wrong. Find the index of that number. (1-indexed)
Subtask 4: D = 1
We start from st4 as it is the easiest.
Using A[0], generate an increasing sequence where adjacent numbers differs by exactly one.��Compare with the original array. If exactly one number is wrong, output the corresponding index. ��If more than one number is wrong, then surely A[0] is the wrong number. Print 1 in this case.
26 marks
Subtask 2: N = 4
Now we go back to subtask 2 (and 3).��Important observation: for any 4 elements in array A, at least 1 of the differences between 2 adjacent elements must be D.
This is because changing one element will only affect at most 2 differences.��
4
5
6 9
7
8
9
1
1
1
4
-2
Subtask 2: N = 4
So to solve this subtask, we just brute force all 3 differences as D and check if any works (only 1 wrong), by generating the sequence from the first number. If yes, we output the wrong number.��If none works, the first number must be wrong.��21 marks
Subtask 3: 4 <= N <= 1000
Pick any 4 consecutive numbers, and use Subtask 2 to solve.
22 marks
Subtask 1: N = 3
This is just case bash (but very difficult)
With no restrictions in Ai and D, any one number can be considered to be wrong.
However, A must be increasing, Ai must be non-negative, and D must also be non-negative.
Subtask 1: N = 3
We need to consider all 3 cases:
Case 1: First number can be wrong, if A[1] <= A[2] and A[1] - (A[2] - A[1]) >= 0
Case 2: Second number is wrong if A[0] <= A[2] and (A[0] + A[2]) is even (so that the corrected number is an integer)�Case 3: Third number can be wrong if A[0] <= A[1]
16 marks
Subtask 5: 3 <= N <= 10^6
Q4: Leveling Up
seriously Noodle???
4. Leveling Up - Abridged Problem Statement
You have N levels and M time.
Each level can be completed in Ti time for Ki experience. However, you need to complete at least Si levels before you can play the level.
Maximise the experience gained within the time.
N <= 300, M <= 1000
Subtask 1
Si = i-1 for all i
We can only play levels in order. Therefore, we just simulate until we run out of time, and take the maximum experience gained.
Free 8 marks.
Subtask 2 & 3
Si = 0, ie. all levels are open at the start.
Classic knapsack.
12 + 15 marks
PS. Subtask 2 has additional constraint where T=1. So we can greedy and take the best min(M, N) experience (of course we don’t take any with negative experience.) 12 marks to grab!
Subtask 4
M = 2. This is a special case of the problem.
Notice that 1 <= Ti <= M. Therefore, we can play at most 2 levels. As such, we can at most unlock 1 more level to play. So we can safely ignore levels with Si >= 2.
Let’s consider some cases.
Subtask 4
Case 1: Play no levels. 0 experience.
Case 2: Play exactly 1 level. We ignore those levels with Si >= 0. For the remaining levels, pick the one with the greatest experience.
Case 3: Play exactly 2 levels. Levels can only take 1 time. Either we play 2 levels that are open from the start, or play 1 level, and unlock another level to play it.
Subtask 4
We take the maximum of all the 3 cases.
17 marks.
Subtask 5
N <= 10.
For contestants who knows subset brute force / recursive brute force without memoisation.
13 marks.
Subtask 6 - No additional constraints
We can do DP.
Let dp(current level, number of completed levels, time left) = maximum experience gained.
Assuming 0-indexed, base cases:
dp(N, l, t) = 0; // No more levels
dp(i, l, 0) = 0; // No more time
dp(i, l, t) = 0; if l < S[i] // Cannot unlock this level
Subtask 6 - No additional constraints
Transitions:
dp(i, l, t) = max(dp(i+1, l, t), // not play this level
dp(i+1, l+1, t-T[i]) + K[i]; // play this level. (if t <=T[i])
)
Answer is max(0, dp(0, 0, M));
Code: https://ideone.com/rfBDil
Number of ACs: 0
Maximum Score: 12
Q5: Deliveroo
Not a paid ad
5. Deliveroo
Abridged Statement:
Given N houses located on a straight line, find the maximum cost to visit only x such houses for all x between 1 and N.
Cost is the sum of the distance for the round trip (max Di * 2) and the cost for visiting each house.
Subtask 1
All houses are at distance 1 (Di = 1 for all 1 ≤ i ≤ N)
We just try to maximise the cost of visiting each house. Sort house costs in decreasing order.
Answer for each x is 2 + C[1] + C[2] + … + C[x] (1 indexed)
Subtask 2
House costs are non decreasing. (Ci−1 ≤ Ci for all 2 ≤ i ≤ N)
House distances are also non-decreasing. Thus we visit the last x houses for each x
Subtask 3
N ≤ 2000
We can do DP.
Let dp(i, j) be the max cost after considering the first i houses and visiting j houses.
Base case: dp(i, 0) = 0; dp(N+1, j) = -infinity.
Transition: dp(i, j) = max(dp(i+1, j), dp(i+1, j-1) + Cost(i));
where Cost(i) = D[i] * 2 + C[i] if i == 1
= (D[i] - D[i-1]) * 2 + C[i] otherwise.
Subtask 5 (Full solution)
Constraints for ST4 were to lead people into considering “left” and “right” blocks of houses. This leads to the full solution.
Consider the answer for x = 1. It is easy to see that it is the max( 2D[i] + C[i] ).
I claim that the set of houses chosen for the answer of x = 1 will also appear in the set for x = 2, and so on.
Full Solution - Proof of claim
In contest:
In editorials:
Full solution - Proof of claim
Rigorous Proof: (submitted by Baryiscool(Taeyoung)#6741)
Let the optimal solution when visiting N houses be X = C[k1] + C[k2] + … + C[kn]+ 2 * D[kn], where k1 is the nearest house and kn is the furthest. Let the set of houses used be K.
Let the optimal solution when visiting N + 1 houses be Y = C[p1] + C[p2] + … + 2 * D[pn+1], where p1 is the nearest house and pn+1 is the furthest. Let this set of houses be P such that P does not contain all houses in K.
Full Solution - Proof of claim
Case 1: Pn+1 == Kn
Then,
Y = C[P1] + C[P2] + … C[Pn+1] + 2 * D[Kn] < X + C[Pj], where Pj is not in K.
Full Solution - Proof of claim
Case 2: Pn+1 is on the left of Kn
Then,
Y < C[P1] + C[P2] + … C[Pn+1] + 2 * D[Kn] < X + C[Pj], where Pj is not in K.
Full Solution - Proof of claim
Case 3: Pn+1 is on the right of Kn, then,
Y = C[P1] + C[P2] + … C[Pn+1] + 2 * D[Kn] + 2 * (D[Pn+1] - D[kn]) <
X + C[Pn+1] + 2 * (D[Pn+1] - D[kn])
=> C[P1] + C[P2] + … C[Pn] + 2 * D[Kn] < X
Notice that if we cancel on both sides, the sizes of K and P are equal. Since K is optimal for size N, it is better to add a new house by extending from set K. This holds true for all 3 cases.
Thus, the set of houses for all x will contain the set of houses for x - 1.
Full Solution - Observation
Following up from our claim, we now know that the house for x = 1 will be used as a house for x = 2.
How do we choose the 2nd house for x = 2?
Notice that the first house splits the range of houses in 2 segments, houses with smaller distance and houses with larger distance from the entrance.
Full Solution
If we choose a house on the left, we simply pick the house with the highest cost. This is because our maximum distance is fixed by the rightmost house.
If we choose a house on the right, we pick the house with greatest distance * 2 + cost, as we are extending our rightmost house which contributes to the distance.
Compare the largest value on both sides and choose accordingly
Full Solution
Full Solution
We can implement this using 2 priority_queues, one to keep track of the left half and one for the right.
Note: after choosing a house on the right, we do not need to void houses between the new house and old house. For some house j such that j < mx, our current rightmost house, D[j] - D[mx - 1] < 0,
so D[j] - D[mx - 1] + C[j] < C[j].
Hence that house will not be chosen in the right pq, but instead in the left.
Thanks to SYY for pointing this out
Full Solution
Full Solution
Or just use a segment tree with DnC DP speedup
The end