From ba57c235addf1bd2f734df7339c3ce507eabc731 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Thu, 10 Dec 2015 23:09:29 +0000
Subject: Start report practical 2

---
 Practical2/report/notation.tex | 11 +++++++++++
 1 file changed, 11 insertions(+)
 create mode 100644 Practical2/report/notation.tex

(limited to 'Practical2/report/notation.tex')

diff --git a/Practical2/report/notation.tex b/Practical2/report/notation.tex
new file mode 100644
index 0000000..d21295e
--- /dev/null
+++ b/Practical2/report/notation.tex
@@ -0,0 +1,11 @@
+\section{Notation}
+\label{sec:notation}
+
+Given a list of $n$ numbers $p_0,p_1,\dots,p_{n-1}$, we consider one of its partitions in $k$ (possibly empty) pairwise disjoint substrings such that the sum of the sums of the substrings, rounded to multiples of $5$, is minimal. Output that minimal sum.
+
+I will write $\bar p = \seq{p_i \mid i<n}$ for the sequence of numbers and $k$ for the number of substrings. I redefine $\round{x}$ to mean `the nearest multiple of $5$ to $x$'. We may define the `round profit' as $\PR(x)=x-\round{x}$.
+
+Let $\PM_k(\bar p)$ be the minimal sum of rounded sums of $\bar p$ using $k$ partitions. I will use $\PP_k(\bar p)$ as the `maximum profit' of $\bar p$, that is, $\PP_k(\bar p) = \sum\bar p - \PM_k(\bar p)$. This leads to the term `profit' of a particular partitioning of $\bar p$ and of a particular (sub)string $\bar q$, for which we need not introduce notation. The profit of a string $\bar q$ is defined as $\PR(\sum\bar q)$. It is not difficult to see that the profit of a partition is equal to the some of the profits of its members.
+
+I will write $P^k_p(\bar p)$ for $\PP_k(\seq{p_i\in\bar p\mid i<p})$ (that is, the maximal profit on $\bar p$'s prefix with length $p$ using $k$ partitions). Lastly, let $S_i^j(\bar p)$ be the sum of all $p_x\in\bar p$ with $i\le x<j$.
+
-- 
cgit v1.2.3