FEB-17, MAKETRI Editorial (Unofficial)

editorial
,
41

Can you provide link to the code? A full view would help me debug :slight_smile:

Also, you can compare them with the reference codes too. t might be possible that the bug lies elsewhere.

42

@utsavgoel

Your code fails to check if the possible values of triangle lie inside interval of [L,R] or not. See here. If your run your code against the 3rd corner case I posted in the end, your code would fail as-

Compilation Successful
Input (stdin)
3 50 80
1 5 15
Your Output
-74

It simply updates the values without checking if the lower/upper limits are inside L and R or not. You will take max of start[I] and L, but what if start[I] is more than R? Similar argument holds for end[I].

Check the reference codes carefully. We put have used-

if(interval_end[i]<L || interval_start[i]>R)
            continue;
		// make sure we don't go less than L
		interval_start[i] = max(interval_start[i], L);
		interval_end[i] = min (interval_end[i], R);

The if statement at the start is worth million dollars, as it would immediately skip the iteration if the intervals lie completely outside [L,R]. Hope that clarifies your doubts :slight_smile:

1 Like
43

Thanks @vijju123 for this excellent editorial and also to @meooow for his clear solution
Thank you very much learnt a lot and very happy that count of partially solved problems decreased by one:)

44

Thanks for your kind words dear :slight_smile:

45

@vijju123 @meooow @inovation123
What is wrong in this submission. https://www.codechef.com/viewsolution/16147596

    import java.math.BigInteger;
    import java.util.Arrays;
    import java.util.Scanner;
    class MAKETRI {

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int n = in.nextInt();
	BigInteger l = in.nextBigInteger();
	BigInteger r = in.nextBigInteger();
	BigInteger answer = new BigInteger("0");
	BigInteger arr[] = new BigInteger[n];
	for(int i=0;i<n;i++)
		arr[i] = in.nextBigInteger();
	
	Arrays.sort(arr);
	
	Range obj[] = new Range[n-1];
	for(int i=0;i<n-1;i++){
		obj[i] = new Range(arr[i].subtract(arr[i+1]).abs().add(BigInteger.ONE), arr[i].add(arr[i+1]).subtract(BigInteger.ONE));

	}
	
	//finding range in O(n)
	BigInteger low = r.add(BigInteger.ONE);
	for(int i=n-2;i>=0;i--){
		if(obj[i].start.compareTo(r)>0 || obj[i].end.compareTo(l)<0){
			continue;
		}
		BigInteger effEnd = low.min(obj[i].end);

		BigInteger effStart;
		if(obj[i].end.compareTo(low) >= 0){

			effEnd = effEnd.subtract(BigInteger.ONE);

		}
		if(obj[i].start.compareTo(l) < 0)
			effStart = l; 
		else
			effStart = obj[i].start;
		low = effStart;
		answer = answer.add(BigInteger.ONE).add(effEnd.subtract(effStart));
	}
	System.out.println(answer);
}

static class Range{
	BigInteger start;
	BigInteger end;
	Range(BigInteger start, BigInteger end){
		this.start = start;
		this.end = end;
	}
}

}

46

Did you run it against the test cases I published on discuss (under various questions- just give forums a search by problem code “MAKETRI”). If its not addressed in past and is something new, I will have a look tomorrow.