Search found 76 matches

by wook
Mon Feb 13, 2006 12:06 pm
Forum: Volume 109 (10900-10999)
Topic: 10993 - Ignoring Digits
Replies: 19
Views: 9656

Now I got accepted. my basic approach wasn't wrong, but I had made a simple mistake. Invalid input format above was another mistake, :) the format my source code used was correct, but during posting here I saw things :P BTW, the correct output for "2 29999" is the string whose length is less than 15...
by wook
Mon Feb 13, 2006 10:47 am
Forum: Volume 109 (10900-10999)
Topic: 10993 - Ignoring Digits
Replies: 19
Views: 9656

for input

Code: Select all

3
2 38
52 17725
2 29999
output

Code: Select all

222222222222222222
55222255225
222222222222222222222........(approximately 30000 digits)......22
Is it right?

However, the length of output seems to be very large..
by wook
Sun Feb 12, 2006 2:01 pm
Forum: Volume 109 (10900-10999)
Topic: 10991 - Region
Replies: 17
Views: 8766

Use The Cosine Law(Theorem).

a^2 = b^2 + c^2 - 2bc cosA
by wook
Sun Feb 12, 2006 10:40 am
Forum: Volume 109 (10900-10999)
Topic: 10990 - Another New Function
Replies: 32
Views: 15460

The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN). (I used just 4 arrays of size 2000000, and used memory is almost 30000. You shouldn't use more than 4 linear-arrays, or you'll get MLE.) for each integer v ∈ [1...N], store the prime facto...
by wook
Sun Feb 12, 2006 8:53 am
Forum: Volume 109 (10900-10999)
Topic: 10990 - Another New Function
Replies: 32
Views: 15460

I got the picture by a simple modification of the sieve of Erastosthenes.
It is very simple idea, and now I finally knew how to do that.

Thank you very much, Abednego.
by wook
Sun Feb 12, 2006 7:52 am
Forum: Volume 109 (10900-10999)
Topic: 10990 - Another New Function
Replies: 32
Views: 15460

hmm..

Anybody please, give me some hints for approaching computation of phi(1 to N) in order that its time-complexity may be O(n logn).
I can't easily find clear one!
by wook
Sun Feb 12, 2006 6:46 am
Forum: Volume 109 (10900-10999)
Topic: 10994 - Simple Addition
Replies: 41
Views: 15828

imnew wrote:what is the result for
p = 1, q = 2147483647
p = 100000, q = 200000
Thanks in advance.....
10737418158 and 499998, respectively.
by wook
Sun Feb 12, 2006 4:59 am
Forum: Volume 103 (10300-10399)
Topic: 10370 - Above Average
Replies: 62
Views: 19372

i think there was a precision error.... since a is integer, sum is integer, too. the code ave=((double)sum/(double)n); for(i=0;i<n;i++) { if(grade[i]>ave) c++; } is proabably making a trivial error! the inequation grade > (sum/n) is equal to grade * n > sum for n is positive. In this way, you use no...
by wook
Sun Feb 12, 2006 4:46 am
Forum: Volume 109 (10900-10999)
Topic: 10990 - Another New Function
Replies: 32
Views: 15460

Can I precompute all phi(1) to phi(N) values in O(N lgN) time?
by wook
Sun Feb 12, 2006 4:23 am
Forum: Volume 109 (10900-10999)
Topic: 10994 - Simple Addition
Replies: 41
Views: 15828

Do you think it is efficient to solve this problem?when i compute sum(p~q) directly i got a TLE.And when i use an array flag[p] to save the sum(1~p) I got a MLE.~~~~~I have no idea,so faint~~~~ sure it is. Computing sum(p~q) directly MUST make TLE. and also you CANNOT use an array like a[2147483647...
by wook
Tue Feb 07, 2006 5:36 pm
Forum: Volume 109 (10900-10999)
Topic: 10983 - Buy one, get the rest free
Replies: 15
Views: 6250

There is no need to implement the complicated push-relabel. There is another algorithm that is also O(n^3), but is much, much, MUCH simpler to code. It's called Dinic's algorithm, and consists of Ford-Fulkerson, plus 1 extra line. I have an implementation here: http://shygypsy.com/tools but please,...
by wook
Tue Feb 07, 2006 5:03 am
Forum: Volume 109 (10900-10999)
Topic: 10983 - Buy one, get the rest free
Replies: 15
Views: 6250

what's the time complexity of your algorithm ? my one is of O(lgm * (m + x)), where x is the running time of Edmons-Karp Algorithm. That is to say, I runned a maxflow algorithm O(lgm) times. I got TLE. should I use more fast maxflow algorithm, like a Relabel-To-Front O(V^3) or Preflow-Push algorithm...
by wook
Mon Feb 06, 2006 1:34 pm
Forum: Volume 103 (10300-10399)
Topic: 10330 - Power Transmission
Replies: 43
Views: 16133

10330 Power Transmission

I used Edmonds-Karp algorithm but WA. to deal with the vertex capacity, i used two additional arrays: vc : the vertex capacity of vertex u vf : the current flow of vertex u always vf <= vc residual capacity of vertex is vc -vf then. so, for every augumenting path P, the flow is min{ every residual c...
by wook
Thu Jan 26, 2006 4:27 pm
Forum: Volume 109 (10900-10999)
Topic: 10989 - Bomb, Divide and Conquer
Replies: 25
Views: 13268

I can't think of very efficient method for this problem.
yes, a general maximum-flow minimum-cut algorithm is too slow!

how faster should I make it?
by wook
Wed Jan 25, 2006 3:15 am
Forum: Volume 109 (10900-10999)
Topic: 10989 - Bomb, Divide and Conquer
Replies: 25
Views: 13268

maxflow mincut

just for pair (1, i), 2<=i<=n

S <- pick up any vertex in V
foreach T in V, S ≠ T
......... m[T] <- maximum_flow(S, V, G)

and, then the minimum-cut is min{ m[T] | T ∈ V, S ≠ T}.


so there can be a O(V^4) algorithm, maybe ,..........

Go to advanced search