We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The dynamic programming comes in for computing the next count for each additional item (i.e., mi) from previous count. However, besides the addtional item, computing needs to distinguish whether it is greater than the last item (mi-1) or not, and needs to memorize some state to do the proper next computation.
I have used map (std::map of (int, int) pair into int) to trace such states, and I could pass all cases except the case 35. To pass it finally, I have changed map to 2-dimensional array (std::vector of std::vector of int).
For a hint, I focused on how to divide the sequence M = m0 m1 m2 ... into sub-sequences.
Note also, to compute the number of ways for a divided sequence, I could just think '/' symbol induces a multiplication of permutation.
1 2 5 / 3 4 --> 3P2 = 6 (one '/' here, the counts of its left items = 3, and the counts of its right items = 2.)
1 2 5 / 3 / 4 --> 3P1 * 1P1 (3P1 because left items of first '/' count to 3 and right items do 1. 1P1 because left items of second '/' count to 1 and right items do 1.)
Sherlock's Array Merging Algorithm
You are viewing a single comment's thread. Return to all comments →
The dynamic programming comes in for computing the next count for each additional item (i.e., mi) from previous count. However, besides the addtional item, computing needs to distinguish whether it is greater than the last item (mi-1) or not, and needs to memorize some state to do the proper next computation.
I have used map (std::map of (int, int) pair into int) to trace such states, and I could pass all cases except the case 35. To pass it finally, I have changed map to 2-dimensional array (std::vector of std::vector of int).
For a hint, I focused on how to divide the sequence M = m0 m1 m2 ... into sub-sequences.
For example, when M = 1 2 5 3 4,
1 --> 1 way
1 2 --> 1 way, 1 / 2 --> 1 way
1 2 5 --> 1 way, 1 2 / 5 --> 2 ways, 1 / 2 / 5 --> 1 way
1 2 5 / 3 --> 3 ways, 1 2 / 5 / 3 --> 2 ways, 1 / 2 / 5 / 3 --> 1 way
1 2 5 / 3 4 --> 6 ways, 1 2 5 / 3 / 4 --> 3 ways, 1 2 / 5 / 3 / 4 --> 2 ways, 1 / 2 / 5 / 3 / 4 --> 1 way
So, 6+3+2+1=12 ways in total.
Note also, to compute the number of ways for a divided sequence, I could just think '/' symbol induces a multiplication of permutation.
1 2 5 / 3 4 --> 3P2 = 6 (one '/' here, the counts of its left items = 3, and the counts of its right items = 2.)
1 2 5 / 3 / 4 --> 3P1 * 1P1 (3P1 because left items of first '/' count to 3 and right items do 1. 1P1 because left items of second '/' count to 1 and right items do 1.)