ECOO '18 R1 P2 - Rue's Rings

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 30.0s
Memory limit: 128M

Problem type

A local street planning consulting company, Rue's Rings, is looking to help the city prepare for converting a lot of their medium-traffic one-lane intersections into roundabouts.

After generating a plan, the city wants to run a simulation to see where the possible bottlenecks of traffic could be. The simulation runs by finding the roundabouts along a route and then figuring out which roundabout is the smallest in diameter. The smallest diameter roundabout would be the best possible location for congestion and creating a bottleneck of traffic which would make the traffic patterns even worse than they are now.

There are N roundabout-filled routes from the starting point to the endpoint. Your task as the city simulation specialist, is to analyze the different routes that are available to find out which route (or routes) could generate the most issues.

Input Specification

The standard input will contain 10 datasets. Each dataset begins with an integer N (2 \le N \le 700), the number of routes. The next N lines each contain a series of integers describing a route.

The first integer of each route description is the ID for the route. The second integer R (1 \le R \le 70) is the number of roundabouts along the route. R integers follow which describe the diameter D (1 \le D \le 70\,000) of each roundabout along the route.

Output Specification

For each dataset, output the minimum roundabout diameter along a route followed by a brace-enclosed, sorted list of route IDs for the routes that could cause issues.

Sample Input (Two Datasets Shown)

3
1 6 4 5 2 6 3 2
2 3 2 3 4
3 4 2 3 2 4
4
1 2 3 4
2 3 4 2 4
3 7 2 3 3 4 5 2 6
4 5 3 2 5 1 4

Sample Output

2 {1,2,3}
1 {4}

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments


  • 0
    Kapusha  commented on July 13, 2022, 3:34 p.m. edit 4

    Could someone give a couple of examples of unusual situations? I sorted everything connected with indexes for input but still can't take full points in 2nd (3/7) and 3d(2/7) tests Edited: Not only I had to guess that input can be in disorder, but also that ID is not framed in anyway and input can be even something like this:

    1. 3
    2. 2515413 3 4 7 1
    3. 124124213234 4 5 5 6 9
    4. 21312431 1 2

    (ofc ID in test will be less, just e.g.)


  • -1
    ivan79  commented on June 9, 2022, 6:04 a.m.

    Seriously is this problem missing an explanation. How do we know which route will generate issues? Why make most problems as vague as possible?


    • 0
      John  commented on June 13, 2022, 2:04 p.m.

      Because it's DMOJ. Half of the difficulty of solving the problem is just trying to figure out what you're even supposed to do.


    • -1
      harsimrat  commented on June 10, 2022, 4:48 a.m.

      Author is missing important information. But we can solve the problem by assuming that routes with issues are those containing smallest roundabout(diameter is the smallest)


  • -1
    mikoSingle  commented on May 23, 2022, 12:46 p.m.

    Don't forget to convert your route numbers to int before finding the minimum!


  • 0
    darek  commented on Dec. 31, 2021, 6:33 a.m.

    reminder/hint (python): if considering using sets in output -> they are unordered...;)


  • 6
    boyesm  commented on April 29, 2020, 12:43 p.m. edited

    Just a heads up for anyone having trouble with the 2nd and 3rd test cases, the ID numbers don't always appear in order. I wrongly assumed this because it wasn't specified in the question and the sample cases are very basic.


    • 0
      orchestra_director  commented on July 11, 2022, 2:34 p.m.

      Thank you for commenting about the sorting. I would never have figured that out had you not said it. I did read over the problem again and in the output specification it does mention needing a "sorted list of route IDs"


  • 2
    johnhuang2499  commented on March 8, 2019, 3:12 p.m.

    My submission doesn't even work for the first test case but it works perfectly for the sample, can someone please help me with this? Thank You


    • -1
      boolean  commented on April 18, 2020, 12:37 p.m.

      Are you including the second integer in your roundabout routes? If so, that may be the problem.