### Harta's blog

By Harta, 14 years ago,
I have a problem finding a strongly connected component of size exactly K in a Tournament Graph. Can someone help me?
• 0

By Harta, 14 years ago,
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
• 0

By Harta, 14 years ago,
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.
• +19

By Harta, 14 years ago,
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.
• +12

By Harta, 14 years ago,
anyone know how to add handle in blog?
Thanks
• 0

By Harta, 14 years ago,
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

a. DP k-th lexicographical string
Problem: 1. z-01 paths
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)

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
Problem 1. Game (IOI 2008, Practice session)

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 269273304317356396445447458489494
Thanks to natalia

Reference:
1. Topcoder
2. Codechef
• +4

By Harta, 14 years ago,
Name                     : Harta Wijaya
Country                  : Indonesia
Email                      : [email protected]