BIO 2025

Fast food

In the question we are given the number of houses $N$ and $N-1$ pairs that show the connections between houses. To read a file like 

    7
    1 2
    2 3
    1 4
    1 5
    5 6
    5 7

we can write the following simple program: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>  // std::cout, std::endl, std::cerr
#include <fstream>  // std::ifstream

int main() {
    std::ifstream file("pairs.txt");
    if (!file) {
        std::cerr << "Error: Could not open the file!" << std::endl;
        return 1;
    }

    int N;
    if (!(file >> N)) {
        std::cerr << "First line should have a single integer." << std::endl;
        return 1;
    }

    std::vector<std::vector<int>> pairs;
    int i, j;
    while (file >> i >> j) {
        pairs.push_back({ i, j });
    }
	
    return 0;
}

In line 5 we open a file called pairs.txt; lines 6-9 make sure that this file exists in the root directory of our project. Line 11 declares $N$ and lines 12-15 check whether a single number is contained in the first line. Note that if, somehow, we typed 7.5 instead of 7, $N$ would be still set to 7; unfortunately the remaining part (.5) will still be in the stream. So in line 19, when the program is looking for two integers, the stream will return this remainder and the while loop will abort. If everything goes as planned, the program will keep reading pairs of integers which are used to populate the vector of vectors pairs (we could have created a vector of pairs instead but lets keep things simple).

A very useful quantity is, what is called in graph theory, the adjacency matrix. This is a $N \times N$ matrix that, in for each house, lists, using ones and zeros, the other houses connected to it. Here we modify it by instead creating a vector of sets that lists the houses connected to house $1,\ldots,N$. The code used to do this is shown below: 

1
2
3
4
5
6
7
void buildLinks(const int N, const std::vector<std::vector<int>>& pairs,
    std::vector<std::set<int>>& links) {
    for (const auto& p : pairs) {
        links[p[0] - 1].insert(p[1]);
        links[p[1] - 1].insert(p[0]);
    }
}

Since if house $i$ is connected to house $j$ then house $j$ is also connected to house $i$ (our problem uses an undirected graph) the code uses each pair $(i,j)$ to populate the set of links for both houses (lines 4,5).

Before attempting to find a solution we may want to consider whether it exists. In the beginning, the recipe is always known at houses $1$ and $N$. We are given $N-1$ unique connections. Lets assume that two of the houses $i$, $j$ are only connected to each other ($1<i,j<N$). We are now left with $N-2$ houses; we know that $$ \begin{array}{cc} \text{House $1$ can generate} & \text{$N-3$ new connections,} \\ \text{House $2$ can generate} & \text{$N-4$ new connections,} \\ \ldots & \ldots \\ \text{House $N-3$ can generate} & \text{$1$ new connection.} \end{array} $$ Hence we can generate up to $$ 1 + 2 + \ldots + (N-4) + (N-3) = \frac{(N-2)(N-3)}{2} $$ additional unique connections. Since for $N>5$ \begin{align*} N & > 5 \\ N-3 & > 2 \\ \frac{N-3}{2} & > 1 \\ \frac{(N-2)(N-3)}{2} & > N-2 \\ \frac{(N-2)(N-3)}{2} + 1& > N-1 \end{align*} we can always generate $N-1$ connections where two of the houses are isolated. Note that for $N ≤ 5$ it is impossible to generate two isolated houses. This is obvious for $N=2,3$; for $N=4$ we can try to isolate houses 2 and 3. We then set a single connection between houses 1 and 4; we still need to set one additional connection and this has to be between one of houses 1, 4 and one of houses 2, 3 hence contradicting our assumption that these are isolated. For $N=5$, if we isolate houses 2 and 3 and add a (redundant) connection between houses 1 and 7 we have two more connections left. So we can connect 1 (or 7) with 4 but we still cannot avoid connecting 1 or 4 or 7 with either 2 or 3. One way to avoid running the algorithm when no solution exists is to write the following piece of code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
bool solutionExists(std::vector<std::set<int>> &links, std::set<int> &bag) { // at start bag={1,N}
    int size = bag.size();
    // update bag with links
    for (const auto& e : bag) {
        if (links[e - 1].size() == 0) 
            continue;
        else {
            for (const auto& l : links[e - 1]) 
                bag.insert(l);
        }
    }

    if (bag.size() == size)
        return false; 
    else if (bag.size() == links.size())
        return true; 
    else
        solutionExists(links, bag);
}

The algorithm is very simple: we start with a set (called bag) that only contains houses $1$ and $N$. The nice thing about a set in C++ is that we can throw all sorts of new elements in it but the insert method makes sure they are only added if they differ from all existing members. In lines 4-11 we start with the links for houses $1$ and $N$. If these new houses are different from $1,N$ they are added to the bag. So, using the example given, we start with $\def\txt#1{\style{font-family: Consolas;}{\text{#1}}}\txt{bag}=\{1,7\}$ and after the for loop we have $\txt{bag}=\{1,2,4,5,7\}$. In line 13 we check whether we have made any progress. If, somehow, the size of the bag has not increased then a solution does not exist since houses $1$, $N$ only talk to each other. If (line 15) the size of the bag is equal to $N$ it means that houses $1$, $N$ are connected to all other houses and a solution exists. If neither condition holds we go to line 18 and keep trying.

At this point we can consider how we can arrive at a solution. The links vector of sets allows us to start transmitting information from houses $1$, $N$ to one or more houses. In our example, we have

with common points highlighted in pink. The problem states that house $1$ cannot transmit information to more than one house and that houses $1$ and $7$ cannot transmit information to the same house. We can try to satisfy these constraints by approaching this problem using a modified Cartesian product. One of the great benefits of looking at Python documentation is that it contains very good expositions of how functions work. The itertools function product starts with two or more arrays; in our example there are two arrays, $\{2,4,5\}$ and $\{5\}$ the new houses that can be connected by house $1$ and $7$. If we wrote product('245','5') we would obtain ('2', '5'), ('4', '5'), ('5', '5'). The last pair conflicts with the rules so we can assume that it collapses to ('5'), i.e. house $1$ passes the information to house $5$ while house $7$ does nothing. It is clear that this is a suboptimal decision but we want to keep the code as simple as possible. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
std::set<std::set<int>> cartesianProduct(const std::vector<std::set<int>>& links, const std::set<int> &bag) {
    std::vector<std::set<int>> pools;

    for (const auto& e : bag) {
        std::set<int> diff;
        set_difference(links[e - 1].begin(), links[e - 1].end(), 
                                    bag.begin(), bag.end(), std::inserter(diff, diff.begin()));
        if (diff.size() > 0) {
            pools.push_back(diff);
        }
    } 

    std::set<std::set<int>> result;

    for (const auto& item : pools[0]) {
        result.insert({ item });
    }

    for(size_t i = 1; i < pools.size(); ++i) {
        std::set<std::set<int>> newResult;
        const auto& pool = pools[i];

        for (const auto& res : result) {
            for (const auto& item : pool) {
                auto newSet = res;
                newSet.insert(item);
                newResult.insert(std::move(newSet));
            }
        }
        result = std::move(newResult);
    }

    return result;
}

The code for doing this is shown above; it is an adaptation of the logic of itertools.product. We start with a bag that contains all informed houses. We want to look at the links for each of these houses and see whether they are connected to any houses which are still in the dark. Lines 4-11 accomplish this by using set_difference from the algorithm header (if we are not pressed for time it is fairly easy to write one). It generates the difference between two sets by using two iterators. As we can see in line 6, we use the iterator links[e-1] of links for house e in the bag and the iterator for the bag to obtain a new set diff that contains any elements not shared. The inserter function (as the name suggests) places the result at the beginning of the iterator (std::inserter(diff, diff.begin())). The result is a set of new possible connections for each house in the bag that we store in a vector of sets called pools.

Lines 13-31 are a rewrite of the Python code for itertools.product in C++. At line 13 we start with an empty set of sets result. In the first iteration of the for loop at line 15, result will be a set of sets that only contain a single element. For example if $\txt{bag}=\{1,7\}$ we have $$ \txt{pools}=\{\{2,4,5\},\{5\}\} $$ and so in the first iteration $$ \txt{result}=\qty{\qty{2},\qty{4},\qty{5}}. $$ The curly brackets around each number signify that these are not mere elements but sets.

In the next iteration result is no longer empty. We want to take each set in result and combine it with all distinct elements in the current pool to make a new set of sets. In our example, lines 23-27 do not do much as the second pool is just $\qty{5}$. The newResult is the temporary placeholder of the new set of sets and by the time we reach line 30 it is equal to $\qty{\qty{2,5},\qty{4,5},\qty{5}}$. We are now done and the function can return the result.

You may have noticed that we use the move function from the utility header of STL. This function is used to free resources; by writing newResult.insert(std::move(newSet)) we free the resources allocated to newSet instead of making a copy. In the example above, using move is entirely superfluous since we are dealing with an object that consumes a tiny amount of memory. However, the problem is warning us that the number of houses can be anywhere between 2 and 220. So it makes sense to prepare the code for that scenario.

Now that we have a function that generates legitimate new connections we can find the minimum number of rounds required to pass the information to all houses. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// always start with round=0, combs={{1,N}}
int findDepth(const std::vector<std::set<int>>& links, int round, std::set<std::set<int>> &combs) {
    std::set<std::set<int>> newCombs;
    // Given existing tagged points contained in combs, generate new tagged points from each combination
    // using the cartesian product of the links.
    for (const auto& s: combs) {
        auto temp = cartesianProduct(links, s);
        for(const auto& t : temp) {
            std::set<int> merged = s;
            merged.insert(t.begin(), t.end());
            if (merged.size() == links.size()) {
                return round + 1; // found a complete combination
            }
            newCombs.insert(std::move(merged));
        }
    }
    
    return findDepth(links, round + 1, newCombs);
}

The findDepth function uses recursion until it reaches a round with all the houses informed. It always starts with $\txt{round}=0$ and $\txt{combs}=\qty{\qty{1,N}}$. combs is a set of sets; in every round it contains all possible scenarios of houses that are informed.

In lines 6-16 we go through each of the current combs; given the informed houses in this set we can use cartesianProduct to generate all the possible new connections. These are in the set of sets variable temp; for each set t in temp we generate a merged set by combining it with the informed houses that gave rise to the new connections. For example, suppose that $$ \txt{combs}=\qty{\qty{1,2,5,7},\qty{1,4,5,7},\qty{1,5,7}}; $$ Starting from the first set, 1 could be connected to 4, 2 to 3, 5 to 6 while 7 has done all that is possible. So there is only one new permutation, namely $\qty{4,3,6}$ (there is no conflict as 1, 2 and 5 talk to different houses). Since $\txt{s}=\qty{1,2,5,7}$, $\txt{merged}=\qty{1,2,3,4,5,6,7}$ and we have found a solution. Lines 15-17 check if this is the case; since links.size() is always equal to $N$ if merged.size() has the same value we are done. Otherwise we go to line 22 and keep searching!

If we had time we could have looked at ways of producing the full solution to the problem. With pen and paper the process for finding the solution would look something like this:

At the top right corner we have the sample input. The root of the tree contains the two houses with the recipe. Below (in pink) we have the boxes listing all the possible new connections. From the rules of the problem we know that we can only generate three child nodes. Each of these nodes contains new connections (e.g. $\qty{\qty(1,2),\qty(7,5)}$) except from the third in which house 1 has communicated to the only house with which house 7 has a connection.

In the next step, given, for example node $\qty{\qty(1,2),\qty(7,5)}$ we have houses 1, 2, 5 and 7 which can only generate three new connections: $\qty(1,4),\qty(2,3),\qty(5,6)$. We note that since each of houses 1, 2 and 5 have a single connection, their Cartesian product is just $\qty(1,4),\qty(2,3),\qty(5,6)$. If we append these three new connections to the original two we obtain $\qty{\qty(1,2),\qty(7,5),\qty(1,4),\qty(2,3),\qty(5,6)}$ which is the solution. If the root of the tree is at level 0, the solution is at level 2. This tree goes up to level 4 since the suboptimal child node $\qty{(1,5),7}$ produces two children, one of which ($\qty{\qty(1,5),7,\qty(1,4),\qty(5,6)}$) obtains a solution only through its grandchild.

A useful data structure for this tree is shown below: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
#include <set>
#include <utility>  // pair, move
#include <memory>  // unique_ptr

struct Node {
    int level;
    Node* parent;
    std::vector<std::pair<int, int>> edges;  // content
    std::vector<std::unique_ptr<Node>> children;  // children

    // Constructor
    Node(int l = 0, int N = 1, Node* p = nullptr) : level(l), parent(p) {
    }

    // Get pointer to this node
    Node* get() {
        return this;
    }

    // Is this Node a leaf?
    bool isLeaf() const {
        return children.empty();
    }

    void createChildren(int N, const std::vector<std::vector<int>> links) {
        std::set<int> s;
        pairsToSet(edges, s);
        if (s.size() == N) return;
        std::vector<std::vector<std::pair<int, int>>> groups;
        createGroups(s, links, edges, groups);
        std::vector<std::vector<std::pair<int, int>>> perms;
        createPerms(groups, perms);
        children.clear();
        for (const auto& p : perms) {
            auto child = std::make_unique<Node>(level + 1, N, this);
            std::vector<std::pair<int, int>> temp = edges;
            temp.insert(temp.end(), p.begin(), p.end());
            child->edges = temp;
            children.push_back(std::move(child));
        }
    }
};

The Node data structure has the following members:

  • level is set to zero for the root node and is incremented by 1 for the children of each node.
  • parent is a raw pointer to a Node. It is generated by the constructor where it is set to the address of the parent (or the nullPtr for the root node). It is only used for grouping child nodes in level order traversal (see below).
  • childrenis a vector of nodes implemented as std::vector<std::unique_ptr<Node>>. We use the unique_pt from the memory header for better memory management. Before the advent of smart pointers we would have had to delete all child (and grandchild and so on) pointers by writing an appropriate destructor method. By declaring child nodes as a unique_pt they will be automatically deleted when the parent node is destroyed. One small complication is in declaring the parent node; we should avoid declaring a node using Node* node = new Node() since then we must add a method that deletes it.

createChildren is the method that generates the child nodes given a parent node. This method requires the edges of the parent and links (see above). It uses functions pairsToSet, createGroups and createPerms. pairsToSet, as the name suggests, takes the edges of the parent (which is a vector of integer pairs) and converts it into a set of integers. The code for this is shown below: 

1
2
3
4
5
6
void pairsToSet(const std::vector<std::pair<int, int>>& edges, std::set<int>& s) {
    for (const auto& e : edges) {
        if (e.first != 0) s.insert(e.first);
        if (e.second != 0) s.insert(e.second);
    }
}

If the set s contains all N houses we reach a leaf of the tree that does not have any children (see line 29). Otherwise in line 30 we run createGroups. createGroups takes the elements of the set created by createChildren and generates a matrix of pairs. Each pair (x,y) takes x from the set s and y from the links for x. An example of this process is shown in the pink boxes in the diagram above. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void createGroups(const std::set<int> s, const std::vector<std::vector<int>> links,
    const std::vector<std::pair<int, int>> edges,
    std::vector<std::vector<std::pair<int, int>>>& groups) {
    for (const auto& x : s) {
        std::vector<std::pair<int, int>> g;
        for (const auto& y : links[x - 1]) {  // new element cannot belong to s
            if (!s.contains(y)) {
                g.push_back(std::make_pair(x, y));
            }
        }
        if (!g.empty()) {
            groups.push_back(std::move(g));
        }
    }
}

createPerms is a rewrite of the cartesianProduct function so that it can handle pairs. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void createPerms(const std::vector<std::vector<std::pair<int, int>>> groups,
    std::vector<std::vector<std::pair<int, int>>>& perms) {
    for (const auto& group : groups) {
        if (group.empty()) continue; // Skip empty groups

        if (perms.empty()) {
            for (const auto& pair : group) {
                perms.push_back({ pair });
            }
        }
        else {
            std::vector<std::vector<std::pair<int, int>>> newPerms;
            for (const auto& p : perms) {  // p is a vector of pairs ...
                std::vector<std::pair<int, int>> temp = p;
                for (const auto& g : group) {  // ... to which we add a new pair ...
                    std::set<int> newSet;
                    pairsToSet(p, newSet);
                    // ... only if its elements are new
                    if (newSet.find(g.first) == newSet.end() && newSet.find(g.second) == newSet.end())
                        temp.push_back(g);
                }
                newPerms.push_back(temp);
            }
            perms = newPerms;
        }
    }
}

This structure gives rise to a multiway tree; tree traversal is a term used for an algorithm that visits each node of a tree only once. There are two main methods for tree traversal: depth-first and level-order transversal. An example of each traversal is shown below using the tree drawn above as a template.

(a) Depth-first tree traversal, (b) Level-order tree traversal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Function for level order traversal
void levelOrderTraversal(const Node* root) {
    if (!root) {
        return;
    }

    std::queue<const Node*> q;
    q.push(root);

    while (!q.empty()) {
        int level_size = q.size(); // Number of nodes at the current level

        Node* o = nullptr;
        Node* n;
        for (int i = 0; i < level_size; ++i) {
            const Node* current = q.front();
            q.pop();

            n = current->parent;
            // see if we need an additional separator
            if (i > 0 && o != n)
                std::cout << "|" << " ";
            std::cout << " (" << current->edges[0].first << "," << current->edges[0].second << ")" << " ";
            for (size_t i = 1; i < current->edges.size(); ++i) {
                std::cout << "(" << current->edges[i].first << "," << current->edges[i].second << ")" << " ";
            }
            if (current->isLeaf()) std::cout << "[*] ";
            if (i < level_size - 1) std::cout << "|";

            o = n;

            for (const auto& c : current->children) {
                q.push(c.get());
            }
        }
        std::cout << std::endl; // Print a newline after each level
    }
}

The function shown above prints the level-order traversal of a multiway tree that is generated given the initial input. In the case of the example given in the problem the function produces the following printout: 

 (0,1) (0,7)
 (0,1) (0,7) (1,2) (7,5) | (0,1) (0,7) (1,4) (7,5) | (0,1) (0,7) (1,5)
 (0,1) (0,7) (1,2) (7,5) (1,4) (2,3) (5,6) [*] ||  (0,1) (0,7) (1,4) (7,5) (1,2) (5,6) ||  (0,1) (0,7) (1,5) (1,2) (5,6) | (0,1) (0,7) (1,5) (1,4) (5,6)
 (0,1) (0,7) (1,4) (7,5) (1,2) (5,6) (2,3) [*] ||  (0,1) (0,7) (1,5) (1,2) (5,6) (1,4) (2,3) [*] ||  (0,1) (0,7) (1,5) (1,4) (5,6) (1,2)
 (0,1) (0,7) (1,5) (1,4) (5,6) (1,2) (2,3) [*]

A [*] denotes a leaf while || separates families and | separates siblings. You can tell the parent of each child since in their first few pairs children always resemble their parents.

Comments

Post a Comment

Popular posts from this blog

CSAT 1

Image
Test Section A 1. You have a card of 10cm by 10cm. What is the largest volume in cm 3 of a box (without a lid) that can be obtained by cutting out a square of side x from each corner and then folding the flaps up? We can obtain an idea of the solution by looking at the following diagram: The box will have a base (marked in red on the diagram) with area $(l-2x)^2$ and height $x$. Therefore the volume of this box will be \begin{equation*} V=(l-2x)^x. \end{equation*} To maximize the volume first calculate \[ \dv{V}{x}=-4(l-2x)x+(l-2x)^2 \] using the product rule $d(u\cdot v)=du \cdot v + u \cdot dv$. Solve for $\dv*{V}{x}=0$ to find a (potential) maximum. If we assume that $x\neq l$ (a reasonable assumption since $x=l/2$ creates a nothing box) then \begin{align*} -4(l-2x)x+(l-2x)^2& =0 \\ l-2x-4x & = 0 \\ x & = \frac{l}{6}. \end{align*} To check that this is i...
Read more

Poor man's Daletskii-Krein

Image
Consider a second-order, symmetric tensor $A$ whose components $\def\R{\mathbb{R}}{A^j}_i \in \R$. We know that such a tensor has an eigen decomposition \begin{equation} \label{eigendecomp} A = V \Lambda V^\top \end{equation} where $V$ is an orthonormal, second-order tensor and ${\Lambda^j}_i=\lambda^j \delta^j_i$ ($\lambda^i$ is the $i$th eigenvalue of $A$). One corollary of (\ref{eigendecomp}) is \begin{equation} \label{An} A^n = V \Lambda^n V^\top . \end{equation} A function $f:\R \to \R$ that is analytic at $x=0$ is equal to its Maclaurin series \begin{equation} \label{maclaurin} f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} x^n \end{equation} where $f^{(0)}(0)=f(0)$ and $f^{(n)}(0)=\eval{\dv[n]{f}{x}}_{x=0}$. If we define \begin{equation} \label{def-fA} f(A):= \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!} A^n \end{equation} then $f(A)$ is also a second-order, sy...
Read more

PAT 2022

Image
1. What is the total resistance of the circuit ? 2. For which values of $x$ is $\qty(24-14x -3x^2)^{-1}$ positive? The $-1$ exponent does not change the sign. We can factorise $24-14x -3x^2$ as $(-3x+4)(x+6)$ which is positive either if $x < \frac{4}{3}, x > -6$ or if $x > \frac{4}{3}$, $x < -6$. The second condition cannot hold so we have to go with (D). 3. Molecules of oxygen in the atmosphere absorb solar radiation in bands centred at about 80 nm, 650 nm and 1000 nm. In which parts of the electromagnetic spectrum are these absorption bands? Picture from tikz.net The visible spectrum is in the very narrow band from 380 nm (violet) to 750 nm (red) so 650 nm is in the visible spectrum in the red zone. $1000 \ {\rm nm}=10^{-6} \ {\rm m}$ which is right at the edge of infrared. Finally $80 \ {\rm nm}= 0...
Read more