sakt_coder's blog

By sakt_coder, 7 weeks 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, 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 gennady.korotkevich

  2. Team Money is ours ☭☭☭

  3. Team acceptable

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does someone want to be my teammate?

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Many contestants will be sleepy because of the timings.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is Virtual Onsite round?

  • »
    »
    7 weeks 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.

»
7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it
»
7 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    how many will be selected for second round

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is It decided now?

        • »
          »
          »
          »
          »
          5 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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?

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does teammates need to be from same college?

  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Someone please be my teammate, I have no friends

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

It is clashing with december Cook off.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Spoiler
    • »
      »
      »
      6 weeks 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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest clashes with December Cook-Off

»
6 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is still clashing with codeforces div 3 #762.

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very excited

»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
Meme
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does someone want to be my teammate?

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks 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?

»
5 weeks 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.

  • »
    »
    5 weeks 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!

    • »
      »
      »
      5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +38 Vote: I do not like it

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

»
5 weeks 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.

»
5 weeks 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?

  • »
    »
    5 weeks 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"

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks 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

        • »
          »
          »
          »
          »
          5 weeks 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?

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

          • »
            »
            »
            »
            »
            »
            5 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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

      • »
        »
        »
        »
        5 weeks 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

»
5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, I have also seen it somewhere.

  • »
    »
    5 weeks 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.

»
5 weeks 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.

»
5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for Rain the pain problem?

  • »
    »
    5 weeks 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)

»
5 weeks 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)

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

May I please know what is the qualification criteria?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Will the editorial be released?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sakt_coder Have you sent the invitation to the selected teams?

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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..

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we have to participate using team handle?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  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.