## 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

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### 10271 - Chopsticks

I guess that Dynamic Programming should be used to solve this problem, but I don't know the details. Please help me and thank you very much!

kpo
New poster
Posts: 8
Joined: Tue Apr 01, 2003 6:55 pm

### 10271 Chopsticks

Hi,

Can somebody help me with the problem Chopsticks. I know it's DP but I don't know how...

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Think of matrix multiplication.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 10271 Chopsticks - some tips please :-)

I find this task very interesting, and I would appreciate some hints...

I learn that there exists an O(n*k) solution. So should the program be sth like:

Code: Select all

``````for i := 1 to n do
for j := 1 to k do
update array content``````
Am I correct?

I believe that among a set of three chopsticks, our DP solution should first focus on the shorter pair, and leave the choice of the longer one at the very end. Am I right?

And what should we store in the array? I see that the faster solutions use only ~400K memory, while others consume >20000K. Any idea? Thanks in advance.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

breezechan
New poster
Posts: 4
Joined: Sun Aug 29, 2004 3:46 pm

### 10271-chopsticks .

i don't know how to do this problem using DP.But i think this is an interesting problem, and i want to solve it.
can anyone give me some hint.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I couldn't help laughing when I read this post again, after nearly one year... Today, as I've gained more knowledge on DP, I'm able to solve this task without much difficulties! Yeah~

Some notes on this task:
* For a set of chopsticks, the longest piece C is not important. Of course, we need to ensure that this piece actually exists.
* And for pieces A and B, we always choose neighbours (i.e. L with L[i+1]) so as to minimize (A-B)^2.
* My solution is O(n*k). It uses ~400K memory, and its runtime is ~0.65 sec.

Have fun~~~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

phoenixKonquerer
New poster
Posts: 3
Joined: Thu Mar 17, 2005 3:13 pm

### 10271 - Chopsticks

Hello there,

I don't know how to select the third chopstick. Is there any constraints on how to select the third chopstick or do we just pick the next available chopstick that is longer than the other 2 ?

Also can anyone who got their solution AC provide some test input along with the correct answer so i can test mine.

Thanks so much

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Observer wrote: * For a set of chopsticks, the longest piece C is not important. Of course, we need to ensure that this piece actually exists.
Hi! Can you explain this in little more detail (how to ensure that the longest piece exists). I managed to figure out the O(k*n) algorithm (I'm only checking two neighbour chopsticks, A and B, such that (L - L[A])^2 is minimal). However, I don't know how to check if there is a larger stick I can group A and B with (without violating the other sets of sticks).
I hope you'll understand what i mean. Thanks in advance.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Do the DP in the right order. Then, it is easy to calculate how many sticks are free to be the biggest stick in a set (note that you don't really care about which one you assign to which set).

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Adrian Kuegel wrote:Do the DP in the right order. Then, it is easy to calculate how many sticks are free to be the biggest stick in a set (note that you don't really care about which one you assign to which set).
I don't understand. Am I supposed to do it like this?

Code: Select all

``````for ( i = 0; i < n; ++i )
for ( j = 0; j < k; ++ j )
``````
How does this order help me calculate how many sticks are still free? Any help is appreciated.

TIA.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I was not speaking about the relative order of the two for-loops, but of the order in which you go through the chopsticks during dp. Think about which order does help for what you want to do (easy calculation how many bigger sticks are free).

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Adrian Kuegel wrote:I was not speaking about the relative order of the two for-loops, but of the order in which you go through the chopsticks during dp. Think about which order does help for what you want to do (easy calculation how many bigger sticks are free).
Note: editing this post, since I haven't still solved the problem.

Are you talking about the reversed order? Could you please be more specific? I tried saving the number of sticks that are longer than S, and checking in each iteration of the for loop (which goes from 1 to K) if there is enough longer sticks to cover all the remaining pairs (K - i). This doesn't work, because sticks A and B for person i don't have to be necessary longer than person i-1's (only the stick C has to be longer).
I also thought about adding a new dimension to the table, denoting the number of remaining longer sticks, but then the running time wouldn't be O(n*k) and the program would use much more memory.

Thanks in advance. This problem is driving me crazy.

Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm
Solved it finally.
Hint to the other solvers: the third stick doesn't have to be strictly longer that the other two sticks (for example {1, 1, 1} is the possible set with badness 0). This makes checking whether there are free sticks left extremely easy.
Thanks to Observer.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Can anybody see some critical inputs for which my code would fail??

Code: Select all

``````#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

ll help[2][1024];
ll temp[1024];
ll data[6000];
int n, k, t;

int main(){

cin >> t;
while(t-- && cin >> k >> n){
for(int i = 0; i < n; i++) cin >> data[i];
memset(help, 1, sizeof(help));
memset(temp, 1, sizeof(temp));
help[0][0] = help[1][0] = temp[0] = 0;
for(int i = n - 3; i >= 0; i--){
for(int j = 1; j*3 <= n - i; j++)
temp[j] <?= help[1][j - 1] + (data[i] - data[i + 1])*(data[i] - data[i + 1]);
memcpy(help[1], help[0], sizeof(temp));
memcpy(help[0], temp, sizeof(temp));
}
cout << (help[0][k + 8] <? help[1][k + 8]) << endl;
}

return 0;
}``````

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
whats the correct answer for the input produced by the program below ? I get 1205 with my WA code..,,

Code: Select all

``````#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main(){
int i,j,t,k,n;
int a[5001];
cout <<1<<endl;
k=1000 ; n=5000;
cout << k <<" " <<n<<"\n";
t=n;
while( t-- )a[t]=rand()%32001;
sort(a,a+n);
for( int i=0;i<n;i++ )
cout <<a[i]<<" ";
return 0;
}
``````
if u can think of it .. u can do it in software.