10271 - Chopsticks

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10271 - Chopsticks

Post by stcheung » Fri Oct 24, 2008 6:50 am

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

Post by amr saqr » Mon Jun 29, 2009 10:48 am

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;
}
C++ Is The Best.

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

Re: 10271 - Chopsticks

Post by deathwalk » Thu Jul 23, 2009 1:25 pm

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

Re: 10271 - Chopsticks

Post by annhy » Wed May 23, 2012 11:38 am

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

Post by Farsan » Mon Dec 30, 2013 12:34 pm

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

Re: 10271 - Chopsticks

Post by brianfry713 » Thu Jan 16, 2014 4:08 am

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

Post Reply

Return to “Volume 102 (10200-10299)”