This problem set was for a lecture on Greedy problems I gave in NUSH. I went super overboard with difficulty. Posting here for fun.

Easy Problems

  1. There are $n$ cards on a table, each card has a red side and a blue side. The $i$-th card has the numbers $r_i$ and $b_i$ written on its red and blue sides respectively. You need to have exactly $k$ cards having their red side faced up. What is the optimal way to arrange these cards if we want to maximize the sum of values of those faces which are faced up?
  2. You are given a list of $n$ numbers (some are possibly negative). How can we pick $k$ of these numbers such that their product is maximized?
  3. You are given two vectors $X = (x_1, x_2, …, x_n)$ and $Y = (y_1, y_2, …, y_n)$. You are allowed to reorder the elements of each vector. What is the maximum possible dot product of these two vectors? Recall that the dot product of two vectors is $(x_1, x_2, … x_n) \cdot (y_1, y_2, … y_n) = x_1y_1 + x_2y_2 + … + x_ny_n$.
  4. There is a string with the characters $\texttt{7}$ and $\texttt{2}$ only. The epicness of a string is the number of occurrences of $\texttt{727}$ in the string divided by its length. For example, $\texttt{727}$ has epicness $\frac{1}{3}$, $\texttt{7277727}$ has epicness $\frac{2}{7}$ and $\texttt{7227}$ has epicness $\frac{0}{4}$. Over all contiguous substrings, find the substring what maximal epicness.
  5. There are some shows. Each show has some episodes and each episode has an enjoyment value. You want to watch at most $x$ episodes of any shows but you must follow the watch order of the show (for example, you cannot watch episode $2$ of a show before watching episode $1$). For some reason, the enjoyment of any episode is always greater than the episode which follows it (if it exists). What is the best way to watch at most $x$ episodes?
  6. You have some sticks of positive length. You can chop the sticks at most $k$ times. In $1$ chop, you pick one stick of length $x$ and chop it into two sticks of length $y$ and $z$ such that $x=y+z$. You do not like big sticks so you will give a stick of length $x$ a badness of $x^2$. What strategy can we use to minimize the sum of badness over all sticks.
  7. We have some numbers. Order the number in any way and concatenate them. What strategy can we use to obtain the smallest number possible? For example if the numbers are $(301,30,1)$, the smallest possible number possible is by concatenating $1,301,30$ in that order to produce the number $130130$.
  8. There are two convex arrays $a=(a_1,a_2,\ldots,a_n)$ and $b=(b_1,b_2,\ldots,b_m)$. Array $c$ is defined as $c_i=\min\limits_{j+k=i} a_j+b_k$. Calculate the array $c$. An array $x=(x_1,x_2,\ldots,x_k)$ is convex if $x_i-x_{i+1} \geq x_{i+1}-x_{i+2}$.
  9. There are $n$ books in a library. The $i$-th book takes $a_i$ minutes to read. Alice and Bob wants to read all the books in the library. How much time do they need? Note that they cannot a read single book at the same time and each person must completely finish a book before starting another one.
  10. There is a binary string $s$ (a string with characters $\mathtt{0}$ and $\mathtt{1}$ only). The badness of the string is the number of pairs $i < j$ such that $s_i = \mathtt{1}$ and $s_j=\mathtt{0}$. You can change at most $k$ characters of the string. What is a strategy to minimize the badness?
  11. You are given an array $a$ and an integer $k$. You have to split this array into $k$ contiguous segments. For example, with $a=[3,1,4,1,5,9]$ and $k=2$, you can split the array into $[3,1]$ and $[4,1,5,9]$. Let $g$ be the array describing which group each index belongs to. In the above example, $g=[1,1,2,2,2,2]$. Find a way to split the array such that $\sum\limits_{i=1}^N a_i \cdot g_i$ is maximized.
  12. There are several wrong strategies to solve the knapsack problem. Find counterexamples to each of them (greedily pick the smallest weight, greedily pick the largest value, greedily pick the largest ratio of value to weight).
  13. Show that $(S,\mathcal{I}_k)$ is a matroid where $S$ is any finite set and $\mathcal{I}_k$ is the set of all subsets of $S$ of size at most $k$.
  14. Prove that the minimum spanning tree algorithm is correct by showing that if $G=(V,E)$ is an undirected graph, then $M_G=(E,\mathcal{I}_G)$ is a matroid where $A$ is in $\mathcal{I}_G$ iff $A$ is a subset of $E$ and the graph $G=(V,A)$ does not contain any cycles.

Medium Problems

  1. NUS High has many departments for each subject. Each department has some number of teachers (and teacher belongs to exactly one department). NUS High wants to have some cross-department projects. Each project will have exactly $k$ teachers, each from a different department. What is the maximum number of projects that can be done? No teacher can participate in multiple projects.
  2. There are some people we must arrange in a row in any order we want. The $i$-th person has sickness $a_i$. If person $i$ and $j$ are standing next to each other, they must be separated by at least $a_{\max(i,j)}$ meters. What is the minimum distance between the leftmost and rightmost person?
  3. There are $n$ potions arranged in a line. The $i$-th potions gives you $a_i$ health points ($a_i$ can be negative). You start with an initial health of $0$ and will walk from left to right, each time you encounter a potion, you can either drink it or ignore it. If your health drops below $0$, you will die. What is the maximum number of potions you can drink?
  4. You have some sticks of positive integer length. You can chop the sticks at most $k$ times. In $1$ chop, you pick one stick of length $x$ and chop it into two sticks of length $y$ and $z$ such that $x=y+z$ and $y$ and $z$ are both positive integers. You do not like big sticks so you will give a stick of length $x$ a badness of $x^2$. What strategy can we use to minimize the sum of badness over all sticks.
  5. Given an $m \times n$ matrix $T$ over the real numbers (or any field), show that $(S,\mathcal{I})$ is a matroid, where $S$ is the set of colums of $T$ and $A \in \mathcal{I}$ iff the columns in $A$ are linearly independent.

Hard Problems

  1. There are $n$ continuous function. The $i$-th function is $f_i$. For all functions, $\int_0^1 f_i(x) \, dx=n$. Prove that there exists two sequences $(x_0,x_1,\ldots,x_n)$ and $(p_1,p_2,\ldots,p_n)$ where $0=x_0 < x_1 < \ldots < x_n = 1$ and $p$ is a permutation of integers from $1$ to $n$ such that $\int_{x_i}^{x_{i+1}} f_{p_i}(x) \, dx \geq 1$.
  2. Let us call a sequence $a=(a_1,a_2,\ldots,a_k)$ beautiful if $a_i \neq a_{i+1}$. You are given a sequence $s$. In one move, you can choose some contiguous beautiful subsequence of $s$ and delete it. How many moves do you need to turn $s$ into the empty sequence?
  3. You are given a graph. Partition the edges into $3$ sets $A,B,C$ such that $A \cup C$ and $B \cup C$ are both trees or determine that it is impossible.
  4. There are some $n$ towers of blocks. The $i$-th tower contains $a_i$ blocks and no two towers have the same number of blocks. We want to sort the towers in increasing order of height. We can swap the heights of towers $i$ and $j$ using $\lvert a_i-a_j \rvert +c$ seconds. What the minimum time needed to sort the towers?
  5. Show that if $(S,\mathcal{I})$ is a matroid, then $(S,\mathcal{I}’)$ is a matroid, where $\mathcal{I’} = {A’ : S-A’ \text{ contains some maximal } A \in \mathcal{I} }$. That is, the maximal independent sets of $(S,\mathcal{I}’)$ are just the complements of the maximal independent sets of $(S,\mathcal{I})$.

Random Shit

  1. The Catalan numbers are a sequence of natural numbers that occurs in various counting problems. The first few terms of the catalan nunbers are $1,1,2,5,14,42,\ldots$. Let the $i$-th Catalan number be $C_i$. One of the many objects that the Catalan numbers count are the number of balanced bracket sequences where $C_i$ is the number of balanced bracket sequences with $n$ open brackets and $n$ closed brackets. Recall that a bracket sequence is called balanced if it can be turned into a valid math expression by adding the characters $1$ and $+$. For example, $\mathtt{(()())}$ and $\mathtt{()}$ are balanced while $\mathtt{(()))(}$ is not. It is well known that $C_n = \frac{1}{2n+1} \cdot \binom{2n+1}{n}$. Notice that $\frac{1}{2n+1} \cdot \binom{2n+1}{n}$ is the number of distinct binary strings containing $n$ $\mathtt{0}$s and $n+1$ $\mathtt{1}$s up to cyclic rotation. Find a bijection between these $2$ sets.
  2. You are gambling your life savings and have $x$ dollars currently. You will play a game where you have $p$ probability to gain $1$ dollar and $1-p$ probability to lose $1$ dollar. If you have $0$ dollars you will lose the gamble. You will play the game until you lose. What is the probability that you will lose in terms of $x$ and $p$ (surprisingly, there is non-zero chance that you will never lose)?
  3. There are $2^n$ switches arranged on a spinning table. You wish to turn off all the switches to save electricity. However, you are blindfolded and also handcuffed (so you don’t even know the initial state of the switches). In one move, all you can do is say some set of positions of these $2^n$ switches, then someone will randomly spin the table and toggle the positions of switches that you have said. You will win if there exists a point in time where all the switches are off. Show that there exists a winning strategy using at most $2^{2^n}$ moves.
<
Previous Post
MA5131 Summary 5
>
Next Post
Trigonometry