Some days ago I was checking the algorithm problems for the algorith exam preparation of SoftUni and I have decided to solve one problem.
The problem is named “Bridges” (hence the youtube link above) and is a nice example of Greed algorithm. In general, this is how the problem looks like:
Input
On the single input line you are given the sequence seq holding integers separated by space.
Output
- At the first line print the maximal number of non-crossing bridges.
- If no bridges can be placed in the sequence, print “No bridges found”.
- Print “X bridge(s) found” at the first line where X is the maximal number of bridges.
- Print “bridge” for one bridge and “bridges” (plural) for more than one bridge.
- Print the bridges that form the best solution at the second line.
- In the input sequence replace with “X” all numbers that do not take part in the solution and leave the numbers that take part in bridges.
- If several maximal solutions exist, print the bridges that end as early as possible.
- Example: the sequence {2 1 3 1 2 3 4 5 4 5} we have multiple configurations having the same maximal number of 2 bridges. We first print the bridge that ends as early as possible {1 – 1}, then the next bridge on the right that ends as early as possible {4 – 4}. The expected result is: {X 1 X 1 X X 4 X 4 X}.
So, where to start with a problem like this? In general, as I have already mentioned, start with the greed! Notice, that what the program is interested in is the maximal number of bridges, hence a small bridge is at least as good as a big bridge. Furthermore, it requires the bridges that end as early as possible. Thus, simply start looking for those. With a simple nested loop, once we find that a point is a bridge, it is for sure the bridge we are looking for. Then, we can mark it as taken:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
for (int i = 1; i < liInput.Count; i++) { liStrOutput[i] = liInput[i].ToString(); for (int j = intLastPosition; j < i; j++) { if (liInput[j] == liInput[i]) { intLastPosition = i; liStrOutput[i] = "X"; liStrOutput[j] = "X"; bridges++; break; } } } |
And, because we make a greedy implementation, we know that the local optimum is the general optimum solution. Once we have marked the position of the bridges, we need to reverse them, as far as the result is interested in the bridges as numbers and we have marked them with X. This is done easily:
|
1 2 3 4 5 6 7 8 9 10 11 |
for (int i = 0; i < liInput.Count; i++) { if (liStrOutput[i] == "X") { liStrResults.Add(liInput[i].ToString()); } else { liStrResults.Add("X"); } } |
At the end, based on the counter bridges, we prepare our output.
The whole solution works flawlessly (and it is probably possible to make it with less variables). The complexity is N^2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Startup { static void Main() { List<int> liInput = ReadLineAndParseToList(); List<string> liStrOutput = new List<string>(new string[liInput.Count]); List<string> liStrResults = new List<string>(); int intLastPosition = 0; liStrOutput[0] = liInput[0].ToString(); int bridges = 0; for (int i = 1; i < liInput.Count; i++) { liStrOutput[i] = liInput[i].ToString(); for (int j = intLastPosition; j < i; j++) { if (liInput[j] == liInput[i]) { intLastPosition = i; liStrOutput[i] = "X"; liStrOutput[j] = "X"; bridges++; break; } } } //Reverse the X for (int i = 0; i < liInput.Count; i++) { if (liStrOutput[i] == "X") { liStrResults.Add(liInput[i].ToString()); } else { liStrResults.Add("X"); } } string strAnswer; switch (bridges) { case 0: strAnswer = "No bridges found"; break; case 1: strAnswer = "1 bridge found"; break; default: strAnswer = bridges + " bridges found"; break; } Console.WriteLine(strAnswer); Console.WriteLine(string.Join(" ", liStrResults.ToList())); } public static List<int> ReadLineAndParseToList() { return Console.ReadLine().Split().Select(int.Parse).ToList(); } } |
Enjoy it!