Programming Challenge

Guys, I'm trying out a problem from CodeChef(dot)com, and I'm kinda stuck right now.
The objective is to build an efficient algorithm using Dynamic Programming, here is the problem (taken from the Website):

"Malvika gets bored along with her Cats

Malvika's cats, Chingam and Jimma are also bored of solving problems. Fortunately, Chingam has found n bars of dark chocolate. They all have the same width, but differ in their lengths. In fact, no two chocolate bars have the same length. All the n bars are kept in a row. Let's say that their lengths are given by L[1], L[2], ... , L[n] from left to right. That is, length of the bar i is L[i].

Chingam decided to play a little game with Jimma. In one step, Jimma has to choose some bar which has not been eaten yet. Chingam hates inversions, so he will instantaneously eat that bar, along with every other Bar with which it forms an Inversion Pair. We say that bars i and j form an Inversion Pair, if the bar to the left is longer than the bar to the right.

That is, if Jimma selects bar i, whose length is L[i], then Chingam will eat this, as well as every bar j such that j > i and L[j] < L[i], as well as every bar k such that k < i and L[k] > L[i]. After this, the step ends, they proceed to the next step, where Jimma selects another bar and the whole process repeats. The game ends when all the n chocolate bars are eaten.

Jimma doesn't like this game because she does not get any chocolate. So, she wants to finish it as soon as possible and go back to sleep. Please help her find the minimum number of steps needed for the game to end.
Input

The first line of input contains a single integer T denoting number of test cases.
The first line of each test case contains one integer: n.
The second line contains n space separated integers, which correspond to L[1], L[2],... , L[n].

Output

For each test case, output a single integer in a line corresponding to the answer of the problem.

Constraints

1 <= T <= 5
1 <= n<= 105
1 <= L[i] <= n

Example

Input:
1
4
3 1 4 2

Output:
2

Explanation

In the first step, Jimma can choose bar 4, which is of length 2. Bar 3 and bar 1 form Inversion Pairs with bar 4. So Chingam eats all these 3 bars. In the second step, Jimma chooses bar 2, and she's done. You can check that Jimma cannot get rid of all the four bars in one step."

How would go to complete this? On a quick analysis we see that a recursive algorithm would take O(n!) ~ O(n^n), which is completely unfeaseble for large numbers of n (for n= 105 we get 105^105, which is bigger than square of the total number of atoms in the observable universe).

They suggest using Square Root Decomposition, which is where I got completely lost. How would you implement it in this problem?

Thanks!

So if I understood this correctly, he eats the bars with a higher length on the left of i, and a lower length on the right of i?

for n=16 i randomized the digits to be as follows;
7 13 10 11 | 1 3 6 16 | 2 9 12 5 | 15 14 8 4

You can deduct some information about the sequences without knowing the order of the numbers outside of the first or last cluster.

For example if you pick 13, there are 12 numbers below it and 3 numbers above it. Of the 12 below it, only 1 is to your left, so you'll be able to remove 13, and 11 other position from the right side. If you pick this, you'll be left with 7 16 15 14

Alternatively, picking the lowest number from the rightmost cluster gets you 4, which has 3 below and 12 above it. From the numbers above it, none are to your right so you will be able to remove 13 numbers, leaving you with(after processing it) with 1 3 2.

So now we have to look at each of these.

7 16 | 15 14 -> pick 16 to have only the 7 left
1 | 3 | 2 -> pick 2 to have only the 3 left

both result in a step count of 3

Not sure if this is how you're meant to do it, nor do i have the time to implement this as a test to check the O count.

Originally Posted by Hell_Demon

So if I understood this correctly, he eats the bars with a higher length on the left of i, and a lower length on the right of i?

for n=16 i randomized the digits to be as follows;
7 13 10 11 | 1 3 6 16 | 2 9 12 5 | 15 14 8 4

You can deduct some information about the sequences without knowing the order of the numbers outside of the first or last cluster.

For example if you pick 13, there are 12 numbers below it and 3 numbers above it. Of the 12 below it, only 1 is to your left, so you'll be able to remove 13, and 11 other position from the right side. If you pick this, you'll be left with 7 16 15 14

Alternatively, picking the lowest number from the rightmost cluster gets you 4, which has 3 below and 12 above it. From the numbers above it, none are to your right so you will be able to remove 13 numbers, leaving you with(after processing it) with 1 3 2.

So now we have to look at each of these.

7 16 | 15 14 -> pick 16 to have only the 7 left
1 | 3 | 2 -> pick 2 to have only the 3 left

both result in a step count of 3

Not sure if this is how you're meant to do it, nor do i have the time to implement this as a test to check the O count.

Yeah, but couldn't the optimal bar not have the highest / lowest length, or even be in anouther cluster? Or was it a guess?

I actually found this nice way to calculate the number of bars removed at index i, but it doesn't use the sqrt decomposition... let's take the randomized sequence you had:
7 13 10 11 | 1 3 6 16 | 2 9 12 5 | 15 14 8 4

If you chose any value (e.g. 13), and if you know how many bars are eaten on the left side (e.g. using a binary search tree), then you can get the total number of bars that are eaten when choosing that bar:
Total bars eaten: number_of_bars_to_the_left*2 + (bar_length - bar_index) + 1

For the bar with length 13 (and index 2), we know we can't eat any bar to the left, so we get: 0*2 + (13 - 2) + 1 = 12
If we apply this analysis to the whole sequence (and using a AVL tree for searching and saving lengths of the bars as I search), we'll take:

O(n) = log(1) + log(2) + ... log(n) = log(n!) <= O(n*log(n))

My idea was to use this function (total bars eaten), and choose the bars that maximize it, but then again it doesn't use the sqrt decomposition so I don't know if this is the best way to do it.

After we remove each bar, we can see that the sequence can be reduced to another subproblem:

(after picking 13) 7 16 | 15 14 -> 1 4 | 3 2
(after picking 4) 1 | 3 | 2 -> 1 | 3 | 2

So we get a time-complexity of (in the worst case, we only remove one bar at a time e.g. completely ordered array):

T(n) = O(n*log(n)) + T(n-1) ~= O(n*log(n) + (n-1)*log(n-1) + ...) <= O(n^2*log(n)) <= O(n^3), so it's polynomial but it's proporcional to n^3, which is much better than exponencial but still bad.

I could not think of any example where numbers in the other clusters could have a benefit over ones in the outside clusters, as numbers in the outside clusters have the advantage that you know exactly how many you can remove on either the left or the right side, without needing to know the contents of the other clusters, whereas for the middle clusters you would be required to know the contents of the other clusters to determine how many will be removed.

Programming Challenge

Post a Reply

Similar Threads

Tags for this Thread