Connection Status:
Competition Arena > RoadsAndFools

RoadsAndFools

SRM 323 · 2006-10-19 · by Pawa

SRM 323 · 2006-10-19 · by Pawa · Greedy, Simple Search, Iteration
Class Name: RoadsAndFools
Return Type: String
Method Name: determineOrientation
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

In one big country there is a saying that "we've got only two troubles: roads and fools". This problem is about both of them.

Two cities of this country are connected by a highway. Some points on the highway are marked with milestones. On the two sides of each milestone the distances to the two cities are written. When you travel from one city to another, the milestones show the distance traveled from the origin city. If the milestones are placed correctly, the numbers you see while traveling must go in ascending order since the distance you've traveled is always increasing.

During the reconstruction of the highway, some of the milestones were stolen, some were broken and some... just disappeared. On top of it all a group of bandits with unexplained motives set out to the highway one night and reversed some of the milestones.

Given the state of the remaining milestones after the act, determine if it is possible to restore the correct orientations.
You are given an int length, the length of the highway, and a int[] frontSides. Each element of frontSides is the mark on the front side of the milestone in the order they are seen traveling from the first city to the second. The mark on the opposite side of milestone i is obviously length-frontSides[i].

Return a String containing the restored sequence of milestones separated by single spaces (again, as seen traveling from the first city to the second). If there is more than one solution, return "MULTIPLE SOLUTIONS". If no solution exists (you can never tell what else could have happend to the milestones in that big country...), return "NO SOLUTION".

Two solutions are considered equal if you see the same numbers on all milestones when traveling between the cities (see examples 4 and 5 for further clarification).

Constraints

  • length will be between 1 and 1000, inclusive.
  • frontSides will contain between 1 and 50 elements, inclusive.
  • each element of frontSides will be between 0 and length, inclusive.
Examples
0)
5
{1, 2, 3}
Returns: "1 2 3"

The first milestone has the numbers 1 and 4 on it. The second and third both have the numbers 2 and 3 on their two sides. "1 2 3" is the only correct orientation.

1)
5
{5, 2, 0}
Returns: "MULTIPLE SOLUTIONS"

There are two correct orientations: {0, 2, 5} and {0, 3, 5}.

2)
5
{4, 4}
Returns: "1 4"
3)
5
{4, 4, 4}
Returns: "NO SOLUTION"
4)
5
{3}
Returns: "MULTIPLE SOLUTIONS"

Both {2} and {3} are correct orientations.

6)
10
{5}
Returns: "5"

Both sides of the milestone contain the number 5, so the solution is unique.

Submissions are judged against all 100 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RoadsAndFools with a public method string determineOrientation(int length, vector<int> frontSides) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous