interestingproblem's blog

Very interesting graph theory problem
By interestingproblem, history, 20 months ago, translation, In English

Hello, codeforces!

Recently I came across a very interesting problem (and unfortunately I couldn't come up with an optimal solution): You are given an undirected graph with N <= 10^5 vertices and M <= 2*10^5 edges. Each edge has a color c_i <= 10^6. You need to find the minimum cost of the path from vertex 1 to vertex N, and the cost of the path is calculated as follows: the colors of the edges in the path are written in turn, and then the number of subsegments with the same colors is counted. Example: N=4, M=4, edges: 1<->2 with color 1, 2<->3 with color 2, 3<->4 with color 1, edge 1<->3 with color 1.

If we go the way 1->2->3->4, then the final price will be 2, because we will write out the colors of the edges: 1,2,1,1, and there will be 3 subsegments where the colors are the same: [1; 1], [2; 2], [3; 4]. But if we go the way 1->3->4, then the price will be 1, because all edges in the path have color 1.

Please help me with this problem and thanks in advance!

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

»
20 months ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

This is a constructive graph problem.

In this problem, we want to walk through the path switching colors as few times as possible.

So we set the value of all edges to $$$0$$$. create a staging point of value $$$0$$$ for edges of the same color, and a staging point of value $$$1$$$ for edges of a different color.

Then the shortest path $$$-1$$$ is the answer.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    For the example in blog, your solution will give answer 3, won't it?

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 6   Vote: I like it +18 Vote: I do not like it

      Sorry, I didn't take into account the incoming edge at the start and end, the answer should have been -1, I've amended it.

      example graph

      It seems that there are still many holes in my thinking and I thank the blogger for asking such a good question. The corrected formula should be x/2. (Why my reply looks so much like chatGPD)

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        That's ok! However, I think this is still a little bit incorrect. Actually, the value shortest_path should be divided by two. This is because we are entering and leaving every group of colors exactly two times, therefore we calculate it two times in our answer. Thanks a lot for such a cool idea!

        → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide the link for this problem please?

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

    I came up with statement on my own. I tried to search it on the web, but didn't find any similar problem.

    → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    It's probably ARC061E I think. The constraints for $$$n$$$, $$$m$$$ and $$$c_i$$$ is the same too.

    → Reply