10271 - Chopsticks

[stcheung]

There's not much hints on this problem so I had to get inspiration by actually reading the code above. Let me throw out some pointers:
(1) Your DP solution should keep track of D[k][n], which represents the minimal badness that can be achieved if you must pick k pairs of chopsticks from chopsticks 1...n
(2) You need to determine how to fill D[k] based on all the D[k-1][]
(3) Note that the 3rd chopstick for each set in D[k][n] above may or may not come from chopsticks 1...n
(4) While filling the D[k][n], you need to separately keep track of how many more chopstick pairs you can form, and whether there are enough "3rd chopsticks". You need to be careful and think through the couple different cases.

[amr saqr]

I don't know what's wrong with my code, it gives TLE,
can anyone help me plz,
here is the code

Code: Select all

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
int memo[1008][5000],k,n,t,sticks[5000];
int sqr(int x)
{
	return x*x;
}
int val(int x,int y)
{
	return sqr(x-y);
}
int dp(int p,int ind)
{
	if (p==k)
		return 0;
	int &ret=memo[p][ind];
	if (ret!=-1)
		return ret;
	ret=INT_MAX;	
	for (int i=ind;(n-i-3)/3.0>=k-p-1.0;i++)
		ret=min(ret,val(sticks[i],sticks[i+1])+dp(p+1,i+2));
	return ret;
}
int main()
{
	//freopen("input.txt","r",stdin);
	cin>>t;
	while (t--)
	{
		cin>>k>>n;
		k+=8;
		for (int i=0;i<n;i++)
			cin>>sticks[i];
		for (int i=0;i<k;i++)
			memset(memo[i],-1,n*4);
		cout<<dp(0,0)<<endl;
	}
	return 0;
}

[deathwalk]

All right - I gave in after trying this for too long:( Searched around a bunch and found the following code in two places - funny it works too.

!!!Spoiler Alert!!!
http://code.google.com/p/acm-uva-ufrgs/ ... svn24&r=24
!!!End Spoiler!!!

Can someone take a look at the code and explain a couple of things to me? because if I change the values according to my questions below, this one fails.

0. How do you figure out what are the pairs chosen? (I am assuming at the turn of the numbers - am I right?)
1. What do they do to prevent choosing the same value over and over again? (Note: Even after the accumulated sum, you could end up being the smallest on the whole list). This also means the 0 question assumption is wrong.
2. What is the significance of their supposed third stick move? How does it ensure there is a left over stick?

Thanks a lot and sorry for the necro!

[annhy]

If you reverse the input array first (descending order), checking the existence of the longest chopstick of each set would be easier.

Hope it helps.

[Farsan]

Got TLE... is memoization possible for such huge size of input??

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;

long long dp[1010][5010],N,K;
int stk[5010];

long long solve(int prson,int chop,int baki)
{
    if(N-chop+1<baki)
    return inf;
    if(prson>K)
    {
        if(N-chop+1>=baki)
        return 0;
        return inf;
    }
    if(dp[prson][chop]!=-1)
    return dp[prson][chop];
    long long i,j,k,m,mx1=inf,mx=inf;
    for(i=chop,k=0;i<N;i++)
    {
        for(j=i+2,k=0;j<=N;j++,k++)
        {
            mx1=(stk[i+1]-stk[i])*(stk[i+1]-stk[i]);
            m=baki-k;
            if(m<0)
            m=0;
            mx1+=solve(prson+1,j,m+1);
            mx=min(mx1,mx);
        }
    }
    return dp[prson][chop]=mx;
}


int main()
{

    int i,j,k,m,n,t;
    inp1(t);
    while(t--)
    {
        inp2(K,N);
        K=K+8;
        for(i=1;i<=N;i++)
        {
            inp1(stk[i]);
            mem(dp[i],-1);
        }
        cout<<solve(1,1,1)<<endl;
    }
    return 0;
}

[brianfry713]

You can solve each test case in O(K * N) using DP.