## Search found 519 matches

- Thu Apr 03, 2008 4:45 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11446 - Where is the 'back' button?
- Replies:
**17** - Views:
**3175**

### Re: 11446 - Where is the 'back' button?

Oh, no wonder I couldn't find any faster algorithm. I thought of a bruteforce O(n*2^n) algorithm long time ago, but thought that the time limit is too tight for it. Now I see that I can use bitmask to make it O(2^n), which should be fast enough.

- Thu Apr 03, 2008 11:38 am
- Forum: Volume 114 (11400-11499)
- Topic: 11446 - Where is the 'back' button?
- Replies:
**17** - Views:
**3175**

### Re: 11446 - Where is the 'back' button?

So what's the idea for the correct algorithm?

- Thu Apr 03, 2008 3:30 am
- Forum: FAQ
- Topic: About the new forum
- Replies:
**13** - Views:
**8976**

### Re: About the new forum

yep, I think we are both supposed to be gurus instead of new posters.

- Thu Apr 03, 2008 2:55 am
- Forum: Volume 114 (11400-11499)
- Topic: 11442 - Linear Diophantine Tidbits
- Replies:
**1** - Views:
**888**

### Re: 11442 - Linear Diophantine Tidbits

Short answer is: No, there is no known generalization of Pick's theorem for 3d space. You probably know that the given triangle lies on a certain plane, so it lies in 2d space. All you need to do is to find a parametrization of the plane in such a way that the use of Pick's theorem on the parametriz...

- Wed Apr 02, 2008 4:20 am
- Forum: Volume 114 (11400-11499)
- Topic: 11446 - Where is the 'back' button?
- Replies:
**17** - Views:
**3175**

### Re: 11446 - Where is the 'back' button?

My guess would be 0, but I could be wrong. What I'm getting at is that isolated vertices can be treated separately anyway. Just try both and see which one works. A more general question, for P=2 and L=2, and if we have edge (0,0) and (0,1). Is the solution 0, since you can never leave vertex 1, and ...

- Wed Apr 02, 2008 4:17 am
- Forum: Volume 114 (11400-11499)
- Topic: 11408 - Count DePrimes
- Replies:
**12** - Views:
**5643**

### Re: 11408 - Count DePrimes

There a few problems with the code. I can definitely tell that it is TLE even without running the code. First factor(n) is too slow for 3 secs. Why not use the information in the sieve to help you factor? If you coded it correctly, factoring n can be done using O(k) operations for each n, where k is...

- Tue Apr 01, 2008 10:02 am
- Forum: Volume 114 (11400-11499)
- Topic: 11446 - Where is the 'back' button?
- Replies:
**17** - Views:
**3175**

### Re: 11446 - Where is the 'back' button?

I think the idea of contraction is still correct. But you need to keep track of vertices of 2 types, those that already formed a loop, and those that don't. There is an obvious upper bound and lower bound of number of additional edges needed, but I can construct examples that actually requires the u...

- Tue Apr 01, 2008 4:50 am
- Forum: Volume 114 (11400-11499)
- Topic: 11434 - Careless Postman Problem
- Replies:
**4** - Views:
**1184**

### Re: 11434 - Careless Postman Problem

I'm starting to think that the judge input contains bugs.

I used
and it gave run time error.

I used

Code: Select all

```
assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
```

- Mon Mar 31, 2008 9:30 am
- Forum: Volume 114 (11400-11499)
- Topic: 11434 - Careless Postman Problem
- Replies:
**4** - Views:
**1184**

There was a clarification that the third case should be: 2 2 1 2 1 1 1 2 1 1 1 1 ----- Rio Ok, now I don't understand why I keep getting WA. Basically, I convert each edge into an edge with 0 as lower capacity and p-q as upper capacity, and I adjust the supply/demand on the vertices accordingly. I ...

- Mon Mar 31, 2008 6:28 am
- Forum: Volume 114 (11400-11499)
- Topic: 11434 - Careless Postman Problem
- Replies:
**4** - Views:
**1184**

### 11434 - Careless Postman Problem

I am trying to solve this problem using min cost flow, but I don't quite understand the 3rd sample testcase.
Why is the result 2?

Shouldn't it be Impossible, since qi>pi?

Code: Select all

```
2 2
1 2 1 1 0
2 1 1 1 0
```

Shouldn't it be Impossible, since qi>pi?

- Sat Mar 29, 2008 3:24 am
- Forum: Volume 114 (11400-11499)
- Topic: 11428 - Cubes
- Replies:
**64** - Views:
**16907**

- Thu Mar 27, 2008 10:14 am
- Forum: Volume 114 (11400-11499)
- Topic: 11431 - Partitioning a Number
- Replies:
**7** - Views:
**2098**

- Wed Mar 26, 2008 9:11 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11428 - Cubes
- Replies:
**64** - Views:
**16907**

- Tue Mar 25, 2008 1:45 am
- Forum: Volume 114 (11400-11499)
- Topic: 11429 - Randomness
- Replies:
**4** - Views:
**1470**

### Re: 11429 - Randomness

Is the solution correct? Input: 2 5 1 5 1 5 1 5 1 5 1 5 Output: 4.400000 My AC code returns by 3.600000 [don't forget, that :"Input will be terminated by a line containing two zeros."] Ps. I've proved that the greedy solution is correct in all cases. Thanks, I found a bug in my reasoning. I think i...

- Mon Mar 24, 2008 10:29 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11429 - Randomness
- Replies:
**4** - Views:
**1470**

### Re: 11429 - Randomness

For this problem, how would one find the optimal solution? Let g = lcm(b1,b2,...,bn). If R>=g, then the problem is pretty trivial. I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal. My greedy method is independent on the ...