## 10032 - Tug of War

Moderator: Board moderators

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 10032 - Tug of War

there's an easy problem which is quite similar with this one, 562 : dividing coins.

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 10032 - Tug of War

i did first the problem 562 with the knapsack....then a read the problem tug of war,,,but this problem it's totally diferent!!!...i tried with bactracking,,,,but i get TLE,,,so i trying with DP...but i don't see the recurrences...

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

### Re: 10032 - Tug of War

test cases for this problem are not strong enuf...
I saw this code that gets AC but is not correct.

Code: Select all

``````
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

int weight [100 + 10];
bool minWeight [45000 / 2 + 100];
int minPeople [45000 / 2 + 100];
int maxPeople [45000 / 2 + 100];

int main(int argc, char** argv) {
int testCase;
scanf ("%d", &testCase);
bool blank = false;

while ( testCase-- ) {
int n; scanf ("%d", &n);
int total = 0;

For (i, 0, n) { scanf ("%d", &weight [i]); total += weight [i]; }

Set (minWeight, false);
for ( int i = 0; i < 45000 / 2 + 100; i++ ) { minPeople [i] = INT_MAX; maxPeople [i] = 0; }
minWeight [0] = true;
minPeople [0] = 0;

For (i, 0, n) {
for ( int j = total / 2 + 5; j >= 0; j-- ) {
if ( minWeight [j] ) {
minWeight [j + weight [i]] = true;
if ( minPeople [j + weight [i]] > minPeople [j] + 1)
minPeople [j + weight [i]] = minPeople [j] + 1;
if ( maxPeople [j + weight [i]] < maxPeople [j] + 1)
maxPeople [j + weight [i]] = maxPeople [j] + 1;
}
}
}

if ( blank ) printf ("\n"); blank = true;

for ( int i = total / 2; i >= 0; i-- ) {
if ( minWeight [i] && ((minPeople [i] <= n / 2 && maxPeople [i] >= n / 2) || (minPeople [i] <= n / 2 + n % 2 && maxPeople [i] >= n / 2 + n % 2)) ) {
printf ("%d %d\n", i, total - i); break;
}
}

}

return 0;
}

``````
For test case :
1
6
1 1 2 3 3 10
correct output :
8 12
but it gives:
10 10
requesting to fix this problem.

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 10032 - Tug of War

I'm getting WA though I think everything's ok!

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <bitset>
#include <functional>
#include <algorithm>

using namespace std;

int main(){
int n, a[110], sum, gsum, tc, b, d;
bitset<110> is;
bool done;

cin>>tc;
while (tc--){
cin>>n;
sum=0;
for (int i=0; i<n; ++i){
scanf("%d", &a[i]);
sum+=a[i];
}
b= sum/2 + (sum%2==0?0:1);
sort(a, a+n, greater<int>());
is.reset();
gsum=0;
for (int j=0; j<n; j+=2){
is.set(j);
gsum+=a[j];
}
d= gsum-b;

do{
done=true;
for (int i=0; i<n-1; ++i){
if (is[i]&&!is[i+1]&&(a[i]-a[i+1]<=d)){
done=false;
is.reset(i);
is.set(i+1);
d-=a[i]-a[i+1];
}
}
} while (!done);

if (n%2){
int li=n-1, lit=li;
while (!is[li]) --li;
if (a[li]<=d){
while (lit>=0&&a[lit]<=d){
li=lit;
if (lit==0)
break;
--lit;
while (!is[lit]){
--lit;
if (lit<0)
goto out;
}
}
out:
d-=a[li];
}
}

gsum=b+d;

printf("%d %d\n", sum-gsum, gsum);
if (tc) printf("\n");

}
return 0;
}``````

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

### Re: 10032 - Tug of War

Input:

Code: Select all

``````100

9
428
8
243
156
80
88
34
201
361

9
323
349
79
369
83
217
230
309
244

76
367
21
326
168
363
111
359
205
63
428
363
93
435
207
248
116
294
333
368
204
191
240
155
322
158
237
88
439
147
383
165
63
403
92
230
368
202
190
122
317
167
34
11
203
241
258
319
136
193
236
392
435
78
96
306
287
384
445
276
80
430
42
194
382
133
423
351
386
215
22
252
381
108
262
186
400

22
54
85
366
341
78
350
418
173
258
255
158
304
132
289
283
173
32
267
357
57
167
292

71
189
146
253
348
407
438
297
130
93
381
45
434
61
447
3
285
254
257
443
159
440
333
442
162
365
310
120
421
26
412
293
266
107
95
163
115
135
9
245
279
442
341
262
104
337
317
388
192
123
432
351
113
315
394
326
229
253
446
251
278
9
93
146
167
239
360
281
425
369
127
254

62
18
117
65
354
433
2
96
158
434
48
322
350
441
197
128
243
244
378
122
304
72
319
20
310
229
301
285
199
427
140
160
444
256
276
400
239
329
97
396
364
144
267
263
134
65
442
376
309
369
99
214
440
418
234
352
196
136
238
394
112
377
155

58
182
32
159
22
360
255
417
326
398
285
138
133
350
182
110
260
100
208
23
142
175
308
95
422
443
332
417
157
310
121
314
41
204
74
63
114
328
81
41
275
418
230
407
317
411
118
178
113
325
252
306
102
110
400
73
102
333
40

58
192
212
173
284
416
246
398
131
123
81
171
449
48
400
7
364
413
124
143
75
51
394
380
152
53
329
276
207
263
367
14
4
129
239
339
146
34
339
276
209
419
48
207
16
49
266
431
11
441
123
85
41
118
14
192
223
394
70

29
258
436
442
313
114
282
202
311
316
90
136
74
58
235
332
125
284
199
105
294
190
279
431
282
396
46
76
168
42

95
146
299
130
190
162
296
21
363
156
388
54
292
63
163
76
447
287
411
195
391
307
436
271
287
268
216
332
343
436
373
37
183
274
166
424
435
11
47
399
167
434
2
60
99
164
187
95
52
148
289
44
4
275
314
342
144
131
275
36
116
250
72
351
73
289
324
57
300
422
5
68
8
58
179
106
221
365
252
272
114
90
367
169
416
230
60
109
360
335
144
78
134
267
30
206

56
405
314
7
377
318
126
436
427
304
91
197
218
342
70
384
33
436
102
51
267
162
211
228
98
407
305
231
223
386
38
380
341
351
438
319
270
113
304
246
18
446
44
288
389
165
221
421
202
322
73
18
33
284
245
182
240

52
412
64
139
51
444
29
3
33
347
272
146
252
119
215
247
162
52
185
378
272
208
129
144
332
146
228
165
443
410
6
196
423
70
334
24
115
415
78
147
363
350
344
165
18
109
13
232
160
250
159
432
7

90
177
338
35
6
105
79
415
110
326
440
231
210
65
345
226
142
94
138
93
39
354
111
147
367
394
359
166
154
392
224
43
118
111
130
123
267
208
140
377
136
181
157
397
245
104
172
386
197
361
29
235
265
191
434
181
186
394
398
339
335
171
382
54
333
113
176
202
320
367
128
57
97
336
3
341
41
174
329
289
85
409
74
349
149
109
131
386
52
130
274

86
352
257
439
286
369
216
37
291
185
164
347
281
102
350
224
142
73
154
431
209
112
106
159
312
266
341
247
317
20
70
304
371
379
344
207
297
161
243
189
345
9
86
228
162
435
1
303
109
206
335
370
317
440
78
178
307
419
424
225
40
95
130
411
23
23
219
372
236
63
110
182
71
247
409
284
283
11
137
392
216
21
363
82
63
440
311

21
10
284
196
50
431
325
62
55
400
280
28
185
394
138
366
67
436
377
350
269
387

86
262
205
109
174
286
223
163
199
245
225
84
440
274
64
315
387
171
316
268
198
50
211
387
17
277
373
393
177
191
330
264
2
84
424
175
421
248
389
169
43
163
253
84
38
368
450
424
88
315
241
338
416
54
274
433
330
248
375
108
438
254
424
41
389
449
267
412
299
206
182
393
420
434
26
60
404
26
33
93
392
326
430
358
379
306
340

60
103
264
20
143
120
443
235
110
43
52
71
341
309
253
283
330
288
361
389
293
438
422
438
379
349
19
338
277
324
279
136
29
93
155
223
264
199
7
425
242
110
98
184
20
350
69
350
239
429
340
134
18
363
121
396
261
139
336
87
13

14
275
93
308
31
367
173
282
425
148
73
85
245
308
156

46
376
107
434
406
447
169
423
359
289
421
222
428
306
308
42
19
184
186
379
267
102
101
98
76
248
222
212
42
79
368
289
57
24
325
12
72
43
435
431
332
7
202
361
312
111
402

82
347
137
362
163
290
13
260
365
312
83
127
406
161
96
244
217
119
118
281
191
161
317
223
42
323
26
402
236
136
405
219
84
143
131
246
432
195
107
346
56
189
74
11
402
169
255
220
340
424
102
80
134
418
354
227
342
379
178
127
116
184
398
200
326
130
445
359
324
154
307
431
342
380
44
345
151
350
115
40
323
216
171

7
236
74
233
127
54
13
306

19
196
305
368
124
434
363
32
359
118
338
391
61
320
434
406
20
333
122
111

6
389
281
264
174
406
46

53
9
110
260
177
358
114
95
31
149
59
114
109
176
54
49
236
425
85
243
444
417
364
104
224
355
436
37
78
391
135
32
399
244
291
125
151
6
271
233
206
329
399
314
106
2
415
342
28
49
186
21
67
100

76
291
4
213
379
133
153
63
217
153
307
109
329
59
167
150
292
372
80
240
288
186
293
252
129
320
352
366
392
20
15
169
362
70
381
291
255
135
405
73
287
261
181
217
372
347
366
265
269
48
106
158
285
398
409
15
319
362
380
312
381
447
82
293
66
64
185
372
198
139
444
86
2
227
302
373
123

20
187
443
369
292
150
203
291
160
269
211
123
198
124
54
194
205
398
312
320
132

85
67
322
331
204
323
107
107
297
229
428
85
274
398
376
25
150
268
185
20
28
359
218
203
412
13
407
411
376
276
144
263
394
16
143
199
390
249
358
237
79
335
321
352
283
299
429
34
116
215
54
196
123
323
398
85
387
407
45
365
284
241
177
280
256
319
28
195
169
385
33
247
322
354
201
206
202
179
291
369
393
396
166
65
268
166

51
257
174
298
171
7
88
347
286
395
267
366
139
435
352
172
283
275
127
33
30
380
263
373
350
205
318
66
322
188
283
124
444
6
421
164
12
110
112
350
54
378
317
245
414
218
416
246
43
144
279
124

23
143
46
422
348
416
37
271
153
371
394
198
376
417
361
440
128
74
391
234
1
257
28
16

74
45
261
118
188
141
294
260
284
391
283
233
356
372
105
110
292
100
307
218
118
269
259
246
342
199
29
394
5
108
409
80
204
272
250
391
412
93
252
297
85
136
79
441
57
183
152
349
283
9
168
400
277
426
247
221
226
327
164
230
36
175
361
239
446
160
179
9
304
32
306
389
168
436
431

24
221
132
174
105
140
393
106
19
420
353
239
195
281
4
26
317
178
439
105
225
200
336
234
54

67
141
44
136
126
24
412
398
155
135
52
347
130
158
417
99
112
205
346
392
260
423
310
40
411
415
264
161
300
99
266
268
239
309
404
417
384
365
364
88
101
18
36
230
227
2
381
338
258
328
331
120
300
191
159
313
207
422
75
56
123
340
323
361
250
276
379
183

40
345
322
291
414
358
122
190
411
52
129
271
379
61
390
281
251
98
143
7
121
269
114
243
210
437
206
9
314
186
243
106
80
114
448
95
73
119
284
34
223

64
304
151
75
295
33
377
392
227
436
114
45
99
357
254
137
164
314
1
349
106
158
31
220
155
125
292
273
11
377
45
24
282
248
98
126
280
77
119
109
62
233
205
160
191
9
349
354
374
401
304
30
108
334
301
262
61
194
84
71
173
181
146
4
30

46
182
309
372
352
19
433
134
224
194
376
284
92
279
207
42
185
236
149
68
138
12
180
332
148
250
54
328
396
109
357
293
290
267
214
192
286
248
377
111
441
355
394
135
235
150
228

19
438
429
89
177
440
268
58
137
68
163
66
65
272
422
409
111
291
172
354

28
419
333
288
11
237
283
145
21
34
373
440
73
351
130
250
340
397
307
79
66
72
144
130
343
168
88
55
60

11
11
237
331
343
126
342
181
408
36
253
43

60
294
116
360
423
365
302
370
273
432
435
344
125
167
236
344
306
343
403
219
353
189
99
297
366
440
27
323
78
331
366
87
175
83
49
199
447
402
170
321
383
155
267
109
373
104
3
280
446
7
48
348
248
147
246
163
188
324
88
265
205

5
352
431
137
2
179

85
403
401
55
335
105
373
45
79
27
99
358
22
106
8
422
353
206
217
117
393
91
204
208
347
258
161
327
394
162
107
180
166
57
287
102
213
209
146
343
235
245
303
309
402
310
280
304
65
98
22
59
240
226
318
136
33
80
64
29
293
171
260
8
279
96
109
42
305
307
384
89
101
236
449
104
147
278
9
263
428
30
322
217
255
241

53
340
321
416
420
163
188
229
171
17
377
331
58
231
187
43
371
339
331
370
442
79
249
450
342
226
82
265
443
336
55
345
277
427
362
298
140
100
77
362
116
3
294
225
285
31
319
205
421
199
176
413
278
425

14
221
200
95
35
192
33
141
138
361
170
102
209
309
201

87
272
368
391
115
142
225
145
62
31
168
313
207
130
192
181
195
412
432
342
48
226
374
240
415
284
409
66
94
319
266
430
140
235
370
307
376
196
53
40
227
220
352
35
349
93
267
146
54
248
37
153
23
12
392
40
347
351
105
441
271
423
22
411
207
392
267
185
189
371
224
415
141
125
449
91
217
265
236
322
115
324
24
189
387
415
228
284

67
385
326
188
357
347
200
165
340
68
349
79
438
122
95
128
298
94
271
64
410
56
437
74
432
10
315
368
27
92
253
393
26
128
182
434
77
433
149
416
50
47
96
90
221
191
269
120
336
89
236
347
197
222
23
178
232
337
147
258
30
400
252
56
77
36
91
205

18
239
223
120
338
318
261
160
110
79
279
47
220
116
394
416
338
416
195

71
354
393
30
383
342
281
40
21
368
131
225
386
421
447
107
308
367
367
69
78
47
400
125
266
65
68
283
402
85
79
122
438
22
151
422
363
34
12
383
401
194
210
388
164
258
44
74
174
410
142
252
7
143
428
324
208
97
157
159
181
235
333
220
256
85
191
221
118
202
153
121

97
414
58
161
222
154
286
447
165
29
300
223
172
277
97
379
373
253
139
103
89
73
374
397
158
115
167
327
368
371
447
365
335
107
127
106
260
412
154
424
42
4
197
213
280
345
193
203
147
332
357
287
404
333
233
163
447
399
40
416
372
88
382
256
194
58
413
55
71
116
81
113
119
329
325
1
223
68
255
421
1
213
257
6
95
92
169
91
92
260
109
13
347
40
268
143
98
282

47
220
398
329
332
118
207
259
118
31
326
372
1
378
135
310
383
281
3
153
424
94
412
82
107
361
121
426
53
270
258
301
40
257
180
371
374
438
179
94
71
106
67
71
85
253
432
70

84
36
222
57
130
236
138
288
146
310
263
250
130
122
100
221
378
331
193
354
371
424
49
441
79
115
113
216
368
147
285
1
182
56
57
311
291
246
200
38
105
65
287
286
186
439
56
166
319
301
121
291
274
169
281
404
283
446
169
200
142
3
200
323
59
308
236
401
103
435
439
260
49
327
95
287
315
203
2
236
53
122
76
326
342

59
279
174
404
448
374
95
450
175
19
110
85
306
61
187
291
101
446
391
29
143
279
344
345
332
129
397
55
204
272
396
214
152
120
167
149
95
313
201
321
332
310
405
187
422
194
79
124
241
72
153
383
350
98
277
232
226
275
286
31

98
284
245
300
403
13
50
99
326
250
419
259
162
426
47
133
169
126
309
409
249
63
394
200
160
220
33
437
97
371
69
244
204
365
93
208
378
143
306
253
392
274
113
155
301
159
288
19
336
198
30
134
260
423
386
419
244
418
7
340
338
75
186
143
440
278
350
419
22
205
273
16
81
385
170
381
93
59
2
429
256
31
164
65
55
99
85
350
67
91
292
6
218
27
149
259
304
100
227

28
305
49
393
437
433
112
367
75
171
420
105
28
450
269
145
106
367
281
58
35
424
349
93
191
375
241
449
280

90
225
259
246
273
201
232
307
365
201
433
137
170
88
164
222
408
360
379
376
191
436
411
164
334
53
354
310
345
404
192
286
230
450
134
52
253
365
410
167
167
392
303
337
29
68
108
436
428
36
414
220
74
374
383
407
28
338
319
424
291
60
311
70
111
444
173
363
411
132
131
127
125
35
65
206
103
172
243
132
260
206
351
333
129
335
341
208
222
209
181

64
320
42
235
33
87
9
395
47
140
128
226
316
162
290
71
264
64
314
447
375
69
399
257
198
283
199
7
106
10
188
219
381
281
55
413
367
63
410
414
254
87
241
120
248
80
190
114
143
53
162
67
122
111
375
371
393
176
377
49
185
166
319
167
446

74
130
415
436
141
430
240
227
220
411
76
299
150
189
44
255
351
162
428
63
87
348
5
314
326
105
48
94
26
214
141
399
395
105
436
85
136
225
363
355
185
439
204
387
229
299
191
181
10
168
243
148
117
300
11
44
404
110
137
429
324
330
429
320
434
415
405
172
241
317
76
28
357
331
414

36
179
206
316
189
425
161
336
91
10
399
134
15
58
323
444
381
202
24
303
237
438
309
408
229
175
86
308
134
416
323
321
145
78
186
385
52

48
270
194
407
218
379
422
328
251
17
310
54
40
162
291
28
20
300
308
247
385
165
380
351
89
250
97
166
37
31
269
435
352
12
443
172
390
414
49
243
430
358
296
72
122
188
99
141
90

8
387
24
224
368
426
312
219
124

79
256
154
347
292
108
410
284
279
401
300
379
193
279
338
91
402
9
330
50
150
419
109
138
45
332
56
72
245
274
196
323
131
401
271
422
58
230
308
388
233
157
368
27
37
256
169
439
316
49
38
15
69
199
205
165
132
260
237
377
135
34
249
266
434
122
289
94
351
146
83
185
302
1
212
339
308
380
327
173

80
416
240
99
164
444
263
348
305
49
274
41
82
124
358
118
245
197
211
198
394
293
382
298
345
195
186
202
125
114
427
154
131
216
304
347
261
117
244
115
217
67
207
351
190
115
18
37
363
280
234
306
174
217
153
69
412
390
322
138
53
298
343
184
115
197
80
375
313
323
91
131
441
298
31
232
14
48
268
376
379

53
231
103
372
384
223
385
323
94
72
428
444
414
161
160
212
292
137
74
216
227
205
258
126
287
39
139
387
359
64
315
63
295
417
434
280
241
368
204
335
41
181
380
57
393
89
268
286
225
342
103
54
148
360

79
434
399
370
370
359
433
287
421
329
305
7
210
96
374
16
430
17
196
411
73
191
49
340
78
326
283
181
379
430
90
159
16
90
78
437
50
113
273
21
43
180
27
305
275
2
320
306
18
117
266
90
307
314
430
437
189
262
167
169
294
308
328
361
450
405
347
49
119
222
69
162
401
147
16
225
201
335
80
218

51
397
360
360
312
391
346
51
254
62
271
97
421
148
7
420
155
406
19
273
229
139
434
231
286
51
57
36
385
188
305
438
134
214
347
445
154
294
97
408
407
368
106
377
65
165
347
271
172
417
94
400

55
77
180
390
128
288
27
114
25
332
101
158
95
49
204
301
342
301
310
350
270
415
277
386
129
225
207
300
191
300
301
295
428
82
287
157
369
313
271
393
246
423
152
393
74
356
243
17
206
102
367
77
118
245
12
247

19
218
148
261
67
449
157
97
132
443
253
51
358
125
45
153
150
197
95
275

2
337
291

9
40
259
435
158
105
48
6
175
266

55
435
384
203
142
30
387
134
335
437
41
9
31
194
210
227
340
34
380
227
325
288
318
185
324
25
290
372
82
14
239
287
449
172
91
192
254
27
377
138
13
418
198
96
213
408
374
102
441
304
380
367
193
248
102
119

74
391
92
406
6
330
242
56
103
332
247
356
411
174
43
423
193
293
120
405
250
96
108
240
399
90
209
193
389
310
363
262
302
4
269
307
333
60
415
436
444
211
393
404
384
38
428
178
330
150
184
181
245
292
22
245
433
230
437
371
89
402
234
442
405
53
351
340
164
315
377
157
127
371
162

11
408
192
238
339
341
24
69
135
315
91
431

49
320
19
269
11
420
52
54
427
156
404
316
320
320
294
78
447
214
240
109
224
431
398
112
373
421
181
109
337
271
89
235
192
107
105
202
129
157
308
105
312
261
22
233
183
315
311
179
130
100

89
353
132
286
15
106
309
195
214
195
67
354
32
258
10
136
62
138
344
369
294
258
231
315
40
413
179
350
193
361
449
133
263
182
21
277
287
329
73
102
125
139
5
156
449
15
344
60
204
237
30
100
44
260
414
84
275
195
35
69
105
34
202
367
267
222
246
104
152
370
257
276
111
262
34
109
328
377
168
133
215
249
232
259
58
196
394
384
390
428

3
44
63
204

62
382
27
309
87
178
281
343
55
391
154
88
49
31
66
268
164
281
66
395
141
175
140
84
109
131
113
111
226
228
366
290
159
392
148
245
171
428
137
225
420
343
365
18
373
430
337
138
260
4
83
400
179
274
85
287
405
250
449
180
27
416
71

85
357
219
31
129
248
219
405
218
111
319
287
34
351
226
171
212
229
305
162
407
129
298
295
135
97
345
366
175
310
437
411
268
257
441
396
106
210
351
375
320
271
212
405
171
39
178
383
267
32
146
276
212
45
120
346
194
67
262
368
376
300
381
194
106
371
191
211
182
143
188
104
16
1
58
186
39
287
170
305
319
367
182
80
412
354

78
207
420
289
124
345
190
54
140
295
27
383
107
260
75
346
363
90
346
23
328
384
309
47
291
177
16
22
309
427
375
336
183
396
226
358
291
415
14
32
311
92
414
19
351
91
365
264
180
260
286
109
246
144
208
86
373
223
159
231
251
136
168
35
81
393
392
423
357
7
5
269
98
20
287
449
110
253
314

42
63
201
450
360
344
207
445
318
429
153
150
229
288
317
263
421
259
257
393
217
315
397
35
413
19
374
13
128
176
378
19
238
128
19
147
21
225
193
391
256
398
90

34
287
407
349
257
215
207
200
432
71
198
68
85
216
441
97
396
167
24
414
6
151
34
205
224
259
397
164
116
396
305
201
233
261
99

91
26
305
342
59
428
90
126
62
357
117
211
302
335
234
266
340
437
299
94
262
159
93
27
274
90
331
25
322
142
175
15
219
82
356
329
59
445
4
120
404
172
330
255
108
166
70
448
204
421
143
15
181
287
41
57
377
423
133
300
114
307
314
384
440
272
262
48
318
318
220
271
39
151
76
147
316
197
196
121
167
390
187
400
227
279
6
153
252
138
54
417

96
368
351
36
241
162
135
108
29
354
379
120
107
4
318
24
200
115
145
419
54
331
420
280
160
425
34
13
164
88
429
209
57
329
296
297
93
431
404
121
386
332
292
94
387
211
118
189
325
314
209
379
194
178
260
405
204
294
417
367
433
396
177
39
326
23
387
418
55
340
141
42
274
432
188
262
245
305
450
119
168
208
99
413
437
359
368
190
254
386
158
288
331
335
326
207
409

14
226
65
203
366
158
78
400
345
340
194
199
391
364
418

99
13
381
187
423
350
377
278
285
136
115
218
20
42
26
428
355
251
94
107
167
252
237
116
146
126
361
397
118
274
416
266
338
346
55
310
297
33
137
132
168
251
401
188
292
426
217
196
226
311
355
444
164
193
161
361
370
71
307
37
397
273
355
284
220
409
144
67
441
332
250
210
185
200
397
26
227
216
274
2
128
230
48
291
24
208
201
393
279
110
429
225
434
385
110
203
343
253
321
385

37
120
145
371
371
143
448
147
358
323
149
87
102
196
377
125
5
180
119
335
341
150
109
324
84
219
76
29
73
397
413
259
118
159
231
39
302
229

85
261
101
385
348
203
182
326
379
187
107
100
71
447
249
232
320
332
52
448
412
176
394
375
37
113
83
267
151
436
45
336
299
146
322
248
400
54
123
380
292
282
29
414
278
329
195
200
263
298
249
224
24
244
148
60
356
283
378
57
320
423
444
168
170
315
415
119
420
140
100
313
421
129
277
300
7
73
101
321
371
349
95
446
142
294

57
100
126
34
156
48
6
201
215
227
117
232
345
87
423
445
1
445
175
277
346
233
350
447
104
322
397
198
317
141
41
25
240
219
58
447
266
116
197
82
342
313
365
289
1
337
335
2
331
59
330
279
343
229
275
446
152
273

45
70
413
338
94
202
106
204
250
423
319
446
106
262
361
73
152
361
11
36
362
394
94
294
222
39
72
46
34
276
318
331
345
333
218
439
136
375
192
386
399
112
381
54
425
291

78
127
254
189
162
217
132
308
60
353
346
184
450
431
9
369
311
353
251
130
393
387
54
186
374
2
349
304
108
324
197
285
450
52
23
213
268
206
122
328
108
17
61
107
50
121
78
412
23
328
92
18
316
197
255
239
251
154
145
410
27
393
244
78
444
319
342
261
74
14
190
234
82
250
392
131
370
19
145

45
399
288
64
264
34
318
105
336
21
249
295
99
191
141
228
236
61
120
46
186
133
236
419
214
87
413
397
59
431
91
105
431
378
168
245
13
87
349
349
108
199
245
258
441
385

86
226
445
207
323
181
339
160
201
154
247
163
152
357
196
294
11
176
273
230
22
286
316
422
236
25
222
82
335
212
17
370
39
63
178
362
295
66
71
98
271
369
312
25
275
109
318
337
337
141
116
358
28
34
382
315
110
153
396
444
365
412
415
403
77
142
366
423
259
437
70
80
407
382
156
232
40
23
118
428
215
286
336
242
319
267
106

28
419
52
24
385
65
438
390
141
130
305
166
388
343
235
69
352
218
224
133
310
299
302
287
63
189
224
305
109

90
410
139
61
63
162
47
128
149
38
320
330
395
35
268
287
322
388
240
141
214
424
450
62
328
339
124
66
112
30
175
204
42
313
316
104
76
362
283
224
400
205
104
396
291
423
284
162
360
74
303
123
47
354
236
374
242
360
440
354
441
216
107
32
130
422
136
205
385
20
30
386
224
185
331
65
157
165
278
119
238
130
293
336
86
79
260
327
40
301
230

80
66
388
62
247
411
249
1
346
268
82
333
42
267
266
158
423
430
435
91
269
115
436
154
252
64
15
128
155
315
410
184
380
347
297
176
360
95
228
255
415
310
189
58
126
4
215
150
35
199
293
355
365
278
59
166
393
73
294
97
440
305
332
369
201
179
147
110
325
426
416
289
337
207
398
64
262
162
214
297
413

58
201
327
437
311
95
431
436
440
77
425
294
10
395
96
188
91
258
115
119
275
5
5
31
403
69
293
166
334
139
128
43
391
57
29
252
151
9
289
140
137
263
433
146
207
78
386
350
335
102
18
212
106
74
242
58
194
84
224

29
274
403
171
267
9
251
120
159
311
408
350
49
220
332
247
426
12
182
377
398
283
394
159
440
70
3
48
263
138

73
392
14
327
164
280
336
415
399
96
327
408
446
376
177
379
172
204
390
405
183
390
289
126
150
278
247
152
377
60
342
301
1
355
178
216
184
63
180
184
158
57
193
153
34
369
134
205
174
73
159
356
64
49
84
266
326
330
19
305
441
360
155
43
264
332
259
447
446
438
232
154
96
424

58
129
394
41
385
170
166
145
127
281
193
262
96
121
194
115
425
184
24
129
227
288
63
87
336
58
126
170
211
222
195
171
402
191
263
389
360
30
83
88
311
328
350
8
448
93
122
422
328
198
152
156
87
214
242
24
272
368
245

34
191
440
306
142
180
119
132
89
148
215
228
60
92
127
68
141
271
241
112
149
40
315
304
126
79
148
202
350
65
446
35
307
435
341

100
164
9
182
304
208
396
134
268
89
260
387
229
133
229
392
281
269
256
186
446
334
385
197
285
449
193
320
305
229
210
355
445
270
138
350
79
83
33
398
171
345
334
1
27
165
392
359
433
197
146
428
133
81
227
417
131
21
338
38
249
149
444
295
418
131
195
99
213
279
46
435
173
432
37
199
146
428
159
128
226
305
157
358
385
435
377
117
5
264
154
306
413
147
150
432
277
396
80
91
225

26
127
449
159
163
198
304
192
356
33
418
262
189
377
196
174
355
313
230
169
68
85
183
215
287
216
93
``````
AC output:

Code: Select all

``````798 801

1098 1105

9164 9164

2444 2445

9086 9086

7725 7726

6316 6316

5899 5900

3258 3258

9967 9967

6773 6774

5218 5219

9591 9592

9782 9783

2545 2545

11007 11007

6772 6772

1484 1485

5367 5368

9399 9399

520 523

2417 2418

733 827

5077 5077

8803 8803

2317 2318

10165 10165

5935 5936

2761 2761

8559 8559

2448 2448

7972 7972

4221 4222

5950 5951

5328 5329

2214 2215

2818 2819

1155 1156

7528 7528

533 568

8633 8634

6825 6825

1203 1204

10146 10146

6929 6930

2134 2135

7717 7718

10489 10490

5175 5176

9042 9043

6865 6865

10501 10501

3504 3504

11176 11176

6650 6650

8851 8852

4213 4213

5386 5386

1042 1042

8824 8824

8938 8938

6347 6348

9041 9041

6405 6406

6323 6323

1837 1837

291 337

746 746

6302 6303

9623 9624

1291 1292

5501 5501

9247 9247

107 204

6714 6714

9939 9940

8740 8740

5068 5069

3791 3791

9837 9838

11896 11897

1873 1874

11829 11829

3826 3827

10401 10402

6453 6454

5397 5398

8326 8326

4961 4961

9944 9944

3282 3283

10028 10029

9583 9584

5802 5802

3382 3382

8781 8781

5954 5955

3322 3322

12109 12110

2905 2906
``````
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 10032 - Tug of War

Thank you Brian; the first test case was enough to see my algorithm is buggy.
I did some modifications and then I nearly disproved its correctness.

Do you think I'd see light if I try more on greedy or maybe I better move on to something else?

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

### Re: 10032 - Tug of War

DP
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

### Re: 10032 - Tug of War

Thanks! I'll try.

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### Re: 10032 - Tug of War

Code: Select all

``````#include<bits/stdc++.h>

using namespace std;

#define ms(x,val) memset(x,val,sizeof(x))
#define ull unsigned long long
#define iii long long
#define pi acos(-1)
#define repi(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define PII pair<int,int>
#define MP make_pair
#define eps 1e-9
#define inf 999999999

int n,w[101],dp[101][450*50+9],total,target,lim;

int calc(int i,int sum,int taken)
{
if(dp[i][sum]!=-1) return dp[i][sum];
if(i>=n || taken==lim) return 0;

int temp1=0,temp2=n-lim+taken+1,mx=0;

for(int j=i;j<temp2;j++)
{
if(sum+w[j]<=target)
{
temp1=w[j]+calc(j+1,sum+w[j],taken+1);
mx=max(mx,temp1);
}
else break;
}

return dp[i][sum]=mx;
}

int main()
{
//	freopen("in.txt","r",stdin);
int cases;
cin>>cases;
while(cases--)
{
ms(dp,-1);
cin>>n;
total=0;
for(int i=0;i<n;i++)
{
cin>>w[i];
total+=w[i];
}

if(n&1) lim=n/2+1;
else lim=n>>1;

target=total>>1;

sort(w,w+n);

int ans=calc(0,0,0);

cout<<ans<<' '<<total-ans<<endl;
if(cases!=0) cout<<endl;

}
return 0;
}

``````

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

### Re: 10032 - Tug of War

http://en.m.wikipedia.org/wiki/Knapsack_problem

scanf and printf are faster than cin and cout
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

### I use DP, but get WA

I used dp. Here is main part of my algo.

a is array of people weights, from a[0 .. n-1].

f is array meaning that f[k][j] = 1 if we can make sum of weights j with k people, otherwise it equals to 0.

With every persons weight i try to make new sums j, with k (1..m) people.

m is half of n people. it is enough to find sums wich includes m people, which will be the first team.
Because other team will be equal to sum of all people - first teams weight.

m = n / 2;

f[0][0] = 1;

for (i = 0; i < n; i++)
for (j = sum; j >= a; j--)
for (k = 1; k <= m; k++)
if ( f[k - 1][ j - a ] ) f[k][j] = 1;

// if it is possible to make sum of weights ( j - a ) with (k - 1) people
then using ith person i can make sum j with k people.

Let SUM be sum of all people.

At last i find such s, that f[m][s] = 1 and |SUM - s| is minimal.

(f[m][s] means that it is possible to get sum of weights s, including m people)

Can someone check my algo or give me some more input tests.
I've checked several tests that was in this forum but got wa.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10032 - Tug of War

Yes you can solve it using DP
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: 10032 - Tug of War

I am getting TLE with my DP. How can i improve it.

Code: Select all

``removed, after acc..``
Last edited by lighted on Sat Jun 21, 2014 9:54 am, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10032 - Tug of War

You're calling memset on a 19,804,400 byte array for every test case, and there could be many test cases.
I used a single bool array to set if a weight is attainable, and two int arrays to keep track of the min and max number of people that can combine to that weight.
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: 10032 - Tug of War

I didn't change my dp algo. I made some optimizations to avoid TLE.

I removed memset and made necessary memseting manually and got acc with runtime 0.875.

Thanks for help!
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman