Search found 44 matches

by arnsfelt
Wed Jun 11, 2003 9:09 pm
Forum: Algorithms
Topic: Find second min number .
Replies: 10
Views: 4292

Re: Find second min number .

The tournament method.

Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?
by arnsfelt
Tue Jan 07, 2003 10:59 am
Forum: Volume 100 (10000-10099)
Topic: 10020 - Minimal coverage
Replies: 57
Views: 20556

Re: Mmm

Miguel Angel:
It's not very clear how your algorithm works.
But, yes - the line segments (of course?) can overlap.
And, yes - the greedy approch can be applied - if done in the right way.
by arnsfelt
Sat Jan 04, 2003 9:57 pm
Forum: Volume 100 (10000-10099)
Topic: 10020 - Minimal coverage
Replies: 57
Views: 20556

Use the Gready approch.
by arnsfelt
Fri Jan 03, 2003 4:17 pm
Forum: Algorithms
Topic: Minimal Perfect Matching in Full Graphs...
Replies: 3
Views: 2626

The Kuhn-Munkres algorithm is for bipartite graphs only.
For general graphs try Edmonds primal-dual algorithm.
by arnsfelt
Wed Nov 27, 2002 10:32 pm
Forum: Volume 100 (10000-10099)
Topic: 10043 - Chainsaw Massacre
Replies: 18
Views: 7054

No, DP doesn't lead to a good solution. Instead, a sweep-style algorithm is needed. Aim at an O(n^2) time algorithm. WARNING : Spoiler follows: Consider the largest empty rectangle. There are two cases: 1) Left edge is the left border of the forest. 2) There is a tree on the left edge. Case 1 is a s...
by arnsfelt
Wed Nov 20, 2002 10:06 am
Forum: C++
Topic: Grow Array Size
Replies: 13
Views: 4539

try realloc()
by arnsfelt
Wed Nov 13, 2002 8:42 pm
Forum: Algorithms
Topic: Finding the heavier rectangle
Replies: 10
Views: 3860

Yarin: What do you mean by "complexity doesn't matter on input size" ? Anyway, the reference: Hisao Tamaki and Takeshi Tokuyama. Algorithms for the maxium subarray problem based on matrix multiplication. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 446-452, San...
by arnsfelt
Wed Nov 13, 2002 12:41 am
Forum: Algorithms
Topic: Finding the heavier rectangle
Replies: 10
Views: 3860

Actually there is a faster algorithm than O(n^3).
There was one in a siam journal some years ago.
It will probably not be faster on input sizes considered here, though.
by arnsfelt
Mon Oct 14, 2002 5:29 pm
Forum: Volume 1 (100-199)
Topic: 109 - SCUD Busters
Replies: 96
Views: 24397

Ok, I asked because you said you added up for each missile. When I did this problem I succeeded first time with just this standard piece of code for detecting hits. [c] int lefton(point *a, point *b, point *c) { return (b->x - a->x)*(c->y - a->y) - (c->x - a->x)*(b->y - a->y) >= 0; } int pointinpoly...
by arnsfelt
Mon Oct 14, 2002 3:10 pm
Forum: Volume 1 (100-199)
Topic: 109 - SCUD Busters
Replies: 96
Views: 24397

What if a kingdom is struck more than once ?
by arnsfelt
Sat Sep 28, 2002 5:10 pm
Forum: Volume 100 (10000-10099)
Topic: 10055 - Hashmat the Brave Warrior
Replies: 166
Views: 46049

you get integer overflow
by arnsfelt
Fri Sep 27, 2002 5:10 pm
Forum: Volume 100 (10000-10099)
Topic: 10078 - The Art Gallery
Replies: 20
Views: 6237

You miss the last turn,

try:

Code: Select all

5
1 1
0 0
2 1
2 2
0 2
0
Kristoffer Hansen
by arnsfelt
Tue Sep 24, 2002 11:35 am
Forum: Volume 1 (100-199)
Topic: 108 - Maximum Sum
Replies: 233
Views: 22513

Change these line
[cpp]
while (cin)
{
cin >> N;
[/cpp]

to

[cpp]
while (cin >> N)
[/cpp]
by arnsfelt
Fri Sep 20, 2002 10:19 pm
Forum: Volume 100 (10000-10099)
Topic: 10004 - Bicoloring
Replies: 93
Views: 29328

oops, should have read the description again. Just relied on my vague memory ...
by arnsfelt
Fri Sep 20, 2002 8:32 pm
Forum: Volume 100 (10000-10099)
Topic: 10004 - Bicoloring
Replies: 93
Views: 29328

Also, the graph need not to be connected. So one may need to start the recursion several times.

Go to advanced search