VOI (Vietnam National Olympiad in Informatics) 2016 has just ended a few hours ago. You are given 6 problems (3 each day) to solve in the time of 180 minutes per day. As a contestant, I must say for such a small window of time I just couldn't do them all. Anyways here are the (of course, shortened version of) statements of the problems. ↵
↵
The problems have a total score of 40, which divides to 6 / 7 / 7 per day.↵
↵
### Day 1↵
↵
#### Problem 1 (6 pts)↵
You are given a sequence of numbers $A[1..n]$ ($1 \le A_i \le 10^9$). You have to erase the least amount of numbers in the sequence such that for every $i < j$ in the new sequence the following condition holds: $|A_i - A_j| \notin \{1, 8, 9\}$.↵
↵
50% of the tests have $n \le 20$. The remaining have $n \le 2000$.↵
↵
#### Problem 2 (7 pts)↵
There is a road which has a length of $L$. You have a truck with the fuel tank capacity of $K$, andhave to deliverstart off with $Q$ litres of fuel fromat one side (point 0) which you will have to deliver to the other side (point L) of the road. Your truck consumes 1 litre of fuel per unit of length it travels. In order to help you, starting from point 0 there is a fuel tank with unlimited capacity every $D$ units of length (so there are tanks on point $D$, $2D$, ... and they are empty at start). You are allowed to transfer the fuel in and out of any tank. Maximize the amount of fuel you can deliver to point $L$.↵
↵
Given $L$, $K$, $Q$, $D$, calculate the maximum amount of fuel you can deliver to point $L$.↵
↵
Constraints: $1 \le L, K, D \le 10^9$, $1 \le Q \le 10^{12}$. On the first 50% of the tests $\dfrac{L}{D} \le 10^4$.↵
↵
#### Problem 3 (7 pts)↵
You are given an undirected connected graph $G(V, E)$ of $n$ vertices and $m$ edges (with no self edges and multi-edges) and the following algorithm to construct $K$:↵
↵
- First, initialize $K[1..n]$ as an array of empty vectors of integers. Let $K[1] = {0}$. ↵
↵
- Let $f[1..n]$ be an array of booleans, all being false at start. Let $Q$ be a set of indices $i$ such that $f[i] = false$ and $|K[i]| > 0$↵
↵
- While $|Q| > 0$:↵
↵
- Let $u$ be the smallest number in $Q$. Set $f[u] = true$↵
↵
- For each edge $(u, v)$ in $G$ such that $f[v] = false$ we append $u$ into back of $K[v]$.↵
↵
Please renumber all the vertices in the graph so that for the resulting array $K$ of the algorithm the following condition holds: For every $u < v$ we have $K[u] \le K[v]$ alphabetically. ↵
↵
Constraints: 40% of the tests have $n \le 10$. 80% of the tests have $n \le 10^3, m \le 10^4$. All tests have $n \le 2 \times 10^4, m \le 10^6$.↵
↵
### Day 2↵
↵
#### Problem 1 (6 pts)↵
You are given a grid of $n \times m$ cells, each containing a zero or one. Find the diamond-shaped area (which has to be fully inside the grid) containing the most ones such that no two one cells inside the area share the same edge.↵
↵
A diamond-shaped area with center $(x_0, y_0)$ and radius $r$ is a set of cells $(x, y)$ which satisfies $|x - x_0| + |y - y0| \le r$.↵
↵
Constraints: 40% of the tests have $n \le 100$. 80% of the tests have $n \le 500$. All tests have $n \le 1000$.↵
↵
#### Problem 2 (7 pts)↵
You are given a set of $n$ operations containing at most 4 numbers within $[0..10^6]$ and operators `+`, `-`, `*`. You have add brackets to some of the equations such that each of them has an unique value. ↵
↵
Constraints: 50% of the tests have $n \le 20$ and operations having at most 3 numbers. All tests have $n \le 2000$.↵
↵
#### Problem 3 (7 pts)↵
You are given $n$ trees (real world trees) with the $i$-th tree having height $h_i$ and stands at position $i$ and you have to fall down all of them. Falling the tree $i$ to the left causes all trees $j$ with $i - h_i < j < i$ to fall to the left, and falling tree $i$ to the right causes all trees $j$ with $i < j < i + h_i$ to fall to the right (and they to make chains like dominoes). Find a way of cutting the trees such that the number of trees manually fell at minimized.↵
↵
All trees have height not exceeding $4 \times 10^6$ ↵
↵
Constraints: 40% of the tests have $n \le 10^4$, 80% of the tests have $n \le 10^5$, all tests have $n \le 4 \times 10^6$
↵
The problems have a total score of 40, which divides to 6 / 7 / 7 per day.↵
↵
### Day 1↵
↵
#### Problem 1 (6 pts)↵
You are given a sequence of numbers $A[1..n]$ ($1 \le A_i \le 10^9$). You have to erase the least amount of numbers in the sequence such that for every $i < j$ in the new sequence the following condition holds: $|A_i - A_j| \notin \{1, 8, 9\}$.↵
↵
50% of the tests have $n \le 20$. The remaining have $n \le 2000$.↵
↵
#### Problem 2 (7 pts)↵
There is a road which has a length of $L$. You have a truck with the fuel tank capacity of $K$, and
↵
Given $L$, $K$, $Q$, $D$, calculate the maximum amount of fuel you can deliver to point $L$.↵
↵
Constraints: $1 \le L, K, D \le 10^9$, $1 \le Q \le 10^{12}$. On the first 50% of the tests $\dfrac{L}{D} \le 10^4$.↵
↵
#### Problem 3 (7 pts)↵
You are given an undirected connected graph $G(V, E)$ of $n$ vertices and $m$ edges (with no self edges and multi-edges) and the following algorithm to construct $K$:↵
↵
- First, initialize $K[1..n]$ as an array of empty vectors of integers. Let $K[1] = {0}$. ↵
↵
- Let $f[1..n]$ be an array of booleans, all being false at start. Let $Q$ be a set of indices $i$ such that $f[i] = false$ and $|K[i]| > 0$↵
↵
- While $|Q| > 0$:↵
↵
- Let $u$ be the smallest number in $Q$. Set $f[u] = true$↵
↵
- For each edge $(u, v)$ in $G$ such that $f[v] = false$ we append $u$ into back of $K[v]$.↵
↵
Please renumber all the vertices in the graph so that for the resulting array $K$ of the algorithm the following condition holds: For every $u < v$ we have $K[u] \le K[v]$ alphabetically. ↵
↵
Constraints: 40% of the tests have $n \le 10$. 80% of the tests have $n \le 10^3, m \le 10^4$. All tests have $n \le 2 \times 10^4, m \le 10^6$.↵
↵
### Day 2↵
↵
#### Problem 1 (6 pts)↵
You are given a grid of $n \times m$ cells, each containing a zero or one. Find the diamond-shaped area (which has to be fully inside the grid) containing the most ones such that no two one cells inside the area share the same edge.↵
↵
A diamond-shaped area with center $(x_0, y_0)$ and radius $r$ is a set of cells $(x, y)$ which satisfies $|x - x_0| + |y - y0| \le r$.↵
↵
Constraints: 40% of the tests have $n \le 100$. 80% of the tests have $n \le 500$. All tests have $n \le 1000$.↵
↵
#### Problem 2 (7 pts)↵
You are given a set of $n$ operations containing at most 4 numbers within $[0..10^6]$ and operators `+`, `-`, `*`. You have add brackets to some of the equations such that each of them has an unique value. ↵
↵
Constraints: 50% of the tests have $n \le 20$ and operations having at most 3 numbers. All tests have $n \le 2000$.↵
↵
#### Problem 3 (7 pts)↵
You are given $n$ trees (real world trees) with the $i$-th tree having height $h_i$ and stands at position $i$ and you have to fall down all of them. Falling the tree $i$ to the left causes all trees $j$ with $i - h_i < j < i$ to fall to the left, and falling tree $i$ to the right causes all trees $j$ with $i < j < i + h_i$ to fall to the right (and they to make chains like dominoes). Find a way of cutting the trees such that the number of trees manually fell at minimized.↵
↵
All trees have height not exceeding $4 \times 10^6$ ↵
↵
Constraints: 40% of the tests have $n \le 10^4$, 80% of the tests have $n \le 10^5$, all tests have $n \le 4 \times 10^6$
