Funcia
Lv.42-satbinary-searchgraphscc

The First Conflicting Request

Memory limit
256 MB
Correctness time limit
20000 ms
Solvers
0
0

There are n switches numbered 1..n, each on (true) or off (false). Requests arrive in the order of clauses; request [x, y] means "at least one of x, y must hold", where a positive v means "switch v is on" and a negative -v means "switch v is off". Both literals may name the same switch ([3, 3] forces switch 3 on; [2, -2] always holds).

Return the 0-based index of the first request after which no switch setting satisfies all requests so far, or -1 if all requests can be satisfied together.

Examples

nclausesresult
3[[1, 2], [-1, 3], [-2, -3], [-3, 1]]-1
2[[1, 1], [-1, 2], [-2, -1], [2, 2]]2
2[[1, 2], [-1, 2], [1, -2], [-1, -2]]3

Example 1 — on/off/on satisfies everything.

Example 2 — request 0 forces switch 1 on, request 1 then forces switch 2 on, and request 2 can no longer hold.

Example 3 — the first three hold with both switches on; all four together rule out every setting.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, clauses: int[][]) → int

Constraints

  • 1≤1 \le n ≤50,000\le 50{,}000
  • 1≤M=1 \le M = clauses.length ≤100,000\le 100{,}000
  • clauses[i] = [x, y], 1≤∣x∣,∣y∣≤1 \le |x|, |y| \le n (never 0)

Expected complexity

Time
O((N + M) log M)
Space
O(N + M)

Examples

nclausesExpected
3[[1,2],[-1,3],[-2,-3],[-3,1]]-1
2[[1,1],[-1,2],[-2,-1],[2,2]]2
2[[1,2],[-1,2],[1,-2],[-1,-2]]3

Hint

Hint

One check is 2-SAT: "a or b" becomes the implications not a -> b and not b -> a on a graph of 2n2n literals; the requests are satisfiable iff no switch has both literals in the same strongly connected component (O(n+M)O(n + M) with Tarjan or Kosaraju). Satisfiability of a prefix is monotone in its length, so binary search the first failing prefix with O(log⁡M)O(\log M) checks. Re-checking after every request is O(M(n+M))O(M(n + M)) and exceeds the time limit. DFS depth can reach 10510^5, so prefer an iterative DFS.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)364 msestimated
C++ (GCC, gnu++23)364 msderived
Python 3.136948 msderived
Java 252034 msderived
Kotlin 2.4 (JVM)1728 msestimated
C# 14 (.NET 10)1728 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.