2004 TCCC Online Round 1 - Division I, Level Two - FlowerGarden

Problem Statement:        FlowerGarden

Useful Links:        TopCoder Forum

Solutions:

For this problem I have 2 solutions:

1) I look at this problem as a Graph:

Each type of flowers is a node.

If there is an edge between node u and v (u ---> v), means that flower v could block flower u. It's obvious that height[v] is greater than height[u].

So in this problem we have a DAG. For solve this problem I think about 2 way:

1- Topological Sort

2- Use in-degree for each node

Topological Sort can solve this problem and produce an answer for it but it may not be the answer that problem wants. Just because of this:

"...and you also want to have the tallest flowers as far forward as possible.

It means that if for example both 1,2,3 and 2,1,3 be the answers for the problem, then we should choose 2,1,3.

Therefore I used the second way to solve. In each step, in the DAG, I search for a suitable node with ZERO in-degree to remove from DAG and add it to the answer. Then mark that node as visited and try to update the other nodes' in-degree. Here's my code for this solution:

FlowerGarden_Graph.cpp

2) I tried to use DP to solve this problem:

We have n row for flowers, so for each row try to find the most suitable flower for the row!

I had tow idea for it:

1- Bottom-Up:

        I've tried to set the row from the back row to the front one. "The Most Suitable Flower" means "The flower with the minimum height possible that the flowers from the later rows couldn't block it". "The flowers from later rows" means that "Flowers that don't used for any row".

2- Top-Down:

        I've tried to set the row from the front row to back one. "The Most Suitable Flower" means "The Flower with the maximum height suitable that doesn't block any flower from the previous rows". "The flowers from the previous rows" means that "Flowers that don't used for any row".

So, when use a flower for a row, we should mark it as used to don't check again for blocking!

I've coded both of them but the first one failed for this test case:

height = {355, 141, 84, 432}

bloom = {251, 324, 87, 18}

wilt = {293, 344, 234, 200}

Here are my codes for both of them:

FlowerGarden_DP_Bottom-Up.cpp

FlowerGarden_DP_Top-Down.cpp