brain

Each team belongs to a university and has a fixed strength. Inside any contest, all participating teams are ranked strictly by strength, so stronger teams always appear ahead of weaker ones.

We are given a rooted tree where node 1 acts as the root, and each node stores an integer weight. The structure of the tree stays fixed, but the weights change over time due to updates.

We are building an array step by step. At each operation, a new value is appended to the end of the array. After each insertion, we must compute a running expression that depends on all suffixes ending at the current position and on a special prefix-suffix overlap value.

We are given a single integer $n$ per test case, and we want to choose two different numbers $a$ and $b$ in the range $[1, n]$. The constraint is that the binary representations of $a$ and $b$ must not share any position where both have a 1, meaning their bitwise AND is zero.

We are working on a rooted tree where every node initially holds value zero. Over time, we apply updates that either affect entire subtrees or only the immediate children of a node, and we also need to answer queries asking for maximum values over subtrees or over children sets.

We are given an array $a$ of size $n$. We want to count how many distinct multisets of size $n$ over values $1$ to $n$ can appear as follows. Imagine we construct an array $b$ of length $n$, where values are in the range $[1,n]$.

We are given an array and asked to look at every contiguous subarray. For each subarray, we compute a value called the MAD, which is the largest number that appears at least twice inside that subarray. If no number repeats, the MAD is zero.

We are given several independent test cases. In each test case there is a collection of pairs of numbers. Each pair behaves like a small container holding two values, and we are allowed to repeatedly perform operations that either destroy a container while collecting a…

We are given a rectangular grid of size $n times m$, initially empty. We must choose a set of cells to color red and blue, with two strict structural constraints.

We are asked to count how many ordered pairs of integers $(x, y)$ can be formed from a given number $n$, under two binary constraints applied bit by bit.

Let $F$ be continuous and strictly increasing on its support, so it admits a generalized inverse $F^{-1}(u)=\inf\{x:F(x)\ge u\}$.

Let the requests be processed in order, and let each request of size $s_i$ be placed by first-fit into the first available block that can contain it.

Consider any admissible sequence of requests whose total simultaneously allocated memory never exceeds $n_1+n_2$.

<Text>For blocksboxed{N(n,2)=\left\ of size at most 2, the exact value is</Text><lfloor \frac{3n}{2}\right\rfloor+O(Math block value="N(n,1)}, \] more precisely, \[ \boxed{N(n,2)= \begin{cases}

Let $N(n,m)$ denote the minimum memory guaranteeing successful allocation under the constraints of Exercise 38.

Let level $k$ denote blocks of size $2^k$, for $0 \le k \le r$.

The dynamic storage allocation methods of Section 2.

Consider any strategy of the hostess.

Use three passes.

No.

In the buddy system, the buddy of a block of size $2^k$ is obtained by complementing bit $k$ of the block's starting address, counting the least significant bit as bit $0$.

The criticism of this idea is that it conflates typical usage patterns with the correctness and generality of the buddy system.

The buddy system can be adapted to a memory of size $M$ that is not a power of two by partitioning the memory into the largest possible blocks whose sizes are powers of two.

The buddy system depends on the invariant that every free block has size $2^k$ and begins at an address aligned for a block of that size.

Doubly linking the `AVAIL[k]` lists in the buddy system allows a block to be removed from the list without traversing from the head.

In formula (9), `AVAIL` serves as the header of the circular list of available blocks.

Algorithm C can be coded directly in MIX by following the structure of steps C1, C6 and incorporating the optimization of exercise 15.

Modify Algorithm A as follows.

Use the same idea as the improvement to Algorithm A: retain a pointer to the place in the sorted `AVAIL` list where the most recent insertion occurred, and begin the search for the next insertion from...

Modify Algorithm A so that the search does not always begin at the front of the `AVAIL` list.

Suppose the `AVAIL` list contains three free blocks, in order of location, with sizes $100,\ 20,\ 20,$ and suppose two requests arrive consecutively, first for a block of size $18$, then for a block o...

Computer simulations reported in the literature for dynamic storage allocation generally show that best-fit and first-fit have very similar memory utilization.

Let x=\frac{l}{k-b}.

Algorithm C traverses the structure in preorder.

Algorithm A traverses the Data Table to find the first occurrence of an item with a given `NAME`.

Under the last-in-first-out restriction, the dynamic storage problem degenerates into stack allocation.

In Algorithm A, every node whose address is placed on the stack has `SIB=\Lambda`.

If there were no `NAME` link in the Data Table nodes, the test `NAME(S) = P_k` in step B6 could be performed by traversing the `DATAP` chain from `S` to find the data field corresponding to the name a...

To perform the function of Algorithm B with this two-link representation, traverse the tree by comparing the current node $P$ with the root $R$ of the desired subtree.

Algorithm B and Algorithm C can be accelerated by adding auxiliary links that reduce the number of nodes traversed in key searches.

Algorithm C traverses the multilinked structure of a group item and relocates each element to its correct parent or next sibling according to the specification of the data hierarchy.

The COBOL statement `MOVE CORRESPONDING SALES TO PURCHASES` means that each elementary data item in the group `SALES` that has the same name as an elementary data item in the group `PURCHASES` is copi...

Algorithm B can be modified to accept a linked list of Symbol Table references by replacing the indexed access of $P_0, P_1, \ldots, P_n$ with a traversal of the list using the $\operatorname{RLINK}$...

`MOVE CORRESPONDING \alpha TO \beta` transfers every subordinate item of $\alpha$ whose name also appears as a subordinate item of $\beta$, pairing items solely by identical names.

Algorithm A should be modified to verify that each group of items satisfies rule (c) at the point where a new item is read.

In COBOL data descriptions, a group item is written before any of its subordinate items, and each subordinate entry is listed immediately after the declaration of its parent group with increased inden...

Algorithm A must be modified to allow level numbers of items within a group to decrease by more than one between successive elements, rather than requiring strict increment by one as in COBOL.

Algorithm A performs a loop in which each iteration consists of a fixed number of arithmetic operations on the current data values, including a division step that determines the next state.

The copying procedure is defined on nodes reachable from $P_0$ using a depth-first traversal in which the field $\mathrm{REF}$ temporarily stores the correspondence between an original node $x$ and it...

The term $c_2M$ arises from the need to traverse all the pointers contained within the nodes of the Lists during the marking phase of garbage collection.

Let $P_0$ denote the initial node.

Let $P$ denote the current node and $R$ the root.

We represent each node of the List as a single MIX word, with the fields assigned as specified: `MARK` in $(0:0)$, `ATOM` in $(1:1)$, `ALINK` in $(2:3)$, `BLINK` in $(4:5)$, and $\Lambda = 0$.

Algorithm E constructs the set of nodes reachable from the designated list heads by repeatedly following the structural fields `DLINK` and `RLINK`, marking each visited node by setting its mark bit `S...

Label the $n$ nodes of a binary tree using an inorder traversal from left to right with the integers $1$ through $n$.

List structures can be threaded in the same sense as threaded binary trees by using otherwise unused pointer fields to store links that represent the successor of a node in a chosen traversal order.

A configuration of $k$ noncrossing diagonals in an $r$-gon partitions the polygon into $k+1$ regions.

A partition of the vertices of a convex $n$-gon with the property that no diagonal drawn inside one part crosses a diagonal drawn inside another part is equivalent to requiring that each part induces...

Number the vertices of an $(n+2)$-sided convex polygon consecutively as $V_1,V_2,\ldots,V_{n+2}$ in clockwise order.

Let $w_1,\ldots,w_m$ be the given weights and $l_1,\ldots,l_m$ the lengths of the paths to the corresponding external nodes in an extended binary tree.

Let $F(w_1,\ldots,w_m)$ denote the minimum weighted external path length over all extended binary trees with external weights $w_1,\ldots,w_m$.

The Dewey decimal notation in Exercise 2.

Let $T$ be a binary tree with $n$ nodes, and let $d(v)$ denote the distance from the root to a node $v$.

Let $E$ and $I$ denote the external and internal path lengths of an extended $t$-ary tree, and let $n$ be the number of internal (circular) nodes.

Let $T$ be an extended binary tree with external nodes carrying weights $w_1,\ldots,w_m$.

Let $T$ be a binary tree with left subtree $T_L$ and right subtree $T_R$.

Let the extended $t$-ary tree contain $n$ circular (internal) nodes and $s$ square (external) nodes.

For an extended binary tree, each external node corresponds to a unique path from the root, and thus to a binary string of length $l_j$ in which each left edge is encoded by $0$ and each right edge by...

Let $T$ be a binary tree with $n=12$ internal nodes and minimal internal path length $I$.

Each configuration counted by $r(n,q)$ consists of a directed acyclic graph on ${1,2,\ldots,n}$ in which every designated vertex has outdegree $1$ and every nondesignated vertex has outdegree $0$, wit...

The $( (3,2,4),(1,4,2) )$-construction in the notation of the section determines a decomposition in which the first index sequence selects the root structure at level $t=8$, while the subsequent index...

An ordered tree with $n$ vertices determines, by the correspondence in Section 2.

Let the vertices be ${1,2,\ldots,n}$ and let the oriented tree be directed toward its root $r$.

By the correspondence of equation (16), every labeled oriented tree on ${1,\ldots,n}$ corresponds uniquely to an $(n-1)$-tuple $(x_1,\ldots,x_{n-1})$, where each $x_i$ is an integer between $1$ and $n...

Let $x_1,x_2,\ldots,x_{n-1}$ be given and define $V_1,V_2,\ldots,V_n$ inductively by selecting at each stage the smallest vertex not yet chosen that does not appear in the corresponding suffix of the...

After $n-2$ deletions in the construction, exactly two vertices remain: the root and $V_{n-1}$.

Suppose the canonical representation of an oriented tree with $n$ vertices is given as the sequence $x_1,x_2,\ldots,x_{n-1}$, where $1\le x_j\le n$.

Let $G$ be the complete graph on the labeled vertices ${1,2,\ldots,n}$, and orient every edge toward the specified root, say vertex $1$.

Let the two centroids be $C_1$ and $C_2$.

Let $C(z)=\sum_n c_n z^n$.

Let $G(z)=\sum_{n\ge1} g_n z^n$ denote the generating function for oriented binary trees, where each vertex has in-degree $0,1,$ or $2$; equivalently, in the rooted orientation used in Section 2.

We have $A(z)=\sum_{n\ge1} a_n z^n$ and we seek a recurrence for $a_{n+1}$ in terms of previous $a_j$.

A program based on exercise 2 computes the coefficients $a_n$ recursively from na_{n+1}=\sum_{k=1}^{n}k\,a_k\,s_{nk}, \qquad s_{nk}=\sum_{1\le j\le n/k}a_{n+1-jk},

Suppose $k$ sets $S_1,\ldots,S_k$ of positive integers cover all positive integers.

Assume, to obtain a contradiction, that there exists an infinite _bad_ sequence T_1,T_2,T_3,\ldots such that $T_j\not\subseteq T_k$ whenever $j<k$.

Assume that for every positive integer $N$ there exists a partition of ${1,2,\ldots,N}$ into $k$ sets $S_1^{(N)},\ldots,S_k^{(N)}$ such that none of the sets contains an arithmetic progression of leng...

Stopped thinking

The given 92 tetrad types implement a hierarchical constraint system in which every $\beta$-tetrad forces $\alpha$-tetrads on both horizontal sides and $\delta$-tetrads vertically, while the internal...

For each positive integer $n$, let $T_n$ be the finite set of all legal tilings of the $n\times n$ torus by the given tetrad types, where legality means adjacency constraints hold and opposite edges m...

Yes, it is always possible.

The closure property (i) ensures that whenever a sequence $(x_1,\ldots,x_n)$ lies in $S$, its initial segment of length $0$ also lies in $S$.

Each arc $e$ of the directed graph is represented by a node whose identity is $e$ itself, with fields $\text{ALINK}$, $\text{BLINK}$ and one-bit tags $\text{ATAG}$, $\text{BTAG}$.

Let $A=(a_{ij})$ be the transition matrix.

Let $G$ be a directed graph with $n+1$ vertices $V_0,V_1,\ldots,V_n$, and let $A$ be the matrix defined in the statement of the exercise.

By Exercise 16, the game is won if and only if the digraph on $V_1,\ldots,V_{13}$ determined by the bottom cards is an oriented tree.

False.

The exercise depends essentially on the specific digraph in Fig.

For each vertex $V\ne R$, choose one oriented path from $V$ to $R$, which exists because $R$ is a root.

Let $T$ be an oriented tree with root $R$.

Let $v_0=\operatorname{init}(e_1)$ and for $1\le k\le n$ let $v_k=\operatorname{fin}(e_k)$, so $v_k=\operatorname{init}(e_{k+1})$ for $1\le k<n$ and $v_n=v_0$.