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.
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.
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.