# 2022-Spring-CSE109-Introduction to Programming Contests

Undergraduate Seminar, *CSE, UCSD*, 2022

**Class Time**: Mondays 12PM to 12:50PM. **Room**: WLH 2204. **Piazza**: piazza.com/ucsd/spring2022/cse109.

# Additonal Course Policy for COVID-19

While the university does not close, we are still in a pandemic. Here are some additional policies specifically designed to better protect our students in this course from COVID-19 risks.

**First-week lectures online**. We will deliver the first-week lectures online, as the students on the super-long waitlist may want to attend the first lecture too and we will likely flood the physical classroom.- Zoom link for the first week: https://ucsd.zoom.us/j/92762034655

**Attendance is optional**. Podcast is enabled. You can also check out my previous offering, which has Zoom videos.

# Overview

This course introduces the algorithms and concepts necessary to compete effectively in the ACM International Collegiate Programming Contest (ICPC) and similar contests. It is highly recommended for students intending to compete in the ICPC Southern California (SoCal) Regional contest. The course requires weekly completion of short problem sets. Topics covered include standard library classes and data structures useful for programming contest problems, basic complexity analysis, dynamic programming, graph algorithms, number theory, combinatorics, computational geometry, combinatorial games, and competitive programming contest strategy.

# Prerequisites

CSE 30, must have programming competency in C++, Java, or Python. (CSE 100 highly recommended)

Most importantly, eagerness to learn and practice

# UCSD ICPC Club

UCSD ICPC Club is a student-org organized to help students learn techniques for solving problems with computer algorithms and to compete in algorithmic programming competitions. - Jingbo Shang is the faculty advisor and coach - Zihan Wang is the president and student co-coach.

# Guest Lecturer

- Zihan Wang
- Zihan is our co-coach at UCSD-ICPC Club.
- Zihan will contribute some guest lectures to the seminar.

# Office Hour

- Jingbo Shang
- Office Hour: Wednesdays, 10 to 11 AM
- Zoom link: https://ucsd.zoom.us/my/jshang

# Lecture Schedule

**Recording Note**: Please download the recording video for the full length. Dropbox website will only show you the first one hour.

Date | Topic & Slides | Homework | Additional Notes |

03/28 | Introduction | Problem Set #0 | Solutions STL Notes |

04/04 | Ad Hoc, Simulation & Search | Problem Set #1 | |

04/11 | Dynamic Programming (Simple) | Problem Set #2 | |

04/18 | Basic Graph Algorithms | Problem Set #3 | |

04/25 | Computational Geometry | Problem Set #4 | |

05/02 | Dynamic Programming (Intermediate) | Problem Set #5 | |

05/09 | Combinatorics and Algebra | Problem Set #6 | |

05/16 | Network Flow | Problem Set #7 | |

05/23 | Segment Tree | Problem Set #8 | |

05/30 | No Class (Memorial Day) |

# Homework and Grading Policy

You are required to solve the problem on the online judge site and provide the instructor with your online judge usernames for validation of your submission. **Please fill in this Google Form before you work on homework**. Don’t worry if you filled wrong information. Just fill another one. Only the last one counts.

This course provides a pass/fail grade ONLY. **Passing the course requires completion of at least 6 of the 9 problem sets**. **[Warning]** If you select this course for grade, you will only receive a B for Pass.

Completion of a problem set requires obtaining a total score of **at least 4 points** for the problem set. You can calculate your score on a problem set by summing the point value next to each problem you have solved. You may not use points from one problem set to fulfill the score requirements for another. Problem sets must be completed by 11:59 PM on the last date of Spring Quarter. That is, **11:59PM Jun 10, 2022**. **No extensions** will be given for any reason.

We encourage you to solve as many problems from each problem set as you have time to solve, even if you have completed the minimum requirements. The more practice you get in, the better your skills will become and the better you will perform during tryouts and official competitions.

Starting from Jun 3, we will calculate your grades by a web scraper and will send emails to notify you about your status at a weekly basis.

**Problem Set #0: Introduction**

- POJ 1000: A+B Problem - 0 Point
- POJ 1004: Financial Management - 0 Point
- POJ 1477: Box of Bricks - 1 Point
- POJ 3030: Nasty Hacks - 1 Point
- POJ 3096: Surprising Strings - 2 Points
- POJ 3852: String LD - 2 Points
- POJ 1917: Automatic Poetry - 3 Points
- POJ 2719: Faulty Odometer - 3 Points
- POJ 2413: How many Fibs? - 5 Points
- POJ 1338: Ugly Numbers - 6 Points
- POJ 2354: Titanic - 8 Points

**Problem Set #1: Ad Hoc, Simulation & Search**

- UVA 628: Passwords - 1 Point
- UVA 154: Recycling - 1 Point
- UVA 133: The Dole Queue - 1 Point
- UVA 706: LC-Display - 2 Points
- UVA 457: Linear Cellular Automata - 2 Points
- UVA 448: OOPS! - 3 Points
- UVA 868: Numerical Maze - 4 Points
- UVA 232: Crossword - 5 Points
- UVA 278: Chess - 5 Points
- UVA 10582: ASCII Labyrinth - 8 Points

**Problem Set #2: Dynamic Programming (Simple)**

- POJ 2663: Tri Tiling - 1 Point
- POJ 1163: The Triangle - 1 Point
- POJ 2181: Jumping Cows - 1 Point
- POJ 3624: Charm Bracelet - 2 Points
- POJ 1160: Post Office - 2 Points
- POJ 2033: Alphacode - 2 Points
- POJ 3186: Treats for the cows - 2 Points
- POJ 1159: Palindrome - 3 Points
- POJ 1050: To The Max - 4 Points

**Problem Set #3: Basic Graph Algorithms**

MST

- UVA 10034: Freckles - 1 Point
- UVA 11631: Dark Roads - 2 Points
- UVA 11747: Heavy Cycle Edges - 2 Points
- UVA 544: Heavy Cargo - 3 Points

Shortest Path

- UVA 821: Page Hopping - 1 Point
- UVA 10986: Sending email - 2 Points
- UVA 558: Wormholes - 2 Points
- UVA 10557: XYZZY - 2 Points
- UVA 10278: Fire Station - 3 Points
- UVA 11367: Full Tank? - 3 Points
- UVA 11635: Hotel Booking - 3 Points
- UVA 11693: Speedy Escapes - 4 Points
- UVA 10269: Adventure of Super Mario - 4 Points
- UVA 515: King - 6 Points

TopoSort

- SPOJ TOPOSORT: Topological Sorting - 3 Points

**Problem Set #4: Computational Geometry**

- UVA 378: Intersecting Lines - 1 Point
- UVA 11817: Tunnelling the Earth - 1 Point
- UVA 10297: Beavergnaw - 1 Point
- UVA 833: Water Falls - 2 Points
- UVA 10078: The Art Gallery - 2 Points
- UVA 478: Points in Figures: Rectangles, Circles, Triangles - 2 Points
- UVA 634: Polygon - 2 Points
- UVA 10387: Billiard - 3 Points
- UVA 10065: Useless Tile Packers - 3 Points
- UVA 11265: The Sultan’s Problem - 4 Points
- UVA 811: The Fortified Forest - 5 Points
- SPOJ BALLOON: Balloons in a Box - 5 Points
- UVA 10577: Bounding Box - 6 Points
- SPOJ KPPOLY: Projections of a Polygon - 8 Points

**Problem Set #5: Dynamic Programming (Intermediate)**

- UVA 662: Fast Food - 1 Point
- UVA 348: Optimal Array Multiplication Sequence - 2 Points
- UVA 10891: Game of Sum - 2 Points
- UVA 11151: Longest Palindrome - 2 Points
- UVA 1220: Party at Hali-Bula - 3 Points
- UVA 10911: Forming Quiz Teams - 4 Points
- UVA 10118: Free Candies - 4 Points
- UVA 1407: Caves - 5 Points
- UVA 10401: Injured Queen Problem - 5 Points

**Problem Set #6: Combinatorics and Algebra**

- UVA 11000: Bee - 1 Point
- UVA 10229: Modular Fibonacci - 1 Point
- UVA 10341: Solve It - 1 Point
- UVA 583: Prime Factors - 1 Point
- UVA 369: Combinations - 2 Points
- UVA 543: Goldbach’s Conjecture - 2 Points
- UVA 10083: Division - 2 Points
- UVA 10717: Mint - 2 Points
- UVA 10061: How many zero’s and how many digits? - 3 Points
- UVA 11282: Mixing Invitations - 3 Points
- UVA 1280: Curvy Little Bottles - 5 Points
- UVA 10900: So you want to be a 2n-aire? - 5 Points
- UVA 684: Integral Determinant - 7 Points

**Problem Set #7: Network Flow**

- UVA 10746: Crime Wave - The Sequel - 1 Point
- POJ 1273: Drainage Ditches - 2 Points
- POJ 3565: Ants - 2 Points
- UVA 11045: My T-shirt suits me - 2 Points
- UVA 10594: Data Flow - 3 Points
- UVA 10888: Warehouse - 3 Points
- UVA 10806: Dijkstra, Dijkstra. - 3 Points
- UVA 11301: Great Wall of China - 3 Points
- UVA 11506: Angry Programmer - 4 Points
- UVA 11544: Recruiter’s Problem - 5 Points

**Problem Set #8: Segment Tree**

- SPOJ GSS3: Can you answer these queries III - 1 Point
- SPOJ RMQSQ: Range Minimum Query - 1 Point
- POJ 3468: A Simple Problem with Integers - 2 Points
- SPOJ LCA: Lowest Common Ancestor - 2 Points
- POJ 2104: K-th Number - 4 Points

# Resources

Here are the Online Judges that we may use for assignments:

Some Tutorials or Books:

- USACO Training Program
- Steven Halim’s Competitive Programming book (the free e-book for the 1st edition is available here)

# Communication

We will be using a Piazza page for problem set announcements, practice contest announcements, and all course discussions. Please ask all general course questions and questions about the problem sets in the course Piazza page. Chances are, if you have the question, so does someone else. Asking in the Piazza page also allows other students to answer your question more quickly if the instructors are busy.

Please use @ucsd.edu e-mail addresses for all other course communication.

# Collaboration

Discussing problems with friends is highly encouraged. In fact, we intend for you to work with small groups of other students during the regular ICPC-Club practice sessions to solve the problems from the problem sets. Remember, the ACM-ICPC is a team competition. However, **you should code your own solution entirely by yourself**. You will only be hurting yourself by copying someone else’s (potentially buggy) code.

**Please do not post any code or solutions to problems to the Piazza page**. Discussion of the problems is encouraged, but outright spoiling is frowned upon and can result in censorship from the Piazza page.

# When you get stuck…

It is more than common to spend many hours solving a single problem. This is particularly true of the harder problems in each problem set. If, however, you have spent over a day seriously working on a problem and have not made any progress, follow these steps:

- First, reread the problem statement. Did you miss something important? Are you sure you have understood what the problem is asking for? Double-check your understanding on the sample input and output.
- Carefully go through the lecture slides. Think about which of the algorithms or techniques should be applied to the problem. For additional explanation of the algorithms, refer to Steven Halim’s Competitive Programming book.
- Check Piazza. It is likely that someone else has asked a question about the problem already.
- Attend the weekly ICPC-Club meeting and try to work out the problem with other students at the meeting. If necessary, ask one of the course assistants at the meeting.
- If none of the previous steps have worked, post your question to Piazza without giving away any obvious solutions.