SRM 564, D2, 500-Pointer (TheBrickTowerMediumDivTwo.cpp.html)

James S. Plank

Wed Jan 30 08:18:01 EST 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2012.
Competitors who opened the problem: 1009
Competitors who submitted a solution: 655
Number of correct solutions: 410
Accuracy (percentage correct vs those who opened): 40.6
Accuracy (percentage correct vs those who submittes): 62.6
Average Correct Time: 25 minutes, 13 seconds

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of numbers that represent heights of towers.
The vector will contain between 1 and 7 elements, and the elements will be between 1 and 47.
You want to place each tower on an integer coordinate on the x axis.
You want to make sure that every pair of adjacent towers is at least u units apart, where u is the height of the taller tower of the pair.
You want to minimize the distance between the first tower and the last.
To do this, you need to determine the optimal ordering of the towers.
Return the indices of the towers in this order.
If multiple orderings give you this minimized distance, then return the ordering that is lexicographically the smallest.

To help you, let's look at example 0: { 4, 7, 5 }. There are six orderings of these three towers. Here is where you would place them on the x axis if the leftmost tower goes at coordinate 0. Note that these orderings are sorted lexicographically:

{ 0, 1, 2 }: Tower with height 4 -> 0.   Tower with height 7: 7.   Tower with height 5: 14.
{ 0, 2, 1 }: Tower with height 4 -> 0.   Tower with height 7: 12.  Tower with height 5: 5.
{ 1, 0, 2 }: Tower with height 4 -> 7.   Tower with height 7: 0.   Tower with height 5: 12.
{ 1, 2, 0 }: Tower with height 4 -> 12.  Tower with height 7: 0.   Tower with height 5: 7.
{ 2, 0, 1 }: Tower with height 4 -> 5.   Tower with height 7: 12.  Tower with height 5: 0.
{ 2, 1, 0 }: Tower with height 4 -> 14.  Tower with height 7: 7.   Tower with height 5: 0.

Four of these orderings have a distance of 12, and two have distance of 14. So, you want to return the lexicographically smallest ordering whose distance is 12. That ordering is: { 0, 2, 1 }

The examples

Example	Input	Answer
0	{4, 7, 5}	{0, 2, 1}
1	{4, 4, 4, 4, 4, 4, 4}	{0, 1, 2, 3, 4, 5, 6}
2	{2, 3, 3, 2}	{0, 3, 1, 2 }
3	{13, 32, 38, 25, 43, 47, 6}	{0, 6, 3, 1, 2, 4, 5 }

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

As with a lot of Topcoder problems, you'll be tempted to try to be smart with this one, and do some variant of sorting the towers. Don't succumb to that temptation. The constraints are so small that you can easily enumerate all orderings of towers,

What kind of enumeration? This is an enumeration of permutations of the indices of the towers. Go ahead and use next_permutation() from the C++ algorithms library to implement this -- for each permutation, calculate the distance between the towers, and store the permutation that gives you the minimum. Store the first of these, because next_permutation runs in lexicographic order.

What is the running time of this? For a vector of size n, there are (n!) permutations, so the running time is O(n!). Yes, that's slow, but since the maximum vector size is 7, and (7!) = 5040, this will run easily within Topcoder's constraints.