## 10271 - Chopsticks

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10271 - Chopsticks

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
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

### Re: 10271 - Chopsticks

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,k,n,t,sticks;
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;
}
``````
C++ Is The Best.

deathwalk
New poster
Posts: 1
Joined: Thu Jul 23, 2009 1:21 pm

### Re: 10271 - Chopsticks

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.

!!!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
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

### Re: 10271 - Chopsticks

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
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10271 - Chopsticks

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 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_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,N,K;
int stk;

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10271 - Chopsticks

You can solve each test case in O(K * N) using DP.
Check input and AC output for thousands of problems on uDebug!