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

Thanks in advance

Thanks in advance

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 150 |

7 | SecondThread | 150 |

9 | pajenegod | 145 |

10 | BledDest | 144 |

Thanks in advance

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

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.

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

Thanks

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

a. DP k-th lexicographical string

Problem: 1. z-01 paths

2. z-board3. 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 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494

Thanks to natalia

Reference:

1. Topcoder

2. Codechef

Country : Indonesia

Email : [email protected]

Link : z-trening

Topcoder Handle : Harta

Facebook Account : harta01

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 21:55:00 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|