\documentclass[10pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usetheme{metropolis}
\usepackage{booktabs}
\usepackage[scale=2]{ccicons}
\usepackage{pgfplots}
\usepgfplotslibrary{dateplot}
\usepackage{xspace}
\usepackage{pbox}
% a few macros
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\ig}{\includegraphics}
% title info
\title{Introduction}
\author{Bjarki Ágúst Guðmundsson\\ Tómas Ken Magnússon}
\institute{\href{http://ru.is/td}{School of Computer Science} \\[2pt] \href{http://ru.is}{Reykjavík University}}
\titlegraphic{\hfill\includegraphics[height=0.6cm]{kattis}}
\date{\textbf{Árangursrík forritun og lausn verkefna}}
% Tikz
\usepackage{tikz}
\usetikzlibrary{arrows,shapes}
% Minted
\usepackage{minted}
\usemintedstyle{manni}
\newminted{cpp}{fontsize=\footnotesize}
% Graph styles
\tikzstyle{vertex}=[circle,fill=black!50,minimum size=15pt,inner sep=0pt, font=\small]
\tikzstyle{selected vertex} = [vertex, fill=red!24]
\tikzstyle{edge} = [draw,thick,-]
\tikzstyle{dedge} = [draw,thick,->]
\tikzstyle{weight} = [font=\scriptsize,pos=0.5]
\tikzstyle{selected edge} = [draw,line width=2pt,-,red!50]
\tikzstyle{ignored edge} = [draw,line width=5pt,-,black!20]
\begin{document}
\maketitle
\begin{frame}{Welcome}
\bi
\item T-414-AFLV, Árangursrík forritun og lausn verkefna
\vspace{10pt}
\item Bjarki Ágúst Guðmundsson, {\alert{bjarkig12@ru.is}}
\item Tómas Ken Magnússon, {\alert{tomasm12@ru.is}}
\ei
\end{frame}
\begin{frame}{Goal}
\bi
\item Given a problem, we want to
\bi
\item solve it efficiently
\item by using algorithms and data structures,
\item convert our solution into a program,
\item do it as quickly as possible (under pressure)
\item and do it correctly (without bugs)
\ei
\vspace{20pt}
\item This course will exercise this process
\ei
\end{frame}
\begin{frame}{How?}
\bi
\item Study common types of problems
\item Show common applications of algorithms and data structures you already know from
\bi
\item Reiknirit (the algorithms course)
\item Gagnaskipan (the data structures course)
\ei
\item Introduce other common algorithms and data structures
\item Go over some commonly used theory
\item Practice problem solving
\item Practice programming
\item More practice
\item More practice
\ei
\end{frame}
\begin{frame}{Course book}
\bi
\item \alert{Competitive Programming} by Steven Halim
\item First edition can be downloaded from the book homepage:
\item \textbf{https://sites.google.com/site/stevenhalim/}
\vspace{10pt}
\item We will loosely follow the first edition
\item There's also a 2nd and 3rd edition (both should be compatible with our course), but they need to be ordered online
\ei
\end{frame}
\begin{frame}{Piazza}
\bi
\item Piazza can be used to ask questions
\item \textbf{https://piazza.com/class/in9iwmhczfd1dv}
\ei
\end{frame}
\begin{frame}{Course schedule}
\scriptsize
\begin{center}
\begin{tabular}{cl|ll}
Class no. & Date & Topics & Activities \\
\hline
1 & 25.04 & Introduction & \\
2 & 26.04 & Data structures and libraries & \\
3 & 27.04 & Data structures & \\
4 & 28.04 & Problem solving paradigms & \\
5 & 29.04 & Greedy algorithms & Problem session I \\
\hline
& 30.04 & & \\
& 01.05 & & Problem sets week 1 \\
\hline
6 & 02.05 & Dynamic programming & \\
7 & 03.05 & Unweighted graphs & \\
8 & 04.05 & Graphs & \\
9 & 05.05 & Network flow & \\
10 & 06.05 & & Problem session II \\
\hline
& 07.05 & & \\
& 08.05 & & Problem sets week 2 \\
\hline
11 & 09.05 & Mathematics & \\
12 & 10.05 & Strings & \\
13 & 11.05 & Geometry & \\
14 & 12.05 & & \\
15 & 13.05 & & Final exam \\
\hline
& 14.05 & & \\
& 15.05 & & Problem sets week 3, Bonus problems \\
\hline
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Problem sets}
\bi
\item Each class covers a topic
\item A talk about the topic before noon
\item After noon you get a set of problems about that topic
% \item You should solve them individually
% \item You can solve the problems in groups of up to three people, but each individual must hand in their own code
\item Groups of up to three people can discuss the problems, but each individual must write and hand in their own code
\bi
\item We will check for similar submissions, and take action if we think that people are cheating
\ei
\ei
\end{frame}
\begin{frame}{Problem sets}
\bi
\item Each problem set has 5 problems
\item Each problem is assigned some amount of points
\item To get a perfect score you need to get at least a certain amount of points
\item The grade follows linearly from the number of points you get
\bi
\item If you get 85\%{} of the required points, your grade is 8.5
\item If you get 50\%{} of the required points, your grade is 5.0
\item If you get 100\%{} or more of the required points, your grade is 10.0
\ei
\vspace{10pt}
\item The deadline for a problem set is the following Sunday
\item Except for Friday's problem set, which is handed in the Sunday next week
\ei
\end{frame}
\begin{frame}{Bonus problems}
\bi
\item Each problem set contains two challenging bonus problems
\item Deadline for all bonus problems is the same as the deadline for the last problem set
\item Bonus problems are only taken into account if the student would pass the course before they're taken into account
\ei
\end{frame}
\begin{frame}{Late handins, partial grading}
\bi
\item Late handins will not be accepted
\bi
\item There should be more than enough time for each problem set
\ei
\item Solutions will not be partially graded %, either they're correct or they aren't
\ei
\end{frame}
\begin{frame}{Problem sessions}
\bi
\item On each Friday is a programming contest
\item Problems will be related to topics covered so far
\item Teams of up to three people compete together
\item Each team can only use a single computer
\ei
\end{frame}
\begin{frame}{Final exam}
\bi
\item Will be held on the last Friday
\item Similar to a problem set from all the topics
\vspace{10pt}
\item Need to pass the exam to pass the course
\ei
\end{frame}
\begin{frame}{Course evaluation}
\begin{center}
\begin{tabular}{lr}
Problem sets & $70\%$ \\
Problem sessions & $10\%$ \\
Final exam & $20\%$ \\
Bonus problems & $20\%$ \\
\hline
Total & $120\%$ \\
\end{tabular}
\end{center}
\bi
\item Remember that bonus problems are only considered if the student
passes the course, and is only used to raise the final grade
\item A final grade greater than 10 will be reduced down to 10
\ei
\end{frame}
\section{Introduction}
\begin{frame}{The problems}
\bi
\item Typical programming contest problems
\item Usually consists of
\bi
\item Problem description
\item Input description
\item Output description
\item Example input/output
\item A time limit in seconds
\item A memory limit in bytes
\ei
\item You are asked to write a program that solves the problem for all valid inputs
\item The program must not exceed time or memory limits
\ei
\end{frame}
\begin{frame}{Example problem}
\begin{block}{Problem description}
Write a program that multiplies pairs of integers.
\end{block}
\vspace{10pt}
\begin{block}{Input description}
Input starts with one line containing an integer $T$, where $1\leq T \leq
100$, denoting the number of test cases. Then $T$ lines follow, each
containing a test case. Each test case consists of two integers $A,B$,
where $-2^{20} \leq A,B \leq 2^{20}$, separated by a single space.
\end{block}
\vspace{10pt}
\begin{block}{Output description}
For each test case, output one line containing the value of $A\times B$.
\end{block}
\end{frame}
\begin{frame}{Example problem}
\begin{center}
\begin{tabular}{|l|l|}
\hline
{\footnotesize Sample input} & {\footnotesize Sample output} \\
\hline
\begin{minipage}{80pt}
\vspace{10pt}
\ttfamily
4\\
3 4\\
13 0\\
1 8\\
100 100\\
\end{minipage}
&
\begin{minipage}{80pt}
\vspace{10pt}
\ttfamily
12\\
0\\
8\\
10000\\
\end{minipage}
\\
\hline
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[fragile]{Example solution}
\begin{minted}[fontsize=\scriptsize]{cpp}
#include
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
\end{minted}
\bi
\onslide<2->{\item Is this solution correct? \onslide<5->{\alert{No!}}}
\onslide<3->{\item What if $A = B = 2^{20}$? \onslide<4->{The output is $0$...}}
\ei
\end{frame}
\begin{frame}[fragile]{Example solution}
\bi
\item When $A = B = 2^{20}$, the answer should be $2^{40}$
\onslide<2->{\item Too big to fit in a 32-bit integer, so it overflows}
\onslide<3->{\item Using 64-bit integers should be enough}
\ei
\end{frame}
\begin{frame}[fragile]{Example solution}
\begin{minted}[fontsize=\scriptsize]{cpp}
#include
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
long long A, B;
cin >> A >> B;
cout << A * B << endl;
}
return 0;
}
\end{minted}
\bi
\onslide<2->{\item Is this solution correct? \onslide<3->{{\alert{Yes!}}}}
\ei
\end{frame}
\begin{frame}{Automatic judging}
\bi
\item The problems will be available on \alert{Kattis}:
\item \textbf{https://ru.kattis.com/}
\vspace{20pt}
\item Kattis is an online judge, similar to Mooshak
\item You will submit your solutions to Kattis, and get immediate feedback about the solution
\item You can submit in any of the supported languages:
\bi
\item C
\item C++
\item Java
\item Python 2
\item Python 3
\item C\#{}
\item and others
\ei
\ei
\end{frame}
\begin{frame}{Judge verdicts}
\bi
\item Feedback about solutions is limited
\item You will (usually) receive one of:
\bi
\item Accepted
\item Wrong Answer
\item Compile Error
\item Run Time Error
\item Time Limit Exceeded
\item Memory Limit Exceeded
\ei
\item We will not reveal which test cases Kattis uses to test your solution
\ei
\end{frame}
\begin{frame}{Tips}
\bi
\item There are a couple of tips and guidelines you can keep in mind towards becoming a more effective programmer and better problem solver
\ei
\end{frame}
\begin{frame}{Tip 0: Faster typing}
\bi
\item Become a faster/better typist
\item Don't let your fingers be the limiting factor of solving problems quickly
\item Good problem solvers have simple solutions; they don't have to type as much, but it's still important to type in quickly
\vspace{20pt}
\item TypeRacer is a fun and effective way to practice:
\item \textbf{http://play.typeracer.com/}
\ei
\end{frame}
\begin{frame}{Tip 1: Quickly classify problems}
\bi
\item Practice quickly identifying problem types
\vspace{10pt}
\item Rate of appearance of different problem types in recent ICPC Asia Regional problem sets (which usually consists of 7-11 problems):
\ei
\vspace{5pt}
{
\scriptsize
\begin{center}
\begin{tabular}{ccc}
Category & Sub-Category & Frequency \\
\hline
Ad Hoc & Straightforward & 1-2 \\
Ad Hoc & Simulation & 0-1 \\
Complete Search & Iterative & 0-1 \\
Complete Search & Backtracking & 0-1 \\
Divide \&{} Conquer & & 0-1 \\
Greedy & Classic & 0 \\
Greedy & Original & 1 \\
Dynamic Programming & Classic & 0 \\
Dynamic Programming & Original & 1-3 \\
Graph & & 1-2 \\
Mathematics & & 1-2 \\
String Processing & & 1 \\
Computational Geometry & & 1 \\
Harder Problems & & 0-1 \\
\end{tabular}
\end{center}
}
\end{frame}
\begin{frame}{Tip 2: Do Algorithm Analysis}
\bi
\item When solving a problem, our solution has to be fast enough and can not use too much memory
\item We also want our solution to be as simple as possible
\vspace{5pt}
\item We can use Algorithm Analysis to determine if a solution will run within the time limit
\item Rule of thumb: $10^{8}$ operations per second
\vspace{10pt}
\item<2-> We want to sort $n \leq 10^{6}$ integers, and we have 3 seconds.
\bi
\item Can we use a simple $O(n^2)$ bubble sort?
\item What about a more complex $O(n\log n)$ merge sort?
\ei
\vspace{5pt}
\item<3-> We want to sort $n \leq 10^{3}$ integers, and we have 3 seconds.
\bi
\item Can we now use the simple $O(n^2)$ bubble sort?
\ei
\vspace{5pt}
\item<4-> Always go for the simplest solution that will pass the time limit
\ei
\end{frame}
\begin{frame}{Tip 2: Do Algorithm Analysis}
\bi
\item You should practice doing approximate mental calculations
\item Rule of thumb: $2^{10} \approx 10^{3}$
\vspace{10pt}
\item Sometimes you have a solution that you're not sure is correct
\item Try to prove it's correct!
\item Even if you don't manage to prove or disprove it, you will probably get a better understanding of the problem
\vspace{20pt}
\ei
\end{frame}
\begin{frame}{Tip 2: Do Algorithm Analysis}
\vspace{10pt}
{
\scriptsize
\begin{center}
\begin{tabular}{c|c|c}
$n$ & Slowest Accepted Algorithm & Example \\
\hline
$\leq 10$ & $O(n!), O(n^6)$ & Enumerating a permutation \\
$\leq 15$ & $O(2^n\times n^2)$ & DP TSP \\
$\leq 20$ & $O(2^n), O(n^5)$ & DP + bitmask technique \\
$\leq 50$ & $O(n^4)$ & DP with 3 dimensions + $O(n)$ loop, choosing $_nC_4$ \\
$\leq 10^2$ & $O(n^3)$ & Floyd Warshall's \\
$\leq 10^3$ & $O(n^2)$ & Bubble/Selection/Insertion sort \\
$\leq 10^5$ & $O(n\log_2{n})$ & Merge sort, building a Segment tree \\
$\leq 10^6$ & $O(n), O(\log_2{n}), O(1)$ & Usually, contest problems have $n\leq10^6$ (to read input) \\
\end{tabular}
\end{center}
}
\end{frame}
\begin{frame}{Tip 3: Master Programming Languages}
\bi
\item You should know your programming language like the back of your hand
\item This includes your programming language's library
\bi
\item C++'s Standard Template Library
\item The Java Class Library
\ei
\item If it's already implemented in the standard library, you usually don't need to implement it yourself
\ei
\end{frame}
\begin{frame}{Tip 4: Test your solution}
\bi
\item You want to make sure your solution is correct and runs within the time limit
\item Or you already know it's wrong, but don't know why
\vspace{10pt}
\item Try to break your solution by finding a counterexample (an input for which your solution gives incorrect output, or takes too long to compute an answer)
\item Try edge cases, large inputs, ...
\ei
\end{frame}
\begin{frame}{Tip 5: Practice and more practice}
\bi
\item Problem solving and programming skills come with practice
\item Lots of online judges that let you solve problems from past contests
\item Some of these online judges also hold contests frequently
\item Open Kattis, Codeforces, HackerRank, Codechef, UVa, TopCoder, ...
\ei
\end{frame}
\section{Ad Hoc Problems}
\begin{frame}{Ad Hoc problems}
\bi
\item The simplest kind of problem
\item Just do what the problem description tells you
\item Straightforward or a simulation
\item Time limit is not an issue
\item Sometimes long and misleading problem descriptions
\item Sometimes tricky edge cases
\item Complex problems can be hard to implement
\ei
\end{frame}
\begin{frame}{Problem: Cost Cutting}
\vspace{10pt}
{
\small
Company XYZ have been badly hit by recession and is taking a lot of cost cutting measures. Some of these measures include giving up office space, going open source, reducing incentives, cutting on luxuries and issuing pink slips.
\vspace{10pt}
They have got three (3) employees working in the accounts department and are going to lay-off two (2) of them. After a series of meetings, they have decided to dislodge the person who gets the most salary and the one who gets the least. This is usually the general trend during crisis like this.
You will be given the salaries of these 3 employees working in the accounts department. You have to find out the salary of the person who survives.
}
\end{frame}
\begin{frame}{Problem: Cost Cutting}
\begin{block}{Input}
{\small
The first line of input is an integer $T$ ($T<20$) that indicates the number of test cases. Each case consists of a line with 3 distinct positive integers. These 3 integers represent the salaries of the three employees. All these integers will be in the range $[1000, 10000]$.
}
\end{block}
\vspace{20pt}
\begin{block}{Output}
{\small
For each case, output the case number followed by the salary of the person who survives.
}
\end{block}
\end{frame}
\begin{frame}{Problem: Cost Cutting}
\begin{center}
\begin{tabular}{|l|l|}
\hline
{\footnotesize Sample input} & {\footnotesize Sample output} \\
\hline
\begin{minipage}{100pt}
\vspace{10pt}
\ttfamily
3\\
1000 2000 3000\\
3000 2500 1500\\
1500 1200 1800\\
\end{minipage}
&
\begin{minipage}{100pt}
\vspace{10pt}
\ttfamily
Case 1: 2000\\
Case 2: 2500\\
Case 3: 1500\\
\end{minipage}
\\
\hline
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[fragile]{Cost Cutting: Solution}
\begin{minted}[fontsize=\scriptsize]{cpp}
#include
#include
using namespace std;
int main() {
int T;
scanf("%d", &T);
for (int t = 0; t < T; t++) {
int salary[3];
scanf("%d", &salary[0]);
scanf("%d", &salary[1]);
scanf("%d", &salary[2]);
sort(salary, salary + 3);
printf("Case %d: %d\n", t + 1, salary[1]);
}
return 0;
}
\end{minted}
\end{frame}
\begin{frame}{Problem: SMS Typing}
{\small
Cell phones have become an essential part of modern life. In addition to
making voice calls, cell phones can be used to send text messages, which
are known as SMS for short. Unlike computer keyboards, most cell phones
have limited number of keys. To accommodate all alphabets, letters are
compacted into single key. Therefore, to type certain characters, a key
must be repeatedly pressed until that character is shown on the display
panel.\\
\vspace{10pt}
In this problem we are interested in finding out the number of times keys on a cell phone must be
pressed to type a particular message.
}
\end{frame}
\begin{frame}{Problem: SMS Typing}
{
\small
In this problem we will assume that the key pad of our cell phone is arranged as follows.
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& abc & def \\
\hline
ghi & jkl & mno \\
\hline
pqrs & tuv & wxyz \\
\hline
& & \\
\hline
\end{tabular}
\end{center}
In the above grid each cell represents one key. Here means a space. In order to type the letter
‘a’, we must press that key once, however to type ‘b’ the same key must be repeatedly pressed twice
and for ‘c’ three times. In the same manner, one key press for ‘d’, two for ‘e’ and three for ‘f’. This is
also applicable for the remaining keys and letters. Note that it takes a single press to type a space.
}
\end{frame}
\begin{frame}{Problem: SMS Typing}
\begin{block}{Input}
{\small
The first line of input will be a positive integer $T$ where $T$ denotes the number of test cases. $T$ lines
will then follow each containing only spaces and lower case letters. Each line will contain at least 1 and
at most 100 characters.
}
\end{block}
\vspace{20pt}
\begin{block}{Output}
{\small
For every case of input there will be one line of output. It will first contain the case number followed
by the number of key presses required to type the message of that case. Look at the sample output for
exact formatting.
}
\end{block}
\end{frame}
\begin{frame}{Problem: SMS Typing}
\begin{center}
\begin{tabular}{|l|l|}
\hline
{\footnotesize Sample input} & {\footnotesize Sample output} \\
\hline
\begin{minipage}{150pt}
\vspace{10pt}
\ttfamily
2\\
welcome to ulab\\
good luck and have fun\\
\end{minipage}
&
\begin{minipage}{100pt}
\vspace{10pt}
\ttfamily
Case \#{}1: 29\\
Case \#{}2: 41\\
\end{minipage}
\\
\hline
\end{tabular}
\end{center}
\end{frame}
\begin{frame}[fragile]{SMS Typing: Solution}
\begin{minted}[fontsize=\scriptsize]{cpp}
#include
#include
#include
using namespace std;
string keys[12] = {
"", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz",
"", " ", ""
};
int main() {
int T;
scanf("%d\n", &T);
for (int t = 0; t < T; t++) {
// Each test case is handled here
}
return 0;
}
\end{minted}
\end{frame}
\begin{frame}[fragile]{SMS Typing: Solution}
\begin{minted}[fontsize=\scriptsize]{cpp}
// Each test case:
string line;
getline(cin, line);
int cnt = 0;
for (int i = 0; i < line.size(); i++) {
int cur;
for (int j = 0; j < 12; j++) {
for (int k = 0; k < keys[j].size(); k++) {
if (line[i] == keys[j][k]) {
cur = k + 1;
}
}
}
cnt += cur;
}
printf("Case #%d: %d\n", t + 1, cnt);
\end{minted}
\end{frame}
\begin{frame}{Problem set 1}
\bi
\item The first problem set is already online
\item Deadline is next Sunday
\item We urge you to start right away nonetheless
\ei
\end{frame}
\end{document}