Learning Algorithms Via Competitive Programming

What is this

An attempt to game our way past technical interviews without any formal background or experience by playing around in competitive programming, though even if you're not interested in wage slaving you will build skills and confidence to write your own software/startup.

We are going to do:

  • The book Competitive Programming 4 (the first volume, 4 chapters), which is around 260 pages and was written both for passing those silly FAANG job interviews, and for anybody interested in beginning competitive programming as the author is the coach of Singapore's national ICPC team. Everything we learn we practice with the Kattis Problem Archive and some other online judges like UVa or Codeforces, so producing working code for hundreds of problems and submitting them for tests of correctness and running time constraints. Kattis also hosts the ICPC archive problems which when we're done if you're interested we'll try and do those too. The book teaches problem solving techniques like complete/greedy search, divide and conquer, backtracking, and dynamic programming and all the costs of built-in data structures. Kattis even hosts the NSA challenges.
  • VisuAlgo to show us visualizations of the algorithms in the book
  • YouTube videos from Joe Gibbs Politz's Advanced Data Structures course at UCSD to see how to do informal analysis. There's a free online book for it too.
  • The computational geometry lectures from CMU's 15-451 Algorithms undergrad course (a mix of sp20 and f20) because we have access to the fall 2020 recitations and some spring 2020 lectures.
  • Relevant chapters from The Art of Computer Programming series by DEK. This is casual reading, if you like the book buy it and work through the whole thing on your own time after you get hired somewhere.

Optional I highly recommend a stroll through Functional Data Structures by Prof Ragde to see how analysis of modern algorithms is done, like how you should read the Akra-Bazzi paper instead of the 'master theorem' junk that most books peddle. It's short enough to do in a single month and if anything comes up in the CP4 book I'll point to a relevant page from it.

A torrent backup of the 15-451 content, we won't do it all

15-451 5gig backup
- some recorded sp20 lectures (lec 16-23)
  all recorded fa20 recitations and solutions
  
magnet:?xt=urn:btih:VCMKEFO57H5F4K5PH4LA5IXJZRARFCQE&dn=15451&tr=udp%3A%2F%2Ftracker.cyberia.is%3A6969%2Fannounce

Prereqs

If you are doing CS19 here at the same time then this will be easy, because that's where we learn what property-based testing is, dynamic programming, graphs, trees, and how to write examples to figure out a problem. The often difficult assignments in that course teach you how to solve these IOI/ICPC style problems.

Languages

The book has a public code repository of all the algorithms contained in it, and explains built-in data structures in the standard libraries for OCaml, Python 3, Java 11 and C++17 but you can use any of these languages/compiler versions. Pick whatever you personally like from the list of Kattis supported languages though if you're doing this to pass some interview, choose a language hackerrank/codility or coderpad supports as screeners and interviewers tend to use those. The author(s) of CP4 expect you to know multiple languages to solve any problem as Python makes string manpulation tasks simple, and Java has gigantic number manipulation or gregorian calender libraries. I will use C++ since the book recommends you learn that language, for both interviews and competitions. There are recommendations how to program C++ safely once you're done doing hacks in competitive programming, where it is typical to do unsafe things like not bothering to free anything because that adds unnecessary costs to a competition or backtracking with excessive bit manipulation.

If you're using a phone, there are some offline interpreters/compilers you can install from whatever app store you use or try free version of repl.it. You submit to Kattis for judging by pasting in the code through a web editor, uploading a source file(s) or write a script to automate this using their API. You get unlimited judging submissions.

Real contests

We can compete on CodeForces, ICFP, Google Kickstart, Facebook Hacker Cup, Code Golf, microcorruption or cryptopals type challenges, most of which we have no hope of winning of course but it's practice to pick up more experience. Apply for a job and the interview is another live contest, you win a signing bonus and salary. If you lose who cares find another interview.

Example class

There's a good writeup here of an exchange student from Canada who took the CS 3233 in Singapore and how the author of the book organizes those classes. It's a 4 month course. The takeaway here is learn to modify existing algorithms instead of using fancy structures.

Begin

The strategy here is learn through doing, the more problems you do per day, the more you will understand the concept of computation, the greater your confidence grows. Kattis problem difficulty past around 6 or 7 often means you are writing multiple algorithms or altering many data structures, and many problems labelled 'hard' on sites like leetcode (the free version of leetcode anyway) are really just a level 3 difficulty in the competitive programming problem archive universe so some of these may take a lot of time to solve, ie: thinking about the solution all day or all weekend. Try to figure it out yourself before looking at the solution it's the only way you level up and the only way you remember what you did to recall it months later.

I assume you either downloaded the book Competitive Programming 3 from library genesis or bought the 4th edition for $20, it's handbook sized and worth the money as it has a ton of solved exercises just in the book itself let alone the hundreds+ of UVa/Kattis problems it recommends doing. The book has several languages as well, Bulgarian and Spanish for the 4th edition and I believe Korean and Spanish for the 3rd edition.

This book is designed to be read several times, you work through it once then go back and solve the exercises in the book, as they won't make sense the first time around. The author(s) are very blunt in saying if you want to compete, you should know everything in this book and be able to solve any of the problems in under 30 minutes, if very competitive under 10 minutes.

Preface - How many problems

Each chapter topic will have 7 starred 'must try' problems, and all of them are on the site methods to solve and that site is more up to date than the book. It contains a mix of onlinejudge.com (formely called UVa) and Kattis problem sets, the bold problem titles are the recommended problems. Hints how to solve them are on the right-hand side if you haven't figured it out but the book explains that's how the authors solved them, but there could be other ways. The book we are reading (vol I) satisfies the majority of the 2020 IOI syllabus (and also 2021 syllabus since 2020 was virtual and ICPC cancelled until March 2022).

The main changes between this book and CP3 is rearranging some chapters for the new harder IOI syllabus, mainly moving the 'math book 2' content to this book, including new algorithms and including both Python and OCaml as languages as Tezos I believe has sponsored OCaml for the book. CMU's current prof of 15-451 designed their original 15-295 competitive programming seminar, and IIRC most of his code there was in OCaml as well. You could do this book in 2 different languages, 1 language for UVa/onlinejudge problems (ANSI C (C89), C++ (C++98), Pascal, Java, C++11 or Python 3) and Kattis accepts many more languages, like OCaml.

IOI I believe is presently Python/Java/C++ and ICPC regionals only C/C++, with the world finals now accepting Kotlin, C/C++, Java and Python with no guarantee the problems can be solved in all the languages as judges only solve all the problems in Java and C/C++.

Total problems

If we only do the starred problems, how many are we looking at? Chapter 4 has 167, 3 has 195, 2 has 165 and the first chapter has 182 or 709 total problems. If you want to do all the starred problems within 6 months, you must average 3-4 solved problems per day which honestly isn't very hard we aren't doing ICPC/IOI level problems until we get into Chapter 3/4 where the difficulty can get up to 6-8. On average, most problems will be in the 3.2 to 5 difficulty range after chapter 1, so 'very hard' leetcode level (if using free tier leetcode). If you read the above example class writeup of that exchange student, he solved 50 problems a day when he started to get to 500 points on Kattis which is the entrance requirements for the course, and he solved 500 more problems on Kattis during his 4 month course in Singapore all averaging about mid 3 difficulty so this isn't impossible to do, and he did his under time constraint while in the course competing against other students and we have all the time we want.

Chapter 1

Most of this hasn't changed since CP3, so casually read it. 1.3.2 problem solving skills are mentioned, many of which were taught in CS19 in the other workshop. 1.3.3 modern (2020) CPUs can process 108 or 100M operations in a second for our solutions, on average, so they recommend to pay attention to bounds if your algorithm is n4 in complexity but the input is only 50 max, you could still pass the online judge. The book notes that we should already have the skills to judge the runtime complexity of our own algorithms, and the C++ Advanced Data Structures course will teach more of this as we go through the CP4 text. 1.3.4 talks about programming languages, how factorial of 40 is trivial in Python but difficult in C/C++, and requires a special library BigInteger in Java. The point being you should know multiple languages enough to be able to solve any ICPC problem with them. Really if you look at imperative languages at the forest level instead of the trees, they're all just reinvented ALGOL with some kind of dynamic/static dispatch bolted on, this is detailed in Robert Harper's pfpl book.

You may want to switch up languages to something more interesting than yet another ALGOL clone considering we are doing 700 problems, half can be done in C/C++ on UVa and other half on Kattis with Haskell, OCaml, even Prolog. You can also use SPOJ online judge and use any language from assembly to AWK.

Input/Output

TODO


Home