Let’s create a discussion page of April Cookoff, 2020 where you can ask for doubts regarding how to solve a question or why your solution fails. Rather than

creating separate posts for each of your doubts to prevent less spam.

I was able to solve the first 3 questions of Div2.

Here is a quick explanation and my solutions.

## LIFTME

## Explanation

Just simulate whatever is told in the question.

Easiest way is to let currHgt = 0.

then add in ans += abs(f - d) and ans += (currHgt - f).

and after i’th iteration. change currHgt = d (ending point of this person).

So, time complexity → O(N).

## MATBREAK

## Explanation

If we observe,

p1 = a^1 and after 1st iteration, our new ‘a’ will be a = a * p1. (1 cell gets changed)

p2 = a^3. and similarly, after 2nd iteration, our new a = a * p2. (3 cells gets changed)

p3 = a^5. and so on until N’th iteration.

And while taking a^x. You can use binary exponentiation to find it in log(x).

So, time complexity → O(N*log(N)).

## MINOPS

## Explanation

You can view the question as to if I have to do only x operations, then what will be the minimum cost to make string S equal to R.

So our answer then will be the minimum of all the x operations from 1 to N.

Now, so how to find the minimum cost for a particular operation?

## Observation 1

For a bunch of consecutive characters of string that are not equal, it will be optimal to use one operation to make that group equal.

## Observation 2

You can observe your string as consecutive characters as,

(Matching)(Non_matching)(Matching)(Non-matching)… so on.

## Observation 3

Now let us observe how to get an answer for a particular operation.

Consider L: First index where we found a different character.

and R: Last index where we found a different character.

So we are concerned about our string in [L:R].

and let Len = R - L + 1.

For Using only 1 operation: ans = len * 1.

Using 2 operations: We need to remove the 1 largest block of the Non-matching group. So we can have two operations. And if you observe this will be a minimum cost of making string equal if we use 2 operations.

ans = (len - Largest1) * 2.

SImilarly for using 3 operations: We need to make 3 partitions, so we need to remove 2 largest blocks. So

ans = (len - Largest1 - Largest2) * 3.

and so on you can simulate the process for each and print answer as minimum among all.

## How to get first k maximum sum in O(1)?

You can maintain prefix sum.

How to solve TOWCNT?

**UPD**: Added explanation for MINOPS.

You can ask me in comments if you have any queries in my approach.

Thank you!