Osion kuvaus

  • Yleinen

    OVERVIEW

    This is a practical hands-on course that is intended for students who are interested in competitive programming and algorithmic challenges. During this course, you will learn how to solve algorithmic programming challenges, both individually and as a team.

    The course is worth 5 credits. This course is suitable for students of all levels, from BSc students to PhD students. All course material will be in English.

    PREREQUISITES

    Students are expected to have a working knowledge of computer programming, algorithms, and data structures, and preferably some practical experience with C or C++ programming languages.

    Our first meeting will also serve as a prerequisite test; you can there see if you have got sufficient skills to successfully follow our course.

    COURSE FORMAT

    During periods I and II, we will organize two 90-minute practice contest each week:

    • Mondays, at 16:15-17:50. These are usually solo contests: each is student solving problems as an individual.
    • Wednesdays, at 16:15-17:50. These are usually team contests: students are randomly assigned to teams with 2–3 person per team.

    In each contest, the submissions are automatically graded and you will immediately see whether your solution is correct or not. You are primarily competing against yourself, trying to solve as many problems as possible, but in each contest there will also be a scoreboard where you can see your standing in comparison with other students.

    Each week on Wednesday we will announce the topic and the rules of the following week’s contests, and provide pointers to some self-study material. Each week you are expected to spend 6–8 hours on your own to self-study the material. The recommended timeline looks like this:

    • Monday: 1.5 hours, contest
    • Tuesday: 1–2 hours, self-study for Wednesday’s contest
    • Wednesday: 1.5 hours, contest
    • Thursday–Friday: 5–6 hours, self-study for next week’s contests

    During the course, you are also encouraged to take part in NCPC, the Nordic Collegiate Programming Contest.

    We will use Zulip at competitive2022.zulip.aalto.fi for communication, and all participants are expected to follow our Zulip discussion forum actively during the course. All course material will be made freely available online.

    WHAT TO EXPECT

    • You will get a lot of practice in creative problem solving and writing correct and efficient programs quickly.
    • You will learn about useful algorithmic ideas (e.g. range query data structures) and how to apply them in new contexts.
    • You will learn about general algorithm design paradigms (e.g. dynamic programming) that are broadly applicable in coming up with new algorithms.
    • You will learn to use different programming tools for solving different kinds of tasks. There will be some practice contests in which some problems are trivial to solve with Python but really hard with C++ and vice versa. You do not need to know C++ or Python in advance, but you should be willing to learn enough of them during the course.
    • You will get to know other students and get practice in solving problems as teams.
    • And we will try to have fun!

    BEFORE THE FIRST MEETING

    • Read this web page completely.
    • Complete the course registration in Sisu as usual.
    • Join the Zulip discussion forum at competitive2022.zulip.aalto.fi using your Aalto user account.
    • Create a CSES user account at cses.fi/register (you cannot use your Aalto user account to log on to CSES).

    The first meeting will be in classroom T8 at the Computer Science building on Monday, September 5, starting at 16:15 sharp. Bring your own laptop (or be prepared to use the computers that are available in the classroom) and be ready to solve some problems.

    COURSE STAFF

    The course is organized by Jukka Suomela, Amirreza Akbari, Navid EslamiAmirabadi, Unto Karila, Henrik Lievonen, Jan Studený, and Hossein Vahidi.

    GRADING

    In each contest you will get points for solving problems:

    • In each solo contest there will be 4 problems, and you will get 3 points for each task that you solved.
    • In each team contests there will be 5 problems, and all team members will get 2 points for each task that the team solved.

    If you take part in NCPC you will get 3 points for each problem your team solves.

    The grade is determined by the number of points you get:

    • 72 points = grade 1/5
    • 90 points = grade 2/5
    • 108 points = grade 3/5
    • 126 points = grade 4/5
    • 144 points = grade 5/5

    The maximum possible score is 264 (plus extra points you can get from NCPC).

    In each contest the final problem is the most challenging task, and everyone who solves it will get a special supercoder badge. Top three students with the largest number of badges will get a certificate for the outstanding achievement.

    HELP IS AVAILABLE!

    Our course staff will be available during the contests. We will help with technical problems all the time, and we will also provide hints during the second half of each contest.

    If you have any questions or comments related to any of our course material or the problems, please feel free to post in our public Zulip streams!

    COLLABORATION RULES

    In our practice contests, you can freely read any material (you can freely refer to your own notes, textbooks, and Wikipedia, search with Google, watch YouTube videos etc.) but you cannot ask for help (this includes posting questions in online forums, or emailing or calling your friend).

    If you take part in NCPC, you will need to strictly follow the official NCPC rules.

  • Week 1

    HOMEWORK BEFORE WEEK 1

    Here is a short (2.5 min) video about what competitive programming is:

    Other than that, there is no homework before the first week—just read the basic course information and come to the first meeting!

    MONDAY CONTEST

    On Monday (September 5), we will have a solo contest.

    You will need to create a personal CSES user account at cses.fi/register if you do not have an account yet. Please make sure you use your personal CSES user account to take part in the contest.

    The contest will be available at cses.fi/402/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. You will get points based on the number of tasks that you solved correctly during the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (September 7), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    The contest will be available at cses.fi/403/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. You will get points based on the number of tasks that your team solved correctly during the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 2

    Please see the section “Week 2” for more information on what to study before next week! We will announce the homework by Wednesday.

  • Week 2

    HOMEWORK BEFORE WEEK 2

    The tasks of week 2 we will be covering some of the most common techniques in competitive programming, namely sorting, binary search, BFS and DFS. Maybe you are familiar with some or all of these—now it is time to learn how and when to use them.

    Sorting

    Sorting algorithms are rarely implemented by hand during contests as virtually all languages’ standard libraries provide well-optimized and flexible implementations. Make sure you know how to sort by arbitrary conditions. For example, this C++ code creates an order based on arrays a and b:

    vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int l, int r){ return a[l]-b[l] > a[r]-b[r]; });

    Binary search

    Unlike sorting, this is something you should learn to do by hand. See pages 31–34 in the Competitive Programmer’s Handbook. While binary searching for an element in a sorted list is common, problems that require doing it are usually not considered “binary search problems.” Typically the core realization in a binary search task has the form:

    1. We need to find the largest possible X, but this is hard.
    2. Aha! Trying to constructing a solution for some fixed X is easy.
    3. And if there is a solution for some fixed X, there are solutions also for all smaller values.
    4. Use binary search to find the largest X that admits a solution.

    Substitute X for “time” in task “Entrepreneur” from Wednesday’s contests and see if you can solve it.

    Graph essentials

    Knowing how to represent graphs and how to traverse them are essential skills in competitive programming. Make sure you know how to implement Breadth First Search (BFS) and Depth First Search (DFS). See pages 113–120 in the Competitive Programmer’s Handbook.

    MONDAY CONTEST

    On Monday (September 12), we will have a solo contest.

    The contest will be available at cses.fi/404/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (September 14), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/405/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 3

    Please see the section “Week 3” for more information on what to study before next week! We will announce the homework by Wednesday.

  • Week 3

    HOMEWORK BEFORE WEEK 3

    In week 3 our main topic is dynamic programming. Your homework consists of two parts:

    Hint: both tasks in the practice contest can be solved using dynamic programming, and they can be solved with a short program. Please ask in Zulip if you need further hints!

    MONDAY CONTEST

    On Monday (September 19), we will have a solo contest.

    The contest will be available at cses.fi/406/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (September 21), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/407/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 4

    Please see the section “Week 4” for more information on what to study before next week! We will announce the homework by Wednesday.

  • Week 4

    HOMEWORK BEFORE WEEK 4

    In week 4 our main topic is divide and conquer. Your homework consists of three parts:

    MONDAY CONTEST

    On Monday (September 26), we will have a solo contest.

    The contest will be available at cses.fi/408/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (September 28), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/410/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 5

    There is no homework this time, but you are encouraged to take part in the NCPC practice contests.

  • Week 5

    HOMEWORK BEFORE WEEK 5

    There is no homework this time, but you are encouraged to take part in the NCPC practice contests.

    MONDAY CONTEST

    On Monday (October 3), we will have a team contest. This time you can choose your own team! Please create a user account for your team at cses.fi/register?team if you do not have one yet, and please make sure the entire team uses the same user account.

    The contest will be available at cses.fi/411/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (October 5), we will have a team contest. Again, you can choose your own team! Please create a user account for your team at cses.fi/register?team if you do not have one yet, and please make sure the entire team uses the same user account.

    The contest will be available at cses.fi/409/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    Once the contest is over, please fill in the form below to record your score.

    NCPC ON SATURDAY

    Please see nordic.icpc.io/ncpc2022/ for more information!

    HOMEWORK FOR WEEK 6

    Please see the section “Week 6” for more information on what to study before next week! We will announce the homework by Wednesday.

  • Week 6

    HOMEWORK BEFORE WEEK 6

    In week 6 our main topics are Dijkstra’s algorithm and topological sorting. As a homework, please read Sections 13.2 and 16.1 of the Competitive Programmer’s Handbook.

    MONDAY CONTEST

    On Monday (October 11), we will have a solo contest.

    The contest will be available at cses.fi/412/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (October 13), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/413/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 7

    (Will be announced later.)

  • Week 7

    HOMEWORK BEFORE WEEK 7

    In week 7 we are continuing with the theme of graph algorithms. The topics are the lowest common ancestors in trees, representing graphs as matrices, and flows. Read about LCA in chapter 18.3, Floyd-Warshall algorithm in chapter 13.3 and Ford-Fulkerson algorithm in chapter 20.1 in the Competitive Programmer’s Handbook. Prefereably also implement all of them: LCA, Matrix representation, Flow

    MONDAY CONTEST

    On Monday (October 18), we will have a solo contest.

    The contest will be available at cses.fi/414/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (October 20), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/415/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 8

    (Will be announced later.)

  • Week 8

    HOMEWORK BEFORE WEEK 8

    In week 8 we are exploring the benefits and drawbacks of python and C++. The material can be found on Zulip.

    MONDAY CONTEST

    On Monday (October 31), we will have a solo contest.

    The contest will be available at cses.fi/416/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (November 2), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/417/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 9

    (Will be announced later.)

  • Week 9

    HOMEWORK BEFORE WEEK 9

    Week 9 focuses on string algorithms. First and foremost, you should familiarize yourself with hashing. You can read about rolling hashes in Chapter 26 of the Competitiive Programmer’s Handbook. The Z-algorithm also is useful for string matching, and learning it provides insight to the way deterministic string algorithms usually work. You can test your implementations at the "String Algorithms" -section of the CSES Problemset.

    MONDAY CONTEST

    On Monday (November 7), we will have a solo contest.

    The contest will be available at cses.fi/418/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (November 9), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/419/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 10

    (Will be announced later.)

  • Week 10

    HOMEWORK BEFORE WEEK 10

    On week 10 we are going to learn about geometry. In programming competitions, geometry problems are typically meant to measure the contestant's implementation power. However, we will be nice and mostly have tasks that have clean solutions. Read into the basics of geometry in chapter 29 of the Competitive Programmer’s Handbook. Also, familiarize yourself with sweeping line algorithms that come up in Chapter 30. You can exercise with the tasks of the "Geometry" -section of the CSES Problemset.

    MONDAY CONTEST

    On Monday (November 14), we will have a solo contest.

    The contest will be available at cses.fi/420/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (November 16), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/421/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 11

    (Will be announced later.)

  • Week 11

    HOMEWORK BEFORE WEEK 11

    On week 11 we are going to work with number theory and combinatorics. Familiarize yourself with Euclid's algorithm and learn how to implement the basic algorithms required for combinatorics. You can pick up on Euclid's algorithm, modular exponentiation and the modular inverse in chapter 21 of the Competitive Programmer’s Handbook. Information about binomial coefficients and inclusion-exclusion can be found in chapter 22. You can practice your implementations with the CSES problem set: Exponentiation, Combinations.

    MONDAY CONTEST

    On Monday (November 21), we will have a solo contest.

    The contest will be available at cses.fi/422/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (November 23), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/423/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 12

    Week 12 will not have new topics

  • Week 12

    HOMEWORK BEFORE WEEK 12

    Nothing. Come as you are.

    MONDAY CONTEST

    On monday (November 28), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/434/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (November 30), we will have a solo contest.

    The contest will be available at cses.fi/435/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.