## 307 - Sticks

Moderator: Board moderators

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm
To solvers: Help us plz.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Ya, would anybody be kind enough to say where the backtracking can be optimized? The acceptance rate is so low!

zaza123
New poster
Posts: 4
Joined: Sun Oct 16, 2005 1:09 pm

### 307 CE

Hello,

I am trying to solve problem no307, but something is causing compiler error, but i really do not know what.

PS Is there a flag/option that could be used on g++ for it to compile like it was an older version? For example, if I had g++ version 3.3, and I want to use as it was 2.9?

Thanks!

Code: Select all

``````#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> sz, used;
int total, stick_size;

bool ok( int sum, int val, int piece ) {
if( sum == 0 && piece == total ) return true;
if( piece == total ) return false;
int last = -1;

for( int i = 0; i < sz.size(); ++i ) {
if( used[i] == 1 ) continue;
if( last == sz[i] ) continue;

used[i] = 1;

if( val - sz[i] == 0 ) {
if( ok( sum-sz[i], stick_size, piece+1 ) )
return true;
} else if( val - sz[i] > 0 ) {
if( ok( sum-sz[i], val-sz[i], piece ) )
return true;
}

used[i] = 0;
last = sz[i];
}
return false;
}

int solve( int sum )
{
used = vector<int>( sz.size(), 0 );

random_shuffle( sz.begin(), sz.end() );

int sol = (int)( sqrt( (double)sum ) + .5 ) + 1;
for( ; sol > 0; --sol ) {
if( sum % sol != 0 ) continue;

stick_size = sum / sol;
total = sol;

if( ok( sum, stick_size, 0 ) ) return stick_size;
}

return sum;
}

int main( void )
{
for( int n; scanf( "%d", &n ) && n != 0; ) {
int sum = 0;
sz.resize( n );
for( int i = 0; i < n; ++i ) {
scanf( "%d", &sz[i] );
sum += sz[i];
}
printf( "%d\n", solve( sum ) );
}
return 0;
}
``````
Last edited by zaza123 on Mon Jan 02, 2006 3:34 pm, edited 1 time in total.

zaza123
New poster
Posts: 4
Joined: Sun Oct 16, 2005 1:09 pm
nevermind.

is random_shuffle part of the c++ standard or just the extension?

that was causing CE.

camara
New poster
Posts: 6
Joined: Wed Jun 15, 2005 7:52 pm
I'm getting crazy with this one... I've tried all the test cases and even found some other tricky ones, for example:
17
2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 5 3
0
Correct output is 14.

However, I still get WA. The code is very fast, I use DP (I don't allow to re-test total intermediate lengths that have already been tested).

If someone can give a hint...

mars kaseijin
New poster
Posts: 22
Joined: Mon Sep 19, 2005 4:58 am
Contact:

### Re: 307 CE

Greetings zaza, it is now g++ 4.3.0, and processors have dual core churning 64 bits; random_shuffle is part of <algorithm>.
compiling your code now gives warning between unsigned and signed integers, it runs OK!

MIGXEEEL
New poster
Posts: 6
Joined: Mon Jun 18, 2012 6:03 pm

### 307 Sticks

Hi everyone, I need to do this problem with DP, but I can't figure out what I have to store, or how I have to divide the problem.
Here is my code, I did a DP function, but the thing is that some cases give a wrong answer, where is my mistake?

Code: Select all

``````import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
leer.Abrir();
int casos = leer.getCasos();
//System.out.println(casos);
String parte1=leer.getParte1();
//System.out.println(parte1);
String parte2=leer.getParte2();
//System.out.println(parte2);
ArrayList dinamico1 = new ArrayList();
ArrayList dinamico2 = new ArrayList();
Scanner scan1 = new Scanner(parte1);
Scanner scan2 = new Scanner(parte2);
while(scan1.hasNext()){
}
//System.out.println(dinamico1);
while(scan2.hasNext()){
}
//System.out.println(dinamico2);

for(int i=0;i<casos;i++){
String dato = dinamico2.get(i).toString();
//System.out.println(dato);
int[] sticks = new int[largo];
int k=0;
StringTokenizer token = new StringTokenizer(dato);
while(token.hasMoreTokens()){
String aux=token.nextToken();
int aux1=Integer.parseInt(aux);
sticks[k]=aux1;
k++;
}
int[] sticksAnterior = sticks;
Quicksort quick = new Quicksort();
quick.ordena(sticks);
int max = sticks[0];
int suma = 0;
//System.out.println(max);

for(int j=0;j<sticks.length;j++){
suma = suma + sticks[j];
}

//System.out.println(sum);
for(int meta = max; meta<=suma;meta++){
if(suma%meta==0){
int particiones = suma/meta;
if(particiones(sticks,particiones)){
System.out.println(meta);
break;
}

}
}
}
else
{
System.out.println("ERROR");
}

}
}
static boolean particiones(int [] sticks, int partes){
int n=sticks.length;
boolean M[]= new boolean[partes+1];
M[1]=true;
for(int i=1;i<n;i++){
for(int j=sticks[i];j<partes+1;j++){
M[j]=M[j]||M[j-sticks[i]];
}
}
return M[partes];
}
}

``````
Thank you
Last edited by MIGXEEEL on Sat Jul 07, 2012 9:57 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 307 Sticks

I used a dfs.
Check input and AC output for thousands of problems on uDebug!

MIGXEEEL
New poster
Posts: 6
Joined: Mon Jun 18, 2012 6:03 pm

### Re: 307 Sticks

I know but I wanna do it with DP.
This problem is like the partition problem with n subsets isn't?
It means that is NP-Complete?

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

### 307 Sticks

what is the max value of n(number of parts of all sticks)?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 307 Sticks ( got TLE )

100 is big enough.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 307 Sticks

I got acc!

I applied all prunings i used for problem 10364.