10271  Chopsticks
Moderator: Board moderators
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!
10271 Chopsticks
Hi,
Can somebody help me with the problem Chopsticks. I know it's DP but I don't know how...
Thanks in advance
Can somebody help me with the problem Chopsticks. I know it's DP but I don't know how...
Thanks in advance
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: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.
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
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 New poster
 Posts: 4
 Joined: Sun Aug 29, 2004 3:46 pm
10271chopsticks .
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.
can anyone give me some hint.
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 (AB)^2.
* My solution is O(n*k). It uses ~400K memory, and its runtime is ~0.65 sec.
Have fun~~~
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 (AB)^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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 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
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
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).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.
I hope you'll understand what i mean. Thanks in advance.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 Tomislav Novak
 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
I don't understand. Am I supposed to do it like this?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).
Code: Select all
for ( i = 0; i < n; ++i )
for ( j = 0; j < k; ++ j )
TIA.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 Tomislav Novak
 New poster
 Posts: 44
 Joined: Fri Feb 20, 2004 5:52 pm
Note: editing this post, since I haven't still solved the problem.Adrian Kuegel wrote:I was not speaking about the relative order of the two forloops, 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).
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 i1'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
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;
}
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.