Monday, May 28, 2012

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 and 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 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