10032 - Tug of War

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

[LithiumDex]

I'm getting WA in 1.3 seconds

For the following input:

Code: Select all

1
100
84
87
78
16
94
36
87
93
50
22
63
28
91
60
64
27
41
27
73
37
12
69
68
30
83
31
63
24
68
36
30
3
23
59
70
68
94
57
12
43
30
74
22
20
85
38
99
25
16
71
14
27
92
81
57
74
63
71
97
82
6
26
85
28
37
6
47
30
14
58
25
96
83
46
15
68
35
65
44
51
88
9
77
79
89
85
4
52
55
100
33
61
77
69
40
13
27
87
95
40

My output is:

Code: Select all

2641 2643

For this input:

Code: Select all

1
100
384
887
778
916
794
336
387
493
650
422
363
28
691
60
764
927
541
427
173
737
212
369
568
430
783
531
863
124
68
136
930
803
23
59
70
168
394
457
12
43
230
374
422
920
785
538
199
325
316
371
414
527
92
981
957
874
863
171
997
282
306
926
85
328
337
506
847
730
314
858
125
896
583
546
815
368
435
365
44
751
88
809
277
179
789
585
404
652
755
400
933
61
677
369
740
13
227
587
95
540

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

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

[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

[sumantbhardvaj]

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

[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

1
100
434
287
28
116
294
386
137
193
250
272
213
428
141
260
114
77
241
127
323
137
162
369
268
430
333
81
63
374
218
236
330
253
73
409
420
418
344
107
212
143
430
424
172
120
285
338
249
75
66
121
264
227
92
81
207
424
213
321
347
32
106
226
285
178
237
306
197
130
14
408
325
46
433
46
165
268
435
15
394
51
188
259
277
279
339
85
304
102
405
200
133
61
27
19
290
263
377
37
445
390

my WA output is:

Code: Select all

11467 11467

For these:

Code: Select all

4

3
100
90
200

15
10
3
3
3
3
3
1
1
1
1
1
12
13
14
15

1
50

5
500
100
100
100
100 

my WA output is:

Code: Select all

190 200
42 42
0 50
300 600

could someone please verify this input?

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

[Relja]

it's ok.

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

[adelar]

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

[rio]

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

----
Rio

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

[andysoft]

This code in C++:

Code: Select all

this code got too old, look below please.

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

[adelar]

Hi shakil,
is missing:

Code: Select all

#include <stdlib.h>

[]'s

[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");
          
    }
}