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.