Guide to Key Algorithms for Div2 B Problems
Your CP Mentor
This guide covers the core algorithmic techniques commonly tested in Codeforces Div2 B problems. For each
pattern, we explain:
• When to use it,
• The underlying idea,
• Typical problem scenarios,
• A concise code template.
1 Sorting & Greedy
When to use: When you need to reorder data to make a local choice optimal (e.g., minimizing difference, matching
pairs).
Idea: Sorting arranges elements so that simple one-pass or two-pointer scans can solve the problem. A greedy
decision then picks the best local option at each step.
Common scenarios:
• Minimizing maximum gap or difference.
• Assigning tasks or pairing elements by smallest or largest.
• Interval scheduling (selecting non-overlapping intervals).
Template: Sort then scan
1 vector < int > a ; // populated
2 sort ( a . begin () , a . end () ) ;
3 int result = /* initial best */ ;
4 for ( int i = 0; i + 1 < a . size () ; ++ i ) {
5 // greedy choice between a [ i ] and a [ i +1]
6 result = min ( result , abs ( a [ i +1] - a [ i ]) ) ;
7 }
8 cout << result ;
Listing 1: Sort + Greedy Scan
2 Prefix Sums
When to use: For fast range-sum queries or cumulative
P frequency calculations. P
Idea: Build an array pref where pref[i] = jlt;i a[j]. Then any subarray sum a[l..r] is just pref[r+1]−pref[l].
Common scenarios:
• Range-sum or average queries.
• Detecting zero-sum subarrays.
• Counting days above/below threshold.
1
Template: Prefix array
1 int n ;
2 vector < int > a ( n ) ;
3 vector < long long > pref ( n +1 , 0) ;
4 for ( int i = 0; i < n ; ++ i ) {
5 pref [ i +1] = pref [ i ] + a [ i ];
6 }
7 // Query sum on [l , r ]
8 auto rangeSum = [&]( int l , int r ) {
9 return pref [ r +1] - pref [ l ];
10 };
Listing 2: Compute prefix sums
3 Frequency Counting / Hashing
When to use: When you need to count occurrences or lookup complements quickly.
Idea: Use a hash map or array to store frequencies, enabling O(1) updates and queries.
Common scenarios:
• Two-sum variants (count pairs with given sum).
• Counting equal or majority elements.
• Sliding window with dynamic counts.
Template: Counting complements
1 unordered_map < int , int > cnt ;
2 long long ans = 0;
3 for ( int x : a ) {
4 ans += cnt [ target - x ];
5 cnt [ x ]++;
6 }
7 cout << ans ;
Listing 3: Two-sum via hashing
4 Sets & Multisets
When to use: When you need a sorted dynamic collection with fast insertion, deletion, and min/max queries.
Idea: A balanced BST under the hood provides O(log n) operations.
Common scenarios:
• Maintaining the smallest/largest in a sliding window.
• Eliminating duplicates while preserving order requirements.
• Merging or splitting groups dynamically.
Template: Sliding window min
1 multiset < int > window ;
2 for ( int i = 0; i < n ; ++ i ) {
3 window . insert ( a [ i ]) ;
4 if ( i >= k ) window . erase ( window . find ( a [i - k ]) ) ;
5 if ( i >= k -1) cout << * window . begin () << ’␣ ’;
6 }
Listing 4: Window minimum
2
5 Two Pointers
When to use: For problems on sorted arrays or when maintaining a window with variable endpoints.
Idea: Use two indices extitl, extitr to track a subarray/window, and move them based on current sum or condition,
achieving O(n).
Common scenarios:
• Counting subarrays with sum constraint.
• Merging two sorted arrays.
• Removing duplicates in sorted list in place.
Template: Count subarrays sum ≤ S
1 long long sum = 0 , ans = 0;
2 int r = 0;
3 for ( int l = 0; l < n ; ++ l ) {
4 while ( r < n && sum + a [ r ] <= S ) {
5 sum += a [ r ++];
6 }
7 ans += ( r - l ) ;
8 sum -= a [ l ];
9 }
10 cout << ans ;
Listing 5: Two-pointer window
6 Strings
When to use: When processing text, matching substrings, or validating patterns.
Idea: Treat string as a character array; use simple loops or STL functions.
Common scenarios:
• Palindrome checks.
• Find/count substrings or patterns.
• Reordering or rotating characters.
Template: Palindrome check
1 bool isPal ( const string & s ) {
2 int i = 0 , j = s . size () -1;
3 while ( i < j ) if ( s [ i ++] != s [j - -]) return false ;
4 return true ;
5 }
Listing 6: Check palindrome
7 Direct Simulation
When to use: If the problem describes a process directly, simulate it with loops.
Idea: Follow the statement literally, often with O(n) or O(n2 ) if n is small.
Common scenarios:
• Game simulations.
• Water fill or flood fill on 1D/2D grids.
• Step-by-step transformations.
3
Template: 1D flood fill
1 vector < int > left (n ,1) , right (n ,1) ;
2 for ( int i =1; i < n ;++ i )
3 if ( a [ i ] >= a [i -1]) left [ i ]= left [i -1]+1;
4 for ( int i =n -2; i >=0; - - i )
5 if ( a [ i ] >= a [ i +1]) right [ i ]= right [ i +1]+1;
6 int best =0;
7 for ( int i =0; i < n ;++ i )
8 best = max ( best , left [ i ]+ right [ i ] -1) ;
9 cout < < best ;
Listing 7: Rain spread problem