Blog

Notes on competitive programming, machine learning, and quantitative finance by Priyanshu Debnath.

• Scan From Both Ends: How One Line Took My Divide and Conquer From TLE to AC

  My solution to Vlad, Misha and Two Arrays was correct and still got TLE on test 14. The fix was to check the split candidates in the order l, r, l+1, r-1, ... instead of left to right. Here is why that one change turns O(n²) into O(n log n).

• Bin Packing — Why It's Hard, How to Approximate It, and When It Isn't Hard At All

  A full pass through bin packing — the formal problem, why the decision version is NP-complete (and why the optimization version is strongly so), every classical approximation algorithm with its proven bound, the special cases that collapse back to polynomial time, and the backtracking/bitmask-DP techniques you'd actually use to solve small instances in a contest.

• Why My PBDS ordered_multiset Solution TLE'd (and the Fenwick Fix)

  My approach to Zhily and Barknights was correct from the start, but the PBDS ordered_multiset implementation TLE'd twice. This post covers how Red-Black trees and order statistics work, and why a Fenwick tree passed instead.

• Stack, Heap, and the Registers That Finally Made Sense

  Hi, it's my first blog. I went looking for proof that the stack and heap actually exist, and found it.

Redirecting to the blog…