Alternative approach to CF #718 H — Hack me please!

Revision en1, by ecnerwala, 2021-04-24 21:54:04

I had a different approach to H that results in very short, but incorrect code (114044595, 114044982). I also have a few versions which I don't know how to hack (114142853, 114141339, 114141392). Can anyone hack these or prove they're correct?

The main idea is to use strong LP duality: the problem is unsatisfiable if and only if there is some linear combination of the input constraints such that all variables cancel and the constants give a contradiction (e.g. $$$0 \le -1$$$). We can try to simplify this by only checking all "extremal" feasible linear combinations, i.e. linear combinations on the convex hull of all linear combinations whose variables completely cancel.

Here, I came up with the (false) hypothesis that any such extremal linear combination must include 2 "neighboring" constraints which we can treat as a relaxation, e.g. we use both $$$y_{i-1}^+$$$ and $$$z_{i}^+$$$; these can be "merged" into a (possibly tighter) constraint on $$$y_{i}^+$$$ which we will use instead. This is not quite true, and the counterexample can be seen in https://codeforces.com/contest/1517/hacks/731593/test.

Assuming this hypothesis, I made another assumption that, similar to out-of-order Floyd-Warshall, we may be able to simply do all relaxations and loop up to either $$$O(1)$$$ or $$$O(\log n)$$$ times in order to find the cycle. I don't have a proof, but it feels plausible (after the $$$k$$$th iteration, our relaxations must include all paths with at most $$$2^k$$$ zig-zags or something?).

Now, you might've noticed that 114044982 fails with TLE instead of WA; if it were allowed to run for long enough, it would actually print the correct answer. This is because my hypothesis is false for extremal linear combinations, but I think it's true that there must be some negative linear combination which can be attained via these relaxations. This is because we can take the extremal negative cycle, multiply it by a large number, and add any positive cycle including the desired neighbors. Thus, it seems like my code is guaranteed to finish in $$$O(N * MAXVALUE)$$$ or so.

Now for the challenge: I now have a new hypothesis: if, after running for some number of iterations, the relaxations have not stabilized, then there must be a negative cycle and we can just print "NO". That's the basis for my 3 new submissions: 114142853 (60 loops), 114141339 (1000 loops), 114141392 ($$$N$$$ loops). Can anyone hack these or prove them correct?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ecnerwala 2021-04-24 21:54:04 2631 Initial revision (published)