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

Автор GreedyMind, 5 лет назад, По-английски

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:

For the online round, top few global and top few MNNIT teams will get Codechef goodies. For the onsite round, prizes worth 31000 INR to be won. Top Indian teams from the online round will be called for the onsite round to be held at MNNIT Allahabad.

Banner

Problem setting panel includes chinmay0906, smtcoder, GreedyMind (myself), ram_24, xian02, gamer_coder13, acIN1go, ayushghd and mayankrana00.

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

Join our Facebook event for further information.

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

UPD1: The contest was extended by 30 mins.

UPD2: Congratulations to the global winners:

  1. Team Brain_drain (Amoo_Safar, Mobed, ItsRyuk)

  2. Team CPU (Umi, tieunhi, rhymastic)

  3. Team PaduKeDeewane (hitman623, _shanky, Enigma27)

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

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

Previous year problem statements are really good.

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

I m scared that servers may go down :(. I wish it was on Codeforces.

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

Bump! The contest begins in a day.

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

Are there any travel reimbursements for teams going to Onsite?

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

So how many top global teams will get Codechef goodies exactly?

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

    That depends on the number of teams registering for the contest. Last year top 2 Global teams and top 2 MNNIT teams got the CodeChef laddus.

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

10 minutes to go, 1000 teams already registered.

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

How to solve "zero the path"?

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

    Ok so firstly we observe that that the question is equvalent to finding the maximal path but you can throw away the values in the middle. We can do a DP on tree but we need to memo a few things.

    Firstly, lets consider 3 types of path. A full path is a path where you traverse down and take eveerything until a certain point. A bottom path is when you have a full path buy your zeroed path must end at the node you are computing for. A split path is when you have a path where you have an arbituary segment that is zeroed. It turns out you can compute these three things in O(1) based on the values of your children.

    Now to compute the maximal path that involves you and your subtree you must consider the 2 best full path of your children and your value, 1 full path and 1 split path, and 2 bottom paths.

    If you compute everything for each node the maximum of those is your answer.

    I cant explain this very well so ill link my code.

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

Problem Bonds is exact copy of problem B from Grand Prix of Japan XVII OpenCup (for those who have opentrains login: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001489 )

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

How to solve Triangles problem:)

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

    Answer is min(8, n+2).

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

    Given N triangles, there will be N + 2 vertices and let there be S edges, we need to travel atleast S - 1 edges. If you observe, one can only travel all the S edges without repeating any edge if one starts from the top left vertex or the bottom right vertex of the structure formed. So the answer is always greater >= 2.

    Now, it is easy to understand that if we start from the vertices directly connected to any of these 2 vertices through an edge, we can always travel atleast S - 1 edges since we could travel S edges starting from those 2 vertices. Hence, the required answer is 2 + the number of such vertices. For N <= 6, the number of such vertices is N. Hence, the answer is N + 2.

    For N > 6, there are only 6 such vertices (3 each connected to top left and bottom right vertex). So, the answer is 6 + 2 = 8.

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

How to solved Bonds?

I did the following approach cannot find what is wrong in that.

  1. The total number of components with odd number of vertices should be exactly 1.

  2. For that odd component if a vertex is cut vertex then now all new forming components should be even size.

My Code: Link

Accepted code of someone else with a similar type of logic:

I looked at this code but was not able to understand that for a Cut vertex, why they considered the size of last new-formed component only instead of all new-formed components.

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

    That's our code. We considered only the last one because for a cut vertex, there are exactly two newly formed components.

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

      Yeah so why you did not check both of them and checked only 1 instead?

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

        The size of the component is odd, so if we remove one vertex and know that one part is even, then the other one is necessarily even because subtracting an even number from an even number produces an even number

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

How many teams would be selected for the onsite round?

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

Problems were really good, you could have organised a Div2 on CF.

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

Can someone share promblems like https://www.codechef.com/INQU2019/problems/INQU1904 Thank you

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

will editorials be posted?

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

Nice problem set! :)

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

Great contest!! What was the approach to the last problem?

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

    Main catch was to sort the toys according to their velocity, then to find the range in which each toy will immune others on getting immuned,and finally find the best intersection of ranges that cover all and demand least energy. Problem setter will upload editorial shortly in more detail.

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

Any info about date and time of onsite round?

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

The first problem was very similar to: https://mirror.codeforces.com/problemset/problem/579/A

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

where are the editorials?

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

Where are the editorials of the contest ??