1402 editorial
best problem on cbr (until sb takes your clues and solves faster than you)
Prepare for brain damage 😑
Editorial by aww (aka Tux and f0restf1re) and friends
1402
Yes it's a joke problem…
OR IS IT?
1402
Yes it's a joke problem…
OR IS IT?
1402 == crazy maths modelling == dropping important stuff into random garbage memes so every point is important == weird graph problem == ARGHHH FINALLY AC-ED THIS NONSENSE == something probably dreamt up by a lucid dream by the problem setter
Have fun!
1402 - problem analysissss🐍
Output only lol
1402 - problem analysissss🐍
Time to make observations!
1402 - problem analysissss🐍
Time to make observations!
1402 - problem analysissss🐍
Time to make observations!
Graph with N nodes
1402 - problem analysissss🐍
Time to make observations!
Graph with N nodes
Find Hamiltonian cycle (visit every node exactly once)
1402 - problem analysissss🐍
There are M edges
Find lowest-cost Hamiltonian cycle
Observations…
1402 - problem analysissss🐍
Observations…
1402 - problem analysissss🐍
Fully-connected graph
Observations…
1402 - problem analysissss🐍
Fully-connected graph
Observations…
use WolframAlpha…
1402 - problem analysissss🐍
Fully-connected graph
Observations…
lol k=3, t=5
1402 - problem analysissss🐍
Fully-connected graph
Observations…
lol k=3, t=5 (wolframalpha op)
1402 - problem analysissss🐍
Fully-connected graph
Observations…
1402 - problem analysissss🐍
Observations…
Fully-connected graph
Each building is connected to up to 3 roads
Ie the degree of each node is at most 3
1402 - problem analysissss🐍
Fully-connected graph
Observations…
WTF
1402 - problem analysissss🐍
Fully-connected graph
Observations…
lol
1402 - problem analysissss🐍
Fully-connected graph
Observat
lol
This is bullshit
1402 - problem analysissss🐍
Observations…
It is impossible to select 3 edges to remove while still ensuring the existence of an Hamiltonian cycle.
BUT YOU CAN REMOVE 2 EDGES. �This also means an Hamiltonian path exists to begin with (duh)�This is important since almost every node has degree 2 (obviously can’t be 0 or graph isn’t connected)
1402 - problem analysissss🐍
Observations…
look people it's a joke problem for a reason
1402 - problem analysissss🐍
look people it's a joke problem for a reason
Remember to record them 🔴
We blanked out all the parts that u can get a fren to read aloud for fun while they try to find the actual points ;))
1402 - problem analysissss🐍
look people it's a joke problem for a reason
Fun fact: this sentence killed even God's English-parsing machinery
Basically: 1. there are exactly two roads that connect two odd-degree nodes and�2. there are M couples on those two roads
1402 - problem analysissss🐍
If we told you how to get this part, it wouldn’t be fun.
<2 have fun
Observations…
1402 - problem analysissss🐍
If we told you how to get this part, it wouldn’t be fun.
<2 have fun
Observations…
1402 - putting it together
Recall the mathematical definition of a graph: a graph G consists of a set of vertices V and a set of edges E.
Observations…
1402 - putting it together
Recall the mathematical definition of a graph: a graph G consists of a set of vertices V and a set of edges E. We want to find a cycle that goes through every single node at exactly once. How about the edges?
Observations…
1402 - putting it together
Recall the mathematical definition of a graph: a graph G consists of a set of vertices V and a set of edges E. We want to find a cycle that goes through every single node at exactly once. How about the edges?
Observations…
1402 - putting it together
Recall the mathematical definition of a graph: a graph G consists of a set of vertices V and a set of edges E. We want to find a cycle that goes through every single node at exactly once. How about the edges? We want to find a subset of E of cardinality equal to that of V.
Observations…
1402 - putting it together
In this subset of the original graph, every node has a degree of 2, because every node is connected to exactly two other edges.
Observations…
1402 - putting it together
In this subset of the original graph, every node has a degree of 2, because every node is connected to exactly two other edges. Therefore, we must add new edges to fulfil the third condition. But where?
Observations…
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
Notice what happens when we add a single edge between any two nodes:
2
2
2
2
2
2
2
2
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
Notice what happens when we add a single edge between any two nodes:
The sum of all degrees increases by 2. QED.
2
3
2
3
2
2
2
2
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
For more rigour, we will prove the this property by induction.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
Consider our base-case, a graph with N nodes and 0 edges. The degree of every node is 0; there is therefore an even number of odd-degree nodes. Now suppose the graph has E edges for some E≥0, such that there are an even number of odd degree nodes.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities:
1. One node has even degree, one node has odd degree. After adding the new edge, the first node has odd degree, second has even degree. Number of odd-degree nodes remains the same.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities:
2. Both nodes have even degree. After adding the new edge, both nodes with have an odd degree. Total number of nodes with odd degree increases by 2.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities:
3. Both nodes have odd degree. After adding the new edge, both nodes with have an even degree. Total number of nodes with odd degree decreases by 2.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities: notice that in all three cases, the number of odd-degree nodes increases by -2, 0, or 2.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities: notice that in all three cases, the number of odd-degree nodes increases by -2, 0, or 2.
Therefore, if a graph with E edges has x odd-degree nodes, a graph with E+1 edges has either x+2, x, or x-2 odd-degree nodes; if x is even, then x+2, x, and x-2 are all even.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities: notice that in all three cases, the number of odd-degree nodes increases by -2, 0, or 2.
Therefore, if a graph with E edges has x odd-degree nodes, a graph with E+1 edges has either x+2, x, or x-2 odd-degree nodes; if x is even, then x+2, x, and x-2 are all even.
By the principle of mathematical induction, the number of nodes with an odd degree in a graph must be even, given the above observation and the aforementioned base-case. Q.E.D.
1402 - Maths. Proofs.
LEMMA (with thanks to ZX). The number of nodes with an odd degree in a graph must be even.
We will now consider the act of adding one edge. There are three possibilities: notice that in all three cases, the number of odd-degree nodes increases by -2, 0, or 2.
Therefore, if a graph with E edges has x odd-degree nodes, a graph with E+1 edges has either x+2, x, or x-2 odd-degree nodes; if x is even, then x+2, x, and x-2 are all even.
By the principle of mathematical induction, the number of nodes with an odd degree in a graph must be even, given the above observation and the aforementioned base-case. Q.E.D.
fun fact ZX just mentioned this as something "obvious" (to be fair it kinda is) but I wanted to prove it for fun�"Just prove by contradiction lol" –ZX
1402 - putting it together
By the lemma we've just proven, there must be exactly 4 nodes with an odd degree.
Observations…
1402 - putting it together
By the lemma, there must be exactly 4 nodes with an odd degree.�In fact, they must have degree 3. If there is a degree 1 node, then it’s impossible to remove 2 edges and still have an Hamiltonian circuit. Also, the 4 nodes must all be separated! �Because there are exactly 2 roads between nodes that both have odd degree.
That means:
Observations…
1402 - putting it together
Given this graph, which edges can we remove such that there is still an Hamiltonian cycle?
Observations…
1402 - putting it together
Given this graph, which edges can we remove such that there is still an Hamiltonian cycle?
…obviously it's just the two we've just added. �It is clear that we cannot use these edges in our final answer because using them will skip at least one node and wabbit won’t be able to visit all the nodes
Observations…
1402 - putting it together
There is one final observation that we've mentioned but forgot to note down oops�It's that the number of couples on the two red edges is M. Recall:
Observations…
1402 - putting it together
There is one final observation that we've mentioned but forgot to note down oops�It's that the number of couples on the two red edges is M.
Wait what’s M again… oh wait yeah
Observations…
1402 - putting it together
There is one final observation that we've mentioned but forgot to note down oops�It's that the number of couples on the two red edges is M.
We know that M = N + 2 :DDD, therefore the answer is 10N-(N+2).
Observations…
Sssample code:
So the answer is…
(courtesy of vix the f0restf1re)
Sssample code:
So the answer is…
(courtesy of vix the f0restf1re)
Tada!!!!!!!!!!!!!!!!!!!!!!! Betcha never saw that coming! Now go AC 1402
disclaimer f0restf1re made this