1796. How Many Rules You Can Keep

There are n switches and k rules, listed in order. Each rule names two conditions and demands that at least one of them holds, where i means "switch i is ON" and -i means "switch i is OFF".

The whole list may be impossible to satisfy. Print the largest p such that the FIRST p rules can all be satisfied at once by some setting of the switches. p = 0 is always allowed, since the empty list demands nothing.

Problem 1725 answers whether the whole list is satisfiable, which is the case p = k. This asks how far down the list you can get.

## What most people try first

Counting the rules that are individually satisfiable. Every single rule is satisfiable on its own unless it names one switch twice with both signs, so that count is almost always k and almost always wrong.

The second attempt is to add rules one at a time, re-solving after each, and stop at the first failure. That is correct and costs k solves. With k = 50000 and each solve O(n + k), that is around 2 * 10^9 steps.

The third attempt is to add rules one at a time and keep the previous solution, patching it when a new rule breaks it. A satisfying setting is not extendable in general: the rules 1 1 then -1 2 then -2 -1 are satisfiable up to the second and not the third, and no patch of the second setting reaches a third one, because none exists.

## The prefixes are monotone, so the answer is a boundary

If the first p rules are satisfiable then so are the first p - 1, because a setting satisfying more rules satisfies fewer. So the sequence of answers is a run of satisfiable prefixes followed by a run of unsatisfiable ones, with no interleaving, and the answer is the position of the boundary. That is exactly the shape binary search needs.

Note which direction the monotonicity runs. Satisfiability is DOWNWARD closed in the prefix length, not upward, so the search keeps the largest known satisfiable length and moves up only when a probe succeeds.

> lo = 0, hi = k. While lo < hi: let mid = (lo + hi + 1) / 2 rounded > down; if the first mid rules are satisfiable set lo = mid, else set > hi = mid - 1. The answer is lo.

The + 1 in the midpoint matters. With lo = 0 and hi = 1, a plain midpoint gives mid = 0, the probe trivially succeeds, lo stays 0 and the loop never ends.

## Deciding one prefix

Build the implication graph of the first mid rules: a node for each of the 2n conditions, and for a rule a b an arc from NOT a to b and an arc from NOT b to a. The prefix is satisfiable exactly when no switch has both of its conditions in the same strongly connected component. If they were in the same component then each of i ON and i OFF would force the other, which no setting can do; and if they are never together, taking for each switch whichever condition's component comes later in a topological order gives a setting that satisfies every rule.

Rebuild the graph from scratch on every probe. There are about log2(k) probes, 17 at k = 50000, and each build is linear, so the total is O((n + k) log k).

``` n = 2, rules: 1 1 switch 1 ON -1 2 if 1 is ON then 2 is ON -2 -1 if 2 is ON then 1 is OFF

prefix 0: nothing to satisfy works prefix 1: switch 1 ON works prefix 2: switch 1 ON, switch 2 ON works prefix 3: switch 1 ON forces 2 ON forces 1 OFF fails answer: 2 ```

## The boundary that breaks a careless implementation

p = 0 happens only when k = 0. Every single rule is satisfiable on its own: i i is satisfied by switch i ON, -i -i by it OFF, and i -i by either, so a one-rule prefix never fails. The code must still be able to RETURN 0, since that is the k = 0 answer, so initialise lo to 0 rather than to 1.

Build both traversals of the component search with explicit stacks. At n = 20000 the graph has 40000 nodes and a chain can run through all of them.

## Cost

O((n + k) log k). At n = 20000 and k = 50000 that is about 17 passes over 70000 nodes and 100000 arcs.

## Overflow

p is at most k, so at most 50000. The midpoint (lo + hi + 1) is at most 100001, well inside a 32-bit integer.

Constraints - `1 ≤ n ≤ 20000` - `0 ≤ k ≤ 50000` - `1 ≤ abs(a) ≤ n` and `1 ≤ abs(b) ≤ n`, and neither `a` nor `b` is 0 - a rule may name the same switch twice, with the same sign or with opposite signs - the answer is `k` when the whole list is satisfiable, and `0` only when `k` is 0