Table of Contents

• Teaching solutions
  • Introduction to Algorithms
    • Element Occurance
    • Prefix Sum
    • Sorting
    • Stack and Queue
    • Recursion
  • Advanced Algorithms
    • DFS
    • Dijkstra
    • Find and Union
    • MST
    • Topological Sort
    • DP on a Tree
• Implementation
  • Sorting
  • Graphs
  • Other
• Testing

Teaching solutions

Keeping solutions of different problems by topic.

Introduction to Algorithms

Element Occurance

Buttons

Print out press count of each button from 1 to n (count how many times each button was pressed), including that n+1th button resets all values to maximum of all from 1 to n.

Example Input: 5 7 3 4 4 6 1 4 4

Example Output: 3 2 2 4 2

Frog

A frog can cross a river, if all leaves on position from 1 to n exist. Knowing the order of leaf falling, print out when will crossing be possible. Example Input: 5 8 1 3 1 4 2 3 5 4

Example Output: 7

Is Permutation

Check if given sequence of n integers is a permutation of a set from 1 to n. Print out yes or no.

Swap

Given two arrays A and B, print if it's possible to swap an element of A with an element of B to have two lists of equal sum.

Unique Count

Check if for a list of numbers, each number occurs unique amount of time, that is: there is no other number that occurs the same amount of times. (OK: 1 2 2 3 3 3, NOT OK: 1 1 2 2)

Prefix Sum

Maximum Mushrooms Collection

Given a list of n integers, where each value represents the number of mushrooms at that position along a path. A gatherer stands at position k and can make m moves (each move is left or right). Find the maximum mushrooms that can be collected.

Tape

Given a tape with a list of n integers (1 <= n <= 1,000,000), a boy tries to find the minimum possible arithmetic mean of any contiguous subarray.

Passing Cars

Count how many pairs of passing cars exist (cars traveling in opposite directions meeting at the same point), given a list of n cars in order and their travel direction (0 - east. 1 - west).

Hamsters

Count how many pairs of passing cars exist (cars traveling in opposite directions meeting at the same point), given a list of n cars in order and their travel direction (0 - east. 1 - west).

Count Vowels

Count vowels in a word on different query ranges.

Sorting

Unique count

We are given a sequence of n >= 0 integers a0, a1, a2, ..., a(n-1), where -2 * 10^9 <= ai <= 2 * 10^9. The task is to calculate how many distinct numbers appear in this sequence.

Multiplication

Find values x, y, z from a list, such that their product is as large as possible. Do it m times.

Nails

You are given a board with nails sticking out at different heights. Each nail has a specific sticking-out length. Additionally, you are allowed to "nail" (reduce the height of) up to k nails, lowering them to any height less than or equal to their current height. The task is to determine the maximum number of nails that can stick out at the same height after using up to k nailing opportunities.

Minimum Distance

In Bajtocja, railway tracks run in a straight line from east to west. The houses of the residents are located to the north of the railway track. If two people from different houses want to meet, they meet at the midpoint of the distance between their houses. However, this distance is not calculated in a traditional way as a straight-line segment between the houses. Instead, the distance is determined as follows: a person first walks south to the railway tracks, then along the tracks to the line where the target house is located, and finally walks straight north to that house. From all possible pairs of houses, we want to find the pair for which this distance is minimal.

Stack and Queue

Initial Size of a Queue

Determine the minimum number of people who had to be in the queue initially, knowing the order of peopele joining and leaving a queue. We do not know how many people were there initially, but there should not be a moment where a person leaves an empty queue.

Brackets

Determine whether each input bracket sequence is correct.

Fish

Fishes of different sizes swim upstream and downstream. If they meet, bigger fish eats the smaller one. Calculate number of survivors.

Queue Bribe

A boy wants to be the first in the queue. Each person has a price. Calculate the cheapest way the boy can be first in the queue.

Recursion

Add Two Numbers

Add two numbers, but they are a reversed list

Example Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] https://leetcode.com/problems/add-two-numbers/

Bucket Fill

Bucket Fill tool implementation

For an image (n x m array of color as a signle number), apply bucket fill to a pixel with a certain color and print out result image.

Factorization

For a number, print out factorization. Use recursion.

Ineffective Fibonacci

Use recursion to compute n-th Fibonacci number. DO NOT optimize. Make it real bad, but recursive.

Fibonacci Memorization

Fix Ineffective Fibonacci. Still, use recursion but make it smarter.

Find Peak

Find any array peak (that is, for an i-th value in a list, both values on right and left are smaller).

Power Slow

For values x and n, compute x to the power of n. Do not worry about optimization. Just make it recursive.

Power Fast

For values x and n, compute x to the power of n. Try to optimize.

Advanced Algorithms

DFS

All Paths from Source Lead to Destination

Given graph, source, and destination - check if all paths lead to destination. https://leetcode.com/problems/all-paths-from-source-lead-to-destination/description/

Tree Distances I

You are given a tree consisting of n nodes. Your task is to determine for each node the maximum distance to another node. https://cses.fi/alon/task/1132

Longest Increasing Path In A Matrix

Find longest path that has increasing value in each consecutive cell. https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Loud and rich

Find longest path that has increasing value in each consecutive cell. https://leetcode.com/problems/loud-and-rich/description/

Valid Tree

Check if a tree is a valid tree.

Dijkstra

Restricted paths

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti.

A path from node start to node end is a sequence of nodes [z0, z1, z2, ..., zk] such that z0 = start and zk = end and there is an edge between zi and zi+1 where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1.

Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 109 + 7.

https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/description/

Find and Union

Evaluate Division

Given a series of proportions between variables, evaluate proportions between other pairs if possible https://leetcode.com/problems/evaluate-division/description/

Valid Tree

Check if a tree is a valid tree.

MST

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find critical edges (MST cannot exist without this edge), and pseudo-critical edges (MST can, but does not have to exist with this edge) for a given graph.

Min Cost to Connect All Points

Find a MST for a set of nodes represented as points on a 2D grid. https://leetcode.com/problems/min-cost-to-connect-all-points/description/

Optimize Water Distribution in a Village

Every house in a village needs water. House can get water from other hourse or by getting a well. Each operation has different cost. Compute cost of getting water to all the houses in a village. https://leetcode.com/problems/optimize-water-distribution-in-a-village/description/

Topological Sort

Minimum Height Tree

Take a Tree and find node to make the height of tree minimum. https://leetcode.com/problems/minimum-height-trees/description/

Sequence Reconstruction

Check if a sequence can be uniqely reconstructed from dependencies. https://leetcode.com/problems/sequence-reconstruction/description/

DP on a Tree

Maximal Point Path

For a given tree, crossing each edge costs points. Each node visit adds points. Given amount of points earned by node visit and amount of points lost by traveling through an edge, compute a path that results in heighest point gain.

Maximum Height of Tree

Find maximum height of tree when any node could be a root.

Maximum Set of Edges

Given a tree consisting of N Nodes and N-1 edges. The task is to select the maximum set of edges such that each vertex is part of at most one of the selected edges (no two edges share a common end point) i.e., if we select an edge connecting vertex u and v, then we cannot select any other edge connected by vertex u or vertex v.

Sum of Distances In Tree

Compute for each node a sum of distances to all other nodes. https://leetcode.com/problems/sum-of-distances-in-tree/description/

Implementation

This is a place where I keep my implementation of most popular algorithms.

Sorting

• Count Sort (python)
• Heap Sort (C++)
• Insert Sort (C++, python)
• Merge Sort (C++, python)
• Quick Sort (C++)
• Selection Sort (python)
• Topological Sort (C++, with and without queue)
• Unique Count (python)

Graphs

• BFS (C++)
• DFS (C++)
• Dijkstra (C++)
• Bellman-Ford (C++)
• Floyd-Warshall (C++)
• Tree Diameter (C++)
• MST Kruskal (C++)
• MST Prim (C++)

Other

• prefix sum (python)
• 2D prefix sum (C++, python)
• 2-pointer technique (C++)
• Binary Search (C++, python)
• Binary Tree (C++)
• Binary Heap (C++)
• Find and Union (C++)

Testing

Testing is an example on testing your competition solutions - write a generate.cpp code to generate example inputs, write a solution in main.cpp and a brute-force solution in test.cpp. Then use test.sh to find any cases where they give different results.