Problems Base course RU

Found in

science and physics

Articles

DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems GRA Algorithm Johnson's algorithm Shortest paths with negative weights: Bellman–Ford potentials, reweighting and Dijkstra from each vertex. O(V·E + V·(V + E) log V) 2 problems GRA Algorithm Heavy paths Path queries on trees: heavy paths cut any path into O(log n) array stretches under a segment tree. O(log² n) per query 1 problem GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem NUM Algorithm Gaussian elimination A linear system by elimination: the pivot, LU, conditioning, sparse matrices and fill-in. O(n³): about n³/3 multiplications for the forward pass 2 problems GEO Algorithm Convex hull The smallest convex polygon containing all the points, in O(n log n). O(n log n) 2 problems NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 2 problems ML Algorithm Decision tree Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most. O(h · F · n log n) to build; O(h) to answer 2 problems

Problems

Earthquakes in a range The hunting tooth A place in the catalogue Clusters on a map of epicentres How many rooms are needed Rotations on the conveyor Seismic watch The resistance of a circuit The snowplow's runs An electric car in the hills An index of straight lines Kepler's equation without misfires The median over a window A described relative Flood watch

Often together

classic 9 tree 5 interviews 5 geodata 4 graph 3 contests 3 array 2 in production 2 maps and navigation 2 numerical precision 2 points 2 iterative 2