TADELIVE - Editorial

editorial
, , , ,
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[i] = new ll[Y+1];

	ll A[N], B[N];

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

	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[i] cannot be 0 :wink:

1 Like
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 - OeLs9e - Online Python Interpreter & Debugging Tool - Ideone.com

32

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

33

So when SUB[i] 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
1 Like
35

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

36

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

1 Like
37

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

1 Like
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:

2 Likes