sakt_coder's blog

Invitation to Insomnia Qualifier 2021
By sakt_coder, 3 years ago, In English

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, swalen, 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 gennady.korotkevich

  2. Team Money is ours ☭☭☭

  3. Team acceptable

  • Vote: I like it
  • +75
  • Vote: I do not like it

Comments Comments (89)
| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Many contestants will be sleepy because of the timings.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is Virtual Onsite round?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

CodenameGHOST orz
mridul_bhatt orz

→ Reply
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

sakt_coder orz

nisiddharth orz

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    how many will be selected for second round

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is It decided now?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +19 Vote: I do not like it

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

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +36 Vote: I do not like it

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does teammates need to be from same college?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. No such restriction.

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

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It is clashing with december Cook off.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Spoiler
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As said on the CodeChef contest page, non-MNNIT teams have to fill this form to be eligible for prizes.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

Request
Otherwise
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Meme
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does someone want to be my teammate?

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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"

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        My submission

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, I have also seen it somewhere.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe this problem?

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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 5   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for Rain the pain problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

May I please know what is the qualification criteria?

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will the editorial be released?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Follow the hollow + tours on tree

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sakt_coder Have you sent the invitation to the selected teams?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we have to participate using team handle?

      → Reply
»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

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.

→ Reply