[Solved] What is wrong with this solution while solving JUICE on SPOJ?

It’s probably wrong when there is some segments having same start time.

I run this test case with your code:

10

1 1

1 2

3 3

1 4

3 5

3 6

3 7

8 8

3 9

3 10

Your code output 10 but the answer is actually 9

I have several WA because of this test case too,
and got AC after I handle this case…I will share my experience and please see if it is the same bug for you.

Using this test case, my code will output 10, I will explain quickly as follows:

Let dp(i) be the state that you have your last cut at i-th segment’s start time

Clearly, dp(i) = maximum (dp(j) + # of segments(after j)intersect with i-th segment) for all j < i

Physically , it means you have the second last cut at j-th segment’s start time which is logical except if j-th and i-th segment’s start time is the same! Then it is not 2 different cut but the same cut!

To handle this, the correct way is choose the last segment of consecutive segments having same start time ONLY!

(Assuming the segment is sorted by start time already, the order below is the sorted order)

Here is the bug, my program (maybe yours as well) gives the output 10 because (using 0-based)

DP(9) = DP(6) + # overlap segments in [7,9]

= 7 + 3 = 10!

If you look deeper, DP(6) = 7 is actually right, as it does not consider the segments afterwards. But you should not use DP(6) to update any DP(X) for X>6! as the last segment having same start time (with 6-th segment) is the 8-th segment

In short, if we use some DP state which is NOT the last one having the same start time with itself to update other DP states, something may go wrong.

My solution is that when I doing DP on the i-th segment, whenever I find some segments j having same start time with segment i (j < i), I set DP(j) to negative infinity so that it must not be optimal enough to update other states.

EDITED: Accepted Code Added
As required by OP, below is my code which is accpeted

#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define INF 1LL<<28
using namespace std;

int T,n;
int dp[1005];
pii a[1005];
int main(){
	scanf("%d", &T);
	for(int qwe=1; qwe <= T; qwe++){
		scanf("%d", &n);
		for(int i=0; i<n;i++) scanf("%d%d", &a[i].x, &a[i].y);
		sort(a, a+n);
		memset(dp,0,sizeof(dp));
		
		for(int i=0; i<n;i++){
			int cnt = 0;
			for(int j=i-1; j>=0; j--){
				if(a[j].x == a[i].x){dp[j] = -INF; cnt++; continue;}
				cnt += (a[i].x >= a[j+1].x && a[i].x <= a[j+1].y);
				dp[i] = max(dp[i], dp[j] + (cnt>2? cnt:0));
			}
			
			cnt += (a[i].x >= a[0].x && a[i].x <= a[0].y);
			dp[i] = max(dp[i], (cnt>2? cnt:0));
		}
		printf("Case #%d: %d\n", qwe, dp[n-1]);
	}
	return 0;	
}