UVa OJ Board

You'd better google them. Queries like "Karger min cut" will easily get you this link.

Good luck!

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

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?

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

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

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

Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!

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

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

My AC program writes 4.

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

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

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

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.

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