Блог пользователя sakt_coder

Автор sakt_coder, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Many contestants will be sleepy because of the timings.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is Virtual Onsite round?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    how many will be selected for second round

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Is It decided now?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +19 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does teammates need to be from same college?

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It is clashing with december Cook off.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

Request
Otherwise
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Meme
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does someone want to be my teammate?

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -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.

»
3 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
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?

  • »
    »
    3 года назад, # ^ |
    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"

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 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<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?

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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.

        My submission

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
    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.

    • »
      »
      »
      3 года назад, # ^ |
      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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hints for Rain the pain problem?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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)

»
3 года назад, # |
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)

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

May I please know what is the qualification criteria?

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Will the editorial be released?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

sakt_coder Have you sent the invitation to the selected teams?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      we have to participate using team handle?

»
3 года назад, # |
  Проголосовать: нравится +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.