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

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

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
    • Проголосовать: нравится
    • +138
    • Проголосовать: не нравится

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

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

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

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

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

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

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

    Prizes/Goodies?

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

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

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

    how many teams will qualify for the next round?

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

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

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

    A contest worth participating , Great problems in past years.

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

    Will an editorial be posted?

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

      We will try to post it as soon as possible.

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

        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.

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

        How later will be soon?

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

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

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

    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.

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

      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.

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

      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

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

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

    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 .

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

    Can someone explain how to solve Nearest Strong City?

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

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

      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?

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

      Link for the editorial to this problem.