April Cook-Off 2020 Discussion

April Cook-Off 2020

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.


Problem Link


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).

AC Submission


Problem Link:


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)).

AC Submission


Problem Link :


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.

AC Submission

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!


How to do MINOPS?



Why this solution fails?

Please explain MATBREAK.

MATBREAK Solution:

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)).

1 Like

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?

Refer to solution - > CodeChef: Practical coding for everyone

how to do minops??

but how would you keep a track of number of operations this way, or we don’t need them that is the case ?


can someone help me to find out the error??

See this solution → CodeChef: Practical coding for everyone

When will the Submit button be activated for MATBREAK?

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.

1 Like

For KARRAY, can anyone help me figure out my idea goes wrong?

  • First of all, G(i, j) is just i XOR j.

  • If we consider the value added from a position x to a position y for the ith bit:

  1. If both have the same bit state, then there is no contribution.

  2. If they have different bit states, then 2i * ay is added to ax.

  • Therefore, we only need to store the sum for a given bit i for each of its states.

  • Now the next year the sum for the ith bit in the on state is just 2i into sum of off state and vice-versa. Repeat this k times.

  • Add the corresponding sums for bits to the original number

I suspect the mistake is in the second last step but I can’t seem to prove or disprove it, can anyone help?

Edit: Also have rating changes updated only on discuss but not the main site ? I’m 6 star on the normal site, but 5 star here.

1 Like

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

My Solution
I did Exactly the Same thing,But Why I got Wrong Answer.

I hope that the sample test cases must be clearer for a better understanding of problem .

1 Like

This post was flagged by the community and is temporarily hidden.

I thought this approach too, but O(n^2) solution wouldn’t mean 4e8 operations, leading to >1 second time limit?

Please help me with my solution for MINOPS, I can’t figure out why it is giving WA.