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 try all possible subarrays and check whether they are non-decreasing or not. But the time-complexity of such a solution is O(N^3) which will get a TLE verdict. Can we say if the subarray from L to R is non-decreasing then all the subarray whose start and end lies within L to R, also non-decreasing?
Hint 2
We can use the above fact and for each valid i for 1 to N, we find the maximum value of j such that i \le j and subarray i to j is non-decreasing and add j - i + 1 to the answer. But still, the time-complexity of such a solution is O(N^2) which will get a TLE verdict.
Can we do better?
Hint 3
We modify the above approach slightly, instead of trying all valid i, we can try for those only for which A[i-1] > A[i] and add ((j-i)*(j-i+1))/2 to our answer.
Hint 4
We can also do this with DP. Let’s try to find a DP array with the recurrence:
- DP[0] = 1
- DP[i] = DP[i-1] + 1 if i > 0 and A[i-1] \le A[i]
- DP[i] = 1 if i > 0 and A[i] < A[i-1]
Hint 1
If X = 1 then we know that it is impossible to achieve that score as a minimum we can get is 2.
Hint 2
Let’s try to think in the opposite way:
- For a score X, there are two ways we could perform to get there -
- By a cannon shot which implies we are previously at X-2.
- By an In-Off Shot which implies we are previously at X-3.
Hint 3
Let’s try to build a DP array where index represents the score with the recurrence:
- DP[0] = 1 //There is one way to get score 0 by not shooting at all.
- DP[1] = 0 //There is no way to get score 1
- DP[2] = 1 /There is one way to get score 2 by a cannon shot.
- DP[i] = DP[i-2] + DP[i-3] for i >= 3
Hint 1
We can easily find out whether a number is prime or not by the sieve.
Can we modify our sieve to give us more information rather than telling if a number is prime or not?
Hint 2
Yes, of course.
What we can do is instead of just marking the number is prime or not, we can increment a counter.
This way, we can keep track of the number of prime factors.
Hint 1
Try brute force and find the answer for each pair but it gives us TLE. Can sorting help us to reduce complexity?
Hint 2
Yes.
We can sort the coordinates of frogs in non-decreasing order of x coordinate but we need to keep track of the previous ordering as P pairs are given according to them.
Now can we notice that if two adjacent frogs have distance more than K then there is no communication between frogs of different sides of this gap?
Hint 3
We can divide them in groups where two frogs are in one group if they can communicate. This is an easy solution but can we do this with DP?
Hint 4
We can maintain a DP array where the i-th index tells about the i-th frog and value tells us the farthest frog which lies left of it and that it can communicate.
Hint 1
Look at the constraints, There are only 1007 distinct values possible (as primes less than 8000) so we can say that there is no subsequence possible with more than this length. That implies that K > 1007, we only need to calculate the answer up to 1007. In other words, K = min(K, 1007).
"Hint 2
Another observation we can make is that the ordering of elements in a subsequence is not important, so we can combine the same values together.
Now, we can say there are k_1, k_2, …, k_x balls are there for each color i from 1 to x. You have to select k balls for each valid k from 1 to min(K, 1007) such that there are no two identical balls.
Can you write a DP recurrence for this?
Hint 3
Build a 2D DP table where the first index indicates the up to which prefix we are considering and the second index tells us about the number of balls we selected and value in DP table indicates the number of ways to do that.
Hint 4
- DP[i][j] = 1, i >= 0
- DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * cnt[i]
Our desired answer is the sum over i from 1 to min(K, 1007) for DP[i][x].
Hint 1
The observation we can make is that the ordering of elements in a subsequence is not important, so we can rearrange them. Let’s think in this way:
- If there is only one number in the sequence then we can’t perform a move and in order to win the only number present in the sequence should be 1.
- If there are two numbers than what happened, it is similar to compute GCD.
What about numbers greater than 2?
Hint 2
Yes, it is to compute the gcd of the numbers of the sequence. Now you need to find the gcd of all possible sequences.
Pay attention over the constraints, as N is small and A_i \le 4000 which implies that gcd is at most 4000. Try to use the fact to write a recursive solution.
Hint 3
The recursion is simple here:
- DP(n,k) = DP(n+1, k) + DP(n+1, __gcd(k, A[n])
Hint 1
There are a lot of ways to solve the problem…I’m providing the hints for the dynamic programming version.
If somehow, we know about the time when the dirty water last appears to any window then it is easy to find the answer using that.
But how do we know this?
Hint 2
We know that for each j, A[0][j] (considering zero-based indexing) is always cleaned at the end.
similarly, A[1][j] is cleaned if A[1][j] > max(A[0][i-1], A[0][i], A[0][i+1]).
similarly, A[2][j] is cleaned if A[2][j] > max(A[0][i-2], A[0][i-1], A[0][i], A[0][i+1], A[0][i+2], A[1][i-1], A[1][i], A[1][i+1]) and so on…
Can you see any repetition??
Hint 3
Let’s create a 2D DP table such that:
- DP[0][j] = A[0][j] for each valid j
- DP[i][j] = max(A[i-1][j], A[i-1][j+1] for j = 0
- DP[i][j] = max(A[i-1][j-1], A[i-1][j] for j = m-1
- DP[i][j] = max(A[i-1][j-1], A[i-1][j], A[i-1][j+1] for 0 < j < m-1
Can you find the answer with the help of this matrix?
Hint 4
If the DP[i][j] > A[i][j] then answer is 0 else answer is 1 for each valid i and j.
Hint 1
We can consider the observation that all the elements in the string should be strictly ascending in order which means the string should contain the distinct elements.
As there are only 52 choices, that means the number of possible strings is 2^{52} - 1, but checking all the strings gives us TLE.
Hint 2
One observation is based on the previous one as the length is maximum 52 then maximum mapping value(hash value), we can get is 1378. So, S > 1378, the answer is zero.
Hint 3
With the help of the previous two observations, we can solve the problem using dynamic programming.
We make a DP table DP[52][1378] to produce our answer and if you observe the states of this DP then you find out that it is similar to the 0-1 Knapsack problem.
Hint 1
We can re-state the problem in the following way:
For each valid i from 1 to N(1-based indexing), find out the longest subarray that has sum equal to maximum subarray sum of the given array.
Now to solve our problem using this one, we just need to find out the minimum number for each valid i if there is a valid subarray that ends at I.
Hint 2
We need to care about the corner cases when the valid subarray has size 1 and when the valid subarray has only positive elements.
Hint 1
As the constraints are too high, we try to solve the subtask first.
We know that if N = 1, then answer is M and N = 2 then answer M*M but what about the N > 2.
Can we write a recurrence relation for it?
Hint 2
Let’s try to use two DP arrays DP1[i] for each i > 2 where it tells the number of ways to possible arrays whose last two indexes are different and DP2[i] for each i > 2 where it tells the number of ways to possible arrays whose last two indexes are same.
Can you write the recurrence now?
Hint 3
- DP1[i] = (M-1)*DP1[i] + (M-1)DP2[i-1]
- DP2[i] = DP1[i-1]
This can solve our problem for the first subtask, what about the original constraints?
Hint 4
Use matrix multiplication to solve the second task.
Hint 1
It is easy to say if we can find out the answer up to i and denote it f(i) then the answer to the problem is f(b) - f(a).
But how can we find the answer?
Hint 2
We can use the digit DP to solve the problem.
It is a very cool trick to solve this type of problem. How do we apply digit DP here and what are states?
.
.