second_saturday's blog

Is this problem can be solved faster ?
By second_saturday, history, 7 months ago, In English

you are given an array of stones with size n+1 where the initial weight of each stone is 1.

We are playing a game with the stones. At round j starting from 0, we choose any two adjacent stones and combine them together.

Suppose the stones have weight x and y, then the combined stone has weight x+y. This combination requires a cost x*y*v[j].

The quantity v[] is a nonincreasing sequence given to you prior to the game, and changes over rounds.

The game continues with n rounds, and after round nth there is precisely one stone left with weight n+1.

Return the lowest cost you need to pay in total of n rounds.

Input: n=5, v=[4,3,2,0,0] Output: 9

Explanation: [1 1 1 1 1 1]->[2 1 1 1 1]->[2 2 1 1]->[2 2 2]->[4 2]->[6] The output is 1*1*4+1*1*3+1*1*2=9

Input: n=5, v=[4,3,1,1,0] Output: 11

Explanation: [1 1 1 1 1 1]->[2 1 1 1 1]->[2 1 2 1]->[3 2 1]->[3 3]->[6] The output is 1*1*4+1*1*3+2*1*1+2*1*1=11

Input: n=5, v=[4,2,2,1,0] Output: 12

here is what i came up with, it works but it's damn slow time complexity is exponential here. please help if fast solution's are possible

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

typedef array< int , 2 >  ar;
typedef set< ar > node ;

node t[50][50];


int solve( vector<int>A , vector<int>B )
{
	const int N = A.size();


	for( int i = 0 ; i < N ; i++ )
		t[i][i] = { { 0 , 0 } };
	 
	// t[i][j] -> range -> vector[ bitmask , value ]
	// bitmask -> to maintain which rounds have been utilized


	int P[A.size()+1];
	P[0] = 0 ;

	for( int i = 0 ; i < (int)A.size() ; i++ )
		P[i+1] = P[i] + A[i] ;

	auto get = [&]( int a , int b )
	{
		return P[b+1] - P[a] ;
	};

	auto work = [&]( int i , int j , int k , node &left , node &right ) -> void 
	{
		    
		for( auto x : left )
		for( auto y : right)
		{
			int b1 = x[0] ;
			int b2 = y[0] ;

			int v1 = x[1] ;
			int v2 = y[1] ;


			if( (b1|b2) == (b1^b2) )
			{
				int used = b1|b2 ;

				for( int round = 0 ; round < (int)B.size() ; round++ )
				{
					int p = 1<<round ;
					if( (p^used) == (p|used))
					{
						int myBitMask = used|(1<<round) ;
						t[i][j].insert({myBitMask , 
							  v1 + v2 + (get( i , k) * get( k+1 , j) * B[round]) });
					}
				}
			}
		}
	};


	for( int L = 2 ; L <= N ; L++ )
	for( int i = 0 ; i+L-1<N; i++ )
	{
		int j = i+L-1;
		for( int k = i ; k < j ; k++ )
			work( i , j , k , t[i][k] , t[k+1][j] );
	}

  
	int mn = INT_MAX ;

	for( auto x : t[0][N-1] )
		mn = min( mn , x[1] );

	return mn ;
}

int main() {
	// your code goes here
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N; 
	cin>>N ;
	vector<int>A(N+1,0);
	vector<int>B(N);

	for( auto &x : A )
		cin>>x ;

	for( auto &x : B )
		cin>>x ;

	cout<<solve( A , B )<<endl;
	
	return 0;
}
/*
5
1 1 1 1 1 1 
4 3 1 1 0
-> 11 

5
1 1 1 1 1 1 
4 3 2 0 0
-> 9
*/
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by second_saturday (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The thing here is that we want to combine the minimum stone weight with maximum penalty to minimize the result you can use a priority queue or min-heap where you can pop 2 min stones and combine them with the maximum weight as the order of weight doesn't matter because it is given in non-decreasing(either smaller or equal then previous).

Thus when the total time complexity will be (nlog(n)) and O(n) space

It's my first comment on codeforces kindly forgive me if the explanation isn't clear or correct me if my solution is wrong Thank You. 


import heapq
def solve():
    n=int(input())
    v=list(map(int,input().split()))
    stones=[1 for _ in range(n+1)]
    heapq.heapify(stones)
    res=0
    i=0
    while len(stones)>1 and i<n:
        x=heapq.heappop(stones)
        y=heapq.heappop(stones)
        res+=(x*y*v[i])
        i+=1 
        heapq.heappush(stones,x+y)
    print(res)
t=1 
for _ in range(t):
    solve()
→ Reply