UVa OJ Board

1) Yes. I think that's why my solution is slower. But I clear flows and re-run network flow if that job choice for the current worker was not in the previous computed flow. Otherwise just assign that worker to that job and go for the next worker.
2)Ford-fulkerson.

>Suppose just 1 worker, and 5 jobs. Remove any edge, and the flow is still 1.
>This does not seem to work.

When I process the jobs for a worker, actually I remove that worker form the network.

I didn't use min-cost-max-flow. Solved it by normal max-flow. Suppose edges are ordered by worker #1's most preferred job,2nd most preferred job,....worker#2's most preferred,2nd most preferred and so on. To determine the assignment, I removed each edge in increasing order and saw if it reduces the ...

STL map is too slow for this problem. I used trie to determine the matches at every position.

The maximum word length can be 100. So while doing the DP you only need to check the next 100 positions.

Also avoid using cin too.

You can write a brute force solution to generate all pyramid numbers <=100(or 150).
After observing those pyramid numbers you can find the solution. This is the way I solved it.

Also don't forget to handle cases like : "1000 1".
There are inputs where a>b.

In your code change
x = (long long)(p*10);

to:
x=(long long)(p*10+.5);

You only need to deal with the floating point part of all numbers.
Once you realize it , just a simple knapsack like DP is needed.

My code doesn't use Brent's improvement just normal Pollard Rho method.
Robert Gerbicz's solution is much faster than mine.

First I wanted to make the test data little more tight so only the Brent versions could pass, but later
stopped from doing that.

Sometimes your code does not work for an input<=3.

Obaida wrote:How I could reduce time here... Some one please help me...

You can't get AC with a O(N^2) algorithm. Read the previous posts carefully to get an idea of an efficient solution.

I can't believe how terribly I misunderstood the problem.
Thanx...AC now.

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4060 I can't understand why I am getting WA. I also checked with a brute force code. Someone who got AC please verify these inputs: input: 15 60 100 10000 100000 987654321 1234567890123456789 1000000000000000000 9876543210987654321 12...

CMG wrote:Care to elaborate any? Binary search of what?

For angle, of course.

You mean where S/T may be a empty string?

Well there are no such cases in the input file.

tobby wrote: Are there any other tasks that can be solved by this way?

Problem 10743(Blocks on Blocks) needs the matrix multiplication method to solve.