For e.g. in this case : 4 3 2 3 2 3 5 6 .
By your logic it would find the adjacent pair with smallest sum = 5 and it would
first merge the first occuring 3 and 2 , which would not turn into minimum score.
Look in this example …
4 Likes
Can anyone give me any case were the brute force solution of subtask 2 will not work for other subtasks…
Bruteforce will excede the time limit as there is n factorial ways to merge the array
But i did not recieve a tle for rest of subtasks and instead I got WA.
Here is the link of my solution CodeChef: Practical coding for everyone
1 Like
O(N^3) solution working fine…
this is my code
https://www.codechef.com/viewsolution/25117564
2 Likes
Can anyone use different approach other than DP???
Thanks
can u plz explain ur code in detail plz!!!, I couldn’t get it…
If you want to understand the quadrilateral inequality optimization DP, Or in your words, this is: Knuth’s optimization.
You can familiarize yourself with the algorithm by doing the following problems:
Breaking Strings
Post Office(IOI-2000)
Optimal Binary Search Tree
Or you want to understand the Garsia-Wachs algorithm, this is:
Garsia–Wachs algorithm
I haven’t found a similar problem about the algorithm. Maybe some people can find it.
Or you want to understand the Balanced binary tree, you can find it everywhere.
19 Likes
Best one liner editorial ever!!!
2 Likes
I have solved matrix chain multiplication and other similar questions. Can you please explain how the circular part (merging first and last in a subarray) is handled in this problem? Thanks.
Just double the array, so that each subarray of length n corresponds to a situation.
7 Likes
My way
Harry Potter's MIXTURES, Spoj - Dynamic Programming Problem - YouTube, you can see this it is a problem on spoj named mixtures,using this you can find the cost of operation from 1 to n(linear),so after you can take the array of 2n size and place 1-n in the first n posotion and same 1-n (input) in next n position then you can calculate the min value from (1,n),(2,n+1) etc.
CodeChef: Practical coding for everyone
4 Likes
Basically you can first solve for (1 - n),(2 - n+1) and so on till (n - 2n-1) etc. and find the min of these values you will automatically get min cost
2 Likes
I haven’t gone through your code, but from what you explained.
There may be multiple choices for minimum sum leading to different final answers.
Example:
1 2 1 4 2
3 1 4 2
4 4 2
4 6
10
(3+4+6+10=23)
1 2 1 4 2
3 2 1 4
3 3 4
6 4
10
(3+3+6+10=22)
Hope it helps !
1 Like
Here is a tutorial to solve this problem using similar approach as matrix chain multiplication.
9 Likes
Code:
https://www.codechef.com/viewsolution/25279047
Approach:
Let’s assume we are asked to find a solution for linear arrangement,then this has to be done using dp.
Take a 2d array of size nxn, fill the all the diagonal cells with given input elements.
Eg: Input :- 10,10,10,1.
10 0 0 0
0 10 0 0
0 0 10 0
0 0 0 1
You can add only adjacent elements,so store the sum of dp[ i ][ i ], dp[ i+1][ i+1] in dp[ i ][ i+1 ].
for 10 10 10 1, after first merging you will get 20 10 1 && 10 20 1 && 10 10 11.Array would look like this.
10 20 0 0
0 10 20 0
0 0 10 11
0 0 0 1
Now when you add two elements,say for 20 10 1, you will get 30 1 ( 20+10 1) or 20 11 ( 20 10+1).
to handle this,let’s say we have following
a b C X
0 d e F
0 0 g h
0 0 0 i
to fill the cell C,we need minimum (b+g,a+e) and similarly for F we need minimum(e+i,d+h).
if we pay close attention,it’s not hard to see b+g==a+e and e+i==d+h.Why?
if we have x,y,z as our elements then its like taking minimum of ( (x+y)+z , x+(y+z) ), which only gives sum of all the input implements in the end,not userful.
Sum tracking:
We have to store the sum after each merging and for this we need an additional element for each cell,you could create a custom data type using struct or pair of elements in c++ should do the job.
Initially, all the input element along the diagonal should have there second element zero.
Let’s go over the problem again,this time tracking the sum.
<10,0> <0,0> <0,0> <0,0>
<0,0> <10,0> <0,0> <0,0>
<0,0> <0,0> <10,0> <0,0>
<0,0> <0,0> <0,0> <1,0>
after first merging, sum of merged elements is stored in as second element.
<10,0> <20,20> <0,0> <0,0>
<0,0> <10,0> <20,20> <0,0>
<0,0> <0,0> <10,0> <11,11>
<0,0> <0,0> <0,0> <1,0>
for second merging,let’s bring in our earlier arrangment again.
a b C X
0 d e F
0 0 g h
0 0 0 i
To fill in C,
let’s say var = a.first+e.first ( or b.first + g.first ) and we need minimum of ( b.second + g.second , a.second + e.second ), let the value be stored in min.
Now C.first=var and C.second= var+ min
similarly for F.
and for X , var= a.first + F.first and min= minimum(F.second+a.second, b.second+h.second, C.second + i.second).
so X.first= var and X.second=var+min.
Now we have the answer for linear arrangement,for circular arrangement just make the size of 2*n, the arrangement would be
10 0 0 0 0 0 0 0
0 10 0 0 0 0 0 0
0 0 10 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 10 0 0 0
0 0 0 0 0 10 0 0
0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 1
now for every square matrix of size k, the with its diagonal elements as input elements you will have the minimum merged sum of that diagonal elemetns, at it’s top right cell
Eg:
a 0 0 0 0 0 0
0 b 0 0 0 0 0
0 0 c 0 0 0 P
0 0 0 d 0 0 0
0 0 0 0 e 0 0
0 0 0 0 0 f 0
0 0 0 0 0 0 g
for
c 0 0 0 P
0 d 0 0 0
0 0 e 0 0
0 0 0 f 0
0 0 0 0 g
here P will give the minimum sum after merging, for linear arrangement of c,d,e,f,g.Taking minimum of all the diagonal elements after n-1 merge operations should give the answer.
i.e
10 0 0 p 0 0 0 0
0 10 0 0 q 0 0 0
0 0 10 0 0 r 0 0
0 0 0 1 0 0 s 0
0 0 0 0 10 0 0 t
0 0 0 0 0 10 0 0
0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 1
answer= min(p,q,r,s,t)
I don’t know if it’s the optimal approach, but it got me through.Hope it helps someone.
8 Likes
I tried a similar approach, which passed only for the case of powers of 2. In my algorithm, I look at consecutive elements a, b, c ,d. If b <= d and c <= a, replace b and c by b+c. Repeat until only one element left.
I found that this needed a tweak for a sequence like 9 1 4 1 4 9, where it is necessary to remove the first 1 4 or last 1 4 before the middle 4 1. According to where I start I could hit the wrong pair first. So I tried the whole sequence twice, changing the position of the start of the circular sequence, and then choosing the better result.
With this method I get the wrong answer. Can anyone suggest why, or give an example which defeats this simple method?