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

Post by oker » Wed Jul 17, 2002 4:11 am

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

Post by kpo » Mon Jul 14, 2003 4:13 pm

Hi,

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

Thanks in advance

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

Post by Larry » Mon Jul 14, 2003 6:04 pm

Think of matrix multiplication.

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

10271 Chopsticks - some tips please :-)

Post by Observer » Sat Apr 24, 2004 3:20 pm

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. :D
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 .

Post by breezechan » Tue Sep 07, 2004 2:15 pm

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

Post by Observer » Wed Mar 02, 2005 6:25 pm

I couldn't help laughing when I read this post again, after nearly one year... :oops: 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~~~ :D
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

Post by phoenixKonquerer » Fri Mar 18, 2005 2:09 pm

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

:lol:

User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by Tomislav Novak » Thu Mar 24, 2005 2:55 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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Mar 24, 2005 5:58 pm

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).

User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by Tomislav Novak » Sat Mar 26, 2005 11:36 am

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. :oops: 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. :-)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Mar 26, 2005 4:08 pm

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).

User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by Tomislav Novak » Sat Mar 26, 2005 6:00 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. :)

User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

Post by Tomislav Novak » Wed Mar 30, 2005 9:25 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

Post by minskcity » Tue Apr 26, 2005 8:04 am

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;
}

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sun Aug 07, 2005 8:14 am

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.

Post Reply

Return to “Volume 102 (10200-10299)”