Guess they aren't insomniacs then. :)

The final round was supposed to be an onsite round on our college campus, but due to covid, we're conducting it virtually this year.

TBD, but it'll surely be >50.

CodenameGHOST OTZ
mridul_bhatt OTZ

how many will be selected for second round

No. No such restriction.

Although there are some MNNIT Internal prizes as well, and for that, the teams should be all MNNIT.

Insomnia has prizes :D. It is powered and sponsored by CodeChef.

No it was clashing with cook off earlier, now it is clashing with codeforces div 3

deleted

Now, it is working fine.

IMO there are very few who are gonna attend 2 contests sitting 5 hours straight. So taking INSOMNIA until 1am is going to have a negative impact on the participant count. I might be wrong, but kindly consider this as a suggestion. Cheers!

+1

confirm correct!!

I think you can divide both of them by their gcd and ignore the "Initially p & q may not be coprime" part. At least I got accepted taking that into consideration. My guess is that line is intented to mean "They are not necessarily coprime at first but (if you take the gcd) you can make them coprime"

Same, I have also seen it somewhere.

Maybe this problem?

Not exactly the same, the USACO problem has a greedy solution, but the DP solution works for both problems.

One of our clubs used the same problem for an in-college contest as well.

AtCoder ABC054-D

I passed $$$\mathcal{O}(3^N \cdot N)$$$ easily. Where does $$$\log(N)$$$ come from?

UPD: I see similarity with fast exponentiation. That's how $$$\log(N)$$$ can be achieved.

I passed with N*50 dp. dp[i][val] = such j that subarray[i,j] on performing operations reduces to val (val <= 50). And then an extra 1-d dp to calculate the minimum sum on prefixes.

Due to the constraint on $$$ a_i $$$ you can prove that if you start doing operations on index $$$ i $$$, you can make at most $$$ O(30 + log n) $$$ operations. So at every index $$$ i $$$ you can compute a set of pair of values $$$ (d, j) $$$ where $$$ d $$$ is the value you can make by using all numbers from $$$ i $$$ to $$$ j $$$. This set of values is less than 60 by the first observation.

How do we compute that? If we are at index $$$ i $$$, we know for sure we can make value $$$ a_i $$$ by using all values from $$$ i $$$ to $$$ i $$$ (We have pair $$$ (a_i, i) $$$). To check if we can make value $$$ a_i + 1 $$$ we can check if we can make the value $$$ a_i $$$ at index $$$ i + 1 $$$ and if we can (let $$$ (a_i, j) $$$ be that pair ), we will have another pair of values $$$(a_i + 1, j) $$$. In general, to check if we can make value $$$ d + 1 $$$, we consider the last index we used to make value $$$ d $$$ (let it be $$$ last $$$) and we check if we can make the value $$$ d $$$ at index $$$ last + 1 $$$ as well. You can compute all the possible pairs for every index $$$ i $$$ going from right to left.

Then you can think of this a graph where if you are at index $$$ i $$$ and have the pair $$$ (d, j) $$$, you can go to index $$$ j + 1 $$$ with a cost of $$$ d $$$ as you will make that number using all numbers from $$$ i $$$ to $$$ j $$$ and continue with the rest of the array. Then it's just computing minimum cost to reach the end of the array. I used dijkstra but a standard dp can be run as well

We can solve the more general version of "Follow the Hollow" (that is without $$$A_i \leq 30$$$) using This.

dp[mask][k] = minimum cost to cover elements in mask with at most k rectangles. can be evaluated by submask enumeration. (for a particluar mask, cost to fill it with one rect = (max y in the mask — min y in the mask + 1) * (max x in the mask — min x in the mask + 1)

Is there any official editorial for the "Follow the Hollow" USACO problem? If so could you please share the link?

All invite mails have now been sent to the team leaders. Please check inbox as well as spam.

I'm confused, which problem are you talking about? Was it in the Finals or Qualifiers?