Can the algorithm

Revision en4, by z4120, 2019-12-24 16:56:25

Consider a harder variation of Codeforces Global Round 6 — Decreasing Debts (1266D) where the first way to consolidate is changed to: (_first suggested in this comment_)

Let $$$d(a,b) > 0$$$ and $$$d(b,d) > 0$$$ such that $$$a \neq b$$$ or $$$b \neq d$$$. We can decrease the $$$d(a,b)$$$ and $$$d(b,d)$$$ by $$$z$$$ and increase $$$d(a,d)$$$ by $$$z$$$, where $$$0 < z \leq \min(d(a,b),d(b,d))$$$.

(replace $$$c$$$ with $$$b$$$)

It can be proven that any valid submission to this problem is also a valid submission to the easier problem, however the reversion is not true. It appears that some people wrongly assumes that the problem is this harder variation and try to solve it with a "repeated shrinking" algorithm:

  • Loop through the vertices in some order.
  • For each vertex, rewrite all the edges adjacent to that vertex such that it's in-degree or out-degree is 0.

If the order is fixed, then it's possible to hack (sansen's hack looks like this, which works with the order 1, 2, ..., n:  )

There are some other possible orders, see hacked submissions for details. (if you submitted some code which uses the shrinking algorithm described here, consider leaving a comment so people can try hacking it)

However, if the order is random shuffled (like in this submission), is it possible to hack the submission? If it isn't possible, then can you prove that the expected number of touched edges is $$$O(n)$$$? (Or $$$O(n log n)$$$)

(There's only one day hour left for uphacking! Please be quick.)

Tags hack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English z4120 2019-12-24 16:57:21 121
en4 English z4120 2019-12-24 16:56:25 249 Tiny change: 's>day</s> hour left for ' -> 's>day</s> **hour** left for '
en3 English z4120 2019-12-24 04:52:05 115
en2 English z4120 2019-12-24 04:09:47 6 Remove invisible non-breaking spaces
en1 English z4120 2019-12-23 16:26:40 1640 Initial revision (published)