OJ Board

The basic idea is correct. Attention to colinear points especially when you're calculating convex hull by granham's original algorithm, not andrew's variation (this one is preferred). You can send me an email with your code and I'll test it with judge data.

@MRH

if i understand your algorithm correctly, if all the numbers are equal, each query would be linear on average, so TLE

Does the following code make sense to you?


inline int readint() {
char c = getchar();
while(!isdigit(c)) c = getchar();

int x = 0;
while(isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}


BTW: You don't need this kind of tricks to get AC for any problem in this ...

I'm making this problem for educational purpose. So here are the 2 methods used by me (method 1) and Derek Kisman (method2). Method 1 is theoretically faster, but given the limitations of the problem, both programs run very fast. He hints are encoded by rot13, so you won't be able to see them ...

I think for every problems in UVA need hints to learn problem solving.
So request to everyone, give hints to learn new technique .

Uva problem setter always try to adapt new problem with new idea.
But how can we learn new Idea?

Thanks all problem setter.

Right, you need to keep learning :) If ...

try this: printf("%d",count); ==> printf("%d\n",count);

asif_iut wrote:what should have been the idea for solving this problem??

you may take a look at this: http://en.wikipedia.org/wiki/Ternary_search

asif_iut wrote:thanks a lot bm_anas...i made a stupid error as well as reduced the eps to 1e-2 and AC!!!! thanks once again...

oops, this is not the intended way to solve this problem. The test cases are not strong enough but I admit that I have no idea how to generate good ones. Any one has some ideas?

Sorry, I was not aware of this error during the contest. The wrong formula is resulted from to the quick generation of HTML from DOC.
Now the figure is corrected. Thanks for pointing it out!

I been thinking about this problem and the algorithm I thinking is straightforward but it seems too slow:

Create an array "ops" with the four operations: +, -. *, /
Read an array "numbers" and store the n numbers of input
Create a function to create all possible sets of size n-1 where each element ...

Hello rio,

Thanks very much!
I tried something similar to the second idea you proposed and some prune.
My program took about 30 seconds for the testdata you provide above.
It is faster than before, but still slow, and it still got TLE in the onlinejudge.
Can we check whether the expression has ...

Akter_Sust wrote:For all this test case output is 2.
But type of the 2 and 3 no of test case is not in the judge test case
because one of my accepted code is fail generate this output.

Thanks I guess I'll improve the data someday later

yiuyuho wrote:736 yiuyuho Be Together Again and Forever Solved C++ 0.850 2007-06-03 08:28:28

The time during contest was < 1sec...there must have been an error...lol!

maybe that's because the old server (on which you got TLE) uses a older version of g++?
I'm not sure.

yiuyuho wrote:I think I get this problem during contest and I submitted the same algorithm to the OJ and get TLE....did the data got enhanced?

What's happening?

I wanted to enhance the data but finally i did not What is the runtime during the contest?

I have the running theory.. that in the rare(?) case that the greedy algorithm fails, it will only be off by one -- I wonder if there's some way to detect this case quickly and subtract one? hmm...
Yep, that is exactly how I worried when designing test cases. So I used a few pairs of test cases ...