OJ Board

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

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!

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.

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

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

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

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

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

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!

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

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

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

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

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 )

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