307 - Sticks

[rage_true]

To solvers: Help us plz.

[mamun]

Ya, would anybody be kind enough to say where the backtracking can be optimized? The acceptance rate is so low!

[zaza123]

Hello,

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

Please help!!!

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

[zaza123]

nevermind.

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

that was causing CE.

[camara]

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]

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]

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) {
		Lectura leer = new Lectura("entrada.txt");
		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()){
			dinamico1.add(scan1.nextLine());
		}
		//System.out.println(dinamico1);
		while(scan2.hasNext()){
			dinamico2.add(scan2.nextLine());
		}
		//System.out.println(dinamico2);
	
		for(int i=0;i<casos;i++){
			int cantidad = Integer.parseInt(dinamico1.get(i).toString());	
			if(cantidad<=50){
				//System.out.println(cantidad);
				String dato = dinamico2.get(i).toString();
				//System.out.println(dato);
				int largo=cantidad;
				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

[brianfry713]

I used a dfs.

[MIGXEEEL]

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]

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

[brianfry713]

100 is big enough.

[lighted]

I got acc!

I applied all prunings i used for problem 10364.
I added only one optimization:

If (current sum + current stick > target stick length) then current stick = target stick length - current stick.

This avoids summing sticks which makes current sum greater than target stick length.

My runtime is 2.865. I must think to make it better.