Search found 71 matches

by kp
Sun Sep 17, 2006 10:47 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13478

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...
by kp
Wed Sep 13, 2006 8:29 am
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17124

Ok, I give up :)
Do you know some greedy that works?
by kp
Wed Sep 13, 2006 1:31 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13478

FAQ wrote:Please help me some I/O please? I still got WA
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

Answer:
Case #1: 1.00
by kp
Wed Sep 13, 2006 1:24 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13478

It also can be solved using binary search + Floyd.
by kp
Tue Sep 12, 2006 11:39 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17124

Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.
by kp
Tue Sep 12, 2006 10:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11093 - Just Finish it up
Replies: 14
Views: 7734

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...
by kp
Tue Sep 12, 2006 1:36 pm
Forum: Volume 110 (11000-11099)
Topic: 11088 - End up with More Teams
Replies: 30
Views: 17124

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.
by kp
Sun Sep 10, 2006 5:35 pm
Forum: Volume 110 (11000-11099)
Topic: 11084 - Anagram Division
Replies: 19
Views: 9221

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...
by kp
Sun Sep 10, 2006 9:29 am
Forum: Volume 110 (11000-11099)
Topic: 11084 - Anagram Division
Replies: 19
Views: 9221

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.
by kp
Sat Sep 02, 2006 11:19 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 10813

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
by kp
Sat Sep 02, 2006 7:59 pm
Forum: Volume 110 (11000-11099)
Topic: 11077 - Find the Permutations
Replies: 14
Views: 6887

Yes, it can be solved in O(n*k)

Hint:
Let c[n][k] is the answer.
Try to find reccursion like

c[n][k] = Function(c[n-1][k],c[n-1][k-1])
by kp
Tue May 30, 2006 7:47 am
Forum: Algorithms
Topic: Help on testing point inside a polygon
Replies: 5
Views: 1766

You can ignore "bad" random points and wait for a "good" one.
by kp
Sat May 13, 2006 10:49 pm
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 16987

2100000056 67333

answer should be

982...016

your program get
983...016

...

see my third post at this topic
by kp
Sat May 13, 2006 10:25 pm
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 16987

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)
instead of

Code: Select all

search(a,b)
by kp
Sat May 13, 2006 7:25 pm
Forum: Volume 110 (11000-11099)
Topic: 11029 - Leading and Trailing
Replies: 43
Views: 16987

Try to replace your part: temp1 = temp1 - temp2 + 4.0; temp3 = pow(10.0, temp1); sprintf(buf1, "%.0Lf", temp3); with this: temp1 = temp1 - temp2; temp3 = pow(10.0, temp1); while (temp3<1000.0) temp3 *= 10.0; int tmp = floor(temp3); while (tmp>999) tmp /= 10; sprintf(buf1, "%d", tmp);

Go to advanced search