# Maximum Subarray Problem

Given are $n$ numbers $a_1,...,1_n&space;\in&space;\mathbb{Z}$. Find the contiguous subarray with the highest summation; find $i,j&space;:&space;(1&space;\leqslant&space;i&space;\leqslant&space;j&space;\leqslant&space;n)$ that $S&space;=&space;\sum_{k=i}^j&space;a_k$ is the highest. If all the sums are negative, then $S&space;=&space;0$.

### The naive Algorithm: Brutforce

We compute every possible subarray, add them together and return the maximum. How good is the algorithm; How many additions does the algorithm need?

$\sum_{i&space;=&space;1}^n&space;\sum_{j&space;=&space;i}^n(j-i)&space;=&space;\sum_{i&space;=&space;1}^n&space;\sum_{j&space;=&space;0}^{n-i}(j)&space;=&space;\sum_{i&space;=&space;1}^n&space;\frac{(n-i)(n-i+1)}{2}&space;=&space;\sum_{i'&space;=&space;0}^{n-1}&space;\frac{(i')(i'+1)}{2}$

$=&space;\frac{1}{2}&space;(\sum_{i'&space;=&space;0}^{n-1}&space;(i')^2&space;+&space;\sum_{i'&space;=&space;0}^{n-1}i)&space;=&space;\frac{1}{2}(\Theta(n^3)&space;+&space;\Theta(n^2))&space;=&space;\Theta(n^3)$

### Pre-computation of prefix-summations

We can see that the first algorithm calculates the same values multiple times. Now, we calculate for every position $i$ the sum $S_i&space;=&space;\sum_{k=1}^i&space;a_i$ , in words, the sum of position $1$ to $i$. All those values can be calculated in linear time $\mathcal{O}(n)$. To calculate $S_i$ we simply need to add the $i$th number to the sum $S_{i-1}$. Now, for each new sum, we need a single operation: $S&space;=&space;S_j-S_{i-1}$

The time complexity for the precomputation is, as stated above, $\mathcal{O}(n)$ and the number of operations for the subarrays is $\sum_{i=1}^n&space;\sum_{j=i}^n&space;1&space;=&space;\sum_{i=1}^n&space;(&space;n+1-i)&space;=&space;\sum_{i=1}^n&space;(n)&space;+\sum_{i=1}^n&space;(1)&space;+\sum_{i=1}^n&space;(-i)$$=&space;n^2+n-\frac{1}{2}n(n+1)&space;=\frac{1}{2}n(n+1)&space;=&space;\Theta&space;(n^2)$. This means that the whole algorithm runs in $\Theta&space;(n^2)$.

### Divide and conquer

We split the whole array into two equal arrays and solve the problem for the smaller array : $a_1,\ldots,a_{n/2}$ and $a_{n/2&space;+1},\ldots,1_n$.  To ease the calculation, we assume that $n=2^k&space;,&space;k&space;\in&space;\mathbb{N}$, but it works for any number. If we find $i,j$ with $1&space;\leq&space;i&space;\leq&space;j&space;\leq&space;n$ of a solution, we have three distinct cases:

1. The solution is completely in the first subarray $1&space;\leq&space;i&space;\leq&space;j&space;\leq&space;\frac{n}{2}$
2. The solution is completely in the second subarray $\frac{n}{2}&space;+1&space;\leq&space;i&space;\leq&space;j&space;\leq&space;n$
3. The solution is in between the two subarrays $1&space;\leq&space;i&space;\leq&space;\frac{n}{2}&space;<&space;j&space;\leq&space;n$

To handle the third case,  we know that the best subarray is composed of the last parts of the first case (the left subarray) and the first parts of the second case (the right subarray). In other words, we want the suffix-sums $S_1,\ldots,S_{n/2}$ with $S_i&space;=&space;\sum&space;_{k=1}^{n/2}a_k$ and the prefix-sums $P_{n/2+1},\ldots,P_{n}$ with $P_j&space;=&space;\sum&space;_{k=n/2+1}^{j}a_k$. The best solution has the value $\textup{max}_i(S_i)+\textup{max}_i&space;(P_i)$

How is the time complexity of this algorithm? We have to calculate $\frac{n}{2}$ suffix and $\frac{n}{2}$ prefix sums. The sums $S_{i+1}$ and $P_{i+1}$ only need each a single addition, we have an upper bound of $\mathcal{O}(n)$, which means that $\exists&space;a$ such that we have not more than $a&space;\times&space;n$ costs. Looking at the recursion, we make two splits every time, which gives us:

$T(n)&space;=&space;\left\{\begin{matrix}&space;c&space;&&space;\text{if&space;}&space;n=0\\&space;2T(\frac{n}{2})&space;+&space;an&space;&&space;\text{if&space;}&space;n>0&space;\end{matrix}\right.$

We chose $n&space;=&space;2^k&space;;&space;k&space;\in\mathbb{N}$ to facilitate our calculations, we get:

$\overline{T}(k)&space;=&space;\left\{\begin{matrix}&space;c&space;&&space;\text{if&space;}&space;k=0\\&space;2\overline{T}(\frac{k-1}{2})&space;+&space;a\cdot&space;2^k&space;&&space;\text{if&space;}&space;k>0&space;\end{matrix}\right.$

We know that $T(n)&space;=&space;\overline{T}(k)$, wich leaves us with:

$\overline{T}(k)&space;=&space;2^k&space;\cdot&space;c&space;+&space;\sum&space;_{i=0}^{k+1}&space;2^i&space;\cdot&space;a&space;\cdot&space;2^{k-i}&space;=&space;c&space;\cdot&space;2^k+a\cdot&space;k\cdot&space;2^k$

Our complexity is $\Theta&space;(k\cdot&space;2^k)$. Substituting back for $n$ we get $T(n)&space;=&space;\Theta&space;(n&space;\log{n})$

Can we do better? Of course we can!

### Induction

We assume, that we have after $(i-1)$ steps the current maximum.  When we add the element $i$, we compare the new sum with the stored maximum until that point. With a second variable, we can easily check, if we have a new maximum or not. Once we arrive at a negative sum, we start at zero and start a new sum from that point. The code is pretty self-explanatory.

In this case, the time complexity is $\Theta&space;(n)$

Can we do better? Maybe $\mathcal{O}(\log{n})$? No, we can’t:

### Last step

We say that the algorithm has to check every item at least once.

Let’s assume, that the algorithm doesn’t check every item. Therefore, we have an item $a_i$ that wasn’t checked by the algorithm. We have two distinct cases:

1. If we compute a result which contains the element $a_i$ , we simply set $a_i&space;:=&space;-&space;\infty$ and thus rendering our optimal sum useless.
2. If we compute a result which doesn’t contain the element $a_i$ , we simply set $a_i&space;:=&space;\infty$ and thus rendering our optimal sum useless.

In both possible cases, we’ve shown that an algorithm which ignores element $a_i$ can compute the wrong result. Therefore, we can limit our possibilities to :

$\Omega&space;(n)&space;\cap&space;\mathcal{O}(n)=&space;\Theta&space;(n)$

Where $\Omega&space;(n)$ comes from the fact that we need to check every item at least once, and $\mathcal{O}(n)$ is the proposed algorithm above.

# LIO 2005 Preliminary Problem 4 – Chess

The problem statement:

We have an $8&space;\times&space;8$ chess board with at most 2  rooks, at most 2 bishops, at most one queen and one king. The goal is to calculate how many pieces set the king in check. We do not need to calculate wether it is a plausible(realistic, valid) setup, not take in count the colour of the pieces nor of the different fields. The input file is made up like this:
<row__of_piece><column_of_piece> … with the following order: king,queen,rook,rook,bishop,bishop
If a piece is missing it is denoted as 00.
The horizontal axis goes from A to H and the vertical one from 1 to 8. Consider the following example input from the input file chess_in.txt:
D6 B2 G4 00 F4 A7
The output will be
1

The basic idea is to draw on the chess board the line of sight of each piece and see how many hit the king. If the line of sight collides with another piece, it stops there.
We start with an enum and give each piece we place on the board a value.

We create a struct and a vector to have a list where we can save the position of each piece.

We now read in the pieces from the file, convert the chars to integer positions on the board and save the positions to the board and in the vector.

We call our first function with a loop based on our vector

The call_mark_los function takes the board with a reference parameter (that we can modify the board and don’t use a copy),  the position of each piece and the value of the piece to know which direction to look for. The function mark_los (mark line of sight) is then called with the board as reference parameter, the coordinates of the piece and a value for the x direction and one for the y direction the piece has a direct line of sight.

The mark_los function is a recursive function. With each call, the new x and y coordinates are added to the direction the piece can see. We then check if this new field is still in the board and if it doesn’t hit another piece (except the king). If this is all valid, we check if the line of sight hits the king, if it does, we increment our counter variable and exit the function. Otherwise we mark a new field as part of the line of sight of a piece and recall our function.

At the end of all that, we output the counter…

The whole code is available on github, check it out!

Stay tuned, lyinch.

# LIO 2006 Preliminary Problem 3 – Sudoku

The problem statement:

You receive a partially filled Sudoku and the goal is to only fill in the missing numbers in a row, column or 3*3 grid where always 8 numbers are filled in. After each new number, you have to recheck if there is a new row, column, 3*3 field with 8 numbers.
Example input (sudo_in.txt):
0 3 0 0 0 8 0 5 0
0 0 0 0 0 6 0 2 0
8 2 6 1 5 0 3 9 7
6 0 0 5 4 0 0 0 2
0 4 0 8 9 2 0 1 0
0 0 2 3 6 1 0 8 0
0 0 0 0 0 0 0 4 9
1 9 0 4 2 3 8 6 5
0 0 0 0 0 9 0 7 0
Example output:
0 3 0 0 0 8 0 5 0
0 0 0 0 0 6 0 2 0
8 2 6 1 5 4 3 9 7
6 0 0 5 4 7 0 3 2
0 4 0 8 9 2 0 1 0
0 0 2 3 6 1 0 8 0
0 0 0 0 0 5 0 4 9
1 9 7 4 2 3 8 6 5
0 0 0 0 0 9 0 7 0

The idea is to see with a check[10] array how many distinct numbers are filled in. If the first number [0] == 1, we know that the other 8 numbers are filled in. We then look for the missing number and the position of this number and fill it in the grid. We do this for every row, column and 3*3 grid. We repeat the process with a do while loop, because it checks at the end of every iteration if a new number has been added or not.

We start by reading in the sudoku

We check every row and column. The outer loops go trough a row or column, and if we find one where only one zero is filled in, we then look for the missing number and store those value in temporary variables (int val) to save them at the end of the checks in the sudoku field.

The 3*3 grids are based on the same idea but with a more complicated structure. The two outer loops switch every 3*3 block and the two inner loops look for the numbers in every block.

At the end we then output the sudoku:

The code is available on github.

Stay tuned, lyinch!

# LIO 2013 Preliminary Problem 3 – Sudoku

The problem statement:

You receive a sudoku game partially or complete filled and your goal is it to check if the game is correct. You don’t need to find a solution. This means: No repetition in a row, column and $3&space;\times&space;3$ grid.  The filename of the sudoku file is read in by the console.
Example input (in1.txt):
5 6 1 4 8 7 0 9 2
4 9 8 2 1 3 0 6 7
3 2 0 5 6 9 0 4 8
2 5 4 7 9 1 6 8 3
7 8 9 3 2 6 4 1 5
1 3 6 8 0 4 7 2 9
6 1 3 9 7 2 0 5 4
9 7 5 6 4 8 2 3 1
8 4 2 1 3 5 0 7 6
Example output: Correct

The idea is to have an array check[10] which is filled with zeros and each index represents one number of a row, column or 3*3 field. For every number in the sudoku I then increment the value of my check[number] and see if one of the values is greater than 1 after a row, column or 3*3 field.

We start by reading in the sudoku

The checks of the row/column are straightforward. After each row/column we check if the check array has an item larger than one, if yes we set the variable error to true. We reset the check array for each new row/column.

The check for the 3*3 grid is based on the same idea, but the loops are nested more complicated. The inner loops (x and y) always check a 3*3 grid, and the two outer loops switch to every new 3*3 block.

We then check if our error flag has been set or not

The whole code is on github.

Stay tuned, lyinch

# LIO 2003 Preliminary Problem 1 – CILonacci Sequences

The problem statement:

The numbers of the Fibonacci sequence are $0,1,1,2,3,5,8,13,...$. The next number is calculated by adding the two previous ones. A CILonacci (doesn’t exist…) is a generalisation of the Fibonacci sequence. The numbers of the sequence are made out of the sum of the previous M numbers ($M&space;\geqslant&space;2$).
The program reads the number M, followed by the first M numbers and then the number n, which is the position of the digit to calculate. The output shows the n-th term of the sequence.$2&space;\leqslant&space;M&space;\leqslant&space;100$ and $1&space;\leqslant&space;n&space;\leqslant&space;10'000$

We save all the values in a vector, and to calculate the next digit, we have a loop which adds the last position, (last pos-1), (last pos-2),…(last pos-m). The summation is in a loop which counts until the digit we want. We only need to loop to n-m (wanted digit – initial terms) because we already have the first m digits.

# LIO 2002 Preliminary Problem 3 – Pi Determination

The question statement:

Write a program which determines an approximation of $\pi$ with the formula of Bernoulli, which converts to the exact value of $\pi$. The formula is : $\frac{\pi^2}{6}&space;=&space;\frac{1}{1^2}&space;+&space;\frac{1}{2^2}&space;+&space;\frac{1}{3^2}&space;+&space;\frac{1}{4^2}&space;+&space;...$The program reads the number of rounds for the iteration and outputs the approximation of $\pi$. The number of iterations can’t exceed $1'000'000$ and the decimal precision needs to be at least $9$.

The only problems which occur in C++ are that we need to use long double for the precision and to output more than a few decimal places we need setprecision() from iomanip.

# LIO 2004 Preliminary Problem 4 – Shortest path

The question statement:

On an $n&space;\times&space;m$ field are obstacles. The task is to find the shortest path from north to south by only going down, left, right. The program reads in the file input.txt with the dimensions of the maze in the first line followed by the maze made out of $0$ (free path) and $1$ (obstacle).
The program outputs either the smallest path or -1 if no solution has been found. $2&space;\leq&space;m,n&space;\leq&space;127&space;\quad&space;|\quad&space;m,n&space;\in&space;\mathbb{N}$
Example maze.
20 10
00100000000001000100
11111001000001000010
00000001001111100000
00011101000001000111
00000000000011001111
11001000000000010111
11010001111000100000
11000000010110000000
11001111110110001110
11000010010000001110

This was a really tough problem. I didn’t want to use path finding algorithm such as A* because it’s first of all “only” a preliminary problem and should be easy, and secondly, I learned a lot trough this exercise.

We need an array with with the size of $n&space;\times&space;m$. In c++ we can’t create dynamic arrays and I therefore used vectors.

By reading the input.txt file, I first read the size of the matrix, resize my vector and then proceed to read line by line the field data and store it in my 2D vector. (yes, I messed up and resized my vector to $[y][x]$ instead of $[x][y]$ but that can be easily changed)

To output the field I created a simple procedure with two corresponding loops for $x$ and $y$.

The path finding is done with a recursive  boolean function.

1.  Check if coordinates are in range and if that field hasn’t been checked:return false;
2.  Check if goal has been reached : return true;
3.  Check if we hit a wall: return false;
4.  mark the current position as part of the solution (giving it the value 2)
5. Check the next field south, if true (the conditions above haven’t terminated the call): return true;
6.  Check the next field east, if true (the conditions above haven’t terminated the call): return true;
7.  Check the next field west, if true (the conditions above haven’t terminated the call): return true;
8.  Because the above checks couldn’t reach the goal, we unmark the path as part of the solution, give it the value 3 (already checked and wrong): return false;

I used two counters iterp (iterations plus) and iterm (iterations minus) which are incremented/decremented when I mark a field as the solution respectively when I unmark one. The two counters together give me then the number of steps I need to reach my goal. An additional bool print parameter has been added to output the optimal solution once it has been found.

Because I need to go from north to south and don’t have a fixed starting and ending field, I have two nested loops wich try every possibility of starting and ending field. If one of the fields is a wall, I skip it (continue in a loop jumps to the next iteration) and if my end field has a wall above it, it isn’t reachable. (If we can reach it from the east or west, then we already reached the southern line, and don’t need to make more moves to the side). The variable min_steps holds the number of steps for the smallest path and the values bxs and bxg (best_x_start/goal) hold the $x$ values for the best path.

If a boolean reached is true, I rerun my path finding with the best starting and ending coordinates and set the print flag as true to output the best path, else I output -1 which says that no path has been found.

The full code is available on github.  I used this page to help me with the algorithm, it further explains how the backtracking of the algorithm works.

Stay tuned, lyinch

# LIO 2002 Preliminary Problem 2 – Suites

The question statement:

Write a program which generates geometric and arithmetic sequences. An arithmetic sequence is defined: $u_n&space;=&space;u_{n-1}&space;+&space;c$ and a geometric one : $u_n&space;=&space;u_{n-1}&space;*&space;c$ . The program reads the first term from the sequence, the constant, the number of terms and a character ‘A’ or ‘G’ for the sequence. The program then outputs the sequence on the screen from the left to the right with a white space in between.

We have two different loops which either multiply or add the last term to the constant and output it based on the input character. We use the following formula: $u_{n+1}&space;=&space;u_n&space;+&space;c$ with $u_0&space;=&space;i$ and $u_1&space;=&space;u_0&space;+&space;c$ Before that, we check if the input is correct and exit if not.

# C++ Dynamic Multidimensional Vectors

I asked myself, how I could create a two dimensional array in C++ without a fixed size. I read the size from an input and then create the array according to this size. It actually is pretty easy with vectors:

We now somehow read in our dimensions of the field and change the size accordingly.

To access the elements, we don’t need an iterator but can access the elements by an index just like an ordinary array.

If we want to pass this 2D vector to a function we can pass it by value or constant reference if we want to keep the original content, or by reference if we want to change the original content.

And don’t forget to

# LIO 2002 Preliminary Problem 1 – Comptage

The problem statement:

Write a program which counts the number of appearance of a character in a text. The program reads the text from the keyboard and and outputs the number of occurrences. The text only made out if letters from the alphabet (french, but that sucks) and has not more than 100 characters. The program needs to differentiate between capital and lowercase letters, give an error message if the text or the character contain invalid characters and give one if the text is longer than 100 characters.

Pretty straightforward. We read the input with getline until a newline character comes. We then check with a loop every character of the string and increment a variable if an occurrence has been found.