TADELIVE - Editorial

dynamic-programming
editorial
greedy
ltime19
simple

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


#28

my solution passed all the above test cases :slight_smile:


#29

can you add the link of your solution?


#30

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


#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

Your code returns 14 for:

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 :wink:


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