1231 - ACORN

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

Moderator: Board moderators

Post Reply
mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 1231 - ACORN

Post by mehrab2603 » Mon Jan 12, 2015 2:33 pm

Getting TLE. Any help on how to make it efficient will be highly appreciated.

Code: Select all

#include <bits/stdc++.h>

using namespace std;
int t, h, f;
//vector<int> acorn[2010];
int acorn[2010][2010];
int dp[2010][2010];
bool vis[2010][2010];
int func(int, int);

int main() {
    int c;
    scanf("%d", &c);
    while(c--) {
        scanf("%d %d %d", &t, &h, &f);
        memset(acorn, 0, sizeof acorn);
        memset(vis, false, sizeof vis);
        for(int i = 0; i < t; i++) {
            int x;
            scanf("%d", &x);
            for(int j = 0; j < x; j++) {
                int height;
                scanf("%d", &height);
                acorn[i][height]++;
            }
        }
        int ans = -99999;
        for(int i = 0; i < t; i++)
            ans = max(ans, func(i, h));
        printf("%d\n", ans);
    }
    int zero;
    scanf("%d", &zero);
    return 0;
}

int func(int tree, int height) {
    if(height <= 0) {
        return 0;
    }
    if(vis[tree][height]) return dp[tree][height];
    int taken = -99999;
    taken = max(taken, acorn[tree][height] + func(tree, height - 1));
    for(int i = 0; i < t; i++) {
        if(i == tree) continue;
        if(height - f >= 0 && acorn[i][height - f])
            taken = max(taken, acorn[tree][height] + func(i, height - f));
    }
    vis[tree][height] = true;
    dp[tree][height] = taken;
    return taken;

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1231 - ACORN

Post by brianfry713 » Tue Jan 13, 2015 2:07 am

If you are trying to solve a test case in O(t * t * h) plus the time to read the input you will get TLE.
It can be done in O(t * h) plus the time to read the input.

Code: Select all

DP loop:
iterate from h to 0
  iterate through each tree, keeping track of which tree has the most acorns at the current height
    set the DP array for this tree at this height to be any acorns located here plus the max of this tree at current height + 1 or the tree with the most acorns at the current height plus f.
Check input and AC output for thousands of problems on uDebug!

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 1231 - ACORN

Post by mehrab2603 » Wed Jan 14, 2015 4:08 pm

Thanks for the hint. I'll try it again.
However, I was wondering why my code gets TLE while this one gets AC. Seems similar to mine. Just wanted to understand how the complexity was improved.

*code removed*
Last edited by mehrab2603 on Thu Jan 15, 2015 7:56 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1231 - ACORN

Post by brianfry713 » Thu Jan 15, 2015 1:32 am

If you are trying to solve a test case in O(t * t * h) plus the time to read the input you will get TLE.
It can be done in O(t * h) plus the time to read the input.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 12 (1200-1299)”