Search found 124 matches

Thu Oct 30, 2008 12:16 pm
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1932

Re: 11544 - Recruiter's Problem

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.
Thu Oct 30, 2008 10:30 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1932

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.
Mon Oct 27, 2008 12:48 pm
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1932

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

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.
Sun Oct 19, 2008 5:55 pm
Forum: Volume 115 (11500-11599)
Topic: 11522 - Pyramid Number
Replies: 1
Views: 869

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.
Sun Sep 21, 2008 6:52 pm
Forum: Volume 114 (11400-11499)
Topic: 11485 - Extreme Discrete Summation
Replies: 6
Views: 2124

Re: 11485 - Extreme Discrete Summation

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

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.
Mon Aug 04, 2008 10:23 am
Forum: Volume 114 (11400-11499)
Topic: 11476 - Factorizing Large Integers
Replies: 17
Views: 8073

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.
Wed Jun 11, 2008 4:45 pm
Forum: Volume 114 (11400-11499)
Topic: 11431 - Partitioning a Number
Replies: 7
Views: 2097

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

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.
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: 2074
I can't believe how terribly I misunderstood the problem.
Thanx...AC now.
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: 2074

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: 2028
CMG wrote:Care to elaborate any? Binary search of what?
For angle, of course.
Sat Jan 05, 2008 9:33 pm
Forum: Volume 113 (11300-11399)
Topic: 11381 - Elegant Strings
Replies: 8
Views: 2238
You mean where S/T may be a empty string?

Well there are no such cases in the input file.
Fri Dec 14, 2007 9:32 pm
Forum: Volume 110 (11000-11099)
Topic: 11091 - How many Knight Placing?
Replies: 5
Views: 2430
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.