Harta's blog

By Harta, 9 years ago, In English,
I have a problem finding a strongly connected component of size exactly K in a Tournament Graph. Can someone help me?
Thanks in advance

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Harta, 9 years ago, In English,
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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Harta, 9 years ago, In English,
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.

Read more »

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

By Harta, 9 years ago, In English,
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.

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By Harta, 9 years ago, In English,
anyone know how to add handle in blog?
Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Harta, 9 years ago, In English,
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
    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)

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

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By Harta, 9 years ago, In English,
Name                     : Harta Wijaya
Country                  : Indonesia
Email                      : hw_stosa@yahoo.com
Link                       : z-trening
Topcoder Handle   : Harta
Facebook Account : harta01

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it