class-01.Rmd

---
title: "Class 01: Introduction"
date: "01-06-2020"
---

```{r setup, include=FALSE}
htmltools::tagList(rmarkdown::html_dependency_font_awesome())
```

> "Art of thinking"

<div class="topic">What is competitive programming?</div>

1. It's a sport... **a mind sport**
2. Participants are given problems and they have to create computer programs to solve them as quickly as they can
3. There are many type of problems that we will learn **later**...

<div class="topic">Topics of the course</div>

1. Asymptotic Analysis
2. Standard Template Library
3. Brute Force
4. Divide and Conquer
5. Game Theory

<div class="topic">Virtual Judges</div>

<div style="border:1px solid black; background: white;">
<a href="https://codeforces.com/" target="_blank">![](./images/class-01/codeforces.png)</a>
<a href="https://atcoder.jp/" target="_blank">![](./images/class-01/atcoder.png)</a>
<a href="https://www.codechef.com/" target="_blank">![](./images/class-01/codechef.png)</a>
<a href="https://www.spoj.com/" target="_blank">![](./images/class-01/spoj.png)</a>
<a href="https://www.hackerearth.com/" target="_blank">![](./images/class-01/hackerearth.png)</a>
</div>

<div class="topic">Problem structure</div>

* Title and limitations
* Description
* Input and Output (I/O)
* Examples

### Example

**Problem:** You're given **n** numbers and you'd like to find a pair of numbers with the greatest sum. <br>

**Constrains:** <br>
- $2 \leq n \leq 10^8$ <br>
- Time limit: 1 second <br>
- Memory limit per test: 256 megabytes <br>

**Input:** <br>
The first line of each input a single integer n denoting the number of values. The next lines containg the n values.

**Output:** <br>
The greatest sum

**Example:** <br>
*Input* <br>
10

3 4 2 30 104 1 35 104 239 -1

2

3 0

*Output* <br>
343

3

<div class="topic">Veredicts information</div>

- <div style="color: green">AC - Accepted</div>
- <div style="color: red">WA - Wrong Answer</div>
- <div style="color: blue">TLE - Time Limit Exceeded</div>
- <div style="color: orange">RE - Runtime Error</div>

[Other veredicts](https://icpcarchive.ecs.baylor.edu/index.php?option=com_content&task=view&id=14&Itemid=30)

<div class="topic">Environment setup</div>

1. Choose a IDE or a text editor

- [CLion](https://www.jetbrains.com/es-es/clion/)
- [DevC++](https://www.bloodshed.net/dev/)
- [CodeBlocks](http://www.codeblocks.org/)
- [Visual Studio Code](https://code.visualstudio.com/)
- [Atom](https://atom.io/)
- [Sublime](https://www.sublimetext.com/)
- [Vim](https://www.vim.org/)
- [Emacs](https://www.gnu.org/software/emacs/)

2. Select a programming language allowed in most online judges
- C++
- Python
- Java
- Kotlin

3. Always prefer C++ for competitive programming
- Lower level $\rightarrow$ More control
- It's faster
- Makes better use of memory
- The STL is extremaly powerful
- Almost all learning resources in competitive programming are oriented to C++
- It has a strong community

Recommended readings:

- [Training Camp Argentina 2019. Nivel Inicial. E/S + Intro](https://tc-arg.tk/pdfs/2019/ipc.pdf)
- [Competitive Programming 3, chapter 1](https://cpbook.net/)
- [Errichto - How to test your solutions in Competitive Programming, on Linux](https://www.youtube.com/watch?v=JXTVOyQpSGM)
- [An awesome list for competitive programming](https://codeforces.com/blog/entry/23054)


<div class="topic" id="contest">Contest</div>

You can find the contest [here](https://vjudge.net/contest/350658).

<!-- Begins problem A -->
<div class="card">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemA" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">A: Watermelon</p>
</div>
<!-- begin body -->
<div id="collapseProblemA" class="collapse">
<div class="card-body solution-body">

### <a href="https://codeforces.com/problemset/problem/4/A" target="_blank">Problem A: Watermelon</a>

The problem is bassically to find

$a, b \mid 1 \leq a, b \leq n / 2 \land 2a + 2b = n$

The following code use this idea.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemA1" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemA1" class="collapse">
  
```c++
#include <bits/stdc++.h>

using namespace std;

int main () {
  int n;
  cin >> n;
  bool ok = false;
  for (int a = 1; a <= n / 2; a++) {
    for (int b = 1; b <= n / 2; b++) {
      if (2 * a + 2 * b == n) ok = true;
    }
  }
  if (ok) cout << "YES\n";
  else cout << "NO\n";
  return (0);
}
```
  </div>
  <!-- ends code -->

But, we can take $b = 1$ (**why?**) and realize that the problem reduces to find:

$a \leq 1 \leq a \leq n / 2 \land 2a = n - 2$

The following code use this idea.


  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemA2" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemA2" class="collapse">
  
```c++
#include <bits/stdc++.h>

using namespace std;

int main () {
  int n;
  cin >> n;
  bool ok = false;
  if (n - 2 >= 2 and n % 2 == 0) ok = true;
  if (ok) cout << "YES\n";
  else cout << "NO\n";
  return (0);
}
```
  </div>
  <!-- ends code -->


</div>
</div>
</div>
<!-- ends problem A -->




<!-- Begins problem B -->
<div class="card">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemB" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">B: Threatre Square</p>
</div>
<!-- begin body -->
<div id="collapseProblemB" class="collapse">
<div class="card-body solution-body">

### <a href="https://codeforces.com/problemset/problem/1/A" target="_blank">Problem B: Theatre Square</a>

Basically we need to find $x * y$ where

$x = min\{x \mid x * a \geq n\}$

$y = min\{y \mid y * a \geq m\}$

Then, $$x = \lceil \frac{n}{a} \rceil \land y = \lceil \frac{m}{a} \rceil $$

And there is also the property:

$$\lceil a / b \rceil = \lfloor (a + b - 1) / b \rfloor$$

The following code use this idea.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemB" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemB" class="collapse">
  
```c++
#include <bits/stdc++.h>

using namespace std;

int main () {
  long long n, m, a;
  cin >> n >> m >> a;
  long long x = (n + a - 1) / a;
  long long y = (m + a - 1) / a;
  cout << x * y << '\n';
  return (0);
}
```
  </div>
  <!-- ends code -->

What happen if we use `int` instead of `long long` (try $n = m = 10^9, a = 1$)

</div>
</div>
</div>
<!-- ends problem B -->




<!-- Begins problem C -->
<div class="card">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemC" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">C: Way Too Long Words</p>
</div>
<!-- begin body -->
<div id="collapseProblemC" class="collapse">
<div class="card-body solution-body">

### <a href="https://codeforces.com/problemset/problem/71/A" target="_blank">Problem C: Way Too Long Words</a>

Just implement what the problem say.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemC" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemC" class="collapse">
  
```c++
#include <bits/stdc++.h>

using namespace std;

int main () {
  int tc;
  cin >> tc;
  while (tc--) {
    string s;
    cin >> s;
    if (s.size() > 10) cout << s.front() << s.size() - 2 << s.back() << '\n';
    else cout << s << '\n';
  }
  return (0);
}
```
  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem C -->

<p style="float: none; clear: both;"></p>

<div style="float: right;" class="pt-3">	
  <a class="continue-link" href="./class-02.html" 
     data-toggle="tooltip" title="Asymptotic Analysis">
  Next
  </a>
</div>

<script>
  $('#all-classes').collapse('show');
  $('#class-01').addClass('active');
  const cur_class = document.getElementById('class-01');
  cur_class.scrollIntoView({
    behavior: 'smooth',
    block: 'center'
  });
</script>