## Search found 30 matches

Sun Mar 06, 2005 3:09 pm
Forum: Volume 108 (10800-10899)
Topic: 10823 - Of Circles and Squares
Replies: 50
Views: 11289
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.
Sat Mar 05, 2005 11:53 pm
Forum: Volume 108 (10800-10899)
Topic: 10820 - Send a Table
Replies: 34
Views: 14624
Sat Feb 12, 2005 11:48 pm
Forum: Other words
Topic: Programming Contest for Newbies 2005
Replies: 34
Views: 6042
little joey wrote:Did anyone solve A without a prefab bigint class?
Yeah, I did.
Tue Nov 16, 2004 12:21 am
Forum: Volume 106 (10600-10699)
Topic: 10607 - Siege
Replies: 21
Views: 6766
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?
Mon Nov 15, 2004 2:02 am
Forum: Volume 106 (10600-10699)
Topic: 10607 - Siege
Replies: 21
Views: 6766
Hello guys,

What is your output to this?

Code: Select all

``````5 4
DDDD
DBBD
DBAC
DBBD
DDDD
0 0
``````
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).
Sun Oct 24, 2004 11:59 pm
Forum: Algorithms
Topic: Does STL use Boyer-Moore?
Replies: 2
Views: 1431
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.
Sun Oct 24, 2004 11:28 pm
Forum: Algorithms
Topic: calculate n choose k
Replies: 5
Views: 1979

### Re: calculate n choose k

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)).
Sun Oct 17, 2004 9:42 pm
Forum: Volume 107 (10700-10799)
Topic: 10747 - Maximum Subsequence
Replies: 15
Views: 9181
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.
Sun Oct 17, 2004 8:22 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17570
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 a gi...
Sun Oct 17, 2004 5:24 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17570
..: 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 po...
Sun Oct 17, 2004 1:59 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17570
Hint: There are fewer strings one given string can dominate than total number of strings.
Wed May 12, 2004 3:18 pm
Forum: Volume 2 (200-299)
Topic: 209 - Triangular Vertices
Replies: 51
Views: 7341
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 lea...
Wed May 12, 2004 12:11 pm
Forum: Volume 102 (10200-10299)
Topic: 10207 - The Unreal Tournament
Replies: 23
Views: 6618
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.
Mon May 10, 2004 10:26 pm
Forum: Volume 106 (10600-10699)
Topic: 10613 - Mushroom Misery
Replies: 14
Views: 6431
OK, now I'm ashamed. It's sort of school algorithm I got accepted. Thank you very much for your hint.
Mon May 10, 2004 7:14 pm
Forum: Volume 106 (10600-10699)
Topic: 10613 - Mushroom Misery
Replies: 14
Views: 6431
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) , horizon...