Why sorting by left coordinate does not work, while by right coordinate works?

Today, I. have solved Problem D of AtCoder Beginner Contest 230. I have solved it by sorting by right coordinates and increasing the answer by 1 if the left coordinate is greater than the slide.

After the contest ends, I was wondering why sorting by left coordinate does not work and gave WA. Please provide a test case where this fails. Thank You!

Problem: D - Destroyer Takahashi

AC Solution:


import java.util.*;
import java.io.*;
import java.math.*;

public class Main {

  static StringBuffer str=new StringBuffer();
  static long n,d;
  static List<long []> l;

  static void solve(){
    Collections.sort(l, (a, b) -> {
      return (int)(a[1]-b[1]);
    });
    long ans=0;
    long x=-(1l<<40);
    for(long []li:l){
      if(x+d-1 < li[0]){
        x=li[1];
        ans++;
      }
    }
    str.append(ans).append("\n");
  }

  public static void main(String[] args) throws java.lang.Exception {
    BufferedReader bf;
    PrintWriter pw;
    boolean lenv=false;
    if(lenv){
      bf = new BufferedReader(
                          new FileReader("input.txt"));
      pw=new PrintWriter(new
            BufferedWriter(new FileWriter("output.txt")));
    }else{
      bf = new BufferedReader(new InputStreamReader(System.in));
      pw = new PrintWriter(new OutputStreamWriter(System.out));
    }
    
    // int t = Integer.parseInt(bf.readLine().trim());
    // while (t-- > 0) {
      l=new ArrayList<>();
      String []s=bf.readLine().trim().split("\\s+");
      n=Long.parseLong(s[0]);
      d=Long.parseLong(s[1]);
      for(int i=0;i<n;i++){
        s=bf.readLine().trim().split("\\s+");
        l.add(new long[]{Long.parseLong(s[0]), Long.parseLong(s[1])});
      }
      solve();
    // }
    pw.print(str);
    pw.flush();
    // System.outin.print(str);
  }
}

WA solution


import java.util.*;
import java.io.*;
import java.math.*;

public class Main {

  static StringBuffer str=new StringBuffer();
  static long n,d;
  static List<long []> l;

  static void solve(){
    Collections.sort(l, (a, b) -> {
      return (int)(a[0]-b[0]);
    });
    long ans=0;
    long x=-(1l<<40);
    for(long []li:l){
      if(x+d-1 < li[0]){
        x=li[1];
        ans++;
      }
    }
    str.append(ans).append("\n");
  }

  public static void main(String[] args) throws java.lang.Exception {
    BufferedReader bf;
    PrintWriter pw;
    boolean lenv=false;
    if(lenv){
      bf = new BufferedReader(
                          new FileReader("input.txt"));
      pw=new PrintWriter(new
            BufferedWriter(new FileWriter("output.txt")));
    }else{
      bf = new BufferedReader(new InputStreamReader(System.in));
      pw = new PrintWriter(new OutputStreamWriter(System.out));
    }
    
    // int t = Integer.parseInt(bf.readLine().trim());
    // while (t-- > 0) {
      l=new ArrayList<>();
      String []s=bf.readLine().trim().split("\\s+");
      n=Long.parseLong(s[0]);
      d=Long.parseLong(s[1]);
      for(int i=0;i<n;i++){
        s=bf.readLine().trim().split("\\s+");
        l.add(new long[]{Long.parseLong(s[0]), Long.parseLong(s[1])});
      }
      solve();
    // }
    pw.print(str);
    pw.flush();
    // System.outin.print(str);
  }
}

The sliding window logic is wrong because taking the right bound of the leftmost block doesn’t guarantee catching other segment’s right bound.

For example if the segments are [1,3], [2,2], your code will assume that taking 3 as a target will destroy both the first and the second block just because 3+d-1\geq2, which is obviously wrong.

Hint: It’s easier to prove why sorting by the right bound works if you look at the array from the back, but the same idea holds when looking from the front.

Although we get the right answer, it is actually not destroying some blocks, when I sort by left coordinates, is what you are telling, right? But all we need is the answer and why would they check if it is actually destroyed or not?

Consider the following testcase:

3 1
1 10
2 2
3 3

The correct output is 2. But your WA variant prints 1.

2 Likes

This is what I was waiting for! Thanks a ton! It is better to sort by R to not miss the walls that are before the current wall.