tom's blog

By tom, 9 years ago, In English

Hello,

I'm struggling with following problem: We have n < 37 cities and m < n * (n - 1) / 2 undirected roads between them. Every city has a treasure in it with g[i] gold. Our robbers wants to get from city 0 to city n - 1 and take as much gold as they can with them.

To do this, they can (or not) rob every city they visit. They're hurry, so they can visit only cities that land on the shortest path from city 0 to n - 1 (if there are more than one shortest path, they can choose freely).

But there is a catch — they also need to go back from city n - 1 to 0 (now, they can move as they want), but! they cannot visit any city they robbed twice (dwellers will wait for them).

How much gold can they rob on they way to city n - 1?

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

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Should they follow a shortest path and do they rob the cities on their way-back?

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    They don't need to follow shortest path on their way home and they cannot rob anything. I updated the statement.

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

      Then can't you generate all paths between 0 and n-1 and choose each two non-intersecting paths? I'm not sure about the complexity but the constraints are very little.

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm getting TLE. My solution: http://ideone.com/8VYi2L

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

          Okay, try to do this:

          1) Present the graph by matrix of adjacency.

          2) Find the length of the shortest path from 0 to n-1.

          3) Generate all paths from 0 to N-1 with that length;

          4) For each path remove the edges that come from the used nodes(except 0 and n-1) Then run DFS/BFS from n-1 If you can reach 0 this is a correct path, find the amount of gold if you follow it and actualize the answer. Then restore the removed edges.

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

            I think that's what I did above. Attention: In original statement (and in my code) vertexes are 1-indexed, starting vertex has a number 1 and ending has a number 2

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

              Oh, I'm sorry, I started writing the comment before you put your code here. Hope someone will explain a faster solution.

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

Please, provide a link to the problem at an online judge.

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

    It's on the internal site of my University.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      OK.

      I have breafly read your code and think that it can consider one way multiple times.

      For instance, on this input your code has been working for a long time while there is only 211 ways from 0 to 1.

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think this was from NAIPC 2014. http://serjudging.vanb.org/wp-content/uploads/NAIPC-2014-Problems.pdf (Problem F)

Here's how to do it. First you can generate all shortest paths, since there will be at most 2^(n/2) of them, which is 2^18, which should run in time. Now, let's say you take gold from every city. Then, now, you want to find the shortest path from node n-1 to node 0, where if we travel on a node, and it is part of the shortest path, we will remove it from our total cost. Here is a sample solution: http://serjudging.vanb.org/wp-content/uploads/Gold_Calvin.java

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

    I want to add that original testcases are weak — this problemset was also used for Opencup — GP of America, and as i already mentioned in russian discussion of that GP, my AC solution from a contest uses almost naive backtrack, and it wasn't able to solve one of my custom tests even in 45 minutes :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      hahahahahahahahahahahahahahahhahahahaha

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

      Can you send me this custom test? I want to see if it breaks other backtracking solutions. I was sad to see backtracking pass when the intended solution was more beautiful.

      It was also sad to see a few greedy solutions pass on this problem in contest. :(

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

    not :>>

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

      Why?

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

        Because , that's why :P

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

          Why 3n / 3. Where did you get that number from?

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 3   Vote: I like it +13 Vote: I do not like it

            Split graph into N / 3 buckets. Then add 3 edges from each node. This edges will go to next bucket's 3 nodes. If each edge have equal weight then number of shortest paths equals 3N / 3 and shortest path length is N / 3.

            I guess if we split graph into N / e parts we can get more shortest paths :)

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            You can bound the run-time using dynamic programming. The maximum number of paths in a level graph is equal to the maximum product of positive integers that sum to the number of nodes. We assume that between each layer is fully connected. A path simply chooses one node for each layer.

            Write the dp for N=36 and you will see it is not very big. (Do a trace back to find the exact composition)

            The intended solution was to find all possible shortest paths and then use O(V^2) Dijkstra's to payback the cost. A rough estimate of this bound is O(2^(N/2)*V^2) but it is not exact.

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

              not , I said :(!

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

              No need for the DP. You obviously don't want a layer with 1 node, it's better to add that 1 node to another layer. You don't want any layer with 4 or more nodes, because you can always split a layer with k>=4 nodes into a layer with 2 and a layer with k-2 nodes and the number of paths doesn't decrease. And you want at most two layers with 2 nodes because 2 layers with 3 nodes each are better than 3 layers with 2 nodes each (3*3=9 and 2*2*2=8 which is less). This uniquely determines the multiset of layer sizes.

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

My friend JohnPaulII told me this problem recently. I told him one solution I came up with (some kind of backtrack), but he insisted that this will receive TLE, so we made a bet. We agreed that I can have at most 2 TLEs before getting AC to win a bet. I coded one solution and sent it to him. Then I went sleep and when I woke up I realized that in fact my solution is pretty slow and thought that I should tell him that he shouldn't sent my solution, because that will get TLE. But he has sent it before I told him not to do so and it got AC :P. In fact original testcases must have been pretty weak.

Here is my code, simple backtrack: http://ideone.com/sHRqqQ

I know that this is pretty easy to create testcase so that this will TLE, but I remember that there was an optimization such that I didn't know bad testcase for it, but also I didn't know proof why it is running quickly (and don't remember this optimization now, but it was pretty natural).