Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

minimario's blog

By minimario, history, 8 years ago, In English

Hi Guys!

I'm back, with another problem! Link! I have tried to debug for 3 days now to no avail :'( ... so I'd be a really happy if some of you could help :D

Anyways, on to the algo:

I first toposorted the data, and maintained 2 DPs:

dp[i][0] = minimum length to make all paths from topo[i] to topo[n] the same length without any tolls (on any path)
dp[i][1] = minimum length to make all paths from topo[i] to topo[n] the same length with at most 1 toll (on some path)

So the transition seems something like this:

dp[i][0] = dp[j][0] if all the d(i, j) + dp[j][0] are the same (j is a child of i)
dp[i][0] = MAX otherwise (impossible)

Now, for dp[i][1], let's consider j's that are children of i. For some j, if dp[j][0] is not MAX (it's possible to do), then let's add (dp[j][0], 0) to a vector. Otherwise, if dp[j][1] is not MAX, let's add (dp[j][1], 1). Now, let's sort the vector and find the maximum dp value. This represents the final length of the road. But for the other values, if the dp value is less than the final length and it came from a dp[some][1], then we stop, and dp[i][1] = INF. Else, dp[i][1] = the max dp value.

I have the code here, but it's wrong:

Code

I am aware that if there is a solution, the overall price for each path will be the longest path from start to end in the graph. I used this to try to debug, but it didn't help.

I have some test cases here, but the ones that fail are really big. (Also, I just completely ignored the "printing fares" part, because my calculation of the final path length is incorrect for many cases)

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the tests that you have are all correct? and where is the correct output? I've tried to solve the problem with another way and got another WA, but your provided output matched with mine, so I'm curious to know what is the bug :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I.1 is the input, O.1 is the output. And if you could try to describe the method when you get AC, that'd be great!

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is O.1 is your output or is the correct output from some correct solution for the l.1 input?

      Yes, sure I will post the correct method when I get AC!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OK, now that I got AC, I can comment :)

Let nodes of type A be the nodes X for which the route 1 -> X has a constant distance, no matter which path you take. Similarly, let nodes of type B be the nodes X for which the route X -> N has a constant distance, no matter which path you take.

Clearly, all nodes must be either be of type A or type B, or the answer is No solution (you can't fix both 1->X and X->N paths with a single toll). This condition also turns out to be sufficient -- if all nodes of either type A or type B, you can fix all distances by tolling every A->B road. Can you finish the solution now?