# [Fruit Baskets](https://open.kattis.com/problems/fruitbaskets)
This problem can either be solved using brute force or dynamic programming. The brute force solution is slightly more novel.

Instead of brute forcing over the baskets that have at least 200 grams of fruit, we can brute force over those that have strictly less than 200 grams of fruit. Since every fruit weight at least 50 grams, any such basket can have at most four fruits, and there are thus at most $N \choose 4$ such baskets. We can generate all of these using recursion.

Now, how do we actually solve the problem? We can compute the total weight of *all* fruit baskets using combinatorics and then subtract the small baskets. The way to get the total weight is to realize that every fruit is present in exactly half of all possible baskets (this can be seen by looking at the choices of fruits as binary strings).

n=int(input())
fruits = list(map(int,input().split()))

def count_small(i, tot_w):
    if tot_w >= 200:
        return 0
    if i == n:
        return tot_w
    return count_small(i+1, tot_w) + count_small(i+1, tot_w+fruits[i])

tot_weight = 0
for f in fruits:
    tot_weight += f * 2**(n-1)
print(tot_weight - count_small(0, 0))

# [Throwing Bridges](https://open.kattis.com/problems/kastabroar)
This is a graph problem. Mountains are nodes and bridges are edges. First, to let's determine if it's impossible. Note that we can obtain any graph via a sequence of bridge throws (even if it's inefficient). The smallest number of edges needed to connect a graph of $N$ nodes is $N-1$ edges. So if there are less edges available, the answer is `Nej`, otherwise `Ja`.

Now, how do we move the smallest number of edges? The connected components of the graph are already connected. So the goal is to connect the connected components. Thus, a lower bound on the answer is the number of connected components minus 1. This lower bound is actually achievable! We can just repeatedly take edges that don't destroy connected components and use them to connect two different connected components. This can be implemented in something like $O(NM)$.

To implement the solution efficiently, we can instead build a [spanning tree](https://en.wikipedia.org/wiki/Spanning_tree) in each connected component. We must never move any of those edges, while those that are not part of any spanning tree may be moved. The easiest way to build a spanning tree is probably using the union-find data structure.

[C++ solution](https://gist.github.com/Matistjati/10a10adcf9905378980fa5a28a6b11e0).

# [Turbo](https://open.kattis.com/problems/turbo)
Explicitly simulating the algorithm is too slow.

We will instead simulate the following algorithm, which gives the same answer:
- In the first phase, remove number $1$ from the array and pay one unit for all elements to the left of it
- In the second phase, remove number number $N$ from the array and pay one unit for all elements to the right of it

Even further, we can notice that we don't even need to remove the element: we could instead hold an array filled with ones at all positions that are not deleted. Then, each operation becomes to count ones in a prefix or suffix, and set numbers to $0$. This sounds like a job for a [segment tree](https://cp-algorithms.com/data_structures/segment_tree.html)!

[C++ solution](https://gist.github.com/Matistjati/d4ed927b00f57c711280eb5d2807df56).

# [Patuljci](https://open.kattis.com/problems/patuljci2)
There are two major ways to solve this problem.

## Random: $O(\log(N)\log(Q \cdot \text{#testcases}))$
Suppose that a dominating color exists. Then, if we select a random number in the interval, there will be an at least $50\%$ chance that we select the dominating color. Thus, it suffices to take let's say 50 samples and count the number of times said color occurs in the interval: if it occurs a strict majority of the time, we've found the color we're looking for. If not, then there probably doesn't exist a majority.

Now, how do we count the number of occurences of a color in an interval? For each color, store a list of the indices where it occurs. By binary searching in this list, we can count the number of occurences of a certain color in an interval in $O(\log(N))$ time.

[C++ solution](https://gist.github.com/Matistjati/2093b27236f214a3eec0b7bbcddc0f62).

It is possible to analyze the probability of failure. The only way we fail is if there was a majority, but we were unlucky. Suppose we make $K$ trials for every query. Then, the probability of failure is $(\frac{1}{2})^K$. The probability of not failing per query is then $1-(\frac{1}{2})^K$. The number of queries can be bounded $10^4 \cdot 10=10^5$ (at most $10^4$ queries per testcase, and by submitting we find out that there are 10 secret testcases). The probability of not failing any query is then $(1-(\frac{1}{2})^K)^{10^5}$. If we choose $K=30$, then we can see that the probability of failure is one in $10^{-4}$. [Calculation](https://www.wolframalpha.com/input?i=1-%281-%28%5Cfrac%7B1%7D%7B2%7D%29%5EK%29%5E%7B10%5E5%7D+at+K%3D30). If we choose $K=100$, then it's probably more likely for the computer to just execute your code incorrectly than to fail from being unlucky.

## Deterministic: $O(\log(N))$
Take the [Booyer-Moore majority voting algorithm](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm) and throw it in a segment tree. Note that Booyer-Moore only gives a candidate, and we still need the binary search part to check if it actually is the majority element. In practice, this is slower than the randomized variant, but would probably be faster if there were updates that changed color.

[C++ solution](https://gist.github.com/Matistjati/323a7de6010a5ec563effcad9c04a4d5).

# [Hamiltooonian Hike](https://open.kattis.com/problems/hamiltooonianhike)
We have too many options right now. Let's restrict ourselves a little more by taking a spanning tree of the graph. Then, let's root the tree arbitrarily and write a function `solve(x)` that takes some subtree and visits everything in it, ending at a child of `x`. We need to be careful to leave nodes so we can go up after going down, so let's mark vertices blue or red depending on if their depth is even or odd.

My implementation of `solve(x)` works as follows: we only call ever call `solve(x)` on `x` that are red nodes. Iterate over all children `c`. For every grandchild `gc` of `c`, call `gc`. Then, walk to `c`.

We do use three steps if we walk from a blue leaf to a red grandchild:

The full tour my algorithm would produce is illustrated below:

[C++ solution](https://gist.github.com/Matistjati/16a89a0eff2275e7f79dbf66ec2d8051).

# [Modulo Data Structures](https://open.kattis.com/problems/modulodatastructures)

Note that if $B$ is large, then it's fast enough to just do the addition naively. This will take $O(\frac{N}{B})$ time. So if we can handle small $B$ efficiently, we can get a decently fast solution by only running the faster of the two.

To handle small $B$, we can keep a matrix `smalladd[b][a]=` sum of c for all queries with these `b` and `a`. To answer queries, we can first look at the array (the values computed from iterating). Then, we can simply loop over all possible `b` and add up how much they contributed to this particular index.

If the cutoff point is $K$, then we get $\frac{N}{K}+K$, which is optimized when $K=\sqrt{N}$, for a total of $\sqrt{N}$ time per query.

[C++ solution](https://gist.github.com/Matistjati/6e8618e52ff0c1818d162fa95e8d9394).