OJ Board

Or don't use floating point numbers at all. When computing a/b (a,b positive integers), you can use:

a/b - if rounding down
(a+b-1)/b - if rounding up
(2*a+b)/(2*b) - if rounding to the nearest integer (with 0.5 up)

Where / is the integer division.

little joey wrote:Did anyone solve A without a prefab bigint class?

Yeah, I did.

Thanks Adrian, you're right. This is what happens, when I try to understand why my old code works without reading the statement properly.

Any ideas how hard would that problem be without that constraint?

Hello guys,

What is your output to this?
My AC program outputs 2, but the answer should be obviously 3 (B and C must be conquered, but they are not bordering, unless I misunderstood the statement).

AFAIK, STL implementation included in gcc, doesn't use any sophisticated search algorithm. You can still check it out yourself in /usr/include/c++/ if you have it installed.

Maniac wrote:but this could overflow because I multiply before I divide. Is there a way to avoid an overflow without factorizing n and m?

You can use GCD. When computing (A*B)/C, let G=GCD(A,C) then

(A*B)/C = (A/G) * (B/(C/G)).

Your method is good, but there are couple of special cases to consider:

for example, in the input:
4 2
7 -9 -10 100

you have to switch 7 for -10, and not -9 for 100.

Also, in the input
4 3
0 0 -1 -1

It is better to take 0 0 -1, as opposed to 0 -1 -1.

marian: Thanks for your explanation. As far as I understand, you look at the strings as multisets of characters. And in your trie you do not distinguish between strings that give rise to the same multiset. Is that correct?

Exactly.

For example you can sort the string lexicographically. And for ...

..: Aren't you checking O(n^2) pairs in the worst case (ie. no dominating strings)? Unless I didn't get your algorithm.

BiK: I was just saying that one string of length K can dominate at most 2^K-2 strings. Since K<=10, one string can dominate at most 1022 strings. So it's cheaper to generate all ...

Hint: There are fewer strings one given string can dominate than total number of strings.

This problem (or at least it's input) is crap. You are right, there are integers <=0, but you should not always return false. It's weird, but I think you should return
0 1 2 are the vertices of a triangle
0 1 2 3 are the vertices of a parallelogram
-1 1 4 6 are the vertices of a parallelogram
At ...

You do not need to use DP to compute Numberofcalls(i,j). There is explicit formula, which you are asked to find in this problem. Hint: Binomial coefficients.

OK, now I'm ashamed. It's sort of school algorithm I got accepted. Thank you very much for your hint.

Hello,

I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).

We can trivially cover one circle with 2*r rectangles (r is circle radius ...