## Search found 151 matches

Mon Jun 05, 2006 2:35 pm
Forum: Volume 109 (10900-10999)
Topic: 10989 - Bomb, Divide and Conquer
Replies: 25
Views: 13418
You'd better google them. Queries like "Karger min cut" will easily get you this link.

Good luck!
Mon Jun 05, 2006 8:40 am
Forum: Volume 109 (10900-10999)
Topic: 10904 - Structural Equivalence
Replies: 13
Views: 5218
Thanks for the answer. However, the problem statement is still confusing. The only definition of "equivalence" it gives is "if they are both structures containing equivalent types in the same order". Then, are these two equivalent? type A = struct(int A) type B = struct(B int) If we have to merely c...
Sun Jun 04, 2006 6:27 pm
Forum: Volume 109 (10900-10999)
Topic: 10904 - Structural Equivalence
Replies: 13
Views: 5218
Infinite things make me sick..
A = struct (int A int)
B = struct (int B)
Are these two equivalent? A will only have even number of ints but it's not true for B.

Mmm.. Am I missing something?
Sat Nov 06, 2004 12:17 pm
Forum: Other words
Topic: "Mondriaan's Dream" made me crazy
Replies: 3
Views: 2276
You can solve the problem with dynamic programming, with an exponential space complexity of O(w*(2^h)) and time complexity like O(wh*2^h). The key observation is when you are filling column #i, there are 2^h possibilities where a block spans from column #(i-1). (Hmm, it's not easy to explain.. Maybe...
Tue Oct 19, 2004 8:11 am
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17692
Okay, it seems I'm the second C++ programmer who broke the pascal implementation.. Haha :wink: (With a very close shave of 0.002 second :lol: ) What I did was inserting all vectors of alphabet frequencies into a trie. By building the trie with the frequencies (instead of the letter itself) I think y...
Thu Jul 08, 2004 7:06 am
Forum: Volume 106 (10600-10699)
Topic: 10680 - LCM
Replies: 38
Views: 13133
Here is my output:
8
6
4
4
6
2
2
6
8
6
2
4
6
2
8
6
4
2
2
4
4
2
4
4
8
6
6
4
8
6
6
4
4
6
6
6
8
6
6
4
2
2
8
8
2
6
8
2
8
6
6
8
2
2
8
2
4
4
4
8
4
6
2
8
6
8
2
4
6
8
8
4
4
2
6
4
2
2
6
2
8
8
2
4
6
4
6
2
6
8
2
6
6
2
2
4
6
2
6
6
Hope it helps
Tue May 11, 2004 4:41 pm
Forum: Volume 106 (10600-10699)
Topic: 10613 - Mushroom Misery
Replies: 14
Views: 6466
Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!
Mon Mar 15, 2004 8:19 am
Forum: Volume 1 (100-199)
Topic: 143 - Orchard Trees
Replies: 90
Views: 13905
As far as I am concerned, there are extremely many data so your O(100^2) algorithm cannot handle it. You need to do it by O(100).

(My O(100) Program runs in 0.414 sec, so when the constant factor is doubled it will time out.)
Mon Mar 15, 2004 7:53 am
Forum: Off topic (General chit-chat)
Topic: Are you an ACM member?
Replies: 10
Views: 4684
What you should not believe is not your eyes, but your expectation that every user will scroll down the forum list down to here.

A lot of members from here did participate in the Finals, so there should be quite a lot. And I am also one of those
Tue Mar 09, 2004 6:42 pm
Forum: Volume 105 (10500-10599)
Topic: 10595 - Knight on the Bee Board
Replies: 17
Views: 11728
My AC program writes 4.
Mon Mar 08, 2004 7:51 pm
Forum: Volume 101 (10100-10199)
Topic: 10149 - Yahtzee
Replies: 20
Views: 12106
I did Simulated Annealing to get AC..
Assigning categories from the first round, we only have 2^13 possibilities, that each category is used/or not.

So a dynamic programming algorithm seems to be feasible..
Mon Mar 08, 2004 4:41 pm
Forum: Other words
Topic: World Finals Warmup 1 will run for 18 hours.
Replies: 10
Views: 2950
Yeah, all cheaters are spoilling their own chance, to compete against those world class problem solvers. I don't want to miss such a great chance. :) And I strongly believe those who go up in the ranklist will never do that. Isn't it?! I think it will not annoy to have a third ranklist. (Though I'm ...
Fri Mar 05, 2004 9:56 am
Forum: Algorithms
Topic: Hungarian method
Replies: 1
Views: 1752

### Hungarian method

Anyone could point out some useful reference or papers to the hungarian method? I tried google and citeseer, and acm portal but I could pick out which is the one I need. And one more: Are there more than one implementations which are called hungarian methods? I found two differing implementation and...
Sun Feb 29, 2004 5:25 am
Forum: Volume 105 (10500-10599)
Topic: 10575 - Polylops
Replies: 11
Views: 3592
Oops.. my program contained an error on the interpretation of the problem. I'm amazed I got accepted along with this bug.

Your output seems to be correct on Poly 4.
Sat Feb 28, 2004 2:29 pm
Forum: Volume 105 (10500-10599)
Topic: 10575 - Polylops
Replies: 11
Views: 3592
My solution prints Polygon #1 has 4 symmetry line(s). Polygon #2 has 1 symmetry line(s). Polygon #3 has 1 symmetry line(s). Polygon #4 has 3 symmetry line(s). Polygon #5 has 2 symmetry line(s). Polygon #6 has 0 symmetry line(s). Polygon #7 has 0 symmetry line(s). It seems your problem is that you ig...