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: 3250
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: 3250
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: 9056
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: 909
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: 3250
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: 5698
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: 3250
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: 1214
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: 1214
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: 1214
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: 17267
- Thu Mar 27, 2008 10:14 am
- Forum: Volume 114 (11400-11499)
- Topic: 11431 - Partitioning a Number
- Replies: 7
- Views: 2133
- Wed Mar 26, 2008 9:11 pm
- Forum: Volume 114 (11400-11499)
- Topic: 11428 - Cubes
- Replies: 64
- Views: 17267
- Tue Mar 25, 2008 1:45 am
- Forum: Volume 114 (11400-11499)
- Topic: 11429 - Randomness
- Replies: 4
- Views: 1496
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: 1496
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 ...