## Search found 151 matches

Fri Nov 28, 2003 12:21 pm
Forum: Algorithms
Topic: LIS, better then O(n^2)?
Replies: 16
Views: 11944
I'm very sorry to admit I, finally, submitted a precalced version today :oops: With Haeya @ YONSEI I did 0.000 sec. But this is only a precalc and do not think my algo is that fast! :) My original program is ranked 12th, timing 0.521 sec. Yeah I know it's a cheat but sometimes it is tempting. :oops:
Tue Nov 25, 2003 9:29 pm
Forum: Volume 104 (10400-10499)
Topic: 10474 - Where is the Marble?
Replies: 50
Views: 19945
I myself didn't solve this one but you can find "first" expected key when there are duplicates too. This one is covered in "Programming Pearls", a book of collection of issues from CACM. So for your binary search you have a loop invariant, for each turn, the index I you are looking for, suffices the...
Tue Nov 25, 2003 9:18 pm
Forum: Volume 1 (100-199)
Topic: 193 - Graph Coloring
Replies: 93
Views: 22132
I can't think of a P time class solution, for graph coloring is a well-known NP problem. (Of course this problem is not the exact instance of it) My solution is backtracking and it runs in 0.037.

So, if you have discovered any DP algorithm other than 2^N, it will be no dumb but really great
Thu Nov 20, 2003 6:14 am
Forum: Volume 100 (10000-10099)
Replies: 20
Views: 8431
If you try to solve this problem with Dijkstra, You will have one instance of each city in each discrete time. So you can have at most 100 * 1000 = 100,000 vertices. Of course it is unlikely V can be that large, but it can be too critical. So try modeling this problem as something other than a short...
Wed Nov 19, 2003 7:24 pm
Forum: Volume 105 (10500-10599)
Topic: 10511 - Councilling
Replies: 26
Views: 11921
Hi! I just solved this problem using Edmonds-Karp maximum flow algorithm, where the time complexity is O(VE^2). It runs in 0.7 sec, so I think it's your implementation that is wrong but not your algorithm. And, you can use some preflow-push (V^2E) or lift-to-front(V^3), but in this problem E is like...
Fri Nov 14, 2003 10:13 am
Forum: Volume 8 (800-899)
Topic: 861 - Little Bishops
Replies: 33
Views: 21106
No one can help by saying a formula, because giving out formulas can never help someone :) Here you have some observations: Assume a chessboard with black and white squares. If a bishop is on a white square, can it attack bishops on black squares? No. So you can divide the chessboard into two indepe...
Thu Nov 13, 2003 6:50 pm
Forum: Volume 101 (10100-10199)
Topic: 10171 - Meeting Prof. Miguel...
Replies: 68
Views: 24623
After some nasty submissions & WAs, I found out they have some self-loops in the input. (Can be crucial to some who used Floyd's algo like me..)
Thu Nov 13, 2003 5:55 am
Forum: Volume 102 (10200-10299)
Topic: 10249 - The Grand Dinner
Replies: 19
Views: 12546
I cannot think of a greedy solution that works. I used preflow-push, which is O(V*V*E). It sufficed to finish the problem in about 3 sec.. Moreover, the implementation of preflow-push is shorter and maybe easier than that of Edmonds-Karp, so I suggest you should look it up. :) CLR covers it. Good lu...
Thu Nov 13, 2003 5:52 am
Forum: Other words
Topic: Newcomer problems
Replies: 15
Views: 13848
I would recommend these few typical problems in some categories: Dynamic Programming: 10003 Cutting Sticks 10192 Vacation 10306 e-Coins 10051 Tower of Cubes Backtracking: 399 Another Puzzling Problem Graph Theory: 10004 Bicoloring 10099 The Tourist Guide 10147 Highways 10305 Ordering Tasks Some ad-h...
Tue Nov 11, 2003 3:34 pm
Forum: Volume 105 (10500-10599)
Topic: 10580 - Ransom Note
Replies: 3
Views: 4122
Quoting from an e-mail I wrote: You can easily prove that for each message, it is optimal to find the logest prefix infringement and remove it. So from there you can apply mathematical induction to prove the optimality of the solution. So it's (kind of) a greedy method. For the implementation detail...
Fri Oct 31, 2003 9:54 am
Forum: Volume 102 (10200-10299)
Topic: 10226 - Hardwood Species
Replies: 121
Views: 39254
In your code, searching a tree costs O(n) and inserting costs O(1).

But, you can do binary searching to reach O(logn) in searching and doing inserting with O(n).

It is likely the latter will be faster, since you'll have only 10,000 insertings and 1,000,000 searchings.

Hope this helps!
Fri Oct 31, 2003 9:43 am
Forum: Other words
Topic: Microsecond Running Times!
Replies: 10
Views: 2574
You can avoid using printf and scanf too by writing them yourself.
I hear some of the gurus here use their own-written floating point input & output functions, which are much faster than the formatted scanf() and printf().

Great, huh?
Wed Oct 29, 2003 5:55 pm
Forum: Volume 102 (10200-10299)
Topic: 10253 - Series-Parallel Networks
Replies: 16
Views: 5625
I suffered from stupid mistakes I made in solving this problem and I just got AC. You can tackle this problem with dynamic programming. You should focus on there are two types of networks: one kind which are parallel connected, and another kind which are serial connected. You'll have enumerable numb...
Fri Oct 24, 2003 7:23 pm
Forum: Volume 105 (10500-10599)
Topic: 10567 - Helping Fill Bates
Replies: 15
Views: 7757
Hi, I just solved this problem with binary search but I am really curious about whether there might be an observation I am missing, which can lead to a simpler solution. My solution is as follows: (Spoiler!!) For the sequence S, keep an array COUNT of 52 elements for each of the letters S_i, where C...
Thu Oct 16, 2003 8:52 am
Forum: Volume 1 (100-199)
Topic: 165 - Stamps
Replies: 10
Views: 2849
Can anybody who got AC post their output with this input?
It seems like an easy problem but I'm stuck on this
5 4
4 5
6 3
8 2
4 4
5 5
0 0