Is 1266D (Decreasing Debts) hackable with repeated shrinking in random vertices order?

Правка en1, от z4120, 2019-12-23 16:26:40

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?

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

Теги hack

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский z4120 2019-12-24 16:57:21 121
en4 Английский z4120 2019-12-24 16:56:25 249 Tiny change: 's>day</s> hour left for ' -> 's>day</s> **hour** left for '
en3 Английский z4120 2019-12-24 04:52:05 115
en2 Английский z4120 2019-12-24 04:09:47 6 Remove invisible non-breaking spaces
en1 Английский z4120 2019-12-23 16:26:40 1640 Initial revision (published)