Brackets Given a string of N parentheses, such as (()())((), count all correctly parenthesised expressions that can be obtained by erasing some characters. Each expression should only be counted once, even if it can be produced in many ways. ---------------------------------------- Interconnect Given are N cities and M roads that already exist. Each year two distinct cities are chosen uniformly at random and a new road between them is built (even if multiple such roads exist already). Calculate the expected number of years until the country is connected. Estimate the biggest N for which the task be solved in 1 second. ---------------------------------------- Party with three hat colors Given a graph, determine whether it's 3-colorable time better than Theta(2^n). Easily determine the smallest number of colors to color a graph in time better than Theta(3^n). ---------------------------------------- Adjust You are given N, M <= 10^11. You can modify digits of N. (You cannot add or remove digits, and you cannot produce unnecessary leading zeros.) Find the smallest number of changes needed to transform N into a multiple of M. ---------------------------------------- Expected best subsequence For a sequence S, let best(S) be the largest possible sum of a contiguous subsequence of S. You are given a sequence T of N <= 50 integers, each in [0,50]. For each element of T we are going to flip a coin, and if it comes up heads, we write a minus sign in front of it. This will produce a new sequence T'. Calculate the expected value of best(T'). ---------------------------------------- Optimistic An integer is optimistic if its digits contain a 5-digit strictly increasing subsequence. E.g., 81734005291 is optimistic because it contains 13459. Given A, B <= 10^100, count all optimistic numbers in [A,B]. ---------------------------------------- Dice game Your goal is to reach or exceed the score 1000. The game is played in rounds. Calculate the smallest expected number of rounds needed. In each round your bank starts at zero. The round consists of one or more turns. In each turn you roll a standard die. On a 1, your bank resets to zero and the round ends. Otherwise, the roll is added to your bank and you get to make a choice: roll again, or terminate the round and add the bank to your score. ---------------------------------------- Nicest place Given is a graph with 100k vertices, 500k edges. Each vertex has some beauty, each edge has some difficulty. Given is a collection of 500k queries of the form “if you start in location A and you can only travel along edges with difficulty up to B, what is the C-th nicest location you can visit?”