OJ Board

Well! Boring problems vary from person to person. For example two other problems in this contest were boring to me (I won't say which ones because I have learnt courtesy somehow). About the cow problem I have written it long ago and it was just there to be solved by everyone. Doesn't topcoder or ...

Manzoor's problems on today's contest were two of the most boring and unoriginal problems imaginable. It's certainly not worth waking up at 0500h to solve stuff like that, which is why I stopped doing UVA contests a year or two ago. I commend him on his dedication to the site and for organizing ...

Per, I had the same problem during the contest. I did binary search on the radius, which is not precise enough. I guess if you have a really small difference like 0.0000001, the radius can be huge, and with the formula I used, that meant taking the cos of something very close to 0. Searching on the ...

BTW, Adrian, 18 was also the largest set I found. I used an incomplete search (of course), but I suspect that is optimal or very close to it. It is definitely much lower than 30.

Wow... that sucks.

What a waste of time. I wasted more time accomplishing nothing on problems E and G than I did solving the other seven.

There are over 1200 problems now (>1250 solved already). How far is one gonna get if he use brute-force or pre-calc. And whats he gonna do in actual contest.

One mustn't forget the spirit in which most of us do Contests. We want
to improve ourselves. Here the actual limit is not the problemsetter ...

After wasting a fair bit of time trying to solve this using network flow, I discovered that a much simpler approach of repeatedly picking the shortest path, then deleting that path, gets AC. This is incorrect though, according to the problem description. Consider the following test case:

8 11
1 2 0 ...

The judge appears to be completely dead now.

This is pathetic. There have been problems with the judge in pretty much every single UVA contest I've participated in during the past two years. Why doesn't someone actually FIX the system BEFORE deciding to run these contests...

Maybe he means that the j = 0 (j > 0) condition in the problem statement should actually be j = 1 (j > 1). You'll never actually consider j = 0 because k always starts at 1. If you implement this in the obvious way, your loop condition will probably do this check implicitly though.

Anyway, this ...

ya, you can do Lucas number the same way, I believe, I don't know how other ppl do it though, because mine runs pretty fast and there are some really slow solution for some reason...

Those people used a different method, where you compute values in the sequence until the sequence begins to repeat ...

What is the O(n) algorithm for strongly connected components?

I just thought you can find the reverse dfs for a node, and the regular dfs for a node, and if they both reach everyone, then there's one component.. but I get WA..

Yes, that is enough to determine if a graph is strongly connected ...

How do you find the intervals, Lars? Ya, I notice that the abs of roots are within 25, but how do you choose the intervals so that you are certain there's not 2 or more values between that interval?

There can't be 2 or more roots in an interval, because the intervals are chosen so that the ...

I used the bisection method (binary search) to solve 10428. You just need an extra trick to ensure you only consider monotonic intervals: notice that every root of the polynomial f(x) must lie between some local minimum and local maximum. These local optima are precisely the points where the ...

pingus wrote:why wa ?
[c]
printf("Case %i: %i %i %i\n",cases,n,b,calls[n%(m-1)]);
[/c]

I think the second %i should be %lli.

You can't just go through linearly and keep track of the 2 smallest because that can use 2n - 3 comparisons in the worst case.

The tournament method works like this. First, assume n is a power of 2. Split all the elements up into arbitrary pairs. Do a comparison on each of the n/2 pairs, and then ...