2003 TCCC Semifinals 3 - Division I, Level One - ZigZag

Problem Statement:        ZigZag

Solutions:

I solve this problem with help of One-Dimension DP.

I used two one-dimension array with name dp and dif.
dp[i] stores the length of longest zigzag sub sequence that ended to element i of our input sequence.
dif[i] stores the difference between 2 last element for that longest zigzag sub sequence that ended to element i and set dif[i] for each i to 0.

Each element of input sequence can be a zigzag sequence lonely. So the initial state of my solution is to set each element of dp to 1, that means the minimum length for zigzag sub sequences that ended to each element is 1, included only that element.
But how to get the result for dp[i] and dif[i]?

Element i could come as the last element for the longest sequences that ended to element 0,1,..., i-1. So we should check:

1) If the element i could continue the zigzag sequence that ended to element 0,1,...,i-1?
2) If this new zigzag sub sequence is longer than before?

Then we can update dp[i] and dif[i].
After that we should find the biggest number in dp as the answer for this problem.

Here's my code for this problem:

ZigZag_DP.cpp

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