## 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: 2962

### 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: 2962

### 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: 8569

### 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: 834

### 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: 2962

### 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: 5463

### 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: 2962

### 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: 1100

### Re: 11434 - Careless Postman Problem

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

Code: Select all

``````assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
``````
and it gave run time error.
Mon Mar 31, 2008 9:30 am
Forum: Volume 114 (11400-11499)
Topic: 11434 - Careless Postman Problem
Replies: 4
Views: 1100
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: 1100

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

Code: Select all

``````2 2
1 2 1 1 0
2 1 1 1 0
``````
Why is the result 2?
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: 16080
mukeshtiwari wrote:Could someone please tell me why this code is giving WA for problem cubes.
try the testcase n=1
the output should be No solution
Thu Mar 27, 2008 10:14 am
Forum: Volume 114 (11400-11499)
Topic: 11431 - Partitioning a Number
Replies: 7
Views: 1947
I don't want to give the testcase since it will give away the solutions.
There is a good chance that you're not generating the correct numbers n that gives f(n)>f(m) for all m<n.

Just write a bruteforce program that generates all n<=10^6 and compute f(n) to check.
Wed Mar 26, 2008 9:11 pm
Forum: Volume 114 (11400-11499)
Topic: 11428 - Cubes
Replies: 64
Views: 16080
then probably your program is wrong, and the testcases for 11436 didn't catch it.
Tue Mar 25, 2008 1:45 am
Forum: Volume 114 (11400-11499)
Topic: 11429 - Randomness
Replies: 4
Views: 1378

### 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: 1378

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