# [A furious cocktail](https://open.kattis.com/problems/cocktail)
This problem can be solved using a greedy solution. Intuitively, we should drink long-lasting potions fast, and short ones last. Thus, to solve the problem, we sort the potions by length in decreasing order, simulate drinking them in this order, and check if that works.

# [Pizzabestun](https://open.kattis.com/problems/pizzubestun)
We have to buy the most expensive pizza at some point, so we might as well buy it in our first order. Now, note that the second pizza we get along with this one will be free, as the first one we chose was the most expensive one. So which one is best to remove for free? The cheapest one available, of course! Thus, a greedy solution works again: sort the pizzas in decreasing order of cost, and only pay for every other one. Do take care to handle the case where $N$ is odd.

# [Bocchi's Rocks](https://open.kattis.com/problems/bocchinorokku)
There are multiple solutions to this problem.

## Solution 1: binary search
First, let's create a copy of the rocks and sort it. Then, the answer for each rock is the number of rocks smaller than it. Equivalently, since this list is sorted, it's the index where we would insert the rock in the sorted list, which we can find using binary search. Python implements this with the `bisect_left` function. https://docs.python.org/3/library/bisect.html

from bisect import bisect_left
n=int(input())
rocks = [int(i) for i in input().split()]

rocks_sorted = list(sorted(rocks)) # O(NlogN)

for w in rocks:
    print(bisect_left(rocks_sorted, w)) # O(logN)

## Solution 2: two pointers
In the previous solution, there was one log factor from sorting and one from binary searching. In the following one, we make both log factors come from sorting only, which is usually better, since sorting is usually faster, and sometimes you already have the queries in sorted order.

The idea behind the algorithm is to process all rocks at once, in sorted order.

from bisect import bisect_left
n=int(input())
rocks = [int(i) for i in input().split()]

rocks_sorted = list(sorted(rocks)) # O(NlogN)
queries = [(rocks[i], i) for i in range(n)]
queries.sort() # O(NlogN)

answers = [n-1] * n

j = 0
for i in range(n):
    while j < n and queries[j][0] < rocks_sorted[i]:
        answers[queries[j][1]] = i-1
        j+=1

print(*answers)

# [Duck Journey](https://open.kattis.com/problems/andvag)
We will solve this problem using the [union-find](https://cp-algorithms.com/data_structures/disjoint_set_union.html) data structure. First, to check if the answer is `-1` or not, we check if the start and end are in the same component. Then, we can realize that crossing more edges is always better, so we can visit every single node in our component. Further, the set of feathers cleaned will be the bitwise or of all edge weights. To get the number of set bits, we can use `.bit_count()`. So we simply need to aggregate this value per component. This can be done using either DFS, or modifying the union-find.

n,m,q=map(int,input().split())
par = [i for i in range(n)]
size = [1] * n
compval = [0] * n # Cleaned feathers

def find(x): # No path compression because I'm lazy
    return x if x==par[x] else find(par[x])

for i in range(m):
    a,b,w=map(int,input().split())
    a = find(a-1)
    b = find(b-1)
    if size[a] < size[b]:
        a,b=b,a
    compval[a] |= w
    if a != b:
        par[b] = a
        size[a] += size[b]
        
for i in range(q):
    a,b=map(int,input().split())
    a=find(a-1)
    b=find(b-1)
    if a!=b:
        print(-1)
    else:
        print(compval[a].bit_count())

# [Gene block](https://open.kattis.com/problems/geneblock)
This problem is a little unusual. Let's first assume that $N$ is large. In this case, the answer for all numbers ending in $7$ is $1$. Let's continue looking at the last digit. Adding two numbers ending in $7$, the new last digit will be $4$. Adding another one, we get $1$. The full pattern is as follows:

7
4
1
8
5
2
9
6
3
0

And in fact, the answer to any number ending with a given digit is its index in this list. This at least holds for large numbers. Unfortunately, we can't construct some smaller numbers. The smallest numbers we can construct are 7,14,21,.... We can realize that this sequence constructs the last digits in the same order as previously. Thus, to check if a given number is constructible, we look up the smallest number that can construct this last digit, and check if our number is larger.

t=int(input())
order = [7,4,1,8,5,2,9,6,3,0]

for i in range(t):
    q = int(input())
    ans = order.index(q%10)+1
    if q < ans * 7:
        print(-1)
    else:
        print(ans)

# [Segment Monitoring](https://open.kattis.com/problems/segmentovervakning)
See the official solution slides [here](https://docs.google.com/presentation/d/1Go_-f3Tm0_sbMfdcYgadtjLrFWyAhIcM/edit?slide=id.p23#slide=id.p23).

# [Zip Lines](https://open.kattis.com/problems/ziplines)
Let's model this problem as a graph. Let's call every number in the array a rectangle. We will have one node for every rectangle. From every rectangle, draw a directed edge to every other rectangle where a zip line could be built.

Now, there are several nice properties of this graph. First, any zip line system is a path in this graph. Thus, the problem is asking about the longest path in this graph. Second, this graph has no cycles (we decrease in height every time we use a zipline). Third, this graph can never have more than $O(N)$ edges. Why? Every rectangle can have at most two edges going into it, one from the left and one from the right.

From these, it suffices to find all edges and use DP to find the longest path. Google "longest path in DAG" if you haven't seen this before. Now, how do we quickly find the edges? The idea that every rectangle has at most two incoming edges suggests that we should find these every rectangle's incoming edges. This can be done by doing a left-to-right sweep for edges going to the right, and similarly for left-going edges. The details are too annoying to describe.

# [Bustling Busride](https://open.kattis.com/contests/r9o44t/problems/bustlingbusride)
Tip: this kind of "minimize the largest wait" should scream "[binary search the answer](https://hackmd.io/4lrsjyu4TpS47S5V8lORVw)" to you. And indeed, the answer is binary searchable: if some waiting amount works, any longer waiting amount also works. Correspondingly, if some waiting amount doesnt work, any shorter amount won't work.

Now we have the new subproblem to check if the answer is $k$ or less. For this subproblem, the solution is greedy: every time the bus comes to pick up people, pick up as many people as possible, without having any wait more than $k$ seconds. Thus, a tempting solution is to simply simulate this. Unfortunately, adding, when adding a new person to the bus, it's not trivial to calculate how much extra time this adds (it takes $O(N)$ naively). The official editorial solves this by using treaps over the time when people get off. We will instead present a simpler solution.

Let's also binary search for the number of people to add each time. The problem with this? Checking whether adding $x$ people to the bus respects $k$ takes $O(x\log(x))$ time (the log factor is from sorting). So we basically have the problem of doing a binary search, but querying $x$ costs $x\log(x)$ units. Naively binary searching would cost $O(N\log(N)^2)$ per bus ride, which means $O(N^2\log(N)^2)$ per $k$ in the worst case.

One close-to-optimal strategy is to instead first check $x=1$, then $x=2$, $x=4$, etc. At the first failing $x$, we will have interval of possible answers $x, 2x$. We can then do a binary search over $[x,2x]$. If the correct $x$ has value $x_{corr}$, then this strategy costs $O(x_{corr}\log(x_{corr})^2)$. When summed over all bus rides for a given $k$, this is bounded by $O(N\log(N)^2)$, so since we binary search over $k$, we get $O(N\log(N)^3)$ total. This has worse complexity than the treap solution, but is much easier to code and can run much fast if you're smart with your sorting.

The problem can also be solved using DP.