Saturday, November 29, 2014

UVa Problem 10364 - Square

Problem:

Please find the problem here.

Solution:

Brute force search and reducing the search space by eliminating symmetric images.

The problem basically require us to split the input numbers into four disjoint subsets. The ordering of the subsets and the ordering within subsets are not relevant, so let's require the subset itself to be ordered (in input order), and the smallest element of the subsets are ordered as well, that reduce significantly the number of subsets to search.

So for the first element of the first subset, it must be the 0th element. We take it, use a bit mask to record this fact, and move on to search the rest. We require the next element in the same subset to have an index larger than 0.

Suppose we have done with the 0th subset, now we move on to the 1st subset. The 1st subset must start with the least number than the 0th subset didn't use, so we search from the 0th number to find the first unused number, that will be it.

A very simple heuristic (and to avoid rounding) is to make sure the length sum is a multiple of 4, otherwise integers cannot possibly sum to fractions and we can answer no right away.

I haven't stored anything at all, and there are no overlapping sub-problems with this carefully designed search, so it isn't dynamic programming at all.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1305

#include "UVa10364.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

bool feasible(vector<int>& lengths, int length_target, int remaining_segments, int remaining_length, int starting_segment, int used_mask)
{
    if (remaining_segments == 0)
    {
        return true;
    }

    int bit = 1 << starting_segment;
    bool first_entry = (remaining_length == length_target);
    for (unsigned int i = starting_segment; i < lengths.size(); i++)
    {
        if ((used_mask & bit) == 0)
        {
            if (lengths[i] == remaining_length)
            {
                if (feasible(lengths, length_target, remaining_segments - 1, length_target, 0, used_mask | bit))
                {
                    return true;
                }
            }
            else if (lengths[i] < remaining_length)
            {
                if (feasible(lengths, length_target, remaining_segments, remaining_length - lengths[i], i + 1, used_mask | bit))
                {
                    return true;
                }
            }
            if (first_entry)
            {
                break;
            }
        }

        bit = bit << 1;        
    }

    return false;
}

int UVa10364()
{
    int num_test_case;
    cin >> num_test_case;
    for (int c = 0; c < num_test_case; c++)
    {
        int num_sticks;
        cin >> num_sticks;
        vector<int> lengths;
        lengths.resize(num_sticks);
        int length_sum = 0;
        for (int s = 0; s < num_sticks; s++)
        {
            int length;
            cin >> length;
            lengths[s] = length;
            length_sum += length;
        }

        if (length_sum % 4 == 0)
        {
            int length_target = length_sum / 4;
            if (feasible(lengths, length_target, 4, length_target, 0, 0)) 
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
        else
        {
            cout << "no" << endl;
        }
    }

    return 0;
}

No comments :

Post a Comment