Hints for Contest 4 problems:
The idea and motivation behind these hints are 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.
1.Stacks
Hint 1
Binary search on data structure (containing all the top disk radii) to find the smallest top disk radius which the current disc can be placed on top of.
Hint 2
In total, you’ll have three operations you want to handle: adding a new disc, binary searching for a disc and removing a disc.
Hint 3
Simulate the process, using the multiset. Be careful not to use a set because of duplicates being removed.
2.EURON
Hint 1
Consider the answer for some array to be the sum of the number of violations within the left half of the array, the number of violations within the right half of the array, and the number of violations that cross the halfway point in the array.
Hint 2
For every element in the left half of the array, there is some number of elements in the right half of the array smaller than it. Each such pair will create one violation.
HInt 3
For every element in the left half of the array, binary search for the latest position in the right half which is \le it, and add the number of positions to the answer crossing the midpoint.
HInt 4
Combine answers to the left half, right half, and across the midpoint cases to solve the problem.
3.QHOUSE
Hint 1
The bottom of the square is on the x-axis and the diagram is symmetrical across the y-axis.
Hint 2
Binary search for the x-coordinate of the bottom-right corner of the square.
Hint 3
Let the answer to your binary search be X.
Since it’s a square, the base is of side 2X.
The triangle base must also be on the line y=2X
Hint 4
Binary search for the rightmost point on the base of the triangle. Let the answer to this be R.
Similarly, binary search for the top point of the triangle. Let the answer to this be T.
Hint 5
You’ve got the dimensions, combine them to find the area:
2X * 2X + 2Y * (T - 2X) / 2
4.LOWSUM
Hint 1
Consider the alternative problem, “Given an integer X, find the number of pairs (i, j) such that A[i] + B[j] ≤ X.”
Hint 2
How can you use this modified problem to solve the original problem?
If you binary searched over X for the minimum X such that the answer was ≥ Q, this minimum X would be the answer to a query Q.
Hint 3
How can you solve this modified problem?
Sort both arrays A and array B.
Hint 4
For each integer Y in array A, all integers ≤ X - Y in array B will create a valid pair. You can binary search for the number of valid pairs in B. This will take O(NlogN) time.
Hint 5
Can we solve previous hint in O(N) time using two-pointers?
5.ASHIGIFT
Hint 1
Use a similar technique to the previous problem (LOWSUM).
Hint 2
Reach the end starting with some number of soldiers X.
Hint 3
Notice that if you can reach the end starting with X soldiers, you must be able to reach the end with X+1 soldiers as well.
Hint 4
Binary search for X!
6.STRSUB
Hint 1
Use that fact that is a substring is valid then all the substring formed are formed by this also valid.
Hint 2
For each i from 1 to N, we can find the j such that S[i, j] is valid and S[i, j+1] is not and denote this as ans[i].
Hint 3
For each query of type (l, r), we can find a value cnt for which ans[cnt] \le r.
Answer = sum of ans[i] from 1 to cnt - sum of ans[i] from 1 to (l-1) + (R-k)*(R+1) - (R*(R+1)/2 - L*(L-1)/2).
Hint 4
Use prefix sum to produce the sum of first terms of ans array. Find the cnt value using binary search.
7.ACM14KP1
Hint 1
Sort the points by x-coordinate and divide the points into two half and find the answer for each half.
Hint 2
The answer of the first half is ans_1 and the second half is ans_2 then answer of the combination of two half is max(ans_1, ans_2, answer produced by points such that one lie in the first half and the second in second half).
Hint 3
For each point p_i in the first part, we are only looking for the points p_j in the second half such that p_i.y - min(ans_1, ans_2) < p_j.y < p_i.y.
To know more about the above hint please refer to this:
https://cp-algorithms.com/geometry/nearest_points.html
Hint 4
Suppose ans_1 and ans_2 denote the minimum perimeter for the first and the second half and current_ans (without merge) is min(ans_1, ans_2).
Now, we need to check those that can form by merging these two half.
Hint 5
Tringle whose maximum length side is less then current_ans/2 can contribute to the final answer.
8.TRANSACT
Hint 1
Let the answer be denoted by X and let the maximum transaction between any pair of friends be denoted by Y. Note that as X increases, Y either remains the same or also increases. That is, f(X) = Y is a monotonically increasing function. Therefore, we can perform a binary search on the function.
Hint 2
Now, we have to write a function g(x) that returns true or false depending on whether it’s possible for all friends to have >= x coins.
Hint 3
In order to write g(x), a key observation is that in a sorted list of coins, friend i would only take coins from a friend with index > i. Therefore, for each prefix of friends, we can check if the remaining suffix can transfer the required coins to the prefix without breaking the condition. This function should be in O(N).