10727 - Practice

[backslash null]

Hi every body any idea about problem 10727,
I don't understand the problem ....

thank you.

[gvcormac]

Which problem? Your title says 10727 while your message says 10728.

I'll use your problem to entreat everybody to PUT THE PROBLEM NAME IN THE TITLE of your message. Perhaps everybody but me has 1GHz ethernet, a 100GHz processor, and access to a mirror of this site that is 100 times faster than the one I have.

It takes me a good fraction of a minute to look up the problem corresponding to a particular problem number. So if all you post is the problem number, I'm not likely to take the effort to figure out what you're talking about.

[gvcormac]

The problem is asking you to do Logistic Regression. You can search the web or consult a statistics textbook to find more explanation.

[Quantris]

What's the output for the case:
2
1 0
2 1

..my program runs off to -infinity for a, and i'm not sure where to stop it.

[gvcormac]

What's the output for the case:
2
1 0
2 1

..my program runs off to -infinity for a, and i'm not sure where to stop it.

The result is undefined for the example you give. You need to have at least one inversion in the input for the result to be well-defined. The judge data has this property, but it was a little awkward to state the conditions in the problem statement. By an inversion, I mean that
if you sort by one value (n) the other value (w) must not be totally in order.

[Quantris]

ok, thanks. I think I figured out what else was wrong with my program, so hopefully I can fix it.

[backslash null]

isn't it more accurate if u select a=0 and b=0.25 ?

[gvcormac]

isn't it more accurate if u select a=0 and b=0.25 ?

I assume you are referring to the previous example [(1,0), (2,1)]. When you apply the logistic transformation you're trying to fit [(1,log(0/1-0)), (2,log(1/(1-1))] = [(1,-inf),(2,+inf)]. The "solution" to this is a=-inf, b=+inf.

[..]

Just a short note after I get this AC. Hope this can help any people to solve this problem in future.

It was a really really painful journey to find the right reference to help me kill this problem. At first I use Logistic Regression to google, but most of the web pages I get are telling people to use SAS or S PLUS to do the estimation(instead of talking about the algorithm).....

After a few days of research, I finally know that, what you need to know, is Newton Raphson's method only. Just do a small transformation, you can get this problem AC by Newton Raphson's method without knowing any thing in Logistic Regression.......

I write this because I feel little bit disappointed that my few-days-long research makes no contribution to solving this problem..... But I still need to say thanks to Prof. Gordon V. Cormack, through the research on this problem I have learnt knowledge on regression(not only logistic, also linear and non-linear).

[Krzysztof Duleba]

In fact, no fancy algorithms are necessary. Simple nested binary search was enough to give me AC.

[Destination Goa]

I used 2D ternary search (nestes 1D's).