UVa : 10032 (Tug of War)



// http://uva.onlinejudge.org/external/100/10032.html
// Runtime: 0.248s
// Tag: Dp

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 6, 2011, 11:24 PM
 */

// @BEGIN_OF_SOURCE_CODE

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

// @END_OF_SOURCE_CODE
Advertisements

8 thoughts on “UVa : 10032 (Tug of War)

  1. @Saleh
    ya, i can try 🙂
    array minWeight is initially false
    after running the program, if minWeight [x] = true
    it means, it is possible to make weight x, using some people

    for example, if total weight of all people is P
    and if we can make (P/2) using some people
    then definitely we can make another (P/2) using rest of the people

    we have two others array minPeople and maxPeople
    if minPeople [x] = y then
    it means, we can make weight x, but we need at least y people

    if maxPeople [x] = y then
    it means, we can make weight x, using at most y people

    finally i started to search from totalWeight/2 to downward
    if i found a weight that can be made and maxPeople == minPeople then output
    or, find a weight that can be made and (maxPeople + 1 == minPeople) or (maxPeople == minPeople + 1) then output

    hope this may help 🙂

  2. Did it get accepted? Doesn’t this entry brake your code?
    6 persons each with weight: 1 1 2 10 10 20

    The answer should be 22
    team 1: {10 10 2}
    team 2:{20 1 1}

    Yet we can get 22 with:
    {20, 2} two people => minPeople = 2
    {10 10 1 1} four people => maxPeople = 4

    So the final loop would miss the correct answer and not print it, is that correct or i misunderstood you code?

  3. hummm I was wrong what actually would break it would be

    6 persons: 1 1 1 1 1 5
    the answer should be: 3 7
    team1:{1 1 1} and team2:{1 1 5}

    5 weight can be made with
    {5}=> minPeople[5] = 1
    or with
    {1 1 1 1 1}=> maxPeople[5] = 5

    your output would be 5 5 instead of 3 7 is that correct?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s