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

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

### Re: 1231 - ACORN

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

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

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

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!