#21

can anyone explain me why greedy technique is giving optimal solution. I am not able to convince myself why greedy is giving optimal solution. I have read the exchange argument, but not able to relate it.

Thanks

#22

We donāt need below condition at line number 6 in backward dp as It has already been taken care in for loop at line number 4
if (j <= X) {

}

#23

Guys can someone explain me in the test case given in the program andy and bob have 3 orders each
5 3 3
1 2 3 4 5
5 4 3 2 1

Andy can be assigned the last 3 orders of the first row and bob can be assigned the first three orders of the second row.Hence the total comes up to 24 yet we get an o/p of 21 why is that.

#24

I got all the above cases correct but Codechef still shows WA. What could be the reason?

This is the code:

``````#include<iostream>
#include<vector>

typedef long long int ll;

using namespace std;

ll mem_total(ll N, ll *A, ll *B, ll X, ll Y, ll **mem)
{
if(N==0)
return 0;

if((X>0 && mem[X-1][Y] != 0) && (Y>0 && mem[X][Y-1] != 0))
mem[X][Y] = max(A[N-1] + mem[X-1][Y], B[N-1] + mem[X][Y-1]);
else
mem[X][Y] = max(X>0?(A[N-1]+mem_total(N-1, A, B, X-1, Y, mem)):0,
Y>0?(B[N-1]+mem_total(N-1, A, B, X, Y-1, mem)):0);
}

main()
{
ll N, X, Y;

cin>>N>>X>>Y;

ll **mem;

mem = new ll*[X+1];
for(int i=0; i<=X; i++)
mem* = new ll[Y+1];

ll A[N], B[N];

for(ll i=0; i<N; i++)
cin>>A*;
for(ll i=0; i<N; i++)
cin>>B*;

mem_total(N, A, B, X, Y, mem);

cout<<mem[X][Y]<<endl;
}``````

#25

a great question ,
make me realize that my DP approach was cyclic and was getting wrong ans.
took me over an hour to figure it our

#26

my code passed all these testcases. still got 10 points

#27

I know it is not a problem, but B* cannot be 0

#28

my solution passed all the above test cases

#29

#30

good question, enjoyed solving it. I couldnāt score but I knew it was dp @dpraveen

#31

@brobear1995: it failed on last test case, your code returns 13, test properly - http://ideone.com/OeLs9e

#32

which one ? but I know they are wrong.
I was checking for different greedy approaches.

#33

So when SUB* equals SUB[i-1] you will check the two arrays (take the maximum). Nice approach, will check it.

#34

``````2 1 1
5 6
6 8``````

#35

ohh i am sorry for that caseā¦@betlista

#36

@rishabhprsd7: Correct solution should work fine with that, just mentioned

#37

@abcdexter24: I added one more test case (last one), you code returns 14 for this oneā¦

#38

dont check solutionā¦just saw your edit for case 1 and 2

#39

Check last test case

``````2 1 1
5 6
6 8``````

#40

@abcdexter24: Actually if one solves this problem completely after the contest, he can practice bitmask, dp, recursion and greedy all in one