Skip to content

Latest commit

 

History

History
51 lines (34 loc) · 1.89 KB

plans.md

File metadata and controls

51 lines (34 loc) · 1.89 KB

VPCPC 2014 Plans

Day CZ

  • buslines - (combinatorial) number of different paths in tree
  • cutting - (open data) separate points in a plane by the least amount of lines
  • investigation - (graph) generalized binary search on tree

Day HU

  • critical - (graph) Find all critical nodes of a dag in linear time
  • networks - (geometry) Find a connecting segment of two networks in linear time
  • nextperm - (combinatorial) Find the next 3-1-2 pattern avoiding permutation

Day PL

  • sorting - (longest increasing subsequence) given a set of numbers, count its subsets, which have some properties
  • game - (number theory) recursive euclidean algorithm plus modular arithmetic
  • posters - (interval tree) find the area of a sum of rectangles intersected with another rectangle (many queries)

Day SK

  • shades - (stringology) Aho-Corasic on fractions
  • hyperways - (graph) union find but whith detecting 2-connected components
  • malloc - (BST / interval tree) allocating and freeing bytes in memory

Day MIX 1

  • (CZ) - universities - (graph) longest path in tree containing same number of black and white vertices
  • (HU) - newtree - (geometry) find a triangle containing a given point
  • (PL) - wall - (dynamic programming) computing answer for every interval of a sequence with marked end
  • (SK) - rubic - (data structures) resizable interval tree over permutations

Day MIX 2

  • (CZ) - socks - (graph) shortest path in graph from A to B, containing vertex C
  • (HU) - tickets - (greedy) scheduling, union-find
  • (PL) - newspapers - (divide and conquer) given a tree, find a path with the highest average of weights, the path must be longer than k
  • (SK) - slalom - (geometry) find the widest path through a set of vertical line segments