OJ Board

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.

So what's the idea for the correct algorithm?

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

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

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

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

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

I'm starting to think that the judge input contains bugs.
I used and it gave run time error.

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

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?

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

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.

then probably your program is wrong, and the testcases for 11436 didn't catch it.

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

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