CSEDU Training 2012 Week 1

Today, we discussed several data structure dependent problems from this page. Most of them are classical type, i.e. common problems and we found the solution ideas quite interesting.

Here is the summery:

#0: Lazy propagation and slicing (compressing search space) ideas in segment tree.

#1: Finding number of intersecting points among axis parallel line segments.

#2: Perimeter and area of union of rectangles.

#3: Finding points in number of rectangles and rectangles covering points.

#4: Sliding window ideas, finding maximal number of points covered by a rectangle placed arbitrarily.

-- and a few others.

After the discussion, we solved this problem to test if we were able to learn anything at all.

Hopefully, the next class, we will have a discussion on the problems on APIO:2007

Problems to be solved before the next class:

SUBSEQ
GSS1
GSS3
GSS5
INCSEQ
INCDSEQ
LIS2
LPERMUT
FREQUENT

All are from http://www.spoj.pl/

Edit: A virtual contest has been arranged. Visit this link.