[OFFICIAL] DSA Learning Series - Week 10 Hints

Hey guys,

Sorry for the delay. Here are the hints for week 10 of the DSA Learning Series:

1.CSUMD

Hint 1

DP states:

dp(n) = the number of ways to place coins such that the sum of coins = n

Hint 2

DP transitions:

dp(x) = 2 x dp(x-1) + 2 x dp(x-2)

Hint 3

Of course, the naive way of calculation would be too slow.

In order to optimise this we could use matrix exponentiation.

| dp(i) | = | 2 2 | x | dp(i-1) |

| dp(i-1) | | 1 0 | | dp(i-2) |

2.IEMCO8F

Hint 1

This is a vanilla application of matrix exponentiation

Hint 2

| dp(i) | = | a b c d 1 | x | dp(i-1) |
| dp(i-1) | | 1 0 0 0 0 | | dp(i-2) |
| dp(i-2) | | 0 1 0 0 0 | | dp(i-3) |
| dp(i-3) | | 0 0 1 0 0 | | dp(i-4) |
| e | | 0 0 0 0 1 | | e |

3.MCO16403

Hint 1

DP states:

dp(i) represents the sum of heights of all nodes in the subtree of i

Hint 2

Initially calculate dp(i) by taking a random node as the root. Then find a way to efficiently modify the overall answer while changing the root.

Hint 3

If we only shift the root by a single edge (say from u to v), the new answer is:

Initial_answer - (size_of_subtree_of_v - size_of_remaining_tree)

4.CODIE

Hints will be added soon.

5.MATTEG

Hint 1

Note, the number of transportation units (N) is very small (<=9) and each transportation unit exists only in binary states (used or unused). Therefore, the overall state of transportation units can be represented using a bitmask. The i’th bit should be 1 if the i’th transportation unit has been used, and 0 if not. The size of the maximum number will be 2^N - 1 = 511 for subtask 4.

Hint 2

We come to a solution of DP[R][C][Bitmask]. DP[i][j][k] represents the maximum amount you can collect if you are currently at cell (i, j) and the state of transportation units is k. From each state, there are 5 possible steps in the worst case (don’t move, or move to any of the four other options). Therefore, the time complexity is R x C x Bitmask x 5.

Hint 3

Our previous complexity will pass for subtasks 1 and 2. However, subtask 3 requires something faster. Note that in a problem like this, the actual states you will visit are quite limited due to the fact that transitions are heavily constrained by the fact that you can use transportation units only once each (and there are only 9 of them). Using this property, we can try to only calculate states we actually visit. This can be easily achieved by writing a recursive function and then using memoisation, instead of a bottom-up approach. In order to memoise the states, use a map or unordered map.

Hint 4

For the final task you need to optimise your storage method (from map or unordered map). The only way to do this is to write a custom hash function. The details of this are out of the scope for this week, but feel free to refer to the editorial if you’re interested in learning it.

6.STTT

Hint 1

Any prime number p can only be a factor of at-most 1 subtree. Therefore, each prime number exists in a binary state of being used and unused. Furthermore, the number of prime numbers is quite small (Only the first 11 primes can be factors of numbers <= N).

Hint 2

For each node x, define DP[i][j][k] as the number of ways to place j coins in the first i children of x, such that their total mask is k.

Hint 3

In order to optimise the transition, define a matrix ans[N][N][Mask] where ans[i][j][k] represents the number of ways to place exactly j coins in the subtree of i such that the mask of the subtree is k.

Hint 4

Using ans, the transition is DP[i+1][coins+add][mask1 (Bitwise OR) mask2]+=DP[i][coins][mask1]∗ANS[child][add][mask2], if mask 1 and mask2 do not share primes.

Where

‘add’ is the number of coins in the child we are adding.

‘mask 2’ is the mask of coins in the child we are adding.

‘child’ represents in the child that we are adding.

Hint 5

Finally, after doing this for all children of node x, we should be able to update the ans table if you iterate over all possible number of coins and masks, and consider the possibilities of both placing a coin at node x, and not placing a coin at node x.

Hint 6

There are a number of intricacies and some additional optimisations required, so I’d recommend that you look over the editorial if you haven’t AC’d yet.

7.MCO16306

Hint 1

Let’s define DP[i][0] to be the length of the longest sequence (along with the number of sequences) ending at index i such that A(i) > A(i-1).

Let DP[i][1] be the same, expect for when A(i) < A(i-1).

Hint 2

For all j such that A(j) < A(i), DP[i][0] = max(DP[i][0], 1 + DP[j][1]).

The number of such sequences can be calculated by doing:

For all j such that A(j) < A(i) and DP[i][0] = DP[j][1] + 1, number_of_sequences[i][0] += number_of_sequences[j][1].

The same logic applies for DP[i][1], if you invert the 1s and 0s.

Hint 3

In order to optimise the transition, define a matrix ans[N][N][Mask] where ans[i][j][k] represents the number of ways to place exactly j coins in the subtree of i such that the mask of the subtree is k.

Hint 4

This O(N) transition can be optimised to O(LogN) by using a segment tree on a sorted array. Segment_tree(l, u) stores {maximum dp value in range (l, u), number of ways to achieve that dp value). If you build this segment tree on a sorted array, then DP(i) = query(0, i-1) + 1.

8.BLREDSET

Hint 1

Define a node to be “good” if it’s uncoloured and its removal results in at least one pair of red, black nodes that cannot reach each other. This can be calculated using a DFS in O(N). Note, a non root node x’s removal divides a tree into C+1 subtrees where C is the number of children node x has.

Hint 2

We want to find the number of uncoloured components that contain good nodes. Alternatively, we can find total_components - components_without_good_nodes.

Hint 3

To find the total number of components, DP(i, 0) represents the number of components in the subtree of i, not including i. DP(i, 1) represents the number of subtrees in the components of i, including i.

The recurrence is as follows:

For any node x with children c, over all children c(i):

DP(x, 0) = DP(x, 0) + DP(c(i), 0) + DP(c(i), 1)

DP(x, 1) = DP(x, 1) + DP(c(i), 1)*DP(x, 1)

DP(x, 0) is initially 0

DP(x, 1) is initially 1 if x is uncoloured and 0 otherwise

Hint 4

In order to find the total number of components without good nodes, simply recolour good nodes to black or red and then run the above dp again.

1 Like