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

- Thu Nov 20, 2003 6:14 am
- Forum: Volume 100 (10000-10099)
- Topic: 10039 - Railroads
- 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**

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

- Fri Oct 31, 2003 9:43 am
- Forum: Other words
- Topic: Microsecond Running Times!
- Replies:
**10** - Views:
**2574**

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