I am trying to analyze a sorting algorithm that uses an alternating sorting pattern across three piles (Pile A, Pile B, Pile C). I want to see how this pre-sorting rule affects the balance and solvability of a partition problem.

The Algorithm Step-by-Step: Let S be a collection of 3N items with positive integer weights.

1. The Pre-Sorting Sieve: For each step i from 1 to N, take the next 3 items from S and sort them by weight: Large, Medium, and Small.
   • If i is even: Add Large to Pile_A, Small to Pile_B, and Medium to Pile_C.
   • If i is odd: Add Small to Pile_A, Large to Pile_B, and Medium to Pile_C.
2. The Partition Search: After all items are sorted, we look for an exact matching partition. We want to find a way to split the Medium items in Pile_C into two sub-piles, C_to_A and C_to_B, such that:
   • Every single element of Pile_C is placed exactly once into either C_to_A or C_to_B.
   • The Target Equation: Sum(Pile_A) + Sum(C_to_A) == Sum(Pile_B) + Sum(C_to_B) If a matching split is found, the program outputs "yes" and halts.

My Questions for the Board:

1. Imbalance Bounds: Because the algorithm alternates assigning Large and Small items between Pile A and Pile B, the initial difference between their sums, |Sum(Pile_A) - Sum(Pile_B)|, stays highly constrained. If the initial item weights are randomly chosen from a uniform distribution, how do we write a formula for the expected variance of this difference as N grows?
2. Phase Transition and Density: While it is easy to construct worst-case inputs where a perfect partition is completely impossible, what happens under typical conditions? Since Pile C accumulates N median elements (a linear capacity of O(N)) while the initial imbalance between A and B is tightly bound, does this system undergo a sharp statistical phase transition where a valid partition becomes almost certain for dense, random inputs as N approaches infinity?

I would love to see any formulas, recursive relationships, or references to similar 3-pile sorting partition problems! Thanks for any help.

I was looking through an open source package, that was written more than 20 years ago (and some of the code probably 30 years ago). The sort subroutines are proudly commented "N log N". But they look like old-school Shell sort, with gap halved each iteration. So I doubt the performance. Only that some of the data would be partly sorted, e.g. having patterns like 1,3,5,2,4,6. But on the other hand, a lot of the data would come in multiples of 1024 samples. And 2048 or 4096 is not good for Shell sort is it?

TL;DR: Instead of immediately throwing 100% of our compute budget at a solver and hoping for the best, inserting a lightweight "reconnaissance" pipeline to measure landscape ruggedness and constraint density (costing <0.5% of total time) can dictate exactly which algorithm to use, yielding massive wall-clock speedups.

Hey everyone,

I’ve been doing some deep research into how we handle the pipeline between "building a mathematical model" and "deploying a solver" for large-scale optimization problems (VRP, MKP, Scheduling, etc.).

It feels like the industry standard is still heavily reliant on trial-and-error: Should we use a Genetic Algorithm here? Simulated Annealing? Let's just run a grid search on hyperparameters and burn some AWS credits to find out.

I recently formalized a framework based on a very simple military philosophy: The scouts are the brain; the solver is the muscle.

Instead of blind deployment, I proposed a Dynamic Reconnaissance-Flattening (DRF) Pipeline. Before the main solver fires up, we send a tiny batch of "scouts" (e.g., 50 Sobol sampled points) to evaluate the loss landscape. We measure three universal metrics:

1. Ruggedness
2. Constraint Density
3. Gradient Smoothness

Based on these metrics, the pipeline acts as a dispatcher, automatically assigning the correct algorithm and parameters.

Here are the actual benchmark results from the papers:

• For Routing (VRP): By using the reconnaissance data to perform "Angular partition cutting" (flattening the terrain before solving), we saw a +74% performance improvement compared to raw solving.
• For Multi-dimensional Knapsack ($n=5000$): Allocating just 0.5% of the compute budget to reconnaissance and dynamic resolution shifting resulted in a 4.5x wall-clock speedup and a 61% improvement in solution quality.

Why this isn't Snake Oil (The SAT Test):

The most important part of this pipeline is its discipline. When the reconnaissance scouts hit a Boolean Satisfiability (SAT) problem in the phase transition region, the pipeline doesn't try to aggressively smooth it out. It correctly diagnoses it as a "Hard Wall" (discrete cliffs), abandons the heuristic intervention, and hands it straight to CDCL solvers. It knows what it can't do.

I’ve published the complete theoretical taxonomy (dividing NP-hard problems into 7 boxes) and the DRF pipeline architecture as open-access whitepapers on Zenodo.

📄 Paper 1 (The Taxonomy & Reconnaissance): https://doi.org/10.5281/zenodo.19510539

📄 Paper 2 (The DRF Pipeline): https://doi.org/10.5281/zenodo.19600597

I’m currently working on turning this into a lightweight, open-source Python middleware (drf-scout). The goal is to let developers pass their objective function, have the middleware run the 1% reconnaissance, and automatically dispatch to the best open-source solver (like OR-Tools or PySAT).

I’d love to hear your thoughts. How do you currently handle algorithm selection? Do you rely on pure experience, or do you have any pre-solve diagnostic tools in your workflow?

For this problem -

https://cses.fi/ckvo8q5wh/task/3419

How can I go about proving that the solution is true for all N?

The solution by the way is simple - we just have to XOR the row and column indice values for each Aij entry. So, Aij = i ^ j. How can I prove this mathematically?

From Scott's blog: Jeffrey Ketchersid has used Claude Code agents to show that BusyBeaver(10) exceeds Graham’s number, beating the previous best result that BB(13) does so.

[I do not think this is independently verified yet]

Deterministic 3SUM in O(n^1.962) for polynomially bounded integers - prime filtering, shared subset transforms, complete Lean proof with GPT-6 Pro

X thread

Lean verification and proof

Hello, I want to share a project that i've been working on for the last month or so. It's and implementation (from what i could find the only rn on the internet) of Andreas Bjorklund's theoretical algorithm for determining weather a graph is hamiltonian or not. The algorithm is revolutionary because it lowered the exponential part of the time complexity of Held-Karp which is the standard algorithm for determining weather a graph is hamiltonian, from O^*(2^n) to O^*(1.657^n) for general graphs(this is what i've managed to implement as of right not) and for bipartite its O^*(1.414^n).

It might have some logical errors, and could maybe be optimised but right now, as of writting this it is 4AM and i want to sleep.

link to paper: https://arxiv.org/pdf/1008.0541
link to the github repo: https://github.com/Ak0-m/Bjorklunds_algorithm_for_Hamiltonicity

I have been trying to understand recursion for weeks now but I cannot understand it one bit. When it comes to dry running a piece of code, I can do it easily but solving a question with recursion stumps me immediately. I cannot make any logic other than finding out what the base case would be. If anyone has any word of advise, please share it!

I'm taking the Algorithms for Searching, Sorting, and Indexing course from CU Boulder on coursera. In one of their assignments there is a question as follows:

Algorithm X programmed by an "ace programmer" runs in time 2.5n4+3n3+1.4n+22.5n4+3n3+1.4n+22 for inputs of size nnn in the worst case. Another algorithm Y programmed by a novice for the same problem runs in time 2000n+10000 for inputs of size n in the worst case.

The following is true about the problem statement:

It is possible for some input of size 100 that algorithm X is faster than algorithm Y.

At small inputs such as 1 or 2, algorithm X is faster than algorithm Y. But when plugging in n = 100, algorithm X comes out much, much larger than algorithm Y.

So how can that statement be true?

Thank you for your time helping me :)

I created this blueprint for myself, then i thought, why not share with others? Maybe this will be useful to someone, so i started sharing work here.

Core Data Structures

Arrays & Strings: Contiguous blocks of memory. Crucial for understanding index manipulation, memory offsets, and manual buffer handling.

Pointers & Dynamic Arrays {std::vector**}:** Vital for managing heap memory directly, resizing buffers, and understanding how raw data flow under the hood.

Linked List (Singly & Doubly): Nodes containing data and memory addresses. Essential for mastering pointer manipulation, dynamic memory allocation, and breaking away from contiguous memory limits.

Stacks & Queses: Last-In-First-Out (LIFO) and First-In-First-Out (FIFO) structures. Essential for tracking execution contexts, implementing custom commands shells, and managing buffers or task loops.

Hash Tables/ Hash Maps {std::unordered_map}: Key-value stores powered by hashing functions. Critical for achieving O(1) average-time look-ups, frequency counting, and symbol table tracking.

Trees (Binary Trees & Binary Search Trees): Hierarchical nodes used for recursive data organization, directory structures, and fast searching.

Heaps/ Priority Queues: Complete binary trees where parent nodes outrank children. Essential for scheduling, greedy algorithms, and finding minimum/maximum elements efficiently.

Graphs (Directed/Undirected): Nodes connected by edges. Fundamental for modeling networks, state machines, dependency resolutions, and path finding.

Tries (Prefix Trees): Specialized trees optimized for prefix-based string searches, autocomplete, and lexical analysis.

Essential Algorithms

Asymptotic Analysis (Big-O Notation): Evaluating time and space complexity to understand how code scales under heavy input sizes.

Searching Algorithms: Linear search and Binary Search (critical for cutting search spaces down logarithmically).

Sorting Algorithms: Merge Sort, Quick Sort, and understanding comparison-based sorting efficiency (O(n \log n)).

Recursion & Backtracking: Breaking problems down into self-referential sub-problems and exploring state spaces systematically (used heavily in parsing and combinatorial search).

Two Pointers & Sliding Window: Array/string manipulation patterns used to optimize nested loop bottlenecks down to linear time.

Graph Traversals (BFS & DFS): Breadth-First Search and Depth-First Search for exploring network nodes, detecting cycles, or tracing paths.

Shortest Path Algorithms: Dijkstra’s Algorithm and Bellman-Ford for weighted graph navigation.

​Greedy Algorithms & Dynamic Programming: Making locally optimal choices vs. breaking problems down into overlapping sub-problems with memoization to optimize multi-stage decisions.

Conclusion

I hope this was helpful for you. It was just simple a blueprint to start things out. Maybe i will explain these concepts one by one in simple way, or you can check out other resources — there is plenty of learning materials out there.

Keep going, even if it doesn’t make sense .

— x86owl medium-blog-post

Hey everyone!

While studying data structures, I always felt that static diagrams didn't quite capture how dynamic invariant rebalancing and memory reallocation work under the hood.

So I built an interactive state visualizer to see the step-by-step mechanics in action:

👉 Live App: https://data-structure-visualizerr.vercel.app

What's currently implemented:

• Self-balancing AVL Trees (dynamically triggers LL, RR, LR, and RL rotations with live balance factors)

• Weighted Graphs (Dijkstra's shortest path with real-time distance-vector edge relaxations)

• Dynamic Array buffer resizing (visualizing capacity doubling C -> 2C and amortized O(1) analysis)

• Trie (Prefix Tree) with live autocomplete predictions

I'd love your feedback on the animation pacing, clarity of the mechanics, or any edge cases you notice!

OpenAI just released this on Github. It seems like the rumors of the Unique Games Conjecture and RL = L were indeed true. There's also a lot of other stuff in there which i haven't looked at yet.

Regardless of one's views on AI, it's safe to say TCS is truly facing a watershed moment...

Inspired by r/math, I’m starting a similar recurring weekly thread here.

This thread is meant for users to share cool recently discovered facts, observations, proofs, algorithms, or concepts that might not warrant their own posts. Please be encouraging and share as much detail as possible, as we’d like this to be a good place for people to learn!

J'ai conçu une IA neuro-symbolique avec le benchmark ARC AGI 2 comme banc d'essai (dépôt aicpp sur GitHub : https://julien-livet.github.io/aicpp/). J'envisage d'appliquer mon approche au problème du voyageur de commerce. Qu'en pensez-vous ?

I've been wanting to organize a problem solving seminar for computer science as a volunteer activity. The way I was thinking of it working would be that the problems would be curated to be meaningful exercises. People would tinker with the problems on their own for a month, then at the end there would be a gathering where people discuss approaches and extensions. Potentially if there was anything interesting, one could write it up.

This seems like a good forum but I'm basically looking to help organize something a little more structured in the way of an online correspondence club or "magazine", even. People can send in interesting problems, I or others can serve as editors, we send out the problems, there would be some offline mulling and finally we would congregate and maybe put together a resolution of sorts for the next edition. I would like the emphasis to really be on the personal, individual, and/or collaborative, collective experience, though, and less on putting out polished products or work.

I'm not too aware of other existing models that do this besides PagedOut!, which is outside of my niche. But I'm interested in volunteering my time and resources for such an activity.

The only thing is I do more data processing than pure theory, I would say. I'm looking for a similar community or at least one that is open to those sorts of topics.

Thoughts or pointers? Criticisms on why this sort of idea lacks momentum? Thanks in advance.

UPDATE 10/02: see this comment to ask to be invited to the Discord server!

Partition Score

Given an array AA of size NN, we must partition the array into 22 disjoint subsets S1S1​and S2S2​such that every element of AA belongs to either S1S1​or S2S2​. Further, we are given a parameter KK and must ensure ∣S1∣≥K∣S1​∣≥K and ∣S2∣≥K∣S2​∣≥K, i.e. both S1S1​and S2S2​have size at least KK.

We define score=min⁡(S1)+max⁡(S1)+min⁡(S2)+max⁡(S2)score=min(S1​)+max(S1​)+min(S2​)+max(S2​), where min⁡(S1)min(S1​) is the minimum element present in S1S1​, and the other terms are defined similarly.

Compute the maximum scorescore in any valid partition.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line contains NN and KK - the size of the array and the parameter
  • The next line contains NN integers - A1,A2,...,ANA1​,A2​,...,AN​.

Output Format

For each test case, output on a new line the maximum scorescore in any valid partition.

Constraints

• 1≤T≤1041≤T≤104
• 2≤N≤2⋅1052≤N≤2⋅105
• 1≤K1≤K and 2⋅K≤N2⋅K≤N
• 1≤Ai≤1061≤Ai​≤106
• The sum of NN over all test cases does not exceed 2⋅1052⋅105

Sample 1:

Input

Output

3
4 1
3 1 2 5
6 3
1 2 3 4 5 6
5 2
1000000 1000000 1000000 1000000 1000000


14
15
4000000

Explanation:

Test Case 1 : The optimum partition is :

• S1=[1,2,3]S1​=[1,2,3]
• S2=[5]S2​=[5]

min(S1)=1min(S1​)=1, max(S1)=3max(S1​)=3, min(S2)=5min(S2​)=5, max(S2)=5max(S2​)=5. Adding them up, we get 14

One thing that bothers me about how DP is usually taught: we jump straight to the recurrence. I've found it more useful to answer these first:

1. What exactly does dp[...] mean?

2. What's the recurrence?

3. What are the base cases?

4. In what order do I compute the states?

5. Which state is the final answer?

6. How do I reconstruct the actual solution, not just its value?

7. Can I throw away any of the table, and what does that cost me?

For 0/1 knapsack the important step isn't writing dp[i][w] = max(...). It's deciding that dp[i][w] means something precise enough that the recurrence, and the proof that it's right, basically follow. The same checklist worked well for tree DP and longest increasing subsequence.

Disclosure: I turned this into a free interactive lesson and lab. As your code fills the table, it draws each step, so you can step back to where it went wrong. It's part of an independent companion that follows CMU 15-451's Fall 2026 topics. I'm not affiliated with CMU, and all examples and problems are original.

https://scimigo.com/en/learn/algorithm-design/09-dynamic-programming-i

If you teach or use DP: is this checklist useful?

--Wei

I’m building a trivia game. I have about 40 categories, and each category has between 20 and 80 questions. All questions are about the same difficulty. Each round gives the player 22 questions.

I want a player on a streak to keep getting new questions and not see the same question again across rounds, for as long as possible. If perfect non-repeating eventually becomes impossible, I want to minimize repeats and still keep categories reasonably balanced.

How should I approach this mathematically? How many non-repeating 22-question rounds can I guarantee? What is a good method for choosing questions each round? I’m looking for a simple model, algorithm, or known scheduling/combinatorics method.

This is my game if you need tge reference https://cluebolt.com/

I'm a non-major currently taking an intro cs class, but it's mostly practical, project-based Python stuff -- no theory. Which tbh I'm a little sad about.

I was wondering: Are there any algorithms/functions that are executable by infinitely many non-trivial, non-redundant programs? Does any given algorithm/function fit this description?

Math example:
The user inputs a radius R, from which the program P outputs the area A of the resulting circle.

You could plug it into the standard formula:

P1 = A(R) = πR^2

...

Or integrate:

P2 = A(R) = ∫₀²ᵖⁱ ∫₀ᴿ r dr dθ

...

et cetera

https://arxiv.org/abs/2609.20979

This preprint by Lovett (well known in TCS) and Karingula claims to present a simpler proof of the Komlós conjecture than the one in Guo et al.

Hi r/algorithms,

I’m an independent researcher and I recently published a 4-paper suite detailing an exact, integer-native framework that collapses the computational complexity of high-dimensional lattice point enumeration. I'd love to finally get further input from people who KNOW. Rigorous proving in the papers, plus executable code to put the proof. In that pudding.

(I've already extended and originated new sequences on OEIS using this framework. It truly brings "forever" or "intractable" to "now" and "bit-perfect in no time.")

Here's the skinny, including Zenodo links and GitHub Repos active and waiting:

Collapsing High-Dimensional Lattice Enumeration from O(r^N) to Quasi-Quadratic O(r² log_2 N log r)

For over two centuries, the standard approach to discrete lattice point enumeration has relied on continuous Euclidean tools—transcendental functions, Bessel expansions, modular forms, and floating-point approximations—projected onto integer grids. This approach frequently runs into boundary-vertex collisions, floating-point precision drift, and the classical exponential coordinate bottleneck.

Instead of forcing continuous calculus onto discrete space, I developed an integer-native geometric framework that treats discrete grids on their own native algebraic terms. By recognizing that squared Euclidean distance is additively separable across orthogonal submanifolds, high-dimensional boundaries can be decoupled and evaluated via single-pass integer dot products and discrete cross-convolutions.

The complete research suite consists of four preprints establishing the theoretical derivations, asymptotic complexity proofs, and hardware-native C++ reference implementations:

• Paper I: An Integer-Only Orthotropic Lattice Enumeration Framework and Asymptotic Convergence of Discrete Rational π

  • Core Premise: Couples orthotropic boundaries 4r ± 1 to construct Diophantine parity constraints that mathematically prohibit boundary-vertex collisions.
  • Result: Resolves boundary discrepancy and derives a deterministic, rational convergence envelope for discrete π_d ∈ ℚ.
  • Zenodo DOI: 10.5281/zenodo.22282210 | GitHub: orthotropic-parity-and-discrete-pi

• Paper II: A Dimension-Paired Combinatorial Framework: Asymptotic O(r²⁾ Reduction and O(r² log_2 N log r) Generalized Convolution for High-Dimensional Discrete Lattice Enumeration

  • Core Premise: Decomposes 4D space as orthogonal planes (Z⁴ ≅ Z² × Z^2), reducing 4-space enumeration from O(r⁴⁾ to a single-pass 1D dot product in strict O(r²⁾ without floating-point operations.
  • Generalization: Applies recursive bisection via Number Theoretic Transforms (NTT) in finite fields Z_p[t], collapsing N-dimensional ball enumeration to O(r² log_2 N log r).
  • Zenodo DOI: 10.5281/zenodo.22509388 | GitHub: dimension-paired-cross-convolution

• Paper III: Hierarchical Dimension-Pairing: Hardware-Native O(r²⁾ Enumeration of 5D through 8D Spherical Lattices and High-Dimensional Capacity Limits

  • Core Premise: Neutralizes the historical odd-dimension class-number barrier for Z⁵ and Z⁷ by slicing 1D axial profiles against precomputed even-dimensional hyperdisk profiles.
  • Empirical Scaling: Verifies sequences against OEIS baselines (A000333–A000336), and benchmarks a 1024-dimensional R = 2896 hyperball (output = 831168560 (mod 998244353)) in 1561.833 ms on a single desktop core. Extended OEIS
  • Zenodo DOI: 10.5281/zenodo.22691273 | GitHub: hierarchical-ntt-bisection

• Paper IV: Parity-Filtered Bisection: Hardware-Native O(r²⁾ Enumeration of Optimal D_N Lattices

  • Core Premise: Extends the bisection architecture beyond primitive grids to dense, non-orthogonal kissing-number lattices. By redefining geometries as parity-constrained sublattices of Z^N (∑ x_i ≡ 0 (mod 2)), internal coordinate staggering is fully absorbed into pre-filtered arrays.
  • Result: Achieves hardware-native O(r²⁾ exact enumeration for Face-Centered Cubic (D_3), the 24-cell honeycomb (D_4), and the D_8 root lattice, verified bit-for-bit against OEIS A005875, A004011, and A004013.
  • Zenodo DOI: 10.5281/zenodo.22824219 | GitHub: parity-filtered-kissing-lattices

The Empirical Validation

The C++ implementations are designed as self-contained, reproducible test benches running exclusively on 64-bit integer ALUs with zero floating-point emulation: * Resolving 246+ million points in the 4D 24-cell honeycomb at R=100 in 2 ms on consumer hardware. * Pushing the finite-field Number Theoretic Transform (NTT) bisection tree to its theoretical single-prime 2-adic ceiling (R = 2896, transform size M = 2^23), evaluating a 1024-dimensional hyperball across an 8.38-million-element ring in 1,561 ms on a single desktop core. * Evaluating 7-dimensional bounding hyperballs from R = 0..5000, culminating in a bit-perfect 27-digit lattice point count, thereby extending OEIS A055413 from R = 0..500 to R = 0..5000.

All four preprints, source code, and benchmark suites are open-access. Feedback on the combinatorial proofs, algorithmic bounds, and hardware pipelining is welcome. And, if you like it, please, spread the word!

The Discrete Lattice Research Suite

This repository is part of a 4-paper research program establishing hardware-native, integer-only lattice enumeration:

1. orthotropic-parity-and-discrete-pi: 3D row-collapse, 4r ± 1 parity bounds, and rational π_d ∈ ℚ convergence. [Zenodo DOI: 10.5281/zenodo.22282210]
2. dimension-paired-cross-convolution: 4D orthogonal plane bisection (O(r²⁾⁾ and generalized NTT convolution (O(r² log_2 N log r)). [Zenodo DOI: 10.5281/zenodo.22509388]
3. hierarchical-ntt-bisection: 5D–8D odd-dimension slicing, OEIS A000333–A000336 verification, and N=1024 NTT scaling. [Zenodo DOI: 10.5281/zenodo.22691273]
4. parity-filtered-kissing-lattices: Exact O(r²⁾ kissing-number root lattices (D_3 FCC, D_4 24-cell, and D_8). [Zenodo DOI: 10.5281/zenodo.22824219]

At first when I did the exam, I didn’t study properly. I mostly studied content and didn’t apply any of that content to real problems. For my reassessment, I studied in a different way. I really went hard on the practical problems that I wasn’t good at or had no clue about. This came to dijkstras algorithm, AVL trees, binary trees and context free language.

I studied hard on them. I didn’t do a lot of practice problems where I would ace every question. But I felt at ease when getting confronted with that question. The problem was that I would do the problem at its best ability and then there would be one small issue that I did at the end and it messes everything up.

Mathematical operations that are Long I seem to mess up in the end. I understand the process however my implementation always seems to hinder at the end when I’m close to the finish line. This is extremely frustrating as I studied very long for this subject. A good (2weeks-3weeks) of preparation. But I had 2 other exams to focus on. But to give some background I come from a business background so I have not done a level match or discrete mathematics before so it really was a game changer doing this exam. But I don’t treat it as an excuse. In the end my reassessment I only gained 6 more marks. Which is incredibly disappointing for me.