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.
Search found 124 matches
- Thu Oct 30, 2008 12:16 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11544 - Recruiter's Problem
- Replies: 12
- Views: 2253
- Thu Oct 30, 2008 10:30 am
- Forum: Volume 115 (11500-11599)
- Topic: 11544 - Recruiter's Problem
- Replies: 12
- Views: 2253
Re: 11544 - Recruiter's Problem
>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.
>This does not seem to work.
When I process the jobs for a worker, actually I remove that worker form the network.
- Mon Oct 27, 2008 12:48 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11544 - Recruiter's Problem
- Replies: 12
- Views: 2253
Re: 11544 - Recruiter's Problem
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 ...
- Sun Oct 26, 2008 3:18 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11539 - Another Word Game
- Replies: 6
- Views: 2978
Re: 11539 - Another new game
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.
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.
- Sun Oct 19, 2008 5:55 pm
- Forum: Volume 115 (11500-11599)
- Topic: 11522 - Pyramid Number
- Replies: 1
- Views: 990
Re: 11522 - Pyramid Number
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.
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.
- Sun Sep 21, 2008 6:52 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11485 - Extreme Discrete Summation
- Replies: 6
- Views: 2356
Re: 11485 - Extreme Discrete Summation
In your code change
x = (long long)(p*10);
to:
x=(long long)(p*10+.5);
x = (long long)(p*10);
to:
x=(long long)(p*10+.5);
- Thu Sep 18, 2008 11:22 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11485 - Extreme Discrete Summation
- Replies: 6
- Views: 2356
Re: 11485 - Extreme Discrete Summation
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.
Once you realize it , just a simple knapsack like DP is needed.
- Mon Aug 04, 2008 10:23 am
- Forum: Volume 114 (11400-11499)
- Topic: 11476 - Factorizing Large Integers
- Replies: 17
- Views: 8873
Re: 11476
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.
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.
- Wed Jun 11, 2008 4:45 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11431 - Partitioning a Number
- Replies: 7
- Views: 2348
Re: 11431 - Partitioning a Number
Sometimes your code does not work for an input<=3.
- Tue Mar 18, 2008 1:59 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11424 - GCD - Extreme (I)
- Replies: 25
- Views: 7627
Re: Got TLE...
You can't get AC with a O(N^2) algorithm. Read the previous posts carefully to get an idea of an efficient solution.Obaida wrote:How I could reduce time here... Some one please help me...
- Fri Jan 18, 2008 7:33 pm
- Forum: ACM ICPC Archive Board
- Topic: The Bells are Ringing(A problem from Dhaka regional 2007)
- Replies: 2
- Views: 2291
- Thu Jan 17, 2008 5:51 pm
- Forum: ACM ICPC Archive Board
- Topic: The Bells are Ringing(A problem from Dhaka regional 2007)
- Replies: 2
- Views: 2291
The Bells are Ringing(A problem from Dhaka regional 2007)
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...
- Mon Jan 07, 2008 10:02 am
- Forum: Volume 113 (11300-11399)
- Topic: 11382 - Fear of The Dark
- Replies: 8
- Views: 2388
- Sat Jan 05, 2008 9:33 pm
- Forum: Volume 113 (11300-11399)
- Topic: 11381 - Elegant Strings
- Replies: 8
- Views: 2487
- Fri Dec 14, 2007 9:32 pm
- Forum: Volume 110 (11000-11099)
- Topic: 11091 - How many Knight Placing?
- Replies: 5
- Views: 2620