Skip to main content

Practice 3

· One min read
Godmar Back
Godmar Back
ICPC Coach

I checked solution descriptions and solutions in for the problems in practice 3.

Additional resources

  • Sedgwick's Lecture Slides on Dijkstra. See slide 37 for a more precise complexity analysis than I gave in class. We're generally using the "lazy" binary heap variant (Python: heapq, Java: PriorityQueue, C++: priority_queue) with O(E log V) or O(m log n).

Competitive Programming Book

· One min read
Godmar Back
Godmar Back
ICPC Coach

Competitive Programmer's Handbook by Antti Laaksonen contains a nice overview of different complexity classes.

I also updated the pickup sticks example to include DFS versions of the topological sorting algorithms in Python and Java.

Take note of the required increase in the recursion limit. In Java, nothing is required in your source code, but you must run the code with an increased stack size as described here. Use -Xss64m.

In Python, do

import sys

sys.setrecursionlimit(...)

This is all that's necessary for Kattis, but on some systems (where there is a lower OS stack limit), you must add a call to setrlimit. So the complete incantation is:

import sys, resource
sys.setrecursionlimit(2000000)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))