OJ Board • 10032 - Tug of War - Page 4

Page 4 of 7

Posted: Mon Feb 12, 2007 9:10 pm

by ExUCI

Can someone tell what's the problem with this problem. I do the DP recursively with a little pruning. So I don't have TLE, but it's getting WA and my program passed all the inputs on this threads.
I really need some critical inputs.

Please a little help, this problem it's driving me crazy.

Thanks in advance.

10032 WA

Posted: Mon Apr 16, 2007 3:24 am

by LithiumDex

I'm getting WA in 1.3 seconds

For the following input:

Code: Select all

My output is:

Code: Select all

2641 2643

For this input:

Code: Select all

My output is:

Code: Select all

23892 23892

My code is:

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int total;
int half;
int best;
vector<int> u;

#define ABS(_x) ((_x)<0?-(_x):(_x))

void find ( int start )
{
    int any = 0;
    int subttl = 0;
    for (int i=start; i<v.size(); i++)
        if (!u[i])
            subttl += v[i];

    subttl = (subttl/2)+1;

    if (subttl>0
            && ABS(total-(half+subttl)-(half+subttl)) > ABS((total-best)-best))
        return;
    
    for (int i=start; i<v.size(); i++)
    {
        if (!u[i])
        {
            any++;
            u[i]=1;
            half+=v[i];
            find(i+1);
            half-=v[i];
            u[i]=0;
        }
    }
    
    if (!any && ABS((total-half)-half) < ABS((total-best)-best))
        best = half;
}
                               
int main ( void )
{
    int cases;
    cin >> cases;
    while (cases--)
    {
        int count;
        cin >> count;
        v = vector<int>(count);
        total = 0;
        for (int i=0; i<count; i++)
        {
            cin >> v[i];
            total += v[i];
        }
        sort(v.rbegin(), v.rend());
        best = half = 0;
        u = vector<int>(count, 0);
        find(0);

        cout << min(best, total-best) << " " << max(total-best, best) << endl;
    }
    return 0;
}

Can anyone see an error in my code or output, or provide an input at which my program fails?

Thanks

Posted: Mon Apr 16, 2007 8:43 am

by sumantbhardvaj

I am facing TLE in this problem. I tested my program for your I/O and it gave following output :

Code: Select all

   2642 2642

ur second I/O is invalid. since weights should be <=450

By the way, what is your algo ?

I used top down approach with memoization to produce all possible sum using n/2 weights with some pruning , but getting timed out?

Posted: Mon Apr 16, 2007 5:55 pm

by LithiumDex

That algorithm is wrong... it doesn't check if the number of people on both sides differ by <= 1

I've been working on a new algorithm, but still WA

Posted: Mon Apr 16, 2007 6:20 pm

by sumantbhardvaj

What is the correct approach to this problem .... ? somebody plz suggest.

Posted: Mon Apr 16, 2007 7:20 pm

by LithiumDex

I've come up with a better algorithm:

Sort people from heaviest to lightest

N = Number of people
- Backtrack to find all possible combinations of (N is odd: (N/2)+/-1, even: N/2) people

- At any point we have a count (number of people picked for one side),
and we can calculate the lowest difference for any combination from that point to the end
- Use DP to cut off branches, using an NxM array -- where M is the maximum number of people on one side

This solution gives me WA in 5 seconds, but is more accurate to the problem than my last one...

Code: Select all

my WA output is:

Code: Select all

11467 11467

For these:

Code: Select all

my WA output is:

Code: Select all

could someone please verify this input?

Posted: Tue Apr 17, 2007 2:31 am

by LithiumDex

c'mon, someone has to be able to run this test.. there's only 2 other varified test inputs on this board, and they're not very usefull. I'm sure more people then just myself will benifit from this.

Posted: Sun Apr 22, 2007 9:15 pm

by Relja

it's ok.

edit: "The outputs of two consecutive cases will be separated by a blank line"

DP?

Posted: Mon Jun 18, 2007 5:08 pm

by adelar

Hi,
how can I do this problem using Dynamic Programming?
thanks... .

Posted: Mon Jun 18, 2007 5:37 pm

by rio

Yes, you can. At least, I solved this problem using DP (1.859 sec).

----
Rio

Posted: Wed Jul 11, 2007 2:34 pm

by andysoft

Hi guys!
I can't understand - I get TLE every time I submit this task (many times, really). But my algorithm doesn't seem to be complex. Can you have a look and probably find a mistake in my code.
Thanx.

Code: Select all

this code got too old, look below please.

Posted: Wed Jul 11, 2007 3:25 pm

by andysoft

This code in C++:

Code: Select all

this code got too old, look below please.

Posted: Sat Nov 03, 2007 7:57 am

by shakil

Why Compile Error. Please help.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>

long n,N,m,nn,i,j,k,s_u_m,diferen,res,l_o_w,cas,cas1;
long X[22509],Y[22509],XX[22509],YY[22509],sa[109],flag[22509];

int main()
{

	scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{
	if(cas1!=1)
		printf("\n");
	scanf("%ld",&n);
	s_u_m=0;
for(i=0;i<n;i++)
{scanf("%ld",&sa[i]);
s_u_m+=sa[i];}

memset(flag,0,sizeof(flag));

for(i=0;i<n-1;i++)
for(j=0;j<n-1-i;j++)
if(sa[j]>sa[j+1])
{
k=sa[j];
sa[j]=sa[j+1];
sa[j+1]=k;
}
N=0;
diferen=s_u_m;
res=0;
for(i=0;i<n;i++)
if(flag[sa[i]]!=1)
{
X[N]=sa[i];
Y[N]=i;
flag[sa[i]]=1;
if(nn==1||n/2==1)
{
if(diferen>abs(s_u_m-sa[i]-sa[i]))	
{
diferen=abs(s_u_m-sa[i]-sa[i]);
res=sa[i];
}
}
N++;
}
nn=n/2;
if(n%2!=0)
nn++;




for(i=2;i<=nn;i++)
{m=0;
    l_o_w=0;
	for(j=0;j<N;j++)
		for(k=Y[j]+1;k<n;k++)
		{
			if((k+(n/2)-i)>=n)
			break;
		    if(flag[X[j]+sa[k]]!=i)
			{
				XX[m]=X[j]+sa[k];
				YY[m]=k;
				flag[XX[m]]=i;
				m++;
				if(XX[m-1]+490*(nn-i)<=s_u_m/2&&XX[m-1]+490*(nn-i)>l_o_w)
				l_o_w=XX[m-1];
			}
		}

if(i==n/2||i==nn)
{
for(j=0;j<m;j++)
if(abs(s_u_m-XX[j]-XX[j])<diferen)
{diferen=abs(s_u_m-XX[j]-XX[j]);res=XX[j];}
}

if(i!=nn)
{
N=0;
for(j=0;j<m;j++)
if(XX[j]+sa[YY[j]]*(n/2-i)<=s_u_m/2&&XX[j]>=l_o_w)
{
X[N]=XX[j];
Y[N]=YY[j];
N++;
}
}



}

if(s_u_m-res<res)
res=s_u_m-res;

printf("%ld %ld\n",res,s_u_m-res);
}

return 0;
}

Why CE...

Posted: Mon Dec 10, 2007 3:06 pm

by adelar

Hi shakil,
is missing:

Code: Select all

#include <stdlib.h>

[]'s

:-( WA

Posted: Thu Sep 11, 2008 10:03 pm

by DonLimpio

Hello,

I tested it with all inputs of this topic but UVa don't accept it.
Someone know any critical input for this problem outside this topic?

tanks.

Code: Select all

#include <cstdlib>
#include <iostream>

char entrada[50];
int personas, personasProcesadas, personasAdmitidas;
int pesos[100];
int izqPesosPersonas[110];
int derPesosPersonas[110];
int izquierda, derecha;
int izqPersonas, derPersonas;

int izq_UnoPorUnoIzquierda;
int der_UnoPorUnoIzquierda;
int izq_DosPorUnoIzquierda;
int der_DosPorUnoIzquierda;
int izq_UnoAIzquierda;
int der_UnoAIzquierda;
int izq_UnoPorDosIzquierda;
int der_UnoPorDosIzquierda;
int izq_UnoADerecha;
int der_UnoADerecha;
int izq_UnoPorUnoDerecha;
int der_UnoPorUnoDerecha;
int izq_DosPorUnoDerecha;
int der_DosPorUnoDerecha;
int izq_UnoPorDosDerecha;
int der_UnoPorDosDerecha;

int lee_linea( char *s )
{
	int ch, n=0;

	while( (ch=getchar()) != EOF && ch != '\n' ) {
		if ( ch != '\r' ) {
			*s++ = ch;
			n++;
		}
	}

	*s='\0';
	return n;
}

int compadre(const void *aa,const void *bb)
{
    int *a= (int *) aa;
    int *b= (int *) bb;
	return(*a>*b)-(*a<*b);
}

void repartir(){
         int aux;
         if (izquierda < derecha){
                       aux=izqPersonas-derPersonas;
                       if (aux > 0){ //izquierda es menor y ya tiene 1 persona mas
                               derecha+=pesos[personasAdmitidas+1];
                               derPesosPersonas[derPersonas]=pesos[personasAdmitidas+1];
                               derPersonas++;
                               personasAdmitidas++;
                       }else{
                             izquierda+=pesos[personasProcesadas];
                             izqPesosPersonas[izqPersonas]=pesos[personasProcesadas];
                             izqPersonas++;
                             personasProcesadas--;
                       }
         }
         else{
               if (derecha < izquierda){
                  aux=derPersonas-izqPersonas;
                  if (aux > 0){ //derecha es menor y ya tiene 1 persona mas
                     izquierda+=pesos[personasAdmitidas+1];
                     izqPesosPersonas[izqPersonas]=pesos[personasAdmitidas+1];
                     izqPersonas++;
                     personasAdmitidas++;
                  }else{
                     derecha+=pesos[personasProcesadas];
                     derPesosPersonas[derPersonas]=pesos[personasProcesadas];
                     derPersonas++;
                     personasProcesadas--;
                  }
               }else{ //derecha == izquierda
                      aux=derPersonas-izqPersonas;
                      if (aux > 0){
                         izquierda+=pesos[personasProcesadas];
                         izqPesosPersonas[izqPersonas]=pesos[personasProcesadas];
                         izqPersonas++;
                         personasProcesadas--;
                      }
                      if (aux <= 0){
                         derecha+=pesos[personasProcesadas];
                         derPesosPersonas[derPersonas]=pesos[personasProcesadas];
                         derPersonas++;
                         personasProcesadas--;
                      }
               }
         }
}

void DosPorUnoIzquierda(){ // Paso 2 x 1 de izquierda menor derecha mayor
     int izqAux, derAux, izqPesosAux;
     izq_DosPorUnoIzquierda=izquierda;
     der_DosPorUnoIzquierda=derecha;
     for(int i=0; i < izqPersonas; i++){
             for(int j=i+1; j<izqPersonas; j++){
                     izqPesosAux=izqPesosPersonas[i]+izqPesosPersonas[j];
                     for(int k=derPersonas-1; k>=0; k--){

                             izqAux=izquierda;
                             derAux=derecha;

                             if(izqPesosAux > derPesosPersonas[k]) break;
                             izqAux+=derPesosPersonas[k];
                             derAux-=derPesosPersonas[k];
                             izqAux-=izqPesosAux;
                             derAux+=izqPesosAux;
                             
                             if(abs(izqAux-derAux) < abs(der_DosPorUnoIzquierda-izq_DosPorUnoIzquierda)){
                                   der_DosPorUnoIzquierda=derAux;
                                   izq_DosPorUnoIzquierda=izqAux;
                             }
                     }
             }
     }
}                             

void DosPorUnoDerecha(){ // Paso 2 x 1 de izquierda mayor derecha menor
     int izqAux, derAux, izqPesosAux;
     izq_DosPorUnoDerecha=izquierda;
     der_DosPorUnoDerecha=derecha;
     for(int i=izqPersonas-1; i >= 0; i--){
             for(int j=i-1; j>=0; j--){
                     izqPesosAux=izqPesosPersonas[i]+izqPesosPersonas[j];
                     for(int k=0; k<derPersonas; k++){

                             izqAux=izquierda;
                             derAux=derecha;

                             if(izqPesosAux < derPesosPersonas[k]) break;
                             izqAux+=derPesosPersonas[k];
                             derAux-=derPesosPersonas[k];
                             izqAux-=izqPesosAux;
                             derAux+=izqPesosAux;
                             
                             if(abs(izqAux-derAux) < abs(der_DosPorUnoDerecha-izq_DosPorUnoDerecha)){
                                   der_DosPorUnoDerecha=derAux;
                                   izq_DosPorUnoDerecha=izqAux;
                             }
                     }
             }
             
     }
}                             

                             
void UnoPorUnoIzquierda(){ // Paso 1 x 1 de izquierda menor derecha mayor
     int izqAux, derAux;
     izq_UnoPorUnoIzquierda=izquierda;
     der_UnoPorUnoIzquierda=derecha;
     for(int i=0; i < izqPersonas; i++){
             for(int j=derPersonas-1; j>=0; j--){ 

                     izqAux=izquierda;
                     derAux=derecha;

                     if(izqPesosPersonas[i] > derPesosPersonas[j]) break;
                     izqAux+=derPesosPersonas[j];
                     derAux-=derPesosPersonas[j];
                     izqAux-=izqPesosPersonas[i];
                     derAux+=izqPesosPersonas[i];

                     if(abs(izqAux-derAux) < abs(der_UnoPorUnoIzquierda-izq_UnoPorUnoIzquierda)){
                                   der_UnoPorUnoIzquierda=derAux;
                                   izq_UnoPorUnoIzquierda=izqAux;
                     }
             }
     }
}

void UnoPorUnoDerecha(){ // Paso 1 x 1 de izquierda mayor derecha menor
     int izqAux, derAux;
     izq_UnoPorUnoDerecha=izquierda;
     der_UnoPorUnoDerecha=derecha;
     for(int i=0; i < derPersonas; i++){
             for(int j=izqPersonas-1; j>=0; j--){ 

                     izqAux=izquierda;
                     derAux=derecha;

                     if(derPesosPersonas[i] > izqPesosPersonas[j]) break;
                     izqAux-=izqPesosPersonas[j];
                     derAux+=izqPesosPersonas[j];
                     izqAux+=derPesosPersonas[i];
                     derAux-=derPesosPersonas[i];

                     if(abs(izqAux-derAux) < abs(der_UnoPorUnoDerecha-izq_UnoPorUnoDerecha)){
                                   der_UnoPorUnoDerecha=derAux;
                                   izq_UnoPorUnoDerecha=izqAux;
                     }
             }
     }
}


void UnoAIzquierda(){ // Paso de 1 de derecha a la izquierda
     int izqAux, derAux;
     izq_UnoAIzquierda=izquierda;
     der_UnoAIzquierda=derecha;
     for(int i=0; i < derPersonas; i++){
             izqAux=izquierda;
             derAux=derecha;
             izqAux+=derPesosPersonas[i];
             derAux-=derPesosPersonas[i];
             if(abs(izqAux-derAux) < abs(der_UnoAIzquierda-izq_UnoAIzquierda)){
                                   der_UnoAIzquierda=derAux;
                                   izq_UnoAIzquierda=izqAux;
             }
     }
}

void UnoADerecha(){ // Paso de 1 de izquierda a la derecha
     int izqAux, derAux;
     izq_UnoADerecha=izquierda;
     der_UnoADerecha=derecha;
     for(int i=0; i < derPersonas; i++){
             izqAux=izquierda;
             derAux=derecha;
             izqAux-=izqPesosPersonas[i];
             derAux+=izqPesosPersonas[i];
             if(abs(izqAux-derAux) < abs(izq_UnoADerecha-der_UnoADerecha)){
                                   der_UnoADerecha=derAux;
                                   izq_UnoADerecha=izqAux;
             }
     }
}

void UnoPorDosIzquierda(){ // Paso 1 x 2 de izquierda menor derecha mayor
     int izqAux, derAux, derPesosAux;
     izq_UnoPorDosIzquierda=izquierda;
     der_UnoPorDosIzquierda=derecha;
     for(int i=0; i < izqPersonas; i++){
             for(int j=derPersonas-1; j >= 0; j--){
                     for(int k=j-1; k >=0; k--){
                             derPesosAux=derPesosPersonas[j]+derPesosPersonas[k];

                             izqAux=izquierda;
                             derAux=derecha;

                             if(izqPesosPersonas[i] > derPesosAux) break;
                             izqAux+=derPesosAux;
                             derAux-=derPesosAux;
                             izqAux-=izqPesosPersonas[i];
                             derAux+=izqPesosPersonas[i];
                             
                             if(abs(izqAux-derAux) < abs(der_UnoPorDosIzquierda-izq_UnoPorDosIzquierda)){
                                   der_UnoPorDosIzquierda=derAux;
                                   izq_UnoPorDosIzquierda=izqAux;
                             }
                     }
             }
     }
}             

void UnoPorDosDerecha(){ // Paso 1 x 2 de izquierda mayor derecha menor
     int izqAux, derAux, derPesosAux;
     izq_UnoPorDosDerecha=izquierda;
     der_UnoPorDosDerecha=derecha;
     for(int i=izqPersonas-1; i >= 0; i--){
             for(int j=0; j<derPersonas; j++){
                     for(int k=j+1; k <derPersonas; k++){
                             derPesosAux=derPesosPersonas[j]+derPesosPersonas[k];

                             izqAux=izquierda;
                             derAux=derecha;

                             if(izqPesosPersonas[i] < derPesosAux) break;
                             izqAux+=derPesosAux;
                             derAux-=derPesosAux;
                             izqAux-=izqPesosPersonas[i];
                             derAux+=izqPesosPersonas[i];
                             
                             if(abs(izqAux-derAux) < abs(der_UnoPorDosDerecha-izq_UnoPorDosDerecha)){
                                   der_UnoPorDosDerecha=derAux;
                                   izq_UnoPorDosDerecha=izqAux;
                             }
                     }
             }
     }
}             


int main(int argc, char *argv[])
{   
    int casos=0;
    int antipersonas=0;
    
    lee_linea(entrada);
    casos=atoi(entrada);
    
    for(; casos > 0; casos--){
          personas=0;
          antipersonas=0;
          izquierda=0;
          derecha=0;
          izqPersonas=0;
          derPersonas=0;
          for(int i=0; i<110; i++){
                  izqPesosPersonas[i]=0;
                  derPesosPersonas[i]=0;
          }
          
          lee_linea(entrada);
          lee_linea(entrada);
          personas=atoi(entrada);
          if (personas > 100){
                       antipersonas= personas - 100;
                       personas=100;
          }
          
          for (int i=0; i < personas; i++){
              lee_linea(entrada);
              pesos[i]=atoi(entrada);
              if(pesos[i] < 1 || pesos[i] > 450){
                          i--;
                          if (antipersonas >0)antipersonas--;
                          else personas--;
                          
              }
          }
               
          for (int i=0; i < antipersonas; i++){
              lee_linea(entrada);
          }

          qsort(pesos,personas,sizeof(int),compadre);
          
          personasProcesadas=personas-1;
          personasAdmitidas=-1;
          while(personasProcesadas > personasAdmitidas){
                                   repartir();
          }

          qsort(izqPesosPersonas,izqPersonas,sizeof(int),compadre);
          qsort(derPesosPersonas,derPersonas,sizeof(int),compadre);
          
          if(izquierda < derecha){
                       if(izqPersonas > derPersonas){
                                     UnoPorUnoIzquierda();
                                     DosPorUnoIzquierda();
                                     if(abs(derecha-izquierda) > abs(der_UnoPorUnoIzquierda-izq_UnoPorUnoIzquierda)){
                                                               derecha=der_UnoPorUnoIzquierda;
                                                               izquierda=izq_UnoPorUnoIzquierda;
                                     }
                                     
                                     if(abs(derecha-izquierda) > abs(der_DosPorUnoIzquierda-izq_DosPorUnoIzquierda)){
                                                               derecha=der_DosPorUnoIzquierda;
                                                               izquierda=izq_DosPorUnoIzquierda;
                                     }
          
          
          
                       }
                       else{
                            if(izqPersonas < derPersonas){
                                           UnoAIzquierda();
                                           UnoPorUnoIzquierda();
                                           
                                           UnoPorDosIzquierda();
                                           if(abs(derecha-izquierda) > abs(der_UnoAIzquierda-izq_UnoAIzquierda)){
                                                                     derecha=der_UnoAIzquierda;
                                                                     izquierda=izq_UnoAIzquierda;
                                           }
                                           if(abs(derecha-izquierda) > abs(der_UnoPorUnoIzquierda-izq_UnoPorUnoIzquierda)){
                                                                     derecha=der_UnoPorUnoIzquierda;
                                                                     izquierda=izq_UnoPorUnoIzquierda;
                                           }
                                           
                                           if(abs(derecha-izquierda) > abs(der_UnoPorDosIzquierda-izq_UnoPorDosIzquierda)){
                                                               derecha=der_UnoPorDosIzquierda;
                                                               izquierda=izq_UnoPorDosIzquierda;
                                           }
                            }
                       }
                                           
          }
          else{
               if(izquierda > derecha){
                            if(izqPersonas > derPersonas){
                                           UnoADerecha();
                                           UnoPorUnoDerecha();
                                           DosPorUnoDerecha();            
                                           if(abs(derecha-izquierda) > abs(der_UnoADerecha-izq_UnoADerecha)){
                                                                     derecha=der_UnoADerecha;
                                                                     izquierda=izq_UnoADerecha;
                                           }
                                           if(abs(derecha-izquierda) > abs(der_UnoPorUnoDerecha-izq_UnoPorUnoDerecha)){
                                                               derecha=der_UnoPorUnoDerecha;
                                                               izquierda=izq_UnoPorUnoDerecha;
                                           }
                                           
                                           if(abs(derecha-izquierda) > abs(der_DosPorUnoDerecha-izq_DosPorUnoDerecha)){
                                                               derecha=der_DosPorUnoDerecha;
                                                               izquierda=izq_DosPorUnoDerecha;
                                           }
                            }
                            else{
                                 if(izqPersonas < derPersonas){
                                                UnoPorUnoDerecha();
                                                UnoPorDosDerecha();
                                                if(abs(derecha-izquierda) > abs(der_UnoPorUnoDerecha-izq_UnoPorUnoDerecha)){
                                                                          derecha=der_UnoPorUnoDerecha;
                                                                          izquierda=izq_UnoPorUnoDerecha;
                                                }
                                                
                                                if(abs(derecha-izquierda) > abs(der_UnoPorDosDerecha-izq_UnoPorDosDerecha)){
                                                                          derecha=der_UnoPorDosDerecha;
                                                                          izquierda=izq_UnoPorDosDerecha;
                                                }
                                 }
                            }
               }
          }                                

          if(izquierda < derecha) printf("%d %d\n",izquierda, derecha);
          else printf("%d %d\n", derecha, izquierda);
          
          if (casos > 1) printf("\n");
          
    }
}