NPLQ19A Transporter- Editorial

PROBLEM LINK: https://www.codechef.com/NPLQ2019/problems/NPLQ19A

Practice
Contest

Author: Himanshu Khandelwal
Editorialist: Himanshu

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP, Math

PROBLEM:

Find optimal partitioning of an array subject to constraints such that weight is maximized as mentioned in the problem.

EXPLANATION:

Memoize the recurrence relation to find the solution.
find(ind,k) = [for all i>ind&&i<n] max(find(i,k-1)+round(sum(ind, i-1)))

SOLUTIONS:

Setter's Solution
/*
	Author: @himkha_100
	Himanshu Khandelwal, NITW
*/
#include<bits/stdc++.h>
#define MOD 1000000007
#define INFI 1e15
#define INFIM 1e18
#define ll long long int
#define s(t) scanf("%lld",&t)
#define p(t) printf("%lld\n",t)
#define pb push_back
#define f(t) for(int i=0;i<t;i++)
#define fi first
#define se second
#define all(t) t.begin(),t.end()
#define ci(t) cin>>t
#define co(t) cout<<t
#define mii map<int,int>
#define pii pair<int,int>
using namespace std;
struct node{
	int val;
	int pos;
};
bool ac(int x,int y)
{
	return x>y;
}
ll a[3001];
ll k;
ll n;
ll dp[3001][11];
ll pre[3005];
ll sum(int x, int y)
{
	return pre[y+1]-pre[x];
}
ll round(ll k)
{
	int l=k%10;
	if(l>=5)
	{
		return k+10-l;
	}
	else
	{
		return k-l;
	}
}
ll find(int ind, int k)
{
	if(dp[ind][k]!=-1) return dp[ind][k];
	if(k==1||ind==n-1)
	{
		return dp[ind][k]=round(sum(ind,n-1));
	}
	else
	{
		ll ma=0;
		for(int i=ind+1;i<n;i++)
		{
			ll b=round(sum(ind,i-1))+find(i,k-1);
			ma=max(ma,b);
		}
		return dp[ind][k]=ma;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		f(3001)
		{
			for(int j=0;j<11;j++)
			{
				dp[i][j]=-1;
			}
		}
		s(n);
		s(k);
		k=min(k,n);
		pre[0]=0;
		f(n)
		{
			s(a[i]);
			pre[i+1]=pre[i]+a[i];
		}
		p(find(0,k));
	}
	return 0;
}
3 Likes

@himkha_100 thanks a lot

1 Like

@himkha_100 what is β€œind” in your recurrence?
is it the length of the second-half partition?


am I correct?

@himkha_100 could you please elaborate your recurrence I’m not convinced with this problem :pensive:

@ubc_123
i think
find(ind,k) gives the optimal answer from index ind to index n-1

i.e it gives solution for optimal partitioning from index ind to index n-1

Here, find(ind, k) finds the solution for optimal partitioning when starting with subarray [ind, n-1] with k number of packages in hand.

β€˜i’ states the index from which next package starts.

1 Like

thank you completely convinced now :slightly_smiling_face:

1 Like