Parabola Independence

Research note: I checked the official Codeforces Round 1080 editorial/code, the discussion under it, and Arpa's video-tutorial post listing an accepted F submission. The official written tutorial body was not really present, but the posted code and comments point to the DAG/longest-chain approach. The statement here is still the source of truth.

For two functions $f$ and $g$, independence means

$f(x) \ne g(x) \quad \text{for all real } x.$

Equivalently, the difference $g(x)-f(x)$ never equals $0$. Write

$g(x)-f(x)=Ax^2+Bx+C,$

where $A=a_g-a_f$, $B=b_g-b_f$, and $C=c_g-c_f$.

We want to know when $f$ is strictly below $g$ everywhere, meaning $f(x)<g(x)$ for all $x$. That is the same as $Ax^2+Bx+C>0$ for all real $x$.

There are three cases:

• If $A>0$, the quadratic opens upward. It is positive everywhere exactly when it has no real root, i.e. $B^2-4AC<0$. If the discriminant is $0$, it touches $0$, so the parabolas meet at one point. Not independent.
• If $A=0$ and $B\ne 0$, the difference is a nonconstant line, so it has a real root. They intersect.
• If $A=0$ and $B=0$, the difference is the constant $C$. Then $f<g$ iff $C>0$, i.e. $c_f<c_g$.

Also, if $A<0$, then $g(x)-f(x)\to -\infty$ as $|x|\to\infty$, so $f$ cannot be below $g$ everywhere.

So define a directed relation $f\to g$ if $f(x)<g(x)$ for every real $x$. Then two functions are independent iff exactly one of $f\to g$ or $g\to f$ holds.

The key structural observation is that this relation is transitive. If $f(x)<g(x)$ for all $x$, and $g(x)<h(x)$ for all $x$, then clearly $f(x)<h(x)$ for all $x$. No magic, just inequality addition doing its job.

Therefore the functions form a strict partial order. An organized subset is a subset where every pair is independent, meaning every pair is comparable in this order. In a partial order, a pairwise comparable subset is a chain. So the task becomes:

For every vertex $v$ in this DAG, find the maximum size of a chain containing $v$.

Build a DAG with an edge $u\to v$ when $u<v$, meaning $u$ is below $v$ everywhere. This DAG is acyclic because along an edge either $a$ strictly increases, or $a$ and $b$ are equal and $c$ strictly increases.

Now compute two DP arrays:

• $end[v]$: length of the longest chain ending at $v$.
• $start[v]$: length of the longest chain starting at $v$.

Using a topological order:

$end[v]=\max(end[v], end[u]+1) \quad \text{for every edge } u\to v.$

Then process the same topological order in reverse:

$start[u]=\max(start[u], start[v]+1) \quad \text{for every edge } u\to v.$

For a fixed function $v$, any organized subset containing it splits into things below $v$, then $v$, then things above $v$. The lower part plus $v$ has size at most $end[v]$, and $v$ plus the upper part has size at most $start[v]$. So the answer is at most

$end[v]+start[v]-1.$

This bound is achievable: take an optimal chain ending at $v$ and an optimal chain starting at $v$, glue them at $v$, and transitivity guarantees every lower element is below every upper element. So the answer is exactly

$ans[v]=end[v]+start[v]-1.$

Edge cases:

• If two parabolas have the same $a$ but different $b$, their difference is linear, so they intersect. Do not add an edge.
• If they have the same $a$ and $b$, compare $c$ directly.
• Discriminant $0$ is bad because touching still means equal at one real point.
• Use 64-bit or wider arithmetic. The given limits fit in long long, but __int128 makes the discriminant check idiot-proof.

Let $m$ be the number of edges. We test all ordered pairs in $O(n^2)$ and then do DP in $O(n+m)$. Since $m\le n(n-1)/2$, each test case is $O(n^2)$ time and $O(n^2)$ memory. The statement guarantees $\sum n^2\le 3000^2$, so this is comfortably fine.