CCC '10 S4 - Animal Farm

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2010 Stage 1, Senior #4

You are running a farm which has N (1 \le N \le 100) animals. You went to the store and bought M = N pre-made pens that will house your animals. Pens satisfy the following conditions:

  • pens have between 3 and 8 edges;
  • an edge that is specified by two pens connects the two pens;
  • an edge that is specified only once connects that pen to the outside;
  • there is exactly one animal in each pen and no animals outside the pens, initially.

The animals, however, have a game they like to play called "Escape from the pen." They assign a cost to each edge of the pen, and they determine the minimum cost for all of the animals to meet in the same area by trampling over the edge of various pens. The animals may meet inside a particular pen or outside of all the pens. Also note that once an edge has been trampled, any animal may pass over it without incurring any cost.

You will be given a description of the pens, along with the placement of animals, and you are to figure out what the smallest cost is to move all the animals into the same area.

Input Specification

The first line of input will be the integer M, the number of pens. On the next M lines, there will be a description of each pen, with one description per line. The description is composed of three components, with each component separated by one space, as follows:

  • the first component is an integer e_p (3 \le e_p \le 8), which describes the number of edges for this particular pen p;
  • the second component is a sequence of e_p integers describing the corners of each pen, where each integer is less than or equal to 1\,000;
  • the third component is a sequence of e_p integers describing the cost of each edge, where each integer is less than or equal to 5\,000.

For the corner and edge cost description, the descriptions are given in cyclical order. For example, the following description of a pen

\displaystyle 3\ 1\ 2\ 3\ 7\ 4\ 6

means that there are three corners, and thus, three edges, where the edge (1, 2) has cost 7, the edge (2, 3) has cost 4 and the edge (3, 1) has cost 6. Note: at least 20% of the marks for this question have N \le 10 and no pen will have more than four edges in these cases.

Note: Due to the official test data being weak, additional test data worth 50 marks has been uploaded. Credit goes to aaronhe07 for noticing the issue and to d for helping sanity check and add data.

Output Specification

On one line, output the minimal cost that will allow all the animals to gather in one pen or outside all of the pens.

Sample Input

4
3 1 2 3 7 4 6
4 1 2 4 5 7 7 2 6
4 4 7 6 5 4 8 9 2
5 3 2 4 7 8 4 7 4 7 7

Output for Sample Input

10

Explanation of Output for Sample Input

The diagram below explains the input data:

where the circled numbers are the corners, and the numbers in italics are the edge costs. Notice that if the edges (2, 3), (4, 5) and (4, 7) are removed, all the animals can meet in the pen which has five sides.

Comments


  • 4
    jerryzhou196  commented on July 26, 2021, 7:20 p.m.

    As someone said earlier, all the first test cases have pens arranged in two separate clusters


    • 0
      ColonelBy_team10  commented on Jan. 8, 2022, 10:32 p.m.

      If it is separated, do the two pens need to be connected via the outside or does it suffice to make them independently internally connected?


      • 1
        andy_zhu23  commented on Jan. 8, 2022, 11:40 p.m.

        pretty sure you connect them via the outside


  • 24
    tappbros  commented on July 13, 2020, 11:11 p.m.

    Why are we allowing the animals to do this again?


    • 4
      ColonelBy_team10  commented on Jan. 8, 2022, 7:06 p.m.

      to further the struggle of the proletariat


  • -8
    alihu264  commented on April 28, 2020, 9:44 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -12
      aaronhe07  commented on July 29, 2020, 12:15 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 17
        chika  commented on July 29, 2020, 1:27 a.m.

        There are likely two things going on here.

        Firstly, people are much more likely to complain about the input format of S5 than of S4, and in fact the comment pointing out some unexpected issues with the input is upvoted precisely because it's addressing a huge pain point of the problem. The input format of S4 is actually not that unreasonable, expressing pens by their vertices. It might not be desirable once you have a way to solve the problem, but in comparison to S5, it's really not that bad. The input format of S5 could have been avoided by expressing the tree in a more modern format, with labeled vertices connected by edges instead of the provided string representation, and I think many people would therefore claim that figuring out how to handle the S5 input is harder than figuring out how to handle the S4 input.

        Secondly, I think a lot of people who are working their way up to solving this problem would disagree with the assessment that handling the input is the hardest part of the problem. This problem isn't actually substantially easier if the input is given in a different format, you still need to actually come up with an algorithm to find the minimum cost, and a lot of people are likely to find that much harder than figuring out how to handle the input. Complaining about the input format of S4 as the hardest part of the problem comes off as implicitly bragging that the algorithmic component of the problem is trivial in comparison to handling the input, and is likely to garner downvotes as a consequence.


        • -2
          ColonelBy_team10  commented on Jan. 8, 2022, 7:54 p.m. ← edited

          a) the complaint has nothing to do with S5, I don't know why you are trying to rope it in

          b) relatively speaking, converting a graph of walls to a graph of pens is less boilerplate than the minimum spanning tree algorithm. It is most likely for this reason why the original commenter expressed his sentiment. it's a lot easier to look up how to do a minimum spanning tree, than trying to convert walls to pens, the latter of which I wouldn't even know how to google.


        • -44
          aaronhe07  commented on July 29, 2020, 1:51 a.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • 38
            wleung_bvg  commented on July 29, 2020, 2:42 a.m.

            I can assure you that chika knows how to solve this problem (and there are also other sources where this problem exists). While they often prefer to post anonymously, they are a fairly well respected person internationally in the competitive programming community and their comments are not something that should be immediately dismissed.


  • 5
    mango8023  commented on Aug. 17, 2018, 3:01 a.m.

    i study the code from 'aurpine', and find out that his/her code cannot run the sample input/output correctly! because the graphs in all of the test data are NOT connected, but the graph in sample input is connected. can u fix that?


  • 7
    OOOIII  commented on Feb. 21, 2017, 3:25 a.m.

    Passed all test cases but not SAMPLE explanation request


    • 6
      Kevy3030  commented on May 8, 2020, 3:31 a.m.

      In the sample all the pens were together in one group. It just so happened that in all of the test cases the pens were in two or more different clusters.


  • 7
    sunnylancoder  commented on Dec. 28, 2016, 8:48 p.m.

    Can costs be negative?


    • 4
      Arcslogger  commented on Oct. 26, 2019, 2:55 p.m.

      The question doesn't say that the cost has to be positive


    • 5
      USER18381  commented on Oct. 26, 2019, 1:18 p.m. ← edited

      No. I highly doubt that.


      • 1
        mango8023  commented on Oct. 18, 2021, 2:31 a.m.

        No. Cost is bigger than 0 since I tried to add a infinity look while receiving a negative cost and did not get TLE.


  • 5
    atarw  commented on April 26, 2016, 12:20 a.m.

    an edge that is specified only once connects that pen to the outside;

    I don’t understand what this means, what would a sample input of a pen connected to the outside be?


    • 4
      Roronoa_Zoro1540  commented on Feb. 10, 2020, 2:35 a.m.

      means that if you see the specific edge in the input only once that means it must connect the pen to the outside (i.e you don't see the edge again in another pen's description)