OJ Board

Anyone has any idea on how to do this?
I tried some finite cases, but don't see any patterns.
It seems to converge to some constant around 0.6

sclo wrote:Anyone has any idea on how to do this?
I tried some finite cases, but don't see any patterns.
It seems to converge to some constant around 0.6

Maybe I should try to use more symmetry argument to find an recursion.

I am solving for it numerically, and it seems to be
0.6589186226... and accurate to about 12 digits.

From the finite cases, I see that it is of the form 1/2 + a*sqrt(2), where a is a rational number.

I have tried to find soln of this and the other problem on resistance but personally I have no idea how to find resistance of infinite resistor nework.

Will you please ecplain how resistance is computed in some base cases.
( I don't even understand the sample inputs)

study Kirchoff's Law and Ohm's Law

For finite cases, we can view the problem as some kind of network flow from A to B of current = 1:

Ohm: resistance between a,b on a wire = (voltage (potential) drop between a,b) divided by current on the wire.

Kirchoff: Sum of current flowing out of any intersection is equal to 0.

we denote A as source, and B as the sink.
The idea is that we assign each vertex a variable that denotes the potential at that vertex, and apply the 2 laws to each edge incident to a vertex.

Example:
Suppose all the edges in the network are:
A V1
A V2
V1 B
V2 B

And assume d(a,b) is the length of wire between a,b. (we assume uniform resistance on a wire, so resistance of the wire is simply d(a,b))

(This base case is so simple that there is a reduction to a single resistance, but we need to use general case for more complicated ones)

set up equations as follows:
(V1-A)/d(V1,A) + (V1-B)/d(V1,B) = 0
(V2-A)/d(V2,A) + (V2-B)/d(V2,B) = 0
(A-V1)/d(A,V1) + (A-V2)/d(A,V2) - 1 = 0
B = 0

We need to compute A, and that will represent the resistance between A,B since potential = current * resistance.

The solution of above is V1 = V2 = 1/2, A = 1, B = 0 (assuming all edges are length 1)
Closest look at it will tell you that V1=V2 because they top down symmetric, and
V1=V2=(A-B)/2, since left and right is also symmetric.

The observation is always true:
All node in the general case that is eqidistance from A,B has potential A/2,
And all nodes in the upper half has same potential to a corresponding node in the lower half.
Thus, we can just look at say the left half, and we can just set the potential of any vertex equidistance from A,B to 0, and the final solution should be 2*A
Back to our example:
we set V1=0, and V1=V2
so there is only 1 equation left:
(A-V1)/d(A,V1) + (A-V2)/d(A,V2) - 1 = 0
the equation becomes:
A/d(A,V1) + A/d(A,V1) - 1 =0

so the solution is A = 1/2, so the potential between A,B is 2*(1/2) = 1 which is expected.

If I use the computer to recursively construct more and more cases, I found that the potential between A,B to approach 0.6589186226

Through some more work, I've managed to reduce the system into a 1dimensional recurrence, and computed the solution.

So basically, we need to compute 10 million digits of irrationals, which is crazy.

sclo wrote:So basically, we need to compute 10 million digits of sqrt(3) and sqrt(2), which is crazy.
Coincidently, the solution is also sin(pi/3)+sin(pi/6)-sin(pi/4)

My first guess was to use FFT to compute square roots, this is a well known technique, but hard to implement. But what is very annoying:
on contest the time limit was 1 sec. for this problem and pifast can compute sqrt(2) in about 20 sec. on my pc. So it would take about 40 sec. to compute our number, but pifast using a very well optimized FFT and my pc is 1.7 GHz Celeron, it is obviously TLE on judge.

My second guess is to use a BBP formula to compute directly only the required digits of sqrt(2) and sqrt(3). But it is not known if it is exist for sqrt(2). OK, it can be still exist for our number but I don't think that. I've checked some sites but haven't found.

One person already solved, the problemsetter ( and also the input setter?! ), I hope this isn't cheat:

The input specification is incorrect due to a mixup.
I have already sent in a correction, but it may be
awhile before the html is updated since people are busy
updating the new server software.

It should say the following:

k < 10000000 and 0 < min(k,990*10^4-k) < 10^4.

Sorry about the mistake. I will be much more careful the next time.
What happened is my problem tester increased the dataset,
but I didn't submit the correctly updated html file. Even
my solution got TLE, until I submitted his code.
Unfortunately, no one asked for clarification on this problem
during the contest. Hey, on the bright side, maybe someone
come up with a BPP formula for sqrt(2) and win the Fields medal.

baodog wrote:The input specification is incorrect due to a mixup.
I have already sent in a correction, but it may be
awhile before the html is updated since people are busy
updating the new server software.

It should say the following:

k < 10000000 and 0 < min(k,990*10^4-k) < 10^4.

Sorry about the mistake. I will be much more careful the next time.

OK, now solved only in 0.01 sec.
Are you also a member of Elite Problemsetters? Try to avoid Shahriar Manzoor, because he is the top of the leader of posting wrong problems.

It actually takes my program 80 secs to compute the solution.

Is there other way to compute the kth digit instead of storing the first and last 10^4 digits?

goodwill wrote:Is there other way to compute the kth digit instead of storing the first and last 10^4 digits?

You'll get the fields medal if you can figure that out.

Robert Gerbicz wrote: OK, now solved only in 0.01 sec.
Are you also a member of Elite Problemsetters? Try to avoid Shahriar Manzoor, because he is the top of the leader of posting wrong problems.

Hehe! I should not be replying this.

When you post most number of problems, statistically you will make most mistakes.

Most wrong problems posted by me were before the formation of Elite Panel. So there is nothing to relate the Elite Panel with making mistakes.