https://codeforces.com/contest/4/problem/D
Can you help me find bug in my code, I have already solved it with iterative dp but when I’m solving this with recursive solution it is giving wrong output for some TC’s.
static int dri(Pair[] ll, int w, int h, int pw, int ph, int n) {
if (n == 0) {
if (ll[n].w > w && ll[n].h > h && ll[n].w < pw && ll[n].h < ph) {
return 1;
} else {
return 0;
}
}
if (dp[n] != -1)
return dp[n];
if (ll[n].w > w && ll[n].h > h && ll[n].w < pw && ll[n].h < ph) {
int count = 1 + dri(ll, w, h, ll[n].w, ll[n].h, n - 1);
count = Math.max(count, dri(ll, w, h, pw, ph, n - 1));
return dp[n] = count;
} else {
return dp[n] = dri(ll, w, h, pw, ph, n - 1);
}
}
Pair Class -
class Pair {
int w, h, flag, id;
Pair(int w, int h, int id) {
this.w = w;
this.h = h;
this.id = id;
}
}
And the sorting method –
Arrays.sort(ll, new Comparator<Pair>() {
@Override
public int compare(Pair a, Pair b) {
if (a.w == b.w)
return a.h - b.h;
else {
return a.w - b.w;
}
}
});
When ever the envelope is bigger than my letter I get two choices whether to take it or not and in all other cases I will simply wouldn’t take it in any condition, that’s exactly what I did, but somehow I’m getting wrong answer. I know I have done a stupid mistake which I can’t find.
For full code -