Hey,
Here are the hints for Week 6 of the DSA Learning Series.
1.COG2002
Hint 1
We can prove that only 3 adjacent coders can be chosen. Let index k be the index of the middle coder. One coder has to have index >=(k+1) and the other has to have index <=(k-1). If we choose a coder with index k+2, then the difference in indices between the two corner coders will be >2. Therefore, those two will not agree to be in the same team.
Hint 2
Since we only have to check 3 adjacent friends, we can write a brute force function for this. Iterate over all i representing the index of the middle friend. Take max of current_ans and a(i) + a(i-1) + a(i+1).
Hint 3
In order to account for the cyclic nature of the array, take a(i-1) as a((i-1+n)%n) and a(i+1) as a((i+1)%n).
2.CHEFSUM
Hint 1
Prefix_sum(i) + Suffix_sum(i) can be written as a(1) + a(2) + … + a(i) + a(i) + a(i+1) + a(i+2) + … + a(n). Therefore, prefix_sum(i) + suffix_sum(i) = sum_of_array + a(i).
Hint 2
In order to minimise sum_of_array + a(i), we need to only minimise a(i) because sum_of_array is fixed over all indices. Therefore, the problem can be reduced to “output the index of the smallest element in the array”. The reduced problem is trivial.
3.CK87QUER
Hint 1
The expected complexity is B.log(Y)
Hint 2
Since B is <=700, we can iterate over all possibilities for B. Now, we need to find the number of distinct integers A such that A^2 <= (Y - B)
Hint 3
If K^2 <= (Y-B) then (K-1)^2 <= (Y-B). Therefore, we simple need to find the greatest integer A such that A^2 <= (Y-B).
Hint 4
You can perform the above task using binary search.
4.KCON
Hint 1
The expected complexity is O(N)
Hint 2
This problem is just some casework. There are 4 cases we need to check for:
Case 1
When the answer is just the maximum sum present inside a single array of size N.
Eg.
3 2
-1e9 5 -1e9
The answer in this case will be 5
Case 2
When the answer is the sum of the entire array, K times.
Eg.
3 3
3 3 3
The answer in this case will be 27
Case 3
When the answer is the maximum suffix of one array and the maximum prefix of the next.
Eg:
4 2
4 -1e9 -1e9 4
The answer in this case will be 4 + 4 = 8
Case 4
When the answer is the maximum suffix of the first array + the maximum prefix of the last array + all of the arrays in the middle
Eg.
3 4
3 -5 3
The answer in this case will be 8.
Hint 3
You can find the maximum suffix and prefix by doing linear scans from both sides and taking max. You can find the maximum sum present in the array using Kadane’s algorithm.
5.FIBNK
Hint 1
If any subsequence of K students contains no student from the same batch, it means that the students’ batches are repeating with period of K.
Hint 2
In order to minimise the eating capacity, start greedily assigning batches from 0 to K-1.
Eg. If K = 3 and N = 7
0 1 2 0 1 2 0
Hint 3
Now, the answer can be expressed as (sum of first K fibonacci numbers) x (n/k) + (sum of first (n%k) fibonacci numbers)
Hint 4
If you attempt to find the sum of the first N fibonacci numbers in O(N), you will get TLE. Use matrix exponentiation to find the sum in O(LogN). Learn about this technique here:
6.BDGFT
Hint 1
Our first step should be to optimise the process of finding count of 1s and 0s in a range. This can be achieved using RMQ via prefix sums.
Hint 2
Now, let’s analyse the nature of the length of the special sequences. If cnt0 = cnt1 ^ 2 then the length of the sequence is cnt1^2 + cnt1
Therefore, we need only check sequences that can be expressed in the form x^2 + x where (x^2 + x) <= N
Hint 3
Now, for each x (as described above), check each substring of that length for whether it is a special substring.
7.ARRCENT
Hint 1
Let’s look at this expression:
(Sum of kC2 from k = 2 to k = d)*V(i)
kC2 is the sum of the first (K-1) positive integers
Therefore, the expression is really this:
(Sum of (Sum of first k integers) for all k from 1 to (d-1)) x V(i)
Hint 2
If we take repeated prefix sums, we can achieve the above expression. Let me give an idea of this. Consider the following population array:
[V, 0, 0, 0]
Let’s take prefix sums one time
[V, V, V, V]
Now, all array positions have coefficient 1 (the first natural number).
If we take prefix sums again, the coefficient at position i should be i
[V, 2V, 3V, 4V]
Now, if we take prefix sums yet again, the coefficient at position i will be the sum of the first i natural numbers
[V, 3V, 6V, 10V]
Finally, if we take prefix sums yet again, the coefficient at position i will be the sum of (sum of the first k natural numbers) for each k from 1 to i
[V, 4V, 10V, 20V]
Therefore, we have to take the prefix sums 4 times.
Hint 3
Now that we have the prefix sums, we can repeat this process for suffix sums.
For each i, the answer works out to pref[i-1] + suff[i+1]
8.STROPR
Hint 1
We only need to consider the array between index 1 and X, the part after it becomes irrelevant. Therefore, if we set N to X, we need to only find A[N] after M prefix sums operations.
Hint 2
Look at this pattern of doing performing prefix sums repeatedly:
[A, B, C, D]
[A, A + B, A + B + C, A + B + C + D]
[A, 2A + B, 3A + 2B + C, 4A + 3B + 2C + D]
[A, 3A + B, 6A + 3B + C, 10A + 6B + 3C + D]
[A, 4A + B, 10A + 4B + C, 20A + 10B + 4C + D]
[A, 5A + B, 15A + 5B + C, 35A + 15B + 5C + D]
Notice anything?
Look at A(N) after 5 operations:
35A + 15B + 5C + D
Hint 3
Let’s look at the coefficients of each element.
D has coefficient 1 = 4C0
C has coefficient 5 = 5C1
B has coefficient 15 = 6C2
A has coefficient 35 = 7C3
Hint 4
Using this pattern, it’s simple to calculate A(N) in O(N.LogN)
In order to calculate nCr, pre-calculate the values of each factorial and the modular multiplicative inverse of each factorial.
