11666 - Logarithms

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11666 - Logarithms

Post by dodouuu » Mon Sep 14, 2009 4:48 pm

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

Post by SRX » Mon Sep 14, 2009 5:08 pm

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

Post by dodouuu » Mon Sep 14, 2009 5:21 pm

You help me a lot ^^ thank you very much

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

Re: 11666 Logarithms WA again and agian

Post by fushar » Mon Sep 14, 2009 5:54 pm

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

Post by dodouuu » Mon Sep 14, 2009 6:08 pm

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

Post by lgarcia » Mon Sep 14, 2009 7:51 pm

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

Post by apurba » Mon Sep 14, 2009 9:36 pm

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

Post by lgarcia » Mon Sep 14, 2009 10:18 pm

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

Post by noor_aub » Wed Sep 16, 2009 10:33 am

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

Post by ymgve » Thu Sep 24, 2009 6:31 pm

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

Post by stubbscroll » Thu Sep 24, 2009 9:31 pm

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();
        // calculate answer
        bf.append(answer);
        // 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

Post by ymgve » Fri Sep 25, 2009 9:32 am

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

Post by arifcsecu » Fri Sep 25, 2009 11:38 am

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
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11666 Logarithms WA again and agian

Post by calicratis19 » Mon Oct 05, 2009 6:51 am

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

Post by arifcsecu » Fri Nov 13, 2009 3:30 pm

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.

Post Reply

Return to “Volume 116 (11600-11699)”