CSEDU Training 2012 Week 3, 4

Ah, I am two days late!

Week 3 was off due to ACM ICPC World Finals 2012. It was really intense and SPbNRU ITMO won the contest. A practice contest was hosted and here is the link.

Problem from APIO 2008 were discussed. The main focus of the class was on 2-SAT problems. Problems and strategies discussed from infoarena.ro and lightoj.com. The main difficulty on solving 2-SAT problem is understanding that the problem can be formulated as a 2-SAT problem. Generally 3-SAT or k-SAT problems falls on NP range, but 2-SAT is most of the time solvable by finding strongly connected component on a directed graph where edges indicates the clauses.

A little flashback on segment tree was also present on the class. We solved 56-E from codeforces.com which was apparently the solution idea of Google Codejam 2012 Round 2 Problem A.

This week's virtual contest was also based on data-structure based problems. Contest is already finished and the link is here.

CSEDU Training 2012 Week 2

Problems from APIO 2007 were discussed and the solutions seem to be not that hard (well that happens whenever someone tells you the solutions).  A few more data structure based solutions were discussed along with problems from last week's virtual contest.

Next day we will be discussing on APIO 2008 problems, and the problem from tonight's virtual contest. A famous problem from SPOJ is discussed (problem code: CHAIN). I have already seen this problem before but could not manage to solve it and all I got was numerous infamous WA (wrong answer). Shanto vai gave as a different type of simpler solution based on weighted union-find structure (really I heard this for the first time in my life today).

From next week, the classes will be held from 2:30PM instead of 4PM as now, and they will be extended up to 5:30PM hopefully.

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

GIT What I Need

Mainly I use GITHUB for my personal repository so that I can access some files not when I am home, and every time I try to add something to github from my local repository, I almost always forget the commands. That's why I am writing the three line commands I will always need, just for my convenience :)

git status -s

git add <filename>

git config --global user.name "<my_name>"

git config --global user.email <my_email>

git commit -m "<my_commit_msg>"

git push origin master

That will do for now. A total reference can be found here.

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.