## 11782 - Optimal Cut

Moderator: Board moderators

Gourav.in
New poster
Posts: 4
Joined: Sat May 28, 2011 10:40 pm

### 11782 - Optimal Cut

i have written a bottom up DP in tree for it .. but WA can any one just post some corner case for this question .

with regards,
Gourav

Gourav.in
New poster
Posts: 4
Joined: Sat May 28, 2011 10:40 pm

### Re: 11782

here is my code . plzz point out the bug in it

Code: Select all

#include<iostream>
#include<stack>
#include<vector>
#include<cstdio>
using namespace std;
#define INF 1048576001
static int dp[( 1 << 20)][20];
static int N , a[ ( 1 << 20) ] , arr[ ( 1 << 20 ) ], K;
int main()
{
while( 1 )
{
scanf("%d",&N);
if( N == -1) break;
scanf("%d",&K);
int L = ((1 << N) << 1) -1;
for(int i = 0; i < L; ++i)
{
scanf("%d",&a[i]);
}
vector< int > v;
stack < int > s;
s.push(0);
//cout << ":)\n";
while(!s.empty())
{
int x = s.top();
s.pop();
v.push_back(x);
int l =(x+1)*2 -1;
int r =(x+1)*2 ;
if( r < L)
{
s.push(r);
s.push(l);
}
}
for(int i = 0; i < L; ++i)
arr[v[i]] = a[i];
for(int i = 0; i < L; ++i)
dp[i][0] = arr[i];
int F = 2;
int mx = (1 << N);
if( F > K) F =K;
L =  (1 << N) - 1;
N--;
for(int i = L -1 ; i >= 0; --i)
{
//cout << arr[i] << " ";
for( int j = 1; j < F; ++j)
{
dp[i][j]=-INF;
for(int k = 0; k < j ;++k)
{
dp[i][j] = max( dp[i][j] , dp[(i+1)*2 - 1][k] + dp[(i+1)*2][j-k-1]);
}
}
if( i == (1 << N) -1) { F*=2; N--; }
if( F > K) F=K;
}
int res = -INF;
for(int i = 0; i < min(mx,K); ++i)
{
//cout << dp[0][i] << " ";
res= max( dp[0][i] , res);
}
cout << res << "\n" ;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11782

This prints only 0 for the sample input.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11782

Disregard my previous post. I wrote an AC solution using a bottom up DP tree.

Try this input:
3 7 283 -677 63 813 -970 746 526 973 83 118 -283 -970 -540 158 -699

The output should be 1645.
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11782 - Optimal Cut

Getting WA
I have tested several i/o
all of them were correct

Code: Select all

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

/*------- Constants---- */
#define LMT				2100000
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF                      63
#define MEM_VAL                         1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)                         make_pair(i,j)
#define lop(i,a,b)                      for( int i = (a) ; i < (b) ; i++)
#define pb(a)                           push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<25
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)                        cout <<#x <<" -> " << x << endl;
#define EPS				1e-7
#define fred()                          freopen("in.txt","r",stdin);
#define fwrt()                          freopen("in.txt","w",stdout);
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

int H , K ;
int cnt = 0;
int Values[LMT];
int iAr[LMT];
int DP[LMT][22];

void PreOrder(int n , int h )
{
if( h > H ) return;
Values[n] = iAr[cnt ++];
PreOrder(2 * n , h + 1 );
PreOrder(2 * n + 1 , h + 1) ;
}

int Trv(int u , int k , int h )
{

if( h > H ) return -inf ;
DP[u][1] = Values[u];
if( DP[u][k] !=-1 ) return DP[u][k];

int r = -inf;
for( int j = 1; j < k ; j ++ ) {
r = max( r , Trv(2* u , j , h + 1) + Trv(2 * u + 1, k - j , h + 1)) ;
}
return DP[u][k] = r;

}
int main()
{

while( scanf("%d" , &H) == 1) {
if(H == -1 ) break;
scanf("%d",&K);
int T = (1 << (H+1)) - 1;
for( int i = 0; i < T ; i ++ ) {
ms(DP[i+1], -1);
sc(iAr[i]);
}
cnt = 0;
PreOrder(1 , 0 );
int ans = - inf;
for(int i = 1; i <= K ; i ++ ) {
ans = max ( ans , Trv(1 , i , 0));
}

printf("%d\n" ,ans );
}
return 0;
}