TADELIVE - Editorial



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.



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



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.


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

This is the code:


typedef long long int ll;

using namespace std;

ll mem_total(ll N, ll *A, ll *B, ll X, ll Y, ll **mem)
		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]);
		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);

	ll 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++)
	for(ll i=0; i<N; i++)

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



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


my code passed all these testcases. still got 10 points


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


my solution passed all the above test cases :slight_smile:


can you add the link of your solution?


good question, enjoyed solving it. I couldn’t score but I knew it was dp @dpraveen :slight_smile:


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


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


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


Your code returns 14 for:

2 1 1
5 6
6 8


ohh i am sorry for that case…@betlista


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


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


dont check solution…just saw your edit for case 1 and 2


Check last test case

2 1 1
5 6
6 8


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