TADELIVE - Editorial

For all those who are getting partial points,

try these case:

EDIT 1:
4 2 2
5 4 5 2
5 5 7 1
ans=19

4 2 2
5 5 7 1
5 4 5 2
ans=19

4 2 2
5 4 2 2
5 3 3 1
ans=14

4 2 2
5 3 3 1
5 4 2 2
ans=14

2 1 1
5 6
5 7
ans=12

2 1 1
5 7
5 6
ans=12

2 1 1
5 6
6 8
ans=13

4 1 3
7 5 2 2
6 2 9 8
EDIT 2: ans=28

3 2 1
7 4 9
7 2 3
ans=20

EDIT 3:
8 6 8
15 50 77 52 27 62 63 61 
350 271 916 438 281 998 125 241
ans=3620

9 5 9
60 98 21 52 9 15 62 74 83 
552 893 44 920 52 830 155 40 557 
ans=4077

EDIT 4:

More test Cases with correct Output: http://ideone.com/rOMkjI

8 Likes

My Simple Solution

Make another array named as SUB[i]=abs(A[i]-B[i])

After that sort sub and also store their original corresponding index .

Use, Optimizing sorting algo

2 Likes

@rishabhprsd7 Getting AC on All these cases but still got 10 points…
Here is my submission link.
TADELIVE MY CODE

@rishabhprsd7 Getting AC on All these cases but still got 10 points… Here is my submission link.solution

My simple Algorithm:

Sum=0;

for i from 0 to N-1

if A[i]>B[i] && X!=0:

   Sum+=A[i];

   --X;

else

   Sum+=B[i]

print Sum

I am also passing all the test cases above. Still I got 10 points. Please help me.Whats wrong with my code.?
http://www.codechef.com/viewsolution/5659232

What happens when A[i] == B[i], who is assigned to collect the tip? I got 10 for my submission and although the code is similar to the one provided in the editorial I am unable to figure what is (logically)wrong in my code.

Help would really appreciated.

Regards, Ankit

Link to code

Can somebody explain the last test case mentioned above?

My code works for all these test cases. But in the contest it was wrong for one of the cases for 30 points and one for 60 points.Rest all it was correct answer.

should not second last case output be 26… as 1st would deliver 7 and second one would 2+9+8=19
and hence 19+7=26… and please help me where my code is wrong?
http://www.codechef.com/viewsolution/5661711

4 1 3
7 5 2 2
6 2 9 8
should it not be 28?
6+5+9+8
the second last test case
http://www.codechef.com/viewsolution/5663226

1 Like

subtracting the price array and sorting and then optimizing works… i have solved this ques by the same method… is the approach accurate??

1 Like

Guys give attention to sorting d[i] in decreasing order rather than increasing…

1 Like

i got 40 points for this solution
CodeChef: Practical coding for everyone plz tell where my code is lacking :confused:
thanks in advance :slight_smile:
@betlista can u help :slight_smile:

@dpraveen: do add the psuedocode for backward dp in subtask 2.

Can be go via Merge_Sort.

http://www.codechef.com/viewsolution/5658539

plz somebody check what i missed and got 10 points :frowning:
(my code clears all above test cases)

I got AC on 10 pts and 30 pts on my sol and TLE on some test-cases of the 60 pts. I was finding the maximum in each case which was the problem. So I decided to sort it. Now it runs fast but getting WA in test case of 30 pts and 1 in 60 pts.
And My Code is clearing all the test-cases mentioned below…I think some minor mistake i am making.

Here are my two codes :

Getting 40 pts :

http://www.codechef.com/viewsolution/5659672

Getting 10 pts :

http://www.codechef.com/viewsolution/5666065

Someone pls point out the mistake i am making…

Edit 1 :
Got a test case for which i get WA.

6 5 5

76 8 64 12 77 56

397 240 293 287 137 433

My 2nd code gives 1466 and first code gives 1727 (which is the correct one)

I still cant figure out the mistake while i am making while sorting.

my D[j] = Bob[j] - Andy[j] and then I sort array D (in descending order) using comparable interface so that I can store index . After that I loop through array D and give all orders to Bob until I find a value D[j] less than 0 or j reaches max orders Bob can deliver. The remaining orders are assigned to Andy … Got AC :smiley:

why this code is showing sigsegv error??
can any body answer??

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
int n,x,y,ans,i,j,p,q;
cin>>n>>x>>y;
int a[n],b[n];
int dp[n+1][x+1];
for(i=0;i<=n;i++)
{
for(j=0;j<=x;j++)
{
dp[i][j]=0;
}
}
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
}
for(i=1;i<=n;i++)
{
dp[i][0] = dp[i-1][0] + b[i-1];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=x&&j<=i;j++)
{
p=0;
if(j<=x)
{
p = dp[i-1][j-1]+a[i-1];
}
q=0;
if((i-j)<=y)
{
q = dp[i-1][j]+ b[i-1];
}
dp[i][j]= max(p,q);
}
}
ans = 0;
for(i=0;i<=x;i++)
{
if(dp[n][i]>ans)
ans = dp[n][i];
}
cout<<ans<<endl;
return(0);

}

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