10364 - Square

[sazzadcsedu]

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

[lighted]

I got acc!

This is a DP (Dynamic Programming) problem. Backtrack will give u nothing but TLE.

I used backtracking and solved it in 0.015.

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.

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.

[jddantes]

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