Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

2471CoconutMilk's blog

i need your help to solve some 800 rated problems!
By 2471CoconutMilk, 14 months ago, In English

hello codeforces!

these days i am struggling to sovle the extremely hard 800 rated problems on codeforces

one of my boyfriends tells me i can learn some advanced data structure to solve the problems

can you give me some advice on learning data structure?

  • Vote: I like it
  • -40
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

Learning FFT really helped me solve 800's. You can start there.

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Start with segment tree.

→ Reply
»
14 months ago, hide # |
← Rev. 5  
Vote: I like it +55 Vote: I do not like it

The list of topics that you should learn for solving 800 rated problems : Li-Chao Segment Tree
Segment Tree Beats
RMQ in O(n)/O(1)
Any self-balancing tree except treap
Link-cut tree
Wavelet tree
Mergesort tree
Binomial heap
Fibonacci heap
Leftist heap
Dominator tree
3-connected components in O(n)
k-th shortest path
Matching in general graph Weighted matching in general graph Preflow-push
MCMF in O(poly(V,E))
Minimum arborescence (directed MST) in O(ElogV)
Suffix tree
Online convex hull in 2D
Convex hull in 3D
Halfplane intersection
Voronoi diagram / Delaunay triangulation
Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
How to actually use generating functions to solve problems
Lagrange Inversion formula

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

There is a Chinese problemset called ynoi solving it will benefit a lot

→ Reply