CSEDU Training 2012 Week 5, 6, 7, 8

Week 5

Link to practice contest 5

The main focus was mathematics and a few more 2-SAT problems. We've tried several problems regarding Gaussian Elimination. Gaussian Elimination problems are bit difficult because there are lots of things to consider during the process and sometimes there are scopes of optimization. In the practice problemset, there are a few gaussian elimination problems to test you gaussian elimination skills.

Problems from APIO 2009 was also discussed. Next week, we hope to discuss APIO 2010.

Week 6

Link to practice contest 6

The main focus was dynamic programming and a bit of computational geometry. We also discussed problems on heavy light decomposition problems (For example SPOJ GSS7 and problem A from Buet contest). However, there is a way where particular instance of heavy light decomposition can be solved using LCA-to-RMQ approach (tutorial from topcoder). APIO 2010 problems were postponed to next week because no one had their homework in time :P

Week 7

Link to practice contest 7

Problemset consists of APIO 2010 and a number of computational geometry. Vector geometry was discussed. The three types of transformation i.e. Rotation, Translation, Scaling was discussed and how to get them done using matrices. For rotation, there are a simpler way to do where you do not need to remember the matrix.

Then, 3D convex hull gave us a lot of trouble. We could easily derive and idea of O(n^4) but this is too costly. Then we've found a O(n^2) idea which was hard to code. Next schedule was APIO 2011 which is to be discussed on the next class after IUT Contest. Our instructor gave us a few idea on some of the problems though, but the solutions were quite astonishing and none was able to go near the correct solution unfortunately.

Week 8

No practice contest was hosted due to the close coming IUT Contest. Also not much was discussed, a few chit chat and several random problems.

In the mean time, we had a few team contests for IUT practice. Here are the links: (in no particular order)

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=8710#overview

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=8716#overview

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=8754#overview

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=8801#overview

However, we performed really bad in IUT contest, and not that we were not able to solve the problems, but, we failed to manage time and team co-ordination. Better luck next time :)

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.