kesh4281's blog

By kesh4281, history, 4 years ago, In English

Hello Codeforces!

Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, ɪɴᴤᴏᴍɴɪᴀ, 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: Saturday, October 17, 2020, at 21:30 IST
  • Duration: 3 hours
  • Contest Link: https://www.codechef.com/INSO2020
  • Languages allowed: C, C++, Java and Python.

    This year we will be having 2 online rounds. First round will be held on codechef and will be a qualifier round. Top Teams from first online round will be qualified for Virtual Onsite round.

    Update:1

    Prizes: For the online round, Top few global teams will get Codechef goodies. For the virtual onsite round, prizes worth 31000 INR to be won.

    Insomnia Qualifier 2020

    Problem setting panel includes chinmay0906, smtcoder, kesh4281, shubham732, rahulgupta33441, Vivek_Rathi_53, gaurav_2000, rajgarg150873, linesekarenge, kunalanand241, gvshukla321, PrixFiesta, and fauji.

    Past few year's problemset: 2016, 2017, 2018, 2019

    Join our Facebook event for further information.

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

    UPD2: Congratulations to the global winners:

    1. Team AlphaZ : kal013

    2. Team FailedLogicians : gokul.raj , sudoBug, srinivas1999

    3. Team HullCut Jawani : nitixkrai, acraider, fsociety00

    UPD3: Editorial Links

  • INQU2000 — Mah Queen
  • INQU2001 — Musical Chairs
  • INQU2002 — By Hook or By Crook
  • INQU2003 — Biggest Pallindrome
  • INQU2004 — ShareIT
  • INQU2005 — Nearest Strong City
  • INQU2006 — Growing Xor Tree
  • INQU2007 — Connect Coordinate
    • Vote: I like it
    • +138
    • Vote: I do not like it

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

    Auto comment: topic has been updated by kesh4281 (previous revision, new revision, compare).

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

    Auto comment: topic has been updated by kesh4281 (previous revision, new revision, compare).

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

    Auto comment: topic has been updated by kesh4281 (previous revision, new revision, compare).

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

    Prizes/Goodies?

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

    Last year problem sets were very challenging. Excited for this year problem set.

    »
    4 years ago, # |
      Vote: I like it +20 Vote: I do not like it

    how many teams will qualify for the next round?

    • »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Top 15 Indian teams will be selected for the onsite round.

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

    Submissions can be made from team handle only? Or it can be made through any member's handle also?

    »
    4 years ago, # |
      Vote: I like it +14 Vote: I do not like it

    A contest worth participating , Great problems in past years.

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

    Will an editorial be posted?

    • »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      We will try to post it as soon as possible.

      • »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Alright, thanks. I asked because, there aren't any editorials posted for any of the previous contests. So I doubt an editorial will be posted, but it would be helpful if you could prepare editorials beforehand if possible and post it later.

      • »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        How later will be soon?

        • »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Editorials for all the questions are posted on codechef discussion platform.

    »
    4 years ago, # |
      Vote: I like it +20 Vote: I do not like it

    Hurry up! 730+ teams have already registered. Contest begins in less than 45 mins. All The Best!!

    »
    4 years ago, # |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    How do you solve Musical Chairs? We spent the last hour on this problem but were unable to think of any way to cleanly code it. It felt like just maintaining the segments but it didn't feel like there was a simple way to eliminate the case work.

    • »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Hello, Problem Setter for this question here,
      Editorial will be out soon but anyway I'll share the basic idea. I think you already know you have to somehow manage the segments. Well the answer was simply modular arithmetic and recursion.

      Think of it this way :

      Each round and its next round can be seen as a transition between three parameters.
      1) Round No : $$$i$$$ , to track some edge cases for the most part, becomes $$$i+1$$$
      2) No of chairs in current round $$$m$$$ , becomes $$$\lfloor m/2 \rfloor$$$
      3) No of people in current round $$$n$$$ , becomes $$$m$$$

      Let's say we recursively get to know that a subproblem for the next round will grant $$$X$$$ as the winner. We pickup the fact that the next round was formulated after rotation by $$$T_i$$$ positions. So the winner $$$X$$$ here was someone who was at a position $$$X$$$ from the perspective of person $$$0$$$/$$$1$$$(index ambiguity, basically the person with the first chair) after circling in this round. So , the real identity of $$$X$$$ has been revolving around in the round and we basically will have to undo that . Thus, for this round , in the recursion unpacking phase, we can return our winner by going back $$$T_i$$$ positions.

    • »
      »
      4 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      We did it using intervals ... Maintain vector of plausible intervals and keep on elimnating in every step ... Probably use 1 vector for odd turns and 1 for even and keep on switching could be one way

    • »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +17 Vote: I do not like it

      My approach was :

      I gave position one to winner after last round, then I found where he was in the previous round using basic maths and updated the position. Did this until first round and that position was the answer.

      ll pos=1;
      ll length=1;
      for(ll i=ii-1;i>=0;i--){
          length=vv[i];
          ll left=t[i];
          left%=ww[i];
          ll temp=pos;
          if(left>=pos){
              pos=ww[i];
              left-=temp;
          }
          pos-=left;
      }
      cout<<pos<<"\n";
      
    »
    4 years ago, # |
      Vote: I like it +19 Vote: I do not like it

    Although our team managed to get only 1 correct , we really enjoyed the contest. Motilal hosts the best contest among all NITs , if not the best in India. Thank u guys <3 .

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

    Can someone explain how to solve Nearest Strong City?

    Problem link : https://www.codechef.com/INSO2020/problems/INQU2005

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

      So I understand that bridges are weak roads which needs to be removed. But how to calculate "For each weak city, find out the distance to nearest strong city".

      How do you do multi source shortest path in weighted graph?

    • »
      »
      4 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Link for the editorial to this problem.