Hints for Contest 2 problems:
The idea and motivation behind these hints is that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also, open the hints in sequential order.
Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.
The benefit of knowing a partial solution rather than the complete solution is that you can work out the later stages of the problem yourself, thus improving your problem solving skills.
TLDR; use the hints cautiously, if you start relying on them too much, it can hamper with your learning process.
Hint 1
We can dismiss all those rectangles that are not bounded by the plane or a point on all 4 sides since their sides can be extended to form a more optimal rectangle.
Hint 2
If we fix the point that is on the boundary of the top edge of the rectangle (call it pnt) , the sides will be bounded by the first point (on both left and right) such that its y is less than pnt.y. If no such point exists then it will be bounded by the plane
Hint 3
If we sort all points from left to right, we can find the left-right binding points for each point using this algorithm: Find the nearest smaller numbers on left side in an array - GeeksforGeeks
Hint 4
The case where the top edge of the rectangle is touching the plane is solvable by realising that these rectangles are formed between adjacent points. Therefore we can take 500 * max difference of x between adjacent points
Hint 1
For all points i, find the smallest point j such that (j>i) and a(j)<a(i).
Hint 2
After doing this for all i, multiple the answer (initially 1) by (j-i+1)
Hint 3
This can be done fast using this algorithm: Find the nearest smaller numbers on left side in an array - GeeksforGeeks
Hint 1
Find the first βbreak pointβ in the string. A point i is a βbreak pointβ if it is the first point such that the frequency of β>β (from index 0 to index i) is greater than the frequency of β<β. Note that all prefixes ending at location j where (j>=i) are invalid
Hint 2
The second condition for a prefix being valid is that the frequency of β<β is equal to frequency of β>β
Hint 3
Maintain a stack in which you push an element whenever you encounter β<β and pop an element whenever you encounter β>β
Hint 4
If you need to pop an element but the stack is empty, this is a break point
Hint 5
The answer is the last i such that i<break point, and the stack is empty after you have completed the appropriate operation for the character at s(i)
Hint 1
Maintain a stack in which you push an element whenever you encounter β(β and pop an element whenever you encounter
Hint 2
The maximum nesting depth is simply the maximum size of the stack at any point in time.
Hint 3
Letβs push all of the βtimesβ at which the stack became empty into a vector (including time 0). If at index i (0 based indexing), the stack becomes empty, push (i+1) into the vector.
Hint 4
The maximum length of a subsequence is simply the maximum difference between adjacent elements in the vector.
Hint 1
Store the contest start and end times in a pair vector.
Hint 2
Sort the use times of both wormholes in ascending order.
Hint 3
For each contest, find the latest time at which you can arrive and the earliest time at which you can leave.
Hint 4
You can find the latest arrival time by doing an upper bound search on the start time of the contest (and decrementing the pointer) and you can find the earliest leave time by doing a lower bound search on the end time of the contest.
Hint 5
The answer is simply the minimum of (leave time - arrival time + 1)
Hint 1
At any point, we know that team A will the game iff, despite missing all of their remaining shots and team B scoring all of their remaining shots, their score will be higher than team Bβs score. The inverse is true for team B winning.
Hint 2
Denote team Bβs current score by C(B), team Aβs current score by C(A), team Aβs remaining shots by R(A), team Bβs remaining shots by R(B). At any point, team A is winning iff (C(A) - C(B)) > R(B). The inverse is true for B winning.
Hint 3
The implementation for this problem can be simplified by using a queue of pairs. Push pairs in the format {0/1 (for miss or goal), 0/1 (0 indicates team A, 1 indicates team B)}
Hint 4
Keep on popping elements from the queue and updating the scores as required. Break as soon as our win condition has been reached or if the queue is empty.
Hint 1
store all of the values in the array and the answer is simply the maximum of (p(i)/s(i)) x v(i) across all N types of street food.
Hint 1
Each box i can contain a maximum of S(i) tokens. However, whenever you put a token into the ith box, you are also putting a token into boxes 0β¦(i-1).
Hint 2
The practical maximum capacity of each box is minimum of S(0), S(1), β¦ , S(i))
Hint 3
Run a for loop from 0 to n-1 and find the practical max capacity for each point by keeping track of the prefix minimum
Hint 4
Finally, the answer is simply the sum of practical max capacity across all boxes.
Hint 1
While running our algorithm, we will need to keep track of the frequency of each cake flavour in the range. To do this, maintain an int array βarrβ (with all elements initialised to 0) where arr(i) represents the number of cakes with flavour i in the range.
Hint 2
In order to keep track of the number of unique flavours in a range, simply increment the amount whenever a flavour frequency changes from 0 to 1 and decrement it whenever it changes from 1 to 0.
Hint 3
If a range (l, r) contains less than n flavours, we can consider this to be a valid range and check if it is the largest.
Hint 4
If a range (l, r) is valid, we should check if range (l, r+1) is also valid. If range (l, r+1) is not valid, we need to contract it until we get a valid range.
Hint 5
In order to contract a range, we can either do (l, r-1) or (l+1, r). Note that if range (l, r) is invalid, we have already visited range (l, r-1). Therefore, it would be redundant to visit it again. Hence it would be optimal to increase the lower bound and check.