LOCSEP17 :: Problem COCOPROD and CHEFSTCK :: Help Needed

general
, , ,
1

I solved these two questions but had problem.

In COCOPROD I used recursion+memoization but One Test case didn’t passed

My Code : COCOPROD

In CHEFSTCK I reduced it to Trivial Job Scheduling Greedy Problem but Two Test cases didn’t passed

My Code : CHEFSTCK

*If Someone could either rectify my approach or check my code for a minute bug, It would be real helpful.

Thanks*

1 Like
2

Doesn’t the job scheduling give the max number of jobs you can do and not the minimum time you remain free? I don’t think we can reduce it to the standard job scheduling problem.

3

P.S. : my profit[i] will be finish[i] - start[i] i.e. the length of the spanning stick.

Check My Code Attached Above

4

length of max no. of jobs is different from maximum time doing the job… for example if i have a segment 1-10 and have sticks from 1-2, 3-4, 5-6, 3-10… your answer would be 4 as u will pick first three sticks but the answer should be 1 by placing 1st and last stick

1 Like
5

@mohitkurani98 That’s exactly what I was pointing out.

6

@mohitkurani98 first of all the answer would be 2. and My code will give 2 as expected. see @ista2000 :diamonds:

7

0-1 and 2-3 will give me count=2

reference: pNIIcE - Online C++0x Compiler & Debugging Tool - Ideone.com

8

Are you really taking max number of jobs and subtracting it from m? If yes then in this case
1
3 15
3 5
8 10
1 15
Your code returns 1 but it shouldn’t if it is doing what you say it is doing.

9

may be I was not able to convey what I am doing?

for(int i=0;i<n;i++)
{

cin>>arr[i].start>>arr[i].finish;
arr[i].profit = arr[i].finish - arr[i].start;

}

ll ans = m-findMaxProfit(arr,n);

here findMaxProfit is the basic weighted job scheduling algorithm as mentioned.

1 Like
10

for(int i=0;i<n;i++) {

cin>>arr[i].start>>arr[i].finish;
arr[i].profit = arr[i].finish - arr[i].start;

}

ll ans = m-findMaxProfit(arr,n);

here findMaxProfit is the basic weighted job scheduling algorithm as mentioned.

1 Like