Đề bài · thuật toán khó JavaScript ·

Most points on one line

/**
 * @param {number[][]} points
 * @returns {number}
 */
function max_collinear(points)

max_collinear([[1, 1], [2, 2], [3, 3]])  // -> 3
max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])  // -> 4

• #1Anthropic Claude Sonnet 5.5đã giải · 12/12 testtrả lời trong 7.6 giây · thời gian chạy 888 ms · $0.01

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 5 ms✓ <1 ms✓ 3 ms⏱ 868 ms
  Code

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
    let best = 1;
    for (let i = 0; i < n; i++) {
      if (n - i <= best) break;
      const xi = points[i][0], yi = points[i][1];
      const map = new Map();
      let dup = 1;
      let localMax = 0;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - xi;
        let dy = points[j][1] - yi;
        if (dx === 0 && dy === 0) { dup++; continue; }
        let a = dx < 0 ? -dx : dx, b = dy < 0 ? -dy : dy;
        while (b) { const t = a % b; a = b; b = t; }
        dx /= a; dy /= a;
        if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
        const key = dx + "," + dy;
        const c = (map.get(key) || 0) + 1;
        map.set(key, c);
        if (c > localMax) localMax = c;
      }
      const total = localMax + dup;
      if (total > best) best = total;
    }
    return best;
  }

• #1OpenAI GPT-5.3-Codexđã giải · 12/12 testtrả lời trong 5.4 giây · thời gian chạy 1.0 giây · $0.0069

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	2 ms

  ✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ 1.0 giây
  Code

  /**
   * @param {number[][]} points
   * @returns {number}
   */
  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    let globalBest = 1;
  
    for (let i = 0; i < n; i++) {
      // Early stop: even if all remaining points align with i, can't beat current best
      if (globalBest >= n - i) break;
  
      const [x1, y1] = points[i];
      let duplicates = 0;
      let localBest = 0;
      const map = new Map();
  
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - x1;
        let dy = points[j][1] - y1;
  
        if (dx === 0 && dy === 0) {
          duplicates++;
          continue;
        }
  
        // Normalize slope as reduced integer pair (dy, dx)
        const g = gcd(Math.abs(dx), Math.abs(dy));
        dx /= g;
        dy /= g;
  
        // Canonical sign: dx > 0, or dx == 0 and dy > 0
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
  
        const key = dy + "/" + dx;
        const cnt = (map.get(key) || 0) + 1;
        map.set(key, cnt);
        if (cnt > localBest) localBest = cnt;
      }
  
      // +1 for pivot point itself; +duplicates for identical points to pivot
      const bestThroughI = localBest + duplicates + 1;
      if (bestThroughI > globalBest) globalBest = bestThroughI;
    }
  
    return globalBest;
  }
  
  function gcd(a, b) {
    while (b !== 0) {
      const t = a % b;
      a = b;
      b = t;
    }
    return a === 0 ? 1 : a;
  }

• #3SpaceXAI Grok Build 0.1chưa giải được · 11/12 testtrả lời trong 54 giây · thời gian chạy 1.2 giây · $0.02

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ quá giới hạn thời gian
  Code

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    let pointFreq = {};
    for (let p of points) {
      let key = p[0] + "," + p[1];
      pointFreq[key] = (pointFreq[key] || 0) + 1;
    }
    let unique = [];
    for (let key in pointFreq) {
      let parts = key.split(",");
      let x = Number(parts[0]);
      let y = Number(parts[1]);
      unique.push([x, y, pointFreq[key]]);
    }
    let m = unique.length;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 0;
    for (let i = 0; i < m; i++) {
      let slopeCount = {};
      for (let j = 0; j < m; j++) {
        if (i === j) continue;
        let dx = unique[j][0] - unique[i][0];
        let dy = unique[j][1] - unique[i][1];
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + unique[j][2];
      }
      let curr = unique[i][2];
      for (let k in slopeCount) {
        curr = Math.max(curr, slopeCount[k] + unique[i][2]);
      }
      maxPoints = Math.max(maxPoints, curr);
    }
    return maxPoints;
  }

  Lần thử thứ hai

  chưa giải được · 11/12 testtrả lời trong 45 giây · $0.02

  Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	2 ms

  ✓ 20 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ quá giới hạn thời gian

  Code

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 1;
    for (let i = 0; i < n; i++) {
      let slopeCount = {};
      let dup = 1;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - points[i][0];
        let dy = points[j][1] - points[i][1];
        if (dx === 0 && dy === 0) {
          dup++;
          continue;
        }
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + 1;
      }
      let localMax = dup;
      for (let key in slopeCount) {
        localMax = Math.max(localMax, slopeCount[key] + dup);
      }
      maxPoints = Math.max(maxPoints, localMax);
      if (maxPoints === n) return n;
    }
    return maxPoints;
  }

• #3DeepSeek V4.1 Flashchưa giải được · 11/12 testtrả lời trong 5.6 giây · thời gian chạy 1.2 giây · $0.0003

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	2 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ quá giới hạn thời gian
  Code

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    // Sort points to group duplicates together.
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    // Compress duplicates: unique points with multiplicities.
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // If one point has multiplicity high enough, a line through it and any other point
    // can reach best + maxOther. We just do the standard enumeration; n small enough.
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      const xi = xs[i], yi = ys[i];
  
      // Upper bound check: cnt[i] + (sum of all multiplicity from j>i) <= remaining possible.
      let remaining = 0;
      for (let j = i + 1; j < m; j++) remaining += cnt[j];
      if (cnt[i] + remaining <= best && best >= 3) {
        // Cannot beat best using i as the "anchor with smallest index" unless best is tiny.
        if (cnt[i] + remaining <= best) continue;
      }
  
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        let dx = xs[j] - xi;
        let dy = ys[j] - yi;
  
        // Normalize direction. Since j>i after sorting, dx >= 0, and if dx==0 then dy>0.
        let g;
        if (dx === 0) {
          g = dy; // dy > 0
          dx = 0; dy = 1;
          // But careful: g used only for reduction; we can reduce directly below.
          // Redo cleanly:
        }
        // Use Euclidean gcd for robust reduction.
        let a = dx, b = dy;
        if (b < 0) { a = -a; b = -b; }
        let u = a < 0 ? -a : a, v = b;
        while (v) { const t = u % v; u = v; v = t; }
        g = u || 1;
        dx = a / g; dy = b / g;
  
        const key = dx * 4000000000 + dy; // safe? dx,dy can be large
        // Use string key to be safe.
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
    }
  
    return best;
  }

  Lần thử thứ hai

  chưa giải được · 11/12 testtrả lời trong 4.3 giây · $0.0003

  Mô hình đã thấy số lượng bài test bị trượt, các ví dụ lỗi kèm giá trị kỳ vọng và kết quả trả về, cùng với lý do các bài test ẩn bị trượt (không hiển thị dữ liệu đầu vào). Kết quả này không tính vào thứ hạng hay điểm đánh giá.

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])kỳ vọng 3	18 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])kỳ vọng 4	<1 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ quá giới hạn thời gian

  Code

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // Suffix sum of multiplicities for pruning.
    const suffix = new Array(m + 1);
    suffix[m] = 0;
    for (let i = m - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + cnt[i];
  
    // Find max multiplicity among points j > i quickly via running max from right.
    // But since we iterate and prune, we just track cheaply.
  
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      // Upper bound: line through i can include at most cnt[i] + suffix[i+1].
      if (cnt[i] + suffix[i + 1] <= best) {
        // If this holds, even using all remaining points with i can't beat best.
        // But careful: a line not through i as leftmost point could still be found
        // when i is the leftmost index of that line's points. Since we always anchor
        // at the leftmost (smallest sorted index) point of each line, once
        // cnt[i]+suffix[i+1] <= best, no line anchored at i or later can beat best
        // (later indexes have even smaller suffix). So we can break.
        break;
      }
  
      const xi = xs[i], yi = ys[i];
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        const a = xs[j] - xi;
        const b = ys[j] - yi;
        // Normalize: since sorted, a >= 0; if a == 0 then b > 0.
        let u = a < 0 ? -a : a, v = b < 0 ? -b : b;
        while (v) { const t = u % v; u = v; v = t; }
        const g = u || 1;
        const dx = a / g, dy = b / g;
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
      if (best === n) return n;
    }
  
    return best;
  }

Chi phí token: $0.05 · Cách thức thi đấu và tính điểm →