10364 - Square

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10364 - Square

Post by sazzadcsedu » Mon Jul 27, 2009 10:29 pm

Can someone post me some critical i/o??i have used the following algorithm

1.if (sum of stick length)%4!=0. then print no.
2.if some stick length>avg print no.
else
1.if stick length=avg or equal then perform a special check function.
2.sort the input.
3.from the highest stick to match with the 1st lowest stick by adding them,if less then avg ,then add the next(2nd...next) lowest stick.if it becomes greater then avg then backtrack.then start from highest to 2nd lowest,if less then avg ,then add the next lowest(3rd....next) stick and so on.is my algorithm correct???


Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10364 - Square

Post by lighted » Fri Jul 11, 2014 11:46 am

I got acc! :lol: :lol: :lol:
CodeMaker wrote::-? This is a DP (Dynamic Programming) problem. Backtrack will give u nothing but TLE.
I used backtracking and solved it in 0.015.
Adrian Kuegel wrote:I can't think how it is possible to solve it in 0.00 sec (I assume it is a sort of greedy that does not work in all cases). The only way I know is backtracking, because this problem is NP-complete. You can make your program fast enough, if you sort the sticks by length and in each recursion step consider equal lengths only once.
Jan wrote:You should add some other prunings too

1. Each element has to be included in a group. So, set one element fixed and search for the rest to fill.

2. When searching maintain an order. Because the index 1, 2, 5, 3 and 1, 2, 3, 5 both are same.

Hope these help.
Also if sum of sticks is not divisible by 4 or if sum of sticks divided by 4 is less than longest stick answer is "no".

This hints were enough to solve the problem.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10364 - Square

Post by jddantes » Fri Apr 03, 2015 9:16 am

[TLE] Backtracking with memoization. Any tips?

Code: Select all

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, vector<int>> state;

int n;
map<state, bool> memo;
vector<int> input;
bool f(int index, vector<int> arr){
    sort(arr.begin(), arr.end());

    state save = state(index, arr);

    auto itr = memo.find(save);
    if(itr != memo.end()){
        return itr->second;
    }

    if(index == n){
        for(int i = 0; i<4; i++){
            if(arr[i] != 0){
                return memo[save] = false;
            }
        }
        return memo[save] = true;
    }

    bool val = false;

    for(int i = 0; i<4; i++){
        if(arr[i] - input[index] >= 0){
            arr[i] -= input[index];

            bool temp = f(index+1, arr);

            if(temp){
                val = temp;
                break;
            }

            arr[i] += input[index];
        }
    }

    return memo[save] = val;

}


int main(){
    int cases;
    scanf("%d", &cases);

    for(int e = 0; e<cases; e++){

        scanf("%d", &n);
        input.resize(n);
        memo.clear();

        int total = 0;
        for(int i = 0; i<n; i++){
            scanf("%d", &input[i]);
            total += input[i];
        }

        if(total%4){
            printf("no\n");
        } else {
            int cap = total/4;
            vector<int> arr({cap,cap,cap,cap});

            bool ret = f(0, arr);
            if(ret){
                printf("yes\n");
            } else {
                printf("no\n");
            }

        }
    }

    return 0;
}

Post Reply

Return to “Volume 103 (10300-10399)”