Search found 124 matches

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

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

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

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 ...
by sunny
Sun Oct 26, 2008 3:18 pm
Forum: Volume 115 (11500-11599)
Topic: 11539 - Another Word Game
Replies: 6
Views: 2642

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

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

Re: 11485 - Extreme Discrete Summation

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

to:
x=(long long)(p*10+.5);
by sunny
Thu Sep 18, 2008 11:22 pm
Forum: Volume 114 (11400-11499)
Topic: 11485 - Extreme Discrete Summation
Replies: 6
Views: 2082

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

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

Re: 11431 - Partitioning a Number

Sometimes your code does not work for an input<=3.
by sunny
Tue Mar 18, 2008 1:59 pm
Forum: Volume 114 (11400-11499)
Topic: 11424 - GCD - Extreme (I)
Replies: 25
Views: 6612

Re: Got TLE...

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.
by sunny
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: 2035

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

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...
by sunny
Mon Jan 07, 2008 10:02 am
Forum: Volume 113 (11300-11399)
Topic: 11382 - Fear of The Dark
Replies: 8
Views: 1989

CMG wrote:Care to elaborate any? Binary search of what?
For angle, of course.
by sunny
Sat Jan 05, 2008 9:33 pm
Forum: Volume 113 (11300-11399)
Topic: 11381 - Elegant Strings
Replies: 8
Views: 2190

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

Well there are no such cases in the input file.
by sunny
Fri Dec 14, 2007 9:32 pm
Forum: Volume 110 (11000-11099)
Topic: 11091 - How many Knight Placing?
Replies: 5
Views: 2402

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.

Go to advanced search