MAKETRI: Getting WA only for 2 cases. Rest AC. What's wrong with my code?

I get WA on Tasks 15 and 16 and AC on the rest. I am not able to spot the bug. Could someone help. Thanks!

Headers included is bits stdc++.h

using namespace std;

long long min(long long a, long long b) {
	if ( a <= b ) {
		return a;
	}
	else {
		return b;
	}
}


long long max(long long a, long long b) {
	if (a >= b ) {
		return a;
	}
	else {
		return b;
	}
}


int main(void) {
	
	long long n, l, r;
	
	cin>>n>>l>>r;
	

	vector<long long> a, left, right;

	long long tmp;
	for (int i = 0; i < n; i++ ) {
		scanf("%lld", &tmp);
		a.push_back(tmp);
	}
	
	sort(a.begin(), a.end());

	long long le, ri;
	for (int i = 0; i < (n - 1); i++ ) {
		le = a[i+1] - a[i] + 1;
		ri = a[i] + a[i+1] - 1;
		left.push_back(le);
		right.push_back(ri);
	}
	
	long long res = 0;
	long long endIndex, startValue, currentIndex;
	currentIndex = endIndex = n - 2;
	bool shouldBreakOut = false;

	
	while ( currentIndex > 0 ) {
		
		if (right[endIndex] < l) {
			shouldBreakOut = true;
			break;
		}
		
		startValue = left[endIndex];
		 		
		while( ( currentIndex > 0 ) && (startValue <= right[currentIndex-1]) ) {
			currentIndex--;
			if (startValue > left[currentIndex]) {
				startValue = left[currentIndex];
			}
		}
		
		
		if (currentIndex > 0) {
			long long rightVal, leftVal;
			
			rightVal = min(r,right[endIndex]);
			
			if ( startValue <= l ) {
				shouldBreakOut = true;
				leftVal = l;
			}
			else {
				leftVal = startValue;
			}
			
			res += (rightVal - leftVal + 1);
			
			if (shouldBreakOut == true ) {
				break;
			}
			else {
				endIndex = currentIndex - 1;
				currentIndex = endIndex;
			}
		}
	}
	

	if (n > 2 ) {
		if ( shouldBreakOut == false ) {

			long long leftVal = min(startValue, left[currentIndex]);
			long long rightVal = right[endIndex];

			if ( leftVal <= r && rightVal >= l) {
				leftVal = max(leftVal, l);
				rightVal = min(r, rightVal);
				res += (rightVal - leftVal + 1);
			}
		}
	}
	else {
		long long leftVal = left[0];
		long long rightVal = right[0];

		if ( leftVal <= r && rightVal >= l ) {
			leftVal = max(leftVal, l);
			rightVal = min(rightVal, r);
			res += (rightVal - leftVal + 1);
		}
	}
	
	printf("%lld\n", res);
	
	return 0;
}

I wrote an editorial on this Q. I will suggest reading the “How to find intersection” section of it. Further, you can check the reference codes to cross check ur implementation. If even after that you are unable to debug, ping me. I will help :slight_smile:

Edit- I found the test cases which haunt you. They are those test cases where l and r are very close. Check the 3 cases below-

Compilation Successful
Input (stdin)
3 1 20
1 5 15
Your Output
10

This one is good, all fine!

Compilation Successful
Input (stdin)
3 4 5
1 5 15
Your Output
-4

See what happened when I tweaked l and r!!

Compilation Successful
Input (stdin)
3 4 4
1 5 15
Your Output
-6

At l=r.

Since l can be equal to r, your code is failing at some case where l=r or something like that.

EDIT-2- The -6 is coming from this fraction of your code-

if (currentIndex > 0) {
            long long rightVal, leftVal;
            rightVal = min(r,right[endIndex]);
            if ( startValue <= l ) {
                shouldBreakOut = true;
                leftVal = l;
            }
            else {
                leftVal = startValue;
            }
            res += ((rightVal - leftVal + 1));

The “res+=…” when I made absolute, gave an answer of +6 instead of -6. Most probably this part needs a cross check. Try to see how this part of program executes for my given inputs, and I hope your query gets resolved asap. Cause you already solved those big 60 mark subtasks, I hope you soon get the complete green tick too! :slight_smile:

2 Likes

@vijju123 , I wrote the above code after reading your editorial until the “how to find intersection” part. I just went through that part now to see if I missed out any special cases. Surely I must have missed out on something otherwise I wouldn’t have gotten a WA on 2 test cases. But I am still not finding the bug. My best guess is that it is in the interval finding part only. The implementations use a slightly different approach from my code, and although they are much more cleaner and concise, I wanted to find the bug in my code anyways. Will update the post IF I find the bug :slight_smile:

I am also finding debugging your code atm. Its passed all my extra corner cases, so its obvious that you have put in some real marvellous efforts. I am trying to find the corner cases troubling you, just give me some time :slight_smile:

@vijju123, Sure. Thanks for taking your time out!!

@vijju123, Great Thanks a lot. If you could share what approach you took to finding the test cases, it would help. Was it random picks of test cases or is there a systematic way of having generating test cases?

There is a systematic way.I classified the test cases into categories, like " test cases where intervals overlap" or “test cases where final interval crosses range of l and r” (eg- [51,100] when [L,R] is [40,70]" or “test cases where first interval starts before l” (Eg- [2,5] when [L,R] is [4,20]) . There are over 20 categories of test cases for this problem (acc. to me), hence why I asked u for time. A thorough understanding and lots of research on problem and of concept (which the problem wished to test) is needed.

Aside from that, test case generation comes to you naturally when you debug. I recommend hackerearth and hackerrank for that, as you can see test-cases you’re failing, but I strictly recommend seeing the test cases only when you have done LOT of effort in finding test cases and are giving up. Cause how much you improve this ability depends on how much effort you put in while debugging. The seeing of test cases is just for reference that “Okay, this is what I failed to perceive. Will take care next time.”

@vijju123, yes got a complete AC. I had to put in a check for the interval being completely to the right of [L,R], before computing res. Thanks once again.

1 Like

Well done dear :).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class TRIANGLE3 {

static long l = 0, r = 0, low = 0; static int n = 0;
static long high = 0;
static long count = 0;
static long[] a;
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
	// TODO Auto-generated method stub
	String str[] = bf.readLine().split(" ");
	n = Integer.parseInt(str[0]);
    l = Long.parseLong(str[1]);
	r = Long.parseLong(str[2]);
	str = bf.readLine().split(" ");
	a = new long [n];
	for(int i = 0; i < n; i++){
		a[i] = Long.parseLong(str[i]);
	}
	Arrays.sort(a);
	check();
	System.out.println(count);
	bf.close();
}

static void check(){
	if(n==2){
		long x = a[0]+a[1];
		long y = a[0]-a[1];
		if(x < l){
			return;
		}else if(l < x & l >y ){
			if(r <= x){
				count = count + x - l;
				return;
			}else {
				count = count + r - l;
				return;
			}
		}else if(r < y){
			return;
		}else if(l<y & r>y & r<x){
			count = count + r - y;
			return;
		}else{
			count = count + x-y;
			return;
		}
	}else{
		long ht = 0, lt = 0;
		high = a[n-1]+ a[n-2];
		low = a[n-1] - a[n-2];
		for(int i = n-2; i >0; i--){
			ht = a[i]+a[i-1];
			lt = a[i]-a[i-1];
			if(ht<=high & lt>=low){
				if(ht>=r){
					high = ht;
				}else{
					if(high<=r){
						count = count + r - high;
						high = ht;
					}else{
						high = ht;
					}
				}
			}
		}
	}
}

}

Can anyone please debug the code… i am unable to find the bug for the last of the three testCases?? in all the subtasks. Rest is correct. Please help especially vijju123

1 Like

Ok dear, I will try my best :). Give me some time.

@sagar2009kumsr

Your code is has wrong calculation of intersection of intervals. Its giving wrong answer for sample case.

Compilation Successful
Input (stdin)
5 1 4
1 2 3 4 5
Your Output
0

Working on where the error is, but yes, I will advise re-check from your “if-else” statements in check().

EDIT- Can you explain your thinking in this portion of code-

long ht = 0, lt = 0;
        high = a[n-1]+ a[n-2];
        low = a[n-1] - a[n-2];
        for(int i = n-2; i >0; i--){
            ht = a[i]+a[i-1];
            lt = a[i]-a[i-1];
            if(ht<=high && lt>=low){
                if(ht>=r){
                    high = ht;
                }else{
                    if(high<=r){
                        count = count + r - high+1;
                        high = ht;
                    }else{
                        high = ht;
                    }
                }
            }
        }

Okay, the first instance of bug is that count is not getting incremented for the sample case under the given loop conditions. For details see the picture-

alt text

Since I don’t know logic, I cant help much with correction stage. Hope you are able to fix it soon :slight_smile:

EDIT-

Images 1 CodeChef Compiler

Image 2- Hackerrank Compiler

alt text

Hi vijju123,

thank you very much for your response, I am getting the right answer for the testCase you mentioned below… it’s coming as 3.

After sorting it is necessary that the range could not be above the sum of the last and the second last element. Now if sum comes under the range and low is also greater than left then count that else just decrease the high to the sum. Repeat the process for all the section…

Can you provide your fb id??

Its coming as 3? Are you sure you are trying the same code? Can you try running it for the test case at code compile and run? I have posted a screenshot of what I got after running it in my answer.

My FB id wont be useful to you XD. Though I am thinking of making a email address for contacting me (since I cant use my personal one for this).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class TRIANGLE2 {

static long l = 0, r = 0, low = 0; static int n = 0;
static long high = 0;
static long count = 0;
static long[] a;
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
	// TODO Auto-generated method stub
	String str[] = bf.readLine().split(" ");
	n = Integer.parseInt(str[0]);
    l = Long.parseLong(str[1]);
	r = Long.parseLong(str[2]);
	str = bf.readLine().split(" ");
	a = new long [n];
	for(int i = 0; i < n; i++){
		a[i] = Long.parseLong(str[i]);
	}
	Arrays.sort(a);
	check();
	System.out.println(count);
	bf.close();
}

static void check(){
	long ht = 0, lt = 0;
	high = a[n-1]+ a[n-2];
	low = a[n-1] - a[n-2];
	for(int i = n-2; i >0; i--){
		if(low <= 0){
			low = l;
		}
		ht = a[i]+a[i-1];
		lt = a[i] -a[i-1];
		if(ht < high & lt >low){
			if(ht>=r){
				if(high ==1){
					high = r;
				}else
				high = ht;
			}else{// Here might be a bug. incuding of r
				if(r<=high){
					count = count + r - ht;
					high = ht;
				}else{
					count = count + high - ht;
					high = ht;
				}
			}
			if(l>=lt){
				low = l;
			}
		}
		else if(ht < high & lt <= low){
			if(ht>=r){
				if(i==1){
					high = r;
				}else
				high = ht;
			}else{//Here might be a bug.
				if(r<=high){
					count = count + r-ht;
					high = ht;
				}else{
					count = count + high - ht;
					high = ht;
				}
			}
			if(lt>=l){
				if(i==1){
					low = l;
				}else
				low = lt;
			}else{
				low = l;
			}
		}
		else if(ht<low & lt <=low){
			if(ht>=r){
				if(i == 1){
					high = r;
				}else
				high = ht;
			}else{
				if(r>=ht & r <= low){
					count = count + low -ht;
					high = ht;
				}else{
					count = count + r - low;
					high = ht;
				}
			}
			if(lt>=l){
				if(i==1){
					low = l;
				}else
				low = lt;
			}else{
				low = l;
			}
		}
	}
	count = count + high - low;
}

/*
 * if(high >=r){
		high = r;
	}
	if(low <= l){
		low = l;
	}
	
	else if(ht<=low){
			if(ht>=r){
				high = ht;
			}else if( r>ht & r<low){
				high = ht;
			}else{
				count = count + r - low;
				high = ht;
			}
			low = lt;
		}
		if(r>=high&low<=l){
			count = high - l -1;
			return;
		}else if(high<=r & low<=l){
			count = r - l -1;
			return;
		}else if(r>=high& low>=l){
			count = high - low - 1;
			return;
		}else {
			count = r - low -1;
			return;
		}
 */

}

Sorry i think i might have given the wrong code… It’s the code that i have submitted… I almost got tired of debugging it…

Please have a look at the code… And i am sorry for the late reply.

I have given the new code right below.

Yes, that code is the one you submitted. I will start debugging it.

Sagar- the following bugs were seen in your approach to calculate intersection intervals-

There is no check to see if intervals are disjoint. See this test case-

  Compilation Successful
Input (stdin)
3 1 20
1 5 15
Your Output
16

In calculation of count, you made it as-

count= count+ r -ht OR count = count+ high -ht.

You are counting elements from high of one set to high of another. That’s not a correct way of finding intersection. Take these two sets for example-

[3,6] and [10,20]
[4,4] and [11,19]     

Your approach works for non-overlapping continuous intervals, but fails to accommodate these corner cases. I strongly advise that you read editorial’s method and see reference codes given in end in editorial, cause they will tell you how to find intersection in a much simpler way.

For non-overlapping continuous intervals also, there are some bugs. Take case of

Compilation Successful
Input (stdin)
3 1 20
4 5 13
Your Output
17

The intervals in this case are (1,9) & (8,18). Which is equivalent to [2,8] & [9,17] and this is equivalent to [2,17]. The answer is 16, but your code prints 1 more than it, i.e. 17. This trend is seen in all such intervals, and is again due to your formula.

The same trend is followed in case of intervals lying completely inside intervals formed by [low,high]. Eg-

Compilation Successful
Input (stdin)
3 1 20
3 5 7
Your Output
10

Intervals here are (2,8) and (2,12), so effective interval is [3,11]. Answer is 9, but we are getting 10 by your code.

Your approach to find ans for intervals could use tweaking, and hence I suggest you to see the codes and read editorial. Don’t give up, you’re just 1 step away from victory, finding intervals was the last tricky part of this question :slight_smile:

Thank You vijju123. Very very thank you for your time… I got that…