SRM 718, D2, 250-Pointer (RelativeHeights)

James S. Plank

Thu Sep 7 17:44:07 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: July, 2017
Competitors who opened the problem: 234
Competitors who submitted a solution: 175
Number of correct solutions: 160
Accuracy (percentage correct vs those who opened): 68.4
Average Correct Time: 25 minutes, 32 seconds.

An elegant solution to this problem doesn't pop out to me. As with most D2 250's, the constraints are so small that you can write some pretty inefficient solutions that are fast enough. Mine isn't that bad, really, but it feels a little inelegant.

Step 1: Convert Heights to Orders

Since the only thing that matters is the relative order, it's a good first step to convert the h array so that it holds the orders rather than the heights. So, this is what you want to turn h into in each example:

Example 0: { 5, 4, 3, 2, 1, 0 }
Example 1: { 0, 2, 3, 1 }
Example 2: { 3, 5, 0, 2, 4, 1 }
Example 3: { 2, 1, 0, 5, 4, 3 }
Example 4: { 0, 1, 3, 5, 7, 9, 2, 4, 6, 8 }

I did this by inserting each height into a map, with a val of zero. Then I traversed the map, setting the val of each entry to its relative order. Then, I traversed h, and replaced each value with its val in the map. Here's example two:

h is {6,2,352,43,5,44}.
Insert each value into the map with a val of zero. Here's the map: [2,0][5,0][6,0][43,0][44,0][352,0].
Set the vals to the relative orders. Here's the map: [2,5][5,4][6,3][43,2][44,1][352,0].
Replace each value of h with its relative order. Here's h: {3,5,0,2,4,1}.

Step 2: How to modify h when you delete an element

Now you are going to traverse h. For each value of h, you want to simulate deleting it from h, and fixing the relative heights. To do that -- if you are deleting relative height x, then all of the relative heights greater than x should be reduced by one. Continuing with example 2, suppose you delete the first element of h. Its relative height is 3. So, h will become {4,0,2,3,1}. You'll notice, we deleted the first element, and decremented the two elements greater than 3.

Step 3: Instead of actually deleting, creating a string of the new h

Now, to solve the problem -- we don't actually delete the values and modify h. Instead, we create a string that represents what h is after we have deleted a value. Let's consider the previous example (example 2), where we have converted h to {3,5,0,2,4,1} and we are deleting the first element. Instead of actually deleting the element, we create a string of the remaining elements, decrementing the ones whose values are greater than three.

Here's the string that I created: ":4:0:2:3:1". You can use a stringstream for this if you want. I used sprintf() and string concatenation, because I hate stringstreams. Here are all of the strings for example 2:

i h[i] The string, when h[i] is deleted

0 3 ":4:0:2:3:1"

1 5 "3:0:2:4:1"

2 0 "2:4:1:3:0"

3 2 "2:4:0:3:1"

4 4 "3:4:0:2:1"

5 1 "2:4:0:1:3"

Step 4: Using a set to count unique strings

The final piece of the puzzle is to insert these strings into a set. Since sets do not hold duplicates, the size of the set is the number of unique strings. That's your return value.

To help you out, here is all of the information for each example. This should help you debug your answer:

Example 0

Relative Heights: {5,4,3,2,1,0}
Delete element 0.  h[0] = 5.  String: :4:3:2:1:0
Delete element 1.  h[1] = 4.  String: :4:3:2:1:0
Delete element 2.  h[2] = 3.  String: :4:3:2:1:0
Delete element 3.  h[3] = 2.  String: :4:3:2:1:0
Delete element 4.  h[4] = 1.  String: :4:3:2:1:0
Delete element 5.  h[5] = 0.  String: :4:3:2:1:0
Answer: 1

Example 1

Relative Heights: {0,2,3,1}
Delete element 0.  h[0] = 0.  String: :1:2:0
Delete element 1.  h[1] = 2.  String: :0:2:1
Delete element 2.  h[2] = 3.  String: :0:2:1
Delete element 3.  h[3] = 1.  String: :0:1:2
Answer: 3

Example 2

Relative Heights: {3,5,0,2,4,1}
Delete element 0.  h[0] = 3.  String: :4:0:2:3:1
Delete element 1.  h[1] = 5.  String: :3:0:2:4:1
Delete element 2.  h[2] = 0.  String: :2:4:1:3:0
Delete element 3.  h[3] = 2.  String: :2:4:0:3:1
Delete element 4.  h[4] = 4.  String: :3:4:0:2:1
Delete element 5.  h[5] = 1.  String: :2:4:0:1:3
Answer: 6

Example 3

Relative Heights: {2,1,0,5,4,3}
Delete element 0.  h[0] = 2.  String: :1:0:4:3:2
Delete element 1.  h[1] = 1.  String: :1:0:4:3:2
Delete element 2.  h[2] = 0.  String: :1:0:4:3:2
Delete element 3.  h[3] = 5.  String: :2:1:0:4:3
Delete element 4.  h[4] = 4.  String: :2:1:0:4:3
Delete element 5.  h[5] = 3.  String: :2:1:0:4:3
Answer: 2

Example 4

[lap237:Web-Writeups/2017/RelativeHeights] plank% a.out 4
Relative Heights: {0,1,3,5,7,9,2,4,6,8}
Delete element 0.  h[0] = 0.  String: :0:2:4:6:8:1:3:5:7
Delete element 1.  h[1] = 1.  String: :0:2:4:6:8:1:3:5:7
Delete element 2.  h[2] = 3.  String: :0:1:4:6:8:2:3:5:7
Delete element 3.  h[3] = 5.  String: :0:1:3:6:8:2:4:5:7
Delete element 4.  h[4] = 7.  String: :0:1:3:5:8:2:4:6:7
Delete element 5.  h[5] = 9.  String: :0:1:3:5:7:2:4:6:8
Delete element 6.  h[6] = 2.  String: :0:1:2:4:6:8:3:5:7
Delete element 7.  h[7] = 4.  String: :0:1:3:4:6:8:2:5:7
Delete element 8.  h[8] = 6.  String: :0:1:3:5:6:8:2:4:7
Delete element 9.  h[9] = 8.  String: :0:1:3:5:7:8:2:4:6
Answer: 9

i	h[i]	The string, when h[i] is deleted
0	3	":4:0:2:3:1"
1	5	"3:0:2:4:1"
2	0	"2:4:1:3:0"
3	2	"2:4:0:3:1"
4	4	"3:4:0:2:1"
5	1	"2:4:0:1:3"