Guys, i need help with this problem from a offline contest i participated ;(
Given an integer $$$k$$$ ($$$k\le10^{100}$$$) from input
Construct a directed graph that sastified all the following conditions:
at most 1 edge between any pair of nodes
the graph must have at most 500,000 nodes and 1,000,000 edges
graph must be acyclic (no cycle)
must be exactly k ($$$k\le10^{100}$$$) distinct paths from node 1 to the node with largest index (node n)
Thank yall!
Auto comment: topic has been updated by MieAi. (previous revision, new revision, compare).
Auto comment: topic has been updated by MieAi. (previous revision, new revision, compare).
Is it really possible to solve it with such a large k?
First, we can split k into power of 2s. Implementing division by 2 is not so hard so I will leave it to you.
Then we can notice that its not hard to create a graph that contains exactly 2^k path from 1 to n.
For example: Graph with 2 paths.
Graph with 4 paths
Then we can combine these graph together to form k.
Graph with 6 paths.
I don't have a exact maximum number of nodes / edges that this requires but it should be well under the limit
You could also use "split units" of 10 splits instead of 2 and then you wouldn't need any bignum library, could construct the answer digit by digit
Fits in around 90% of the limit by my math
Hi, do you think in the k=6 case, we can connect vertex 1 to 3, 4, 10, 11 directly instead of indirectly via 2 and 9? (If true, can this be expanded to general k)?
Let $$$G$$$ be a complete directed graph (for each $$$i \lt j$$$ there is an edge from $$$i$$$ to $$$j$$$) and let $$$f(i)$$$ be the number of paths to the $$$i$$$th vertex. By definition $$$f(0)$$$ is 1. We can observe the following: $$$f(1)=1$$$, $$$f(2)=2$$$, $$$f(3)=4$$$, ...
since the number of paths is just the sum over all predecessor (which by construction is every previous vertex) we can deduce that $$$f(i \gt 0)=\sum_{j=0}^{i-1}f(j)=2^i$$$.
With one additional vertex that is simply connected to the powers of 2 set in its binary representation we can solve the problem.
This will require at most $$$\lceil log_2(10^{100})\rceil+1=334$$$ vertices and at most $$$\binom{334}{2}=55611$$$
The construction is quite easy and i doubt that you can solve it with 2 vertices less (fewer edges is possible).
The problem is very similar to the problem "slides" from codejam 2016: https://zibada.guru/gcj/2016r1c/problems/#B
Unfortunately I think that you are off by 1. Your number of vertices(334) would be the index of the last vertex and you started with vertex 0 so there would be 335 vertices(see examples for a small k; for $$$k = 2^n$$$ we could use the last vertex of our complete graph as the last one, but if k is not a power of 2 we must add an additional vertex, so I believe that $$$\lceil log_2(k) \rceil+2$$$ is a valid formula).
We can also prove that this is most optimal in terms of vertices. If our DAG has n vertices, than WLOG 1, 2, 3, ..., n is a valid topological order, so it is a subgraph of a complete DAG. Thanks to this we know that each path in this graph exists in a complete graph. As you showed number of paths from 1 to n in a complete DAG is equal to $$$2^{n-2}$$$(except $$$n=1$$$ case). This proves that this construction is optimal(in terms of the number of vertices).
Unfortunately we can not decrease the number of edges with the same number of vertices(see $$$k = 2^n$$$ case).
I will suggest a solution with $$$O(log(k))$$$ nodes and $$$O(log(k))$$$ edges(it is optimal up to a constant factor). As Sammmmmmm has showed we can easily create a graph with $$$2^{\lfloor log_2(k)\rfloor}$$$ paths 1->last, we also create an additional node and connect this node to each power of 2 in the binary representation of k as in MZuenni's solution. Im sure it isn't the most optimal solution, because instead of "building fragments" like in Sammmmmmm's solution, we could use: 1->2, 1->3, 1->4, 2->3, 2->4, 3->4 ie. complete graph of 4 vertices(where we "stack" them on each other, just like in Sammmmmmm's solution).
If my math is correct with this solution for $$$k \leq 10^{\text{100 000}}$$$ we would have a bit less than 500 000 vertices and a bit less than 1 400 000 edges, and the constants are around this so ~ $$$ \lt 5 log_{10}(k)$$$ vertices and ~ $$$ \lt 14 log_{10}(k)$$$ edges. Considering that lower bound on the number of vertices is ~ $$$3.32 log_{10}(k)$$$, I think it's not bad.
You can split to powers of 2 (binary), make a section for each and make a root node that connects to all of them to add them.
How to make a power of 2? You put k pairs of pairs of nodes, and then between a pair and next pair you put 4 edges, so then you have 2^k options (which node of each pair to go through), done Also you can just skip the root if the graph doesnt have to be connected