10271 - Chopsticks

[oker]

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]

Hi,

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

Thanks in advance

[Larry]

Think of matrix multiplication.

[Observer]

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.

[breezechan]

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]

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

[phoenixKonquerer]

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]

* 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]

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]

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.

[Adrian Kuegel]

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]

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]

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]

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]

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