Codeforces Round #415 (Div. 2) E. Find a car [or Div. 1 C]

Problem Statement:
Codeforces Round #415 (Div. 2) E. Find a car

Paraphrase:
An integer matrix M is defined as:
M[i][j] = the minimum integer x >= 1 such that:
- M[i][k] != x for all k < j
- M[k][j] != x for all k < i

Example:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Goal: Given a rectangular block in M {(x1, y1), (x2, y2)} and an integer K, compute the sum of elements in that rectangle, but exclude elements whose value is larger than K.

Induction - A sequence of integers whose sum is one

Problem Statement:
Given a sequence of integers \( x_1, x_2, \ldots, x_n \) whose some is one, prove that exactly one of the cyclic shifts
\((x_1, x_2, \ldots, x_{n-1}, x_n)\),    \((x_2, x_3, \ldots, x_n, x_1)\),   . . . ,    \((x_n, x_1, \ldots, x_{n-2}, x_{n-1} )\)
has all its prefix sums positive. (prefix sum: the sum of first k elements)

Solution:
We will proceed with mathematical induction.
For the base case \(n=1\), the only possible sequence is \(1\). Hence it satisfies all the desired properties.

Codeforces 536A - Tavas and Karafs

Problem Statement:
536A - Tavas and Karafs


Solution (from the official editorial, which is more succinctly written. I'm placing it here for my self reference.):
Given a sequence \(s_i\), we are only allowed to perform m-operation: choose at most m numbers in the sequence and decrease them by 1. Then it is provable that by performing at most t m-operation, we can reduce all \(s_i\) to 0, if and only if \( \max s_i \leq t\) and \( \sum_i s_i \leq tm \).
Proof:
Forward direction: if we can reduce all \(s_i\) using t operations, then it is clear that the biggest \(s_i\) must not exceed t, and that the total sum of \(s_i\) will not be more than \(mt\). The interesting part is to prove that this conditions are sufficient.

a bit of maths: Sets Coloring (Mathematical Induction)

USAMO/2002

Let S be a set with 2002 elements, and let \( 0 \leq N \leq 2^{2002} \). Prove that it is possible to color every subset of S either blue or red satisfying the following properties:

(1) The union of 2 red subsets is a red subset

(2) The union of 2 blue subsets is a blue subset

(3) There are exactly N red subsets

Solution:

The proof is by the magic of mathematical induction (and of course a clever way to abuse certain relationship about the subsets!). We will perform induction on the size of S.

For \( |S| = 1 \), the subsets of S are \(\{ \{\}, \{a\} \} \). Easily we can color the subsets to fulfill the requirements for all N. This will be the base case.

Induction step: suppose that we have shown that the proposition is true for \(|S| = k\) for some \(k \geq 1\). To build \(T\) where \(|T| = k+1\). Notice that the subsets of \(T\) can be divided into 2 groups \(V\) and \(U\) where \(V\) is the set of subsets of \(T\) containing the \(k+1\)-th element, while \(U\) is the set of subsets of \(T\) without the \(k+1\)-th element. This means that \(U\) is exactly the subsets of \(S\). Furthermore, \(|U| = |S| = 2^k\).

 From here, we have 2 cases to color those N subsets of \(T\).

Case 1: where \(0 \leq N \leq 2^k\)

Using our induction hypothesis, we can color these N subsets of \(U\) red, and the remaining subsets of \(T\) blue. This is possible since the 2 subsets in \(U\) cannot map to \(V\) under union, since all subsets in \(V\) contains the \(k+1\)-th element, while \(U\) does not.

Case 2: where \(2^k < N < 2^{k+1}\)

This seems to be a totally new problem, but actually it is just the other side of the same coin! Let \(M = 2^{k+1} - N\), and we know that \(M < 2^k\). Then we are back with the same situation in Case 1, just that now we want to color \(M\) subsets of \(U\) blue, and the rest of \(T\) red. This construction completes our proof.