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.
No comments:
Post a Comment