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.
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).
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)).
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.
Let A_0 = A and A_1 = A. Using the definitions of the A_i's yields the following formula:
A_n = (\prod_{k = 1}^{n - 1}A_k)^{2n - 1}.
Now just iterate from \verb!i = 1! to \verb!i = N! while keeping a prefix product, and add each term to a variable. Make sure you use modular exponentiation when computing these terms, or you may get the wrong answer. The runtime is \mathcal{O}(n\log(n)).
I related MINOPS with max sum subarray, for ever index that match will be -1 and that which don’t match will be 1. It tled but any one can tell me if approach was right or not?
TOWCNT : Can be done using concept of slope. Maintain min and max slope for both left and right lines. Only those lines whose tops are between these slope values will be visible. Now modify the min/max slope accordingly. Few more small things to be kept in mind, like the inputs for lines may not always be in sorted order of their x coordinates, etc.
Complexity = O(n^2)
Think for yourself what I mean, and if it doesn’t strike, reply here.
I haven’t attempted this one… Can you help me MINOPS… My solution TLE’d but I wanted to know if my approach was right or wrong solution link → CodeChef: Practical coding for everyone