11666 - Logarithms

Moderator: Board moderators

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

11666 - Logarithms

I got wrong answer again and again during the contest yesterday. And today, I got wrong answers all day.... Please tell me how to solve this problem. I will appreciate you very much.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: 11666 Logarithms WA again and agian

input:

Code: Select all

``````9
8
7
0

``````
9

output

Code: Select all

``````2 -0.21801755
2 -0.08268227
2 0.05265302
``````
notice that -1<x<1
studying @ ntu csie

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

Re: 11666 Logarithms WA again and agian

You help me a lot ^^ thank you very much

fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

Re: 11666 Logarithms WA again and agian

Rearranging terms gives us
ln(n)-L = ln(1-x) ; -1 < x < 1

So this problem asks for smallest L such that 0 < e^(ln(n)-L) < 2.
That can be accomplished using binary search on L.
I haven't got AC, though.

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

Re: 11666 Logarithms WA again and agian

I think this problem asks for this:

for(l=floor(logn); ; l++){
x = 1-exp(logn-l);
if( fabs(x)<1+eps )return;
}

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

Re: 11666 Logarithms WA again and agian

I solved the problem with this:

Code: Select all

``````L = ceil(log(n) - log(2.));
x = 1 - exp(log(n) - L);``````

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

Re: 11666 Logarithms WA again and agian

lgarcia wrote:I solved the problem with this:

Code: Select all

``````L = ceil(log(n) - log(2.));
x = 1 - exp(log(n) - L);``````
hi, lgarcia
can you please make it clear to me, why you use

Code: Select all

``L=ceil(lon(n) - log(2.0));``
log(2.0) here????

Code: Select all

``keep dreaming...``

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

Re: 11666 Logarithms WA again and agian

I'm sorry, I should be more clear.

We get this from the problem,
ln(n) = L + ln(1 - x) => n = e^L * (1 - x)

Also we have this,
|x| < 1 => -1 < x < 1 => 0 < 1 - x < 2

Then,
e^L * (1 - x) < 2 * e^L => n < 2 * e^L => ln(n) < ln(2) + L => ln(n) - ln(2) < L

Since we don't get (or I didn't see) any other constraint, L is just the lowest integer greater than ln(n) - ln(2).

Actually my solution is wrong if ln(n) - ln(2) is an integer, however my solution was accepted.
The right one (also accepted) should be

Code: Select all

``L = floor(log(n) - log(2.) + 1.);``

noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

Re: 11666 Logarithms WA again and agian

Any body help me to solve the problem. I am getting wrong answer.

Code: Select all

``````l=floor(log(n)/log(2));
x = 1 - exp(log(n) - l);

[\Code]``````

ymgve
New poster
Posts: 7
Joined: Mon Oct 15, 2007 1:17 am

Re: 11666 Logarithms WA again and agian

Is this even possible to do in Java? I just get TLE:

Code: Select all

``accepted``
Last edited by ymgve on Fri Sep 25, 2009 9:25 am, edited 1 time in total.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Re: 11666 Logarithms WA again and agian

ymgve wrote:Is this even possible to do in Java? I just get TLE:
You probably get TLE because there are a lof of test cases, and hence a lot of output. Try buffering the output, for instance:

Code: Select all

``````        StringBuffer bf=new StringBuffer();
// print all output
System.out.print(bf);``````

ymgve
New poster
Posts: 7
Joined: Mon Oct 15, 2007 1:17 am

Re: 11666 Logarithms WA again and agian

Yeah, StringBuffer did the trick. But I feel the time limit is still too close. The largest problem seems to be that formatting strings in Java is quite slow, and there is no easy way of achieving the same combination of rounding and number of decimals as String.format(). It would be more ideal if the task just said "correct to 8 decimal places", but I don't know if the judge is capable of checking that. I assume it basically diffs the answer output with the correct one.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11666 Logarithms WA again and agian

Accepted

Thanks
Last edited by arifcsecu on Mon Oct 05, 2009 7:53 am, edited 1 time in total.
Try to catch fish rather than asking for some fishes.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Contact:

Re: 11666 Logarithms WA again and agian

my ac code gives,

Code: Select all

``````0 0.00000000
1 0.26424112
1 -0.10363832
1 -0.47151776
1 -0.83939721
2 0.18798830
2 0.05265302
2 -0.08268227
2 -0.21801755
2 -0.35335283
2 -0.48868812
2 -0.62402340
4 -0.83156389
5 -0.34758940
6 0.25637435
9 -0.23409804
12 0.26269452
16 -0.12535175
21 0.24174396``````
you can visit here http://www.uvatoolkit.com/problemssolve.php to generate test case.
hope it helps.
Heal The World

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: Replica Mulberry Handbags

abcd264 wrote:Mulberry was founded in 1971 by Roger Saul through a gift of 50-pounds sterling from his mother Joan. Roger began by selling his own designs for leather chokers and belts to such high fashion shops as Biba in London. His first collection of belts in suede and leather demonstrated the influence of saddlery techniques and traditional English crafts, and were worked to Saul's designs by local craftsmen housed in what was once an old forge in his parent's garden in Chilcompton, near Bath. The following year Saul made Mulberry's first significant export an order of a thousand belts from the Paris department store Au Printemps, while Saul created a subsequent belt collection for Jean Muir. By 1975 Mulberry had expanded into Europe, with handbag designs for Kenzo in Paris and a special range for Bloomingdale's in New York. Replica Mulberry Handbags

WHAT IS THIS ?
Try to catch fish rather than asking for some fishes.