## Search found 76 matches

- 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...

- Mon Feb 13, 2006 10:47 am
- Forum: Volume 109 (10900-10999)
- Topic: 10993 - Ignoring Digits
- Replies:
**19** - Views:
**9656**

for input
output
Is it right?

However, the length of output seems to be very large..

Code: Select all

```
3
2 38
52 17725
2 29999
```

Code: Select all

```
222222222222222222
55222255225
222222222222222222222........(approximately 30000 digits)......22
```

However, the length of output seems to be very large..

- Sun Feb 12, 2006 2:01 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10991 - Region
- Replies:
**17** - Views:
**8766**

- 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...

- Sun Feb 12, 2006 8:53 am
- Forum: Volume 109 (10900-10999)
- Topic: 10990 - Another New Function
- Replies:
**32** - Views:
**15460**

- Sun Feb 12, 2006 7:52 am
- Forum: Volume 109 (10900-10999)
- Topic: 10990 - Another New Function
- Replies:
**32** - Views:
**15460**

- Sun Feb 12, 2006 6:46 am
- Forum: Volume 109 (10900-10999)
- Topic: 10994 - Simple Addition
- Replies:
**41** - Views:
**15828**

- 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...

- Sun Feb 12, 2006 4:46 am
- Forum: Volume 109 (10900-10999)
- Topic: 10990 - Another New Function
- Replies:
**32** - Views:
**15460**

- 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...

- 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,...

- 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...

- 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...

- Thu Jan 26, 2006 4:27 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10989 - Bomb, Divide and Conquer
- Replies:
**25** - Views:
**13268**

- 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 ,..........

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 ,..........