Combi's blog

I need an algorithm to generate RANDOM graph for Shortest Path Problems but also want it to be STRONG enough.
By Combi, history, 3 years ago, In English

Hello, Codeforces!

Initially, I intended to just generate random graph with random weights but later have been warned that it may have FEW number of shortest Path and the contestants can random one of those shortest Path and solve the problems.

(Of course it cannot be allowed to pass all the test). So I wanna ask for some effective algorithm to generate test for this problems. Btw I do not know how tests for such problems are generated in the pass.

If you are interested, I will specify the problems:

Statement

There is a connected graph with $$$n$$$ vertices and $$$m$$$ edges ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$).

There are also $$$K (1 \leq K \leq 10)$$$ pairs of vertices $$$a_i$$$ and $$$b_i (1 \leq a_i, b_i \leq n)$$$ in which: - $$$a_i$$$ is the node which the $$$i-th$$$ person lives in. - $$$b_i$$$ is the node which the $$$i-th$$$ person's office located in.

Every morning, $$$i-th$$$ goes to work form home at 7AM along the shortest path connected $$$a_i$$$ and $$$b_i$$$. However, X (the first person) want to walk together with one of $$$K - 1$$$ other people during his path.

Two people are considered walking together on the edges form u to v, if: - both u and v are on the both shortest path that these 2 people walking on - the time at which 2 people reach u and v is the same.

Furthermore, some of these people (except X) agree to start walking later or sooner form home so that the time X walking together with at least one of other person is as large as possible.

The target of this problems is maximizing the amount oft time X walking with one of other people during his path form home to office.

INPUT:

  • The first line contains 3 integer $$$n, m, K (1 \leq n, m \leq 10^5, 1 \leq K \leq 10)$$$
  • The next m lines have the form of $$$u, v, c$$$ ($$$u$$$ and $$$v$$$ is the end of edge, $$$1 \leq c \leq 10^9$$$ is the time required to pass)
  • The next K lines have the form of $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$)

OUTPUT:

The largest amount of time in which X walk together with one of $$$K - 1$$$ other people.

Example:

INPUT:

7 8 4
2 1 2
2 4 2
4 3 2
4 5 1
1 5 3
1 7 3
5 6 2
7 6 8
1 4
0 3 2
1 7 6
0 1 2

OUTPUT:

3

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

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

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

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

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I once generate testcases for similar problems, here is how I do it (but not guarantee strong enough)

  • Step 0: Very make sure that your solution code is correct
  • Step 1: Make a graph that itself is an answer for the problem
  • Step 2: Cover the whole graph with the node that hard to be included in the answer
  • Step 3: If there is a better answer than expected I will try to cut some edges which is optimal but not an expected answer
  • Step 4: If do step 3 for about $$$k$$$ times and still not work, let redo the step 1
  • Step 5: Here we are the new test case ! Repeat step 1 until we have enough test cases
  • Step 6: Among those test cases, try to use a heuristic or greedy but wrong code, whichever code can pass the test, erase it from the set
  • Step 7: Retest if test cases are correct then use for the problem
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Firstly, thanks for your algorithm. Btw, do you still keep the code of this algorithm or store it somewhere? It is really helpful if I can read your code and see how to implement this algorithm.

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

      Sadly that laptop was broken, but still it eliminated half of the contestants in that problem I update tests

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

I think you can just generate the shortest-path tree firstly, then add some random edges (weight of the edge $$$(v, u)$$$ must be at least $$$|dist[v]-dist[u]|$$$; if you need a larger number shortest paths, you can set the weight to $$$|dist[v]-dist[u]|$$$).

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

    That makes sense but the graph will look a little weird, right?

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

      Each graph can be represented as a shortest-path tree and a set of edges $$$(v, u)$$$ with weight $$$\ge |dist[v]-dist[u]|$$$, but the probability of each graph may be different: the more shortest paths in the graph, the greater the probability. I don't think this is weird. Just a connected graph with $$$m$$$ edges is generated in a similar way.

      → Reply