Solved — 3 (A, B, C) Upsolved — 1 (D)

Problem A: Naively we cannot iterate on n as n ≤ 10 ** 9

Let: i mod 3 = i mod 5 = x

⇒ x = i mod 3 and x = i mod 5 ⇒ x = i mod (15) [Chinese Remainder Theorem you can think]

⇒ x = i mod (15) should be 0, 1, 2 ……. as 3 < 5 we cannot have 3, 4

⇒ just compute how many times numbers of the form 15k, 15k + 1, 15k + 2 come in interval [0, n]

⇒ number of complete 15 number blocks = n // 15 and size of last (partial) 15 group = n % 15 + 1

⇒ just compute: ans := (n // 15) * 3 + min(3, n % 15 + 1)

Problem B: Naively cannot simulate the given algorithm as k ≤ 10 ** 18 But seeing as n ≤ 2 * 10 ** 5, we can see an O(n) solution maybe

Observation: in given string, at an index i, if count(L) becomes equal to x + count(R), we have reached origin and then as per the problem, we have to start back from index 0 in given string

⇒ this means that we are going to keep doing this cyclically until the time is up.

thus we need to traverse the given string, keeping track of counts of L and R, find first occurence i where this event happens.

then our remaining time is k — i

now start again from beginning, and see how much time for one cycle, j j will be the index where count(L) becomes equal to 0 + count(R) … we started from 0 this time instead of x

thus we can say (k — i) // j cycles ⇒ (k — i) // j times 0 position is seen

thus ans := 1 (for first time we saw 0) + (k — i) // j is our answer.

just take care of these edge cases where u

cant find valid i ⇒ you never saw a 0. therefore ans := 0 cant find valid j ⇒ once you see a 0 for first time, you never see it again. therefore ans := 1

Problem C: We have to find minimum penalty, where penalty is computed as the maximum of the penalty values of each individual cell which is incorrectly painted.

Reading “minimise the maximum” ⇒ Binary search on the minimum penalty value (the answer) (striver the goat)

search space: [0, max(penalty array)] → we could paint everything correctly, or all of them inverted and get the max penalty of all of them. see that as max(penalty) ⇒ 10 ** 9, our solution will work in O(log(max(penalty)) * n) == O(log2(10 ** 9) * n) == O(30 * n), thus it is acceptable

check() logic: runs in O(n) time

now say we fixed a value of mid in our binary search, we want maximum of all penalties we get to be ≤ mid and we need to paint ≤k subarrays Since our max penalty is mid, every cell whose penalty is > mid has to be colored correctly

Thus the situation could be like (have_to array): RRXXXXBBRBXXXBXXR where X means we dont care what we paint that cell as it has penalty ≤ mid, but rest of them have to be painted correctly

thus the number of subarrays (segments) in the have_to array which have all blues has to be ≤ k (max number of operations that we can do) for this particular value of mid to be acceptable i.e check() returns true.

now we just need to compute the number of subarrays of all only blues or X (or we can also say number of contiguous blocks consisting only of B’s or X’s). This can be done in linear time using a two-pointer approach.

Problem D: this is very intuitively a DP problem as we are asked to count number of valid sequences and we construct each sequence one by one element by element.

we can think like this: if we already have a sequence a b c d e _. in place of underscore we can only put nodes i where level(i) = level(e) + 1 and parent(i) ≠ e. thus dp value of placing k = sum of dp values of all vertices at one level above it and which are not parent of k. this intuition while correct, is too slow as for every vertex (n choices), we are doing a summation of upto n nodes in previous level… thus its O(n**2)

instead → “invert the problem”: dp[i] = number of valid sequences which are ending at i now, dp[i] = sum(dp[k] where level[k] = level[i] — 1) — dp[parent[i]] also notice that we will have to compute the dp values in level by level order as we are dependent on lesser level dp values for our current dp value.

to eliminate the summation, we can precompute the sum of all dp values at a particular level (transition optimisation) in an array called tot.

tot[i] = sum(dp[k] where level[k] == i)

then, dp[i] = tot[i — 1] — dp[parent[i]]

note: for nodes whose parent is the root node, dp[i] = tot[i — 1] — 0

thus the transition time complexity is O(1) and the number of states are O(n) thus, time complexity of our approach is O(n) per testcase.

Base case: dp[1] = 1 as root has only 1 sequence where we end at root tot[0] = 1 as tot means sum of all dp values of nodes at level 0 (only the root)

Final subproblem: sum(dp[i] for all i)… as our sequence can choose to end wherever it wants, just add up all the ways

implementation: adjacency list repr, and use DFS/BFS for computing level of each node. then simple tabulation for dp, also modular arithmetic has to be done as per problem