Class 01: Introduction

“Art of thinking”

What is competitive programming?

It’s a sport… a mind sport
Participants are given problems and they have to create computer programs to solve them as quickly as they can
There are many type of problems that we will learn later…

Topics of the course

Asymptotic Analysis
Standard Template Library
Brute Force
Divide and Conquer
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

3 0

Output
343

Veredicts information

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

Other veredicts

Environment setup

Choose a IDE or a text editor

Select a programming language allowed in most online judges

C++
Python
Java
Kotlin

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

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.

Code

#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.

Code

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

B: Threatre Square

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.

Code

#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\))

C: Way Too Long Words

Problem C: Way Too Long Words

Just implement what the problem say.

Code

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

Class 01: Introduction

01-06-2020

Example

Problem A: Watermelon

Problem B: Theatre Square

Problem C: Way Too Long Words