I have a problem finding a strongly connected component of size exactly K in a Tournament Graph. Can someone help me?
Thanks in advance

I have a problem finding a strongly connected component of size exactly K in a Tournament Graph. Can someone help me?

Edit: sorry. it's double post.

hm.. I don't want to waste this blog, so I put another variation of this task.

Given an undirected graph, find a cycle of size exactly K

So the contest and fun are over. I can give some FAQ that I encountered during the contest.
1. To compete in this contest, you need to have flash player.
2. Contestants are assigned to several rooms
3. There are several tasks with different points. The points keep decreasing over time.
4. You can submit many solutions before you lock your code. After you have locked your code, you could not submit anymore, even though you are hacked. If you haven't locked your code, you can still submit although you are hacked.
5. If you have locked your code, you are allowed to hack other's solution in your room.

Hi all,

I need your help to solve this problem (task mines day 2 Baltic OI 2010). I heard that it can be solved using Gaussian Elimination (but I haven't had detail ideas). According to what I know, Gaussian Elimination runs in O(N^3) and the space is O(N^2). I tried to transform this problem to gaussian elimination version. I ended up with this transformation:
1. Now define (x,y) into a number (we number every cells start from 1 to N*M)
2. Build N*M equations and save it in gaussian table. So table[i][j] has value 1 if node i and j are adjacent, otherwise 0
3. Input[i][j] (the given input) means how many bombs in cell(i,j) then table[transform(i,j)][N*M+1]=Input[i][j]
4. Solve it using gaussian elimination.

Unfortunately, for above-mentioned solution, I need O((N*M)^2) space and O((N*M)^3) time which is far enough to solve this problem. Any helps and ideas are appreciated. Thank you for your attention.

I am looking forward for a reply.

anyone know how to add handle in blog?
Thanks

Dynamic Programming (DP) :

1. Classic Dynamic Programming
a. LCS
   Problem: 1. SAMER08D

b. LIS
   Problem: 1. Beautiful People
                 2. MDOLLS
                 3. MSTICK
                 4. MCARDS

c. Edit Distance

d. Matrix Chain Multiplication
   Problem: 1. Mixtures

e. Knapsack
   Problem: 1. Scubadiv

2. Advance DP
a. DP k-th lexicographical string
                   2. z-board
                   3. Linear Garden (IOI 2008)

b. DP tree
    Problem: 1. z-sumpaths
                   2. River (IOI 2005)
                   3. z-company
                   4. Greedy Hydra (CNOI 2002)
                   5. VOCV
                   6. PT07F
                   7. PT07X
                   8. nagibni

c. DP+ BIT/segment tree
    Problem: 1. Salesman (IOI 2009)
                   2. explosion
                   3. intervali
                   4. RENT
                   5. INCSEQ
                   6. INCDSEQ

d. DP+ convex hull
    Problem: 1. Batch Scheduling (IOI 2002)
                   2. NKLEAVES
                   3. Harbingers (CEOI 2009)
                   4. Commando (APIO 2010)

e. DP pre-processing
    Problem: 1. Oil (APIO 2009)
                   2. Garden (IOI 2005)
                   3. Pyramid (IOI 2006)

f. DP bitmask
   Problem: 1. Reklame
                  2. Chess
                  3. Bond
                  4. TRSTAGE
                  5. HIST2
                  6. LAZYCOWS

g. Problem 1: Grid (BOI 2008)

h. DP matrix multiplication/ DP using recurrence
    Problem 1. SEQ
                  2. SPP
                  3. z-funkcija
                  4. mit-indiv09-words
                  5. Reading (Balkan 2009)
                  6. Super Climber
                  7. z-mario

i. DP+ trie
   Problem 1. MORSE

j. DP+geometry
   Problem 1. MPOLY
                 2. CVXPOLY
                 3. MTRIAREA

k. DP + Binary Search
l. DP + Knuth Optimization
   Problem 1. Breaking Strings
Other Problems in SPOJ can be found here by pt1989
Thanks to pt1989

Here are problems in acm.sgu.ru 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494
Thanks to natalia

Reference:
      1. Topcoder
      2. Codechef

Name                     : Harta Wijaya
Country                  : Indonesia
Email                      : [email protected]
Link                       : z-trening
Topcoder Handle   : Harta
Facebook Account : harta01