Week 1

Programming Review - Array/List + other misc things

​

Intermediate

INTRODUCTIONS

What’s your name, grade, and favorite summer activity?

Housekeeping

The boring stuff before we get to programming….

What?

We are Tyee PROGRAMMING COMPETITION Club. Our mission is for you to get experience in programming by connecting with experts and introducing you to new programming concepts

Expect that we will cover a new topic every meeting.

In-person meetings are only once every month because we recognize that it may be hard to code in a different environment other than the one you’re used too. Also tech often doesn’t work and as a programming club we rely on tech…….

Homework

THE ONLY WAY TO IMPROVE IS TO PRACTICE.

​

Expect 3-4 programming problems per week.

Be good students

YOU ARE STILL AT SCHOOL. SCHOOL RULES STILL APPLY.

Please respect the place. Tyee have generously given us access to the school. If we trash the entire place, TPCC is no more…

We say these things because they have happened to other clubs

Join the Google Classroom

Introduction to Competitive Programming

https://usaco.guide/general/intro-cp

CP Initiative

joincpi.org

The Basics

At a (very) high level, competitive programming involves programmers competing against each other to solve programming questions in a limited amount of time. Often, the objective is to achieve the expected output to a problem for any arbitrary input without having your program take too long to run for complex inputs.

CP Initiative

joincpi.org

Programming Competitions

Competitive programmers partake in–as you could probably guess by the name–programming competitions. These competitions usually last for several hours and consist of a set of problems solved by the competitors in code.

After coming up with an algorithm to solve the problems, a grader tests your code against hidden test cases to make sure your solution works. It is important to come up with scalable solutions, because most test cases have a 2 second time limit and a 256 megabyte memory limit.

CP Initiative

joincpi.org

Competitive Programming vs Software Engineering

While many of the same skills are involved in competitive programming and software engineering, it is worth noting that in competitive programming, unlike software engineering, maintainability of code is not a priority. Often times, a competitive programmer’s code may not make sense to another programmer, but as long as the code works, it’s fine. In contrast, software engineers typically work with a team to develop sustainable software, so practices like documentation and clear variable names are important.

CP Initiative

joincpi.org

USACO

And that brings us to The USA Computing Olympiad, or USACO! USACO is a national programming competition (although coders from around the world compete as well) that has 4 competitions every year: December, January, February, and US Open (March). The first three are four hours long, and the US Open is five hours long. Each contest has three problems with numerous test cases, and the three problems are weighted equally at ~333 points for a maximum of 1,000 points.

There are four divisions: Bronze, Silver, Gold, and Platinum. After every competition, there is a promotion cutoff that competitors must meet to climb to a higher division for future competitions.

CP Initiative

joincpi.org

CP Initiative

joincpi.org

Programming Life Hacks

You will use these.

Master them!

Input & Output

https://usaco.guide/general/input-output

CP Initiative

joincpi.org

Reading Input

In most contests, standard streams are used for reading input and writing output.

• In C++, the standard streams are cin for input and cout for output.
• In addition, the C functions scanf and printf can be used.
• In Java, they are Scanner and System.out.print()
• However, BufferedReader and PrintWriter are faster for large input (tens of thousands of lines!) and generally preferred over Scanner and System.out.print()
• In Python, they input() and print()
• However, like Scanner in java, they are much slower compared to stdin and stdout, which are preferred over input() and print()

​

CP Initiative

joincpi.org

Topic 1: Getting values on one line

Problem Statement:

Input N numbers and compute their product

​

Input Format:

First line will have the number N

Second line will contain all N numbers, separated by spaces

​

Sample Input

6

1 2 3 4 5 6

​

Sample Output:

720

​

CP Initiative

joincpi.org

How to do it

map() for Python or list comprehensions: []

​

Loop with cin >> for c++

​

Java use Scanner.nextInt()

​

# Source: https://usaco.guide/general/io

​

n = int(input())

numbers = [int(num) for num in input().split()]

​

product = 1

​

for num in numbers:

product = product * num

​

print(product)

​

CP Initiative

joincpi.org

print() - Python

format() - Python

print(), println() - Java

printf() - Java

Reading from a file

C++ Method 1: freopen

You will need the <cstdio> library. The freopen statements reuse standard I/O for file I/O. Afterwards, you can simply use cin and cout (or scanf and printf) to read and write data. To test your solution locally without file I/O, just comment out the lines with freopen.

For convenience, we can define a function that will redirect stdin and stdout based on the problem name:

​

C++ Method 2: fstream

​

​

​

​

​

​

Note: You cannot use C-style I/O (scanf, printf) with this method.

Java: BufferedReader and PrintWriter

​

​

​

​

​

​

Note how static initialization of r and pw is slightly different.

Java I/O Template: Kattio

The following template (a shortened version of Kattis's Kattio.java) wraps BufferedReader and PrintWriter and takes care of the string processing for you. You can find the full code at usaco.guide

Python File Input/Output

The most intuitive way to do file I/O in Python is by redirecting the system input and output to files. After doing this, you can then use the above input() and print() methods as usual. See here for documentation about file I/O.

​

A different approach to file I/O in Python is to still use the open() method, but use the built-in functions .readline() or .readlines():

​

Arrays

So you don’t make 1000000 variables

Array / List

Accessing 2D Array

Python

​

A = [[1, 2, 3], [4,5,6], [7,8,9]]

print(A[0][2]) # This will print out 3

print(A[2][2]) # This will print out 9

Java

​

int arr[][] = {{1,2,3},{4,5,6},{7,8,9}};

// This will print out 3

System.out.println(arr[0][2]);

// This will print out 9

System.out.println(arr[2][2]);

C++

​

int arr[3][3] = {{1,2,3},{4,5,6},{7,8,9}};

// This will print out 3

cout << arr[0][2] << endl;

// This will print out 9

cout << arr[2][2] << endl;

Notice that declaring and access 2D array is similar cross Python, Java and C++.

Know your array library - Python

• Instantiating a list:�Example: [3, 5, 7, 11], [1] + [0]*10, list(range(100))
• Basic operations:�len(A), A.append(42), A.remove(2), A.insert(3, 28)
• Instantiating a 2D array:�Example: [[1,2,4], [3,5,7,9],[13]]
• Checking if a value is present in an array:�a in A. (This operation has O(n) time complexity)�

Know your array library - Python (Cont.)

• min, max, sum:�min(A), max(A), sum(A)

​

• Instantiating a 2D array:� Example: [[1,2,4], [3,5,7,9],[13]]�

Know your array library - Python (Cont.)

• Slicing is a concise way of manipulating arrays.�Let A = [1, 6, 3, 4, 5, 2, 7]�A[2:4] is [3, 5], A[2:] is [3,4,5,2,7], A[:4] is [1,6,3,4].�A[:-1] is [1,5,3,4,5,2], A[::-1] is [7,2,5,4,3,6,1]
• List comprehension is a more concise way to create lists.�Example: [x**2 for x in range(6)] returns [0,1,4,9,16,25]
• Sorting�A.sort() (in-place), sorted(A) (returns a copy)�A.reverse() (in-place), reversed(A) (returns an iterator)

Know your array library - Java

// Ex1: declares and allocates memory for 5 integers�int[] arr = new int[5];�arr[0] = 10; // initialize the first element of the array as 10��// Ex2: initializes an array with {1,2,3,4} �int[] arr = new int[] {1,2,3,4};�

Know your array library - Java (Cont.)

// Ex3: declares an array with size 5�int[] arr = new int[5];�Arrays.fill(arr, 10); // Fill the entire array with value 10�System.out.println(Arrays.toString(arr)); // Print array��// Ex4: initializes an array with {10, 7, 3, 6} �int[] arr = new int[] {10, 7, 3, 6};�Arrays.sort(arr); // Sort array�System.out.println(Arrays.toString(arr)); // Print sorted array�

Know your array library - Cont.

• ArrayList is a resizable array, which can be found in java.util package.��import java.util.ArrayList;�// Create an arraylist object�List<String> words = new ArrayList<>();�words.add("Hello");�words.add("World");�

Practice

Teamscode

USACO Bronze Problems

TeamsCode�Easy�Magic Square

TeamsCode�Medium�Changing a 2D Array

BONUS: AtCoder Beginner Contest 081

C - Not so Diverse

https://atcoder.jp/contests/abc081/tasks/arc086_a

Problem 2 (It's Mooin' Time II)

Extra credit: USACO 2016 February Contest, Bronze

Problem 1. Milk Pails

https://usaco.org/index.php?page=viewproblem2&cpid=615

If you still have time, practice CodingBat, HackerRank or LeetCode.

Submit homework here: https://forms.gle/pRsSnatnbnE7C5vF8

Homework

• Complete problems in the “practice section”
• Two problems in either CodingBat, HackerRank or LeetCode