### sakt_coder's blog

By sakt_coder, 7 weeks ago,

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
• 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:

1. Team acceptable

• +75

 » 7 weeks ago, # |   0 Does someone want to be my teammate?
•  » » 7 weeks ago, # ^ |   0 why not?
 » 7 weeks ago, # |   +4 Many contestants will be sleepy because of the timings.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +23 Guess they aren't insomniacs then. :)
 » 7 weeks ago, # |   0 What is Virtual Onsite round?
•  » » 7 weeks ago, # ^ |   0 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.
•  » » » 7 weeks ago, # ^ |   0 So will that also take place on CodeChef?
•  » » » » 7 weeks ago, # ^ | ← Rev. 3 →   +1 Hackerearthupdated below
•  » » » » » 6 weeks ago, # ^ |   0 It will be on codechef only.
•  » » » 7 weeks ago, # ^ |   0 Can participants from outside India participate in the virtual onsite round?
 » 7 weeks ago, # |   0 How many teams will qualify? Checked out previous year's problemset, looking forward to being participating with my team!
•  » » 7 weeks ago, # ^ |   0 TBD, but it'll surely be >50.
 » 7 weeks ago, # |   +10
•  » » 7 weeks ago, # ^ |   +12
•  » » » 7 weeks ago, # ^ |   +12
•  » » » » 7 weeks ago, # ^ |   +9
•  » » » » » 5 weeks ago, # ^ |   +36 Now send upvotes fast.
•  » » » » » » 5 weeks ago, # ^ |   +2
 » 7 weeks ago, # |   -11 sakt_coder orznisiddharth orz
•  » » 7 weeks ago, # ^ |   +5 how many will be selected for second round
•  » » » 7 weeks ago, # ^ |   0 As said above, this will depend on the number of teams participating and is to be decided. The count will surely be >50.
•  » » » » 5 weeks ago, # ^ |   0 Is It decided now?
•  » » » » » 5 weeks ago, # ^ |   0 Top 25 from out of MNNIT, 25 from MNNIT. Invites will be sent soon.
•  » » » » » » 4 weeks ago, # ^ |   +19 We haven't recieved invitation yet. Is it our fault in some way?
•  » » » » » » 4 weeks ago, # ^ |   +36 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.
 » 6 weeks ago, # |   0 Does teammates need to be from same college?
•  » » 6 weeks ago, # ^ |   0 No. No such restriction.Although there are some MNNIT Internal prizes as well, and for that, the teams should be all MNNIT.
•  » » » 6 weeks ago, # ^ |   0 how many problems would be there?
•  » » » » 6 weeks ago, # ^ |   0 8
 » 6 weeks ago, # |   -12 Someone please be my teammate, I have no friends
•  » » 5 weeks ago, # ^ |   0 hi
 » 6 weeks ago, # |   +11 It is clashing with december Cook off.
•  » » 6 weeks ago, # ^ |   0 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 :)
•  » » » 6 weeks ago, # ^ |   0 Yeah. For me the choice is clear but it'll surely lower the participation.
•  » » » » 6 weeks ago, # ^ |   0 Hmm, CodeChef helped, and now will be on the 20th :)
•  » » 5 weeks ago, # ^ |   +5 No it was clashing with cook off earlier, now it is clashing with codeforces div 3
 » 6 weeks ago, # | ← Rev. 2 →   0 Really Excited about this contest! Best of Luck to Everyone! :)
 » 6 weeks ago, # |   0 This contest clashes with December Cook-Off
 » 6 weeks ago, # |   +4 UPDATE : Contest has been shifted to Monday, December 20, 2021 at 21:30 IST due to clash with December Cook-off.
•  » » 5 weeks ago, # ^ |   0 It is still clashing with codeforces div 3 #762.
 » 6 weeks ago, # |   0 As said on the CodeChef contest page, non-MNNIT teams have to fill this form to be eligible for prizes.
 » 6 weeks ago, # |   0 Very excited
 » 6 weeks ago, # | ← Rev. 4 →   0 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 :)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » 6 weeks ago, # ^ |   -7 I think the participation will be less then.
 » 6 weeks ago, # |   +1 Meme
 » 5 weeks ago, # |   0 Does someone want to be my teammate?
 » 5 weeks ago, # |   +13 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.
 » 5 weeks ago, # |   0 It's an amazing event, attended it last time.
 » 5 weeks ago, # |   +10 Why is it showing form link expired, when I am trying to register?
•  » » 5 weeks ago, # ^ |   -8 Now, it is working fine.
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ |   +2 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!
•  » » » 5 weeks ago, # ^ |   -8 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.
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # |   +38 Could you please confirm that the testcases of Problem String Again are correct?
•  » » 5 weeks ago, # ^ |   +21 +1
•  » » 5 weeks ago, # ^ |   +44 confirm correct!!
•  » » 5 weeks ago, # ^ |   -14 +1
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   +6 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?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 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"
•  » » » 5 weeks ago, # ^ |   0 Can you please explain me on how to approach Help Naman problem?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 It can be solved will a technique called Meet in the middle
•  » » » » » 5 weeks ago, # ^ |   0 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,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?
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 5 weeks ago, # ^ |   0 you can do simple knapsack dp as well as the constraints are very small
•  » » » » » » » 5 weeks ago, # ^ |   0 True, I went with Meet in the middle as soon as I saw the 40 in the input but knapsack works as well
•  » » » » 5 weeks ago, # ^ |   0 I solved in $O(n*2^{n/2})$. I mainly used the fact that $\frac{a+s} {b+t}=\frac{p}{q} => (a*q)-(b*p) = -((s*q)-(t*p))$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.
 » 5 weeks ago, # |   0 It feels like i have seen Follow the Hollow somewhere and ignored it then.
•  » » 5 weeks ago, # ^ |   0 Same, I have also seen it somewhere.
•  » » 5 weeks ago, # ^ |   0 Maybe this problem?Not exactly the same, the USACO problem has a greedy solution, but the DP solution works for both problems.
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ |   0 One of our clubs used the same problem for an in-college contest as well.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # | ← Rev. 3 →   0 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +16 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 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.
•  » » 5 weeks ago, # ^ |   +13 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.
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +8 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
•  » » 5 weeks ago, # ^ |   +8 We can solve the more general version of "Follow the Hollow" (that is without $A_i \leq 30$) using This.
 » 5 weeks ago, # |   0 Any hints for Rain the pain problem?
•  » » 5 weeks ago, # ^ |   0 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)
 » 5 weeks ago, # | ← Rev. 2 →   +8 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)
 » 5 weeks ago, # |   +10 May I please know what is the qualification criteria?
 » 5 weeks ago, # |   +3 Will the editorial be released?
 » 5 weeks ago, # |   0
•  » » 5 weeks ago, # ^ |   0 Is there any official editorial for the "Follow the Hollow" USACO problem? If so could you please share the link?
•  » » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 sakt_coder sorry for tag. But it is too late, is there any update on editorial?
 » 4 weeks ago, # |   0 sakt_coder Have you sent the invitation to the selected teams?
•  » » 4 weeks ago, # ^ |   0 All invite mails have now been sent to the team leaders. Please check inbox as well as spam.
•  » » » 4 weeks ago, # ^ |   0 Sir, can i know the selected range.. our rank was 257 and didn't get any email..
•  » » » » 4 weeks ago, # ^ |   0 See this
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » » 4 weeks ago, # ^ |   0 Glad it worked. Also, the time should be fixed now (sorry).
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 4 weeks ago, # ^ |   0 we have to participate using team handle?
•  » » » » 4 weeks ago, # ^ |   0 Yes, In order to provide the authentic ICPC experience, the Finals shall only be accessible through the team handle used in the qualifiers.
 » 4 weeks ago, # |   +77 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.
•  » » 4 weeks ago, # ^ |   -8 I'm confused, which problem are you talking about? Was it in the Finals or Qualifiers?
•  » » » 4 weeks ago, # ^ |   -8 Finals