Search found 30 matches

by marian
Sun Mar 06, 2005 3:09 pm
Forum: Volume 108 (10800-10899)
Topic: 10823 - Of Circles and Squares
Replies: 50
Views: 10631

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.
by marian
Sat Feb 12, 2005 11:48 pm
Forum: Other words
Topic: Programming Contest for Newbies 2005
Replies: 34
Views: 5762

little joey wrote:Did anyone solve A without a prefab bigint class?
Yeah, I did.
by marian
Tue Nov 16, 2004 12:21 am
Forum: Volume 106 (10600-10699)
Topic: 10607 - Siege
Replies: 21
Views: 6543

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?
by marian
Mon Nov 15, 2004 2:02 am
Forum: Volume 106 (10600-10699)
Topic: 10607 - Siege
Replies: 21
Views: 6543

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).
by marian
Sun Oct 24, 2004 11:59 pm
Forum: Algorithms
Topic: Does STL use Boyer-Moore?
Replies: 2
Views: 1400

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.
by marian
Sun Oct 24, 2004 11:28 pm
Forum: Algorithms
Topic: calculate n choose k
Replies: 5
Views: 1837

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)).
by marian
Sun Oct 17, 2004 9:42 pm
Forum: Volume 107 (10700-10799)
Topic: 10747 - Maximum Subsequence
Replies: 15
Views: 8901

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.
by marian
Sun Oct 17, 2004 8:22 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 16965

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...
by marian
Sun Oct 17, 2004 5:24 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 16965

..: 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...
by marian
Sun Oct 17, 2004 1:59 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 16965

Hint: There are fewer strings one given string can dominate than total number of strings.
by marian
Wed May 12, 2004 3:18 pm
Forum: Volume 2 (200-299)
Topic: 209 - Triangular Vertices
Replies: 51
Views: 6808

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...
by marian
Wed May 12, 2004 12:11 pm
Forum: Volume 102 (10200-10299)
Topic: 10207 - The Unreal Tournament
Replies: 23
Views: 6267

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.
by marian
Mon May 10, 2004 10:26 pm
Forum: Volume 106 (10600-10699)
Topic: 10613 - Mushroom Misery
Replies: 14
Views: 6185

OK, now I'm ashamed. It's sort of school algorithm :-? I got accepted. Thank you very much for your hint.
by marian
Mon May 10, 2004 7:14 pm
Forum: Volume 106 (10600-10699)
Topic: 10613 - Mushroom Misery
Replies: 14
Views: 6185

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...

Go to advanced search