Monday, June 25, 2012

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

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

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)

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 :)

3 comments:

  1. Really interesting training weeks! Could you please suggest some problems solved by Gaussian Elimination. I've seen kirchoff's Matrix Theorem, but except for this nothing else.
    Thank you

    ReplyDelete
    Replies
    1. http://lightoj.com/volume_problemcategory.php?user_id=1019&category=Gaussian%20Elimination
      http://problemclassifier.appspot.com/index.jsp?search=gaussian&usr=
      http://uvatoolkit.com/problemssolve.php [ just search gaussian ]
      also some problems are in one of the contests linked on the post.

      Delete
    2. Could you please give me some problems solved with Fast Fourier Transform. I have seen some applications on strings, but not much. Have you tried to code polynomial multiplication with FFT?

      Delete