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

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

10364 - Square

Post by 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.
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.
For Hints: http://salimsazzad.wordpress.com

Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10364 - Square

Post by lighted »

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

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

Re: 10364 - Square

Post by 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);

                val = temp;

            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);

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

        } else {
            int cap = total/4;
            vector<int> arr({cap,cap,cap,cap});

            bool ret = f(0, arr);
            } else {


    return 0;

Post Reply

Return to “Volume 103 (10300-10399)”