307 - Sticks

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

Post by rage_true » Wed Jul 06, 2005 12:47 pm

To solvers: Help us plz.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Dec 04, 2005 6:18 pm

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

Post by zaza123 » Mon Jan 02, 2006 2:28 am

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

Post by zaza123 » Mon Jan 02, 2006 3:33 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

Post by camara » Sun Mar 04, 2007 9:25 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

Post by mars kaseijin » Mon Jun 09, 2008 3:41 am

Greetings zaza, it is now g++ 4.3.0, and processors have dual core churning 64 bits; random_shuffle is part of <algorithm>. 8)
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

Post by MIGXEEEL » Sat Jun 30, 2012 10:42 pm

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

Post by brianfry713 » Mon Jul 02, 2012 9:34 pm

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

Post by MIGXEEEL » Sat Jul 07, 2012 9:59 am

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

Post by BUET » Thu Oct 25, 2012 4:37 pm

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 )

Post by brianfry713 » Fri Oct 26, 2012 12:10 am

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

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

Re: 307 Sticks

Post by lighted » Sat Jul 12, 2014 12:04 pm

I got acc! :lol: :lol: :lol:

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 3 (300-399)”