## Search found 71 matches

Sun Sep 17, 2006 10:47 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13794
It also can be solved using binary search + Floyd. I think you binary search for the mean value, but can you explain how you use floyd warshall to test if a cycle with this mean (or less) exists? Well, I know about Karp's algo (see Cormen) but I solved it using Floyd only! Here is my idea: I want t...
Wed Sep 13, 2006 8:29 am
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17644
Ok, I give up
Do you know some greedy that works?
Wed Sep 13, 2006 1:31 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13794
Be sure you handle cases with muliple edges from a to b correctly.

Test:

1
3 5
1 2 1
2 3 5
3 1 1
3 1 5
2 3 1

Case #1: 1.00
Wed Sep 13, 2006 1:24 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13794
It also can be solved using binary search + Floyd.
Tue Sep 12, 2006 11:39 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17644
Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.
Tue Sep 12, 2006 10:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11093 - Just Finish it up
Replies: 14
Views: 8175
I solved it in O(n) as follows: 1. Starting from any station (let's call it START) and trying to finish the lap. If it's possible then goto print answer, else let's say I couldn't get from p to p+1. 2. Starting from p+1 and trying to finish lap. (I don't need to look for the path starting from inter...
Tue Sep 12, 2006 1:36 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17644
I solved it using both DP and greedy.

Greedy is as follows:
1. Take one guy with maximum value
2. Take two appropriate guys with minimum sum of values

However, I have not proved it.
Sun Sep 10, 2006 5:35 pm
Forum: Volume 110 (11000-11099)
Topic: 11084 - Anagram Division
Replies: 19
Views: 9461
i used smth. like this: mask - bit state need - remainder to get n - number of 1's in mask ... map <pair<int,int>,int> m; int solve(int mask, int need, int n){ int res=m[make_pair(mask,need)]; if (res>0) return res-1; // here comes actual solution m[make_pair(mask,need)]=res+1; return res; } ... But...
Sun Sep 10, 2006 9:29 am
Forum: Volume 110 (11000-11099)
Topic: 11084 - Anagram Division
Replies: 19
Views: 9461
tywok wrote:but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!
You can do memorization using STL's map.
Sat Sep 02, 2006 11:19 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 11611
Problem can be solved without maximum matching.
Just think about bipartite graph and it's connected
components.

Edit: example of useless of maximum matching:

1
8 7
0 5
1 5
2 5
3 5
1 4
1 6
1 7

answer should be 4, but MM=2
Sat Sep 02, 2006 7:59 pm
Forum: Volume 110 (11000-11099)
Topic: 11077 - Find the Permutations
Replies: 14
Views: 7151
Yes, it can be solved in O(n*k)

Hint:
Try to find reccursion like

c[n][k] = Function(c[n-1][k],c[n-1][k-1])
Tue May 30, 2006 7:47 am
Forum: Algorithms
Topic: Help on testing point inside a polygon
Replies: 5
Views: 1857
You can ignore "bad" random points and wait for a "good" one.
Sat May 13, 2006 10:49 pm
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 17755
2100000056 67333

982...016

983...016

...

see my third post at this topic
Sat May 13, 2006 10:25 pm
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 17755
It's because of overflow

Replace

Code: Select all

return (pangkat(search(a,b/2))%1000*a%1000)%1000;
with

Code: Select all

return (pangkat(search(a,b/2))%1000*(a%1000))%1000;
or

in the main program use

Code: Select all

search(a%1000,b)