Search found 146 matches

by hank
Mon Aug 20, 2007 3:59 pm
Forum: Volume 108 (10800-10899)
Topic: 10888 - Warehouse
Replies: 19
Views: 12102

Jan wrote:Is it a simple matching or weighted matching? You can find weighted matching by dp. The algorithm takes O(n^2 * 2^n) time.
Hello ,Jan

I use MaximumFlowMinimumCost method to solve this problem.

But could you show me how to apply DP on this problem briefly?

thanks a lot:)
by hank
Mon Aug 20, 2007 10:30 am
Forum: Volume 108 (10800-10899)
Topic: 10888 - Warehouse
Replies: 19
Views: 12102

Hello ,
I got AC by using simple bipartite matching algorithm.
, but I am curious about how to apply DP on this problem.

If someone else can give me hints... :)

Thanks a lot!
by hank
Sat Aug 18, 2007 1:38 pm
Forum: Algorithms
Topic: Japan 2006 - Manhattan Wiring
Replies: 1
Views: 2251

Japan 2006 - Manhattan Wiring

Japan 2006 - Manhattan Wiring

http://acm.pku.edu.cn/JudgeOnline/problem?id=3133

This problem is from ACM ICPC Japan regional 2006.

Some people solved this problem by DP.
But I don't know how to apply DP on this problem.
Does anybody know how to solve this problem by DP?
Thanks in advance.
by hank
Wed Jul 25, 2007 6:39 am
Forum: Volume 112 (11200-11299)
Topic: 11215 - How Many Numbers?
Replies: 11
Views: 4813

I'm not sure I understand your algorithm correct. Will it try something like (1+1)*(1+1)? Yeah it will. An so it will test: 1+(1*1)+1 and (1+1)+1 1+(1+1) and all possible combinations, it's just a backtracking of all the possible cases but it seems horribly slow! Hello, I use backtracking method, a...
by hank
Mon Jul 16, 2007 5:08 am
Forum: Volume 111 (11100-11199)
Topic: 11199 - Equations in Disguise
Replies: 16
Views: 6986

Hello rio, Thanks very much! I tried something similar to the second idea you proposed and some prune. My program took about 30 seconds for the testdata you provide above. It is faster than before, but still slow, and it still got TLE in the onlinejudge. Can we check whether the expression has solut...
by hank
Sun Jul 15, 2007 8:15 am
Forum: Volume 111 (11100-11199)
Topic: 11199 - Equations in Disguise
Replies: 16
Views: 6986

Re: 11199 Equations in Disguise

This is a realy hard problem. Hard to avoid TLE. I manage to run in time (over 40 sec), but now I'm getting WA. If you have tried this problem, and made some io test cases, please share it here. (Even If you are not sure that it is valid). ... Hello rio, I try to solve this problem, but always get ...
by hank
Sat Apr 07, 2007 6:36 am
Forum: Volume 111 (11100-11199)
Topic: 11166 - Power Signs
Replies: 14
Views: 6822

Re: WA aaaaaaah...

anyone can post some input/output? I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results. I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted. thx in advance Hello, Here are some testdata ...
by hank
Thu Apr 05, 2007 4:10 am
Forum: Volume 111 (11100-11199)
Topic: 11182 - Zeroes III
Replies: 12
Views: 4610

Hello, by calculating the sums on paper you can find a formula to compute the number of occurences of a given prime in F2(n). But for each prime p you have to sum these occurences for p, p^2, p^3, ... (Just as you do to determine the number of occurences of a prime p in n!) These are less then log(...
by hank
Mon Apr 02, 2007 9:35 am
Forum: Volume 111 (11100-11199)
Topic: 11182 - Zeroes III
Replies: 12
Views: 4610

Hello ,
Could you give me some hint about how to reduce the complexity from O(nlogb) to O(lognlogb) ?

since we are only interested in the factors of F2(n) related to input b
What does it mean?
Could you please give me some hints?

Thx in advance! :D
by hank
Fri Sep 29, 2006 8:07 am
Forum: Volume 6 (600-699)
Topic: 657 - The die is cast
Replies: 46
Views: 20967

657 The die is cast [WA]

Hi My solution got Wrong Answer. I try many testdata whuch i found in this forum. but i still cannot find any wrong. The problem is very easy.But i cannot got AC. T T #include <iostream> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; char map[51][51]; int w,h; int sum; i...
by hank
Fri Sep 29, 2006 7:09 am
Forum: Algorithms
Topic: I need some Scheduling Problems
Replies: 0
Views: 1111

I need some Scheduling Problems

Hi

I need some Scheduling Problems.
Such as given some tasks and deadline and we have to find out a best order to minimize the total spent time.

Thanks in advance!!

:D
by hank
Tue Sep 19, 2006 11:33 am
Forum: Volume 109 (10900-10999)
Topic: 10907 - Art Gallery
Replies: 22
Views: 9418

My output for Cho's test data (I just talk about the valid ones in his test input) is a little different with Misof's, some of them are 0.01 more than Misof's. Maybe my algorithm loses precision. But still I get AC. This means the test input of the online judge is not very strict in precision, I th...
by hank
Fri Nov 04, 2005 6:17 pm
Forum: Volume 3 (300-399)
Topic: 302 - John's trip
Replies: 20
Views: 4630

I got Accepted after got WA many times. If you are trying to solve it, you must realize: There are something wrong in this problem. The street number can be large than 44. ( I think it is less than 2000 ) And John lives at the street of the first line of each data block. not the "number 1" street! a...
by hank
Thu Oct 20, 2005 10:24 am
Forum: Algorithms
Topic: MinCost MaxFlow with [Undirected Graph]
Replies: 3
Views: 2056

Hi, misof

Thanks for your help.

But are you sure the method is correct ?

your method seems to be right only in MaxFlow problem , not in MaxFlowMinCost problem.

( I am not sure ... maybe I am wrong )
by hank
Thu Oct 20, 2005 7:14 am
Forum: Algorithms
Topic: MinCost MaxFlow with [Undirected Graph]
Replies: 3
Views: 2056

MinCost MaxFlow with [Undirected Graph]

Hello, everybody I know the method to find the minimum cost maximum flow in a directed grapth. But how to find MinCost MaxFlow with an "Undirected" Graph ? I also see the online judge problem "10594 DataFlow" the graph in that problem also is undirected. ( I need a simple algorithm , not too difficu...

Go to advanced search