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
Auto comment: topic has been updated by Combi (previous revision, new revision, compare).
Auto comment: topic has been updated by Combi (previous revision, new revision, compare).
I once generate testcases for similar problems, here is how I do it (but not guarantee strong enough)
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.
Sadly that laptop was broken, but still it eliminated half of the contestants in that problem I update tests
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]|$$$).
That makes sense but the graph will look a little weird, right?
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.