“Art of thinking”

What is competitive programming?
  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
Topics of the course
  1. Asymptotic Analysis
  2. Standard Template Library
  3. Brute Force
  4. Divide and Conquer
  5. Game Theory
Virtual Judges

Problem structure
  • 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.

Constrains:
- \(2 \leq n \leq 10^8\)
- Time limit: 1 second
- Memory limit per test: 256 megabytes

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

Output:
The greatest sum

Example:
Input
10

3 4 2 30 104 1 35 104 239 -1

2

3 0

Output
343

3

Veredicts information
  • AC - Accepted
  • WA - Wrong Answer
  • TLE - Time Limit Exceeded
  • RE - Runtime Error

Other veredicts

Environment setup
  1. Choose a IDE or a text editor
  1. Select a programming language allowed in most online judges
  • C++
  • Python
  • Java
  • Kotlin
  1. 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:

Contest

You can find the contest here.

Problem A: Watermelon

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.

#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);
}

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.

#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);
}

Problem B: Theatre Square

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.

#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);
}

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

Problem C: Way Too Long Words

Just implement what the problem say.

#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);
}