pk842's blog

Help in a graph question from samsung online round
By pk842, history, 5 years ago, In English

P1 P2 P3 P4

As the round is over, the links are disabled by them.

I can only come up with a very basic brute force solution of $$$(2*N)!$$$ where for each of the order of visiting I calculate the cost and then update the answer accordingly. But as expected this even didn't pass even a single test.

Can someone please help me with some spoilers on how to proceed further with it?

Thanks!

Edit: Hello all! Why everyone is downvoting the post? Is there something wrong with it or I asked the question in a wrong way ? I find the problem difficult so I asked for help and if someone find it easy then instead of directly downvoting please explain the solution (or atleast a step towards it) and then downvote if you think it's irrelevant.

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

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pk842 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I think an algorithm for this can solve hamiltonian path problem. So I don't think that a polynomial time solution exists.

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

    News in 3 days: Samsung engineers solved P = NP

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

      Really it doesn't have any polynomial time solution?

      But there are people who solved it fully. Don't know..

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

        Probably it does have some polynomial time solution, since it is asking for the placement of starting location, and not actual length.

        → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

goes to all K cities one by one

if this means the cities should be visited in the order it is given in input then polynomial time algorithm does exist.

There are some inconsistencies in the statement, for example: the input description says there will be K integers in K lines, but sample gives all K integers in single line.

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

    Any hints towards solution?

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

      Find all pair shortest paths in $$$O(n^2\log n)$$$. Sum up distances between adjacent pair of nodes, and add minimum distance from a node of those $$$N-K$$$ nodes to first and last node of those $$$K$$$ nodes.

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

        how to distinguish the first and last node of $$$K$$$ nodes? Or did you mean to try all possible pairs.

        And also can you please explain "Sum up distances between adjacent pair of nodes" a little bit more?

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Off-topic : Were you eligible(exp.-wise) for interview or appeared in contest just for fun ? It was mentioned that this contest was for experienced candidates, so I didn't participate.

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

    I participated just for sake of practice.

    → Reply