1 of 15

Intro to CP

Jeffrey, Autumn, Steven, and Joshua

Sep 28, 2021

2 of 15

Admin stuff

  • COVID Forms
    • Fill out MCPS ECA forms; submit to MCPS and on our Sign-Up Form
    • Scan QR code and fill out a different form each meeting
  • Fill out the sign-up form:
    • compteam.mbhs.edu/signupform
    • Access Code:
  • Meeting material and other resources available on our website
    • compteam.mbhs.edu
  • Join our Discord!
    • https://discord.gg/MQbw6ddKbu

Sign-Up Form

Discord

3 of 15

Today’s Agenda

Beginner

  • What is Competitive Programming?
  • Coding Time!! :)

Advanced

  • Coding Time!! :)

4 of 15

What is CP?

  • Competitive programming (CP) is a mind sport
  • Focuses on algorithmic programming
  • Solve well-defined mathematical problems
  • Strict time limits, memory limits, and some other constraints
  • Competitive because you compete with other coders on a clock
  • Forces you to write effective, efficient code

5 of 15

Technical Details

  • Many languages���
    • Consider: time/space, familiarity, coding speed
  • Input/output may use standard I/O streams or files
  • Submit solutions by file upload or by pasting in code

​

C++

Java

Python

C

PyPy

Kotlin

Rust

PHP

USACO

​

​

​

​

​

​

​

​

Practice sites

​

​

​

​

​

​

​

​

Most "real" CP contests

​

​

​

​

​

​

​

​

6 of 15

More Technical Details

  • Contest consists of multiple problems
  • Earn points for solving problems or test cases
  • Some contests give penalties
    • Failed attempts
    • Submission time
  • Mechanics of scoring might differ
    • Point allocation
    • Test case sets
  • Hidden/visible verdicts or cases
  • Hacking on some practice sites

​

7 of 15

Structure of Problems

  • Information provided:
    • Task description
    • Time and memory limits
    • Description of input/output (i.e. format)
    • Constraints (e.g. # test cases, bounds of input, etc.)
    • Sample cases

​

8 of 15

Test Case Verdicts

  • Judge verdicts:
    • X (incorrect answer)
    • TLE (time limit exceeded)
    • Memory limit exceeded
    • Run-time error
    • Compilation error

9 of 15

Sample problem 1 (stream I/O)

10 of 15

Solution 1

t = int(input())

for i in range(t):

n=int(input())

for val in range(n):

print("()"*val+"("*(n-val) + ")"*(n-val))

​

11 of 15

Sample problem 2 (file I/O)

12 of 15

Solution 1

#include <iostream>

using namespace std;

​

int psum1[100001];

int psum2[100001];

int psum3[100001];

int a[100001];

int n, q;

​

int main() {

freopen("bcount.in", "r", stdin);

freopen("bcount.out", "w", stdout);

cin >> n >> q;

for(int i=1; i<=n; i++){

cin >> a[i];

}

for(int i=1; i<=n; i++){

psum1[i]=psum1[i-1];

psum2[i]=psum2[i-1];

psum3[i]=psum3[i-1];

if(a[i]==1) psum1[i]++;

if(a[i]==2) psum2[i]++;

if(a[i]==3) psum3[i]++;

}

for(int i=1; i<=q; i++){

int a, b; cin >> a >> b;

cout << psum1[b]-psum1[a-1] << " " << psum2[b]-psum2[a-1] << " " << psum3[b]-psum3[a-1] << '\n';

}

return 0;

}

​

13 of 15

Practice problems

14 of 15

Practice problems hints

​

15 of 15

Questions?

Topic requests?

compteam.mbhs.edu/feedback

​

Material from today: https://compteam.mbhs.edu/curriculum#meeting2-card

​

Make sure you’ve filled out the daily club check-in form:

https://compteam.mbhs.edu/clubcheckin