Hello Codeforces!

Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, **INSOMNIA**, which is an ACM-ICPC style team programming contest of 3 hours duration held on CodeChef during its annual technical fest Avishkar. The team can consist up to 3 members.

**Contest Details**:

- Start Time:
~~Sunday, December 19, 2021, at 21:30 IST~~Monday, December 20, 2021, at~~21:30 IST~~22:00 IST. - Duration: 3 hours
- Contest Link: https://www.codechef.com/INSQ2021
- Languages allowed: C, C++14, C++17, Java, Python 3.6, PYPY, PYPY3.6.

Insomnia 2021 has 2 online rounds:

- First round will be held on Codechef and will be a qualifier round.
- Top Teams from First round will qualify for the Virtual Onsite round.

Total **INR 34700/-** and goodies from **Cuvette** and **Codechef** to grab. Top performers also stand a chance to interact with industry experts from **Groww, India**, and also get PPO and PPI opportunities.

For additional information refer to this brochure : https://bit.ly/InsomniaBrochure.

Problem setters are kesh4281, shubham732, CodenameGHOST, sakt_coder, ashu12_chi, mridul_bhatt, adyyy, swaster, nisiddharth.

Past few year's problemset: 2017, 2018, 2019, 2020.

We have an exciting problemset awaiting for you. Good luck and have fun!

**UPD: Contest shifted to Monday, December 20, 2021 at 21:30 IST due to clash with December Cook-off.**

**UPD: The contest is postponed by 30 mins and will begin at 22:00 hrs IST instead of 21:30 hrs IST.**

**UPD** : Congratulations to the global winners:

Team gennady.korotkevich

Team Money is ours ☭☭☭

Team acceptable

Does someone want to be my teammate?

why not?

Many contestants will be sleepy because of the timings.

Guess they aren't

insomniacsthen. :)What is Virtual Onsite round?

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.

So will that also take place on CodeChef?

~~Hackerearth~~updated belowIt will be on codechef only.

Can participants from outside India participate in the virtual onsite round?

How many teams will qualify? Checked out previous year's problemset, looking forward to being participating with my team!

TBD, but it'll surely be >50.

CodenameGHOST orz

mridul_bhatt orz

CodenameGHOST OTZ

mridul_bhatt OTZ

CodenameGHOST OTZ mridul_bhatt OTZ

CodenameGHOST orz

mridul_bhatt orz

Now send upvotes fast.

CodenameGHOST orz

mridul_bhatt orz

sakt_coder orz

nisiddharth orz

how many will be selected for second round

As said above, this will depend on the number of teams participating and is to be decided. The count will surely be >50.

Is It decided now?

Top 25 from out of MNNIT, 25 from MNNIT. Invites will be sent soon.

We haven't recieved invitation yet. Is it our fault in some way?

wtf, you should have mentioned above that among 50 there will be a reservation quota of 50% for MNIT. I just left in the midway of the contest assuming that rank will surely not exceed 50, as I was sleepy :( Whatever you are planning should be mentioned earlier.

Does teammates need to be from same college?

No. No such restriction.

Although there are

someMNNIT Internal prizes as well, and for that, the teams should be all MNNIT.how many problems would be there?

8

Someone please be my teammate, I have no friends

hi

It is clashing with december Cook off.

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

SpoilerAnd since you are from MNNIT, you can win college internal prizes as well :)

Yeah. For me the choice is clear but it'll surely lower the participation.

Hmm, CodeChef helped, and now will be on the 20th :)

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

Really Excited about this contest! Best of Luck to Everyone! :)

This contest clashes with December Cook-Off

UPDATE : Contest has been shifted to Monday, December 20, 2021 at 21:30 IST due to clash with December Cook-off.It is still clashing with codeforces div 3 #762.

As said on the CodeChef contest page, non-MNNIT teams have to

fill this formto be eligible for prizes.Very excited

Now, this contest is clashing with Codeforces Round #762 (Div. 3).

RequestIf it is possible to shift this contest to 22:30 or 23:00 IST, it would be just great! :)

OtherwiseAs a mnnitian, my choice is clear i.e.

Insomnia:)deletedI think the participation will be less then.

MemeDoes someone want to be my teammate?

It is Clashing with Codeforces Round #762 (Div 3), So please Its a humble Request to shift its time or date, as the participants will get diverted, please take care of the Contests atleast at Codeforces before finalising the dates.

It's an amazing event, attended it last time.

Why is it showing form link expired, when I am trying to register?

Now, it is working fine.

MNNIT Insomnia has been postponed to start from 10 PM IST. Those who wanted to give the contest can now join in after CF Div3.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!

We can't change the date anymore. We can only remove the direct collision with div 3. As far as 1 am is concerned, we feel 30 mins difference might not affect much.

Its clashing with few other contests. I guess another day would be the right choice.Just a suggestion, consider it if possible to postpone. We want to participate but don't want to be up so late nor can switch from codeforces at 10 pm.

Could you please confirm that the testcases of Problem String Again are correct?

+1

~~confirm~~correct!!+1

Thanks for the contest! We were not aware that we were expected to participate after having revised problems we had seen before, so as to be able to find/submit them quickly.

In Help Naman what to do when p and q are not co prime? Are we supposed to check the ratio after making them coprime? And what is the meaning of initially? initially, he has 0 painkillers and 0 medikits right? Please clarify?

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"

Can you please explain me on how to approach Help Naman problem?

It can be solved will a technique called Meet in the middle

I too thought of meet in the middle but wasn't successful in arriving at the full solution.

I first took 2 maps and stored all the subsets of n/2 elements in each of them.

map<pair<int,int>,int> mp1,mp2;

In the map, I stored the a:b in their simplified ratio ie a/gcd(a,b) and b/gcd(a,b) and their min cost.

After this I was not able to find a relation between 2 maps as in say I have 1:5 in first map and say, final required ratio is 2:3 . Then what ratio should I loop up for in mp2?

We can take 3:1 as (1+3):(5+1)=2:3 or we can take 5:4 as (1+5):(5+4)=2:3 or we can take 7:7 .

I noticed that the ratios form an Arithmetic Progression(A.P), but I was not able to proceed any further.

Can you please guide me on how to solve this using MEET IN THE MIDDLE concept?

Sure, the key observation is that the values are small, $$$ n \leq 40, s_i, t_i \leq 10 $$$, so $$$ \sum{}{s_i}, \sum{}{t_i} \leq 400 $$$. Actually because these values are small, you can use a 2D array or vector instead of a map, storing at $$$ dp_{ij} $$$ the minimum cost to get $$$ i $$$ painkillers and $$$ j $$$ medikits after processing the first half.

When processing the second half, when you reach a subset of numbers that add up to $$$ x $$$ painkillers and $$$ y $$$ medikits, you can actually brute force the other pair of values you are looking for. If the ratio is $$$ p : q $$$, you can brute for on $$$ r $$$ such that $$$ p \cdot r \geq x, q \cdot r \geq y $$$ and look at $$$ dp_{pr - x, qr - y} $$$ to check if the first half can build that pair of values. Because the values are small, it is easy to see that $$$ r \leq 400 $$$.

Total complexity is $$$ O(2 ^ {n / 2} \cdot (400 + n) ) $$$ .

Link to submission.

you can do simple knapsack dp as well as the constraints are very small

True, I went with Meet in the middle as soon as I saw the 40 in the input but knapsack works as well

I solved in $$$O(n*2^{n/2})$$$. I mainly used the fact that

lets say $$$f(a,b)= (a*q)-(b*p)$$$

So, for the first half i stored all the $$$f(a,b)$$$ for all subsets.

And for the second half for all subsets checked if $$$-f(a,b)$$$ was there in first half.

My submission

It feels like i have seen Follow the Hollow somewhere and ignored it then.

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.

Help Naman is identical to an AtCoder problem. I don't remember exactly which problem it is, but I remember we used the same problem for an internal club inductions contest.

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

AtCoder ABC054-D

How to solve "Follow the Hollow"? I was trying some N*50 dp but to no success.

Also, what was the intended complexity for the rain one? My $$$O(3^N*log(N))$$$ solution passed without any need for constant optimisation in 0.75s.

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.

Wow. I was scared to try $$$O(3^N*K)$$$. I calculated for each mask, the best way to cover it using $$$K = 1, 2, 4, 8$$$ and then combined the ones corresponding to set bits of given $$$K$$$. This should be bounded by $$$O(6*3^N)$$$ for given range of K.

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.

Any hints for Rain the pain problem?

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)

Can you guys make the problems available for practice? I'm sure a lot of people including me would want to upsolve... Also congrats, it was a nice contest! (apart from the removed question T-T)

May I please know what is the qualification criteria?

Will the editorial be released?

Follow the hollow + tours on tree

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

here

sakt_coder sorry for tag. But it is too late, is there any update on editorial?

sakt_coder Have you sent the invitation to the selected teams?

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

Sir, can i know the selected range.. our rank was 257 and didn't get any email..

See this

Contest page is only accessible with team handle. But team registration is only available for regular user accounts.

What should we do to register team properly?

UPD:

As I see, all teams were now registered by organisers.

BTW, be aware, starting time from the mail differs from the one on the contest page.

UPD2: contest time is fixed now.

Glad it worked. Also, the time should be fixed now (sorry).

Yes, I see that contest timer changed.

I'd be better if you change starting time in "Contest Details" too.

UPD: now it's fixed too.

we have to participate using team handle?

Yes, In order to provide the authentic ICPC experience, the Finals shall only be accessible through the team handle used in the qualifiers.

Ok cool, https://dmoj.ca/problem/bkoi11p5 many of the participants just copy pasted this and we wasted around 1hr. The constraints and sample input are same which means you intentionally copied this problem which is really too bad.

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

Finals