Editorial for Max's Anger Contest Series 1 P4 - Greedily Gamboling

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

It suffices to run Dijkstra's algorithm from $1$ ~1~ to $N$ ~N~.

Time Complexity: $\mathcal{O}(M \log(N))$ ~\mathcal{O}(M \log(N))~

Subtask 2

Realize that since toggles can only be used once, states of what toggles have been used can be represented with a bitmask.

Now, for each node and the current bitmask, consider all edges that connect this node and bitmask through all supersets of the current bitmask: if the current bit is on in the superset but not for the original bitmask and the current edge weight has that bit on, subtract it from the current weight. Once all bits are considered, push that node and new bitmask into the priority queue.

Finally, output the shortest distance from $1$ ~1~ to $N$ ~N~ using none, some, or all of the toggles.

Time Complexity: $\mathcal{O}(MK (4^K + 3^K \log(N 3^K)))$

Note that it is possible to achieve $\mathcal{O}(MK 3^K \log(N 3^K))$ ~\mathcal{O}(MK 3^K \log(N 3^K))~ by iterating only over the bitmasks that are supersets of the current bitmask without considering any extra masks.

Exercise

Consider how you could optimize the full solution to have a smaller power by reducing the base for the number of edges.

Implement and submit to this harder version with increased constraints on $K$ ~K~.

Comments

1

spheniscine commented on Jan. 3, 2023, 3:34 a.m.

Link to harder version just gives error "No such problem; Could not find a problem with the code "macs1p4hard"."

0

maxcruickshanks commented on Jan. 4, 2023, 6:38 p.m.

The problem has been published. I have been busy and just got around to buffing the data—apologies for the inconvenience.