From d37f1fc5632c9365968c082e22b94e05f484ede6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Adri=C3=A1n=20Oliva?= Date: Mon, 24 Apr 2023 20:28:04 -0600 Subject: New blog! Still needs HEAVY review. It currently doesn't have images nor code. Also needs grammar review. --- _posts/2023-04-21-twisty-little-passages.md | 103 ++++++++++++++++++++++++++++ 1 file changed, 103 insertions(+) create mode 100644 _posts/2023-04-21-twisty-little-passages.md (limited to '_posts') diff --git a/_posts/2023-04-21-twisty-little-passages.md b/_posts/2023-04-21-twisty-little-passages.md new file mode 100644 index 0000000..aa7696e --- /dev/null +++ b/_posts/2023-04-21-twisty-little-passages.md @@ -0,0 +1,103 @@ +--- +title: Twisty Little Passages +categories: [Technical Logs, Individual] +tags: [] +math: true +--- + +> This page is still in WIP. A lot of information is missing or not reviewed. +{: .prompt-danger } + +--- + +Try this problem by yourself first! Check the [Code Jam Page](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a45fc0#analysis). + +## Overview + +We are in a cave system with rooms and passages that connects them. Our task is to estimate the number of passages this cave system has, but we have a lot of drawbacks: + +- You can see what room you're in and how many passages it has, but cannot distinguish the passages. If you walk through one, it is chosen at random. +- You're only allowed to do up to $K$ operations: + - Teleport to any room you want. + - Walk through a random passage. +- The total number of rooms ($N$) can (and most probably will) be much larger than $K$. + +How can we estimate the number of passages in these conditions? With the most simple and naive approach we could think of: + +1. Teleport to a random subset of rooms. +1. Calculate the average number of passages for each room. +1. Multiply the average with the total number of rooms and divide by 2. + +And that's how we could find our estimate. Although there would be cases were this fails, those cases are a bit extreme and will be explained in more detail in the [alternative solutions](#alternative-solutions) section. + +For now, we will trust in the testing tool that the Code Jam problem page gives us. It says our solution gets the correct estimate 100% of the times. And that's a lot! + +
+
O     O     O
+
o o o
+
...
+
+ +## Context + +A cave system is generated at random. There are $N$ rooms and they are connected through passages. No passage goes from a room to itself, and no two rooms are connected by more than one passage. We can identify each room and see how many passages it has, but we cannot distinguish them apart. Our task is to estimate the number of passages the cave system has by doing up to $K$ operations. An operation can be: + +- Teleport to a specified room. +- Walk through a random passage. + +If $E$ is our estimate and $P$ the actual number of passages in the cave system, our estimate is considered correct if and only if $P \left( \frac{2}{3} \right) \leq E \leq P \left( \frac{4}{3} \right)$. To successfully pass a test set, at least 90% of the solutions must be correct. + +The problem gives us the following restrains: $2 \leq N \leq 10^5$ and $K = 8\,000$. In this sense, we cannot just teleport to every room, since $N$ may be much larger than $K$. What we can do is teleport to a random subset of the rooms and record how many passages each room has. We can even calculate the average number of passages for each room and extrapolate it to all the rooms. That could give us a pretty good estimate.[^1] + +
+
O     O     O
+
o o o
+
...
+
+ +## Solution + +As described in the [context section](#context), we will compute the average number of passages for a subset of the rooms. Let's describe the algorithm. + +1. Read $N, K$ from input. +1. Initialize `seen_passages` as an empty list and `rooms_not_seen` as a list of integers from 1 to $N$. +1. We start in a random room. Read $R_0, P_0$ from input, the room we're currently in and its number of passages, respectively. +1. Remove $R_0$ from `rooms_not_seen` and append $P_0$ to `seen_passages`. +1. Repeat for $i \in \\{ 1, 2, \ldots, K \\}$: + 1. Select a random room from `rooms_not_seen` and teleport to it. + 1. Read $R_i, P_i$ from input. + 1. Remove $R_i$ from `rooms_not_seen` and append $P_i$ to `seen_passages`. +1. Compute the average number of passages for a single room: + + $$ + \begin{eqnarray} + & \text{average} = \frac{\text{sum of }\texttt{seen_passages}}{\text{size of }\texttt{seen_passages}} . + \end{eqnarray} + $$ +1. Multiply the average of passages with the total number of rooms. Divide the result by 2, because we're counting each passage twice. That's our estimate! :D + + $$ + \begin{eqnarray} + & \text{result} = \frac{(\text{average}) \cdot N}{2} . + \end{eqnarray} + $$ + +
+
O     O     O
+
o o o
+
...
+
+ +## Alternative Solutions + +We have another more sophisticated solution. Instead of just teleporting to random rooms, we alternate the teleportation and walking through a random passage. The rooms seen after teleportation are selected uniformly between all rooms, but the ones seen after walking are not. If you're in a room and walk through a passage, there may be rooms that we could never reach through a single passage. + +What we can do is to use the ones seen after teleporting to calculate the average number of passages. We apply the average to the rooms not seen yet and then we add the passages already seen to the result. We finally divide by two and that would be our estimate. + +The biggest advantage of this alternate solution over the main solution is that if there's a case were a few rooms have tons of passages and the rest just barely have passages, this solution would work and the main wouldn't. It'd be easier to find those hyper-connected rooms by randomly walking through a passage from a barely connected room, than teleporting to that room by chance. That'd be a better solution, but unfortunately time is ticking. :'c + +--- + +## Footnotes + +[^1]: If we assume that the passages are distributed uniformly. Otherwise, the solution may not work. -- cgit v1.2.3