Page 2 of 2
Re: 10271 - Chopsticks
Posted: Fri Oct 24, 2008 6:50 am
by 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.
Re: 10271 - Chopsticks
Posted: Mon Jun 29, 2009 10:48 am
by 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;
}
Re: 10271 - Chopsticks
Posted: Thu Jul 23, 2009 1:25 pm
by 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!
Re: 10271 - Chopsticks
Posted: Wed May 23, 2012 11:38 am
by 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.
Re: 10271 - Chopsticks
Posted: Mon Dec 30, 2013 12:34 pm
by 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;
}
Re: 10271 - Chopsticks
Posted: Thu Jan 16, 2014 4:08 am
by brianfry713
You can solve each test case in O(K * N) using DP.