[Notes] - Competitive Programming 4

Notes for Competitive Programming 4. A very good book.

Foreword

This post are some notes that I have taken from the book CP4. Do note that it is much better if you read the book by yourself and these are just study notes that I have made. I didn’t make notes for all chapters, and the arrangement of this study note might be different from the ordering of chapters in the book.

Menu

Chapter 1

1.3 Algorithm Analysis

Modern Computers can process around commands per second

Familiarity with these bounds:

• , .
• , .
• 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of
  and
  
• double and float has 2^53 = 9e15 and 2^24 = 1.6e7 precision for integers
• If you need to store integers , use Big Integer.
• The largest input size for typical programming contest problems must be .
  Beyond that, the Input/Output (I/O) routine will be the bottleneck.
• Usually, algorithms are sufficient to solve most contest problems for a simple reason:
  and the theoretically better algorithms are hard to differentiate empirically

Useful Libraries

I/O

1. printf("%.*Lf\n", n, pi); prints n decimals of pi. e.g. n=3 would print 3.141

2. if (scanf("%30[^\n]%*c", line) != 1) break;

   • %30[^\n] reads up to 30 non-newline chars (The %[...] reads a run of characters that match what’s inside the brackets.^ at the start means negation (match anything except these).); %*c consumes the newline, The * means assignment suppression: read it but don’t store it anywhere.

String

1. strncmp(a, b, n) compares the first n characters of two C strings

   • Returns 0 if those first n chars are equal,

   • < 0 if a is lexicographically less than b within those n chars, (strncmp("abcdef", "abc", 7) > 0)

2. finding string P in string T.

size_t pos = T.find(P);                  // first
if (pos == string::npos) { /* not found */ }
while (pos != std::string::npos) {
    // use pos
    pos = T.find(P, pos + 1);             // search starting *after* previous start
}

Notes for myself

1. Always remember to check bounds of the index used in the array. from basic programming1

2. Always remember to check the bound of the variables. One example is when integers add up, u might want to consider using long long for sum.

3. Sometimes if n is large, consider using a constant as bound instead of using n related stuff as bound. UVa11614

4. Remember to add a todo: to be changed to problem standard if you are using testing stuff that are temporary. E.g. used 0,30 (for testing) as bound instead of 0,1e9 as bound in first submission.

Study Plan

read 30 pages per week + 9 problems + 1 contest

Nov 2025

Week 1

Before 11.3: Read uptill page 30.
11.3: Kattis: r2, timeloop, judgingmoose
11.4: Kattis:statistics, filip, lineup, 
11.8: Kattis:basicprogramming1 UVa: 11172,11559, 11614

Week 2

11.9: Chapter1.5