## Search found 10 matches

Thu Jan 26, 2006 8:08 pm
Forum: Volume 109 (10900-10999)
Topic: 10985 - Rings'n'Ropes
Replies: 11
Views: 4386
Yes, actually my first solution was O(N^4) with small constant.
Thanks, krijger, I've understood your algorithm.
Thu Jan 26, 2006 3:16 pm
Forum: Volume 109 (10900-10999)
Topic: 10985 - Rings'n'Ropes
Replies: 11
Views: 4386
I had to use bit masks to get the O(N^3) complexity. I won't call my algorithm as Floyd's modification, although I used Floyd to find shortest distances between every pair of vertices. Is there any O(N^3) algorithm without bit masks?
Mon Jan 23, 2006 8:26 pm
Forum: Volume 109 (10900-10999)
Topic: 10982 - Troublemakers
Replies: 17
Views: 6391
Maybe the greedy solution is the following: take vertices one by one, and put each of them in the class where it creates less number of pairs with already added vertices.
Mon Jan 23, 2006 7:05 pm
Forum: Volume 109 (10900-10999)
Topic: 10986 - Sending email
Replies: 65
Views: 27755
Then it's probably some error in your code. I've accepted this task with both STL and mine priority queues.
Mon Jan 23, 2006 5:17 pm
Forum: Volume 109 (10900-10999)
Topic: 10986 - Sending email
Replies: 65
Views: 27755
Do you use heap?
Mon Oct 31, 2005 9:37 am
Forum: Volume 109 (10900-10999)
Topic: 10956 - Prime Suspect
Replies: 24
Views: 12122
I used prime sieve and implemented Suspect function as it is described in problem statement. All values are stored as unsigned int (not int64). No special optimization. Time: 0:02.682.
Sun Oct 30, 2005 8:27 pm
Forum: Volume 109 (10900-10999)
Topic: 10952 - Pattern Transformations
Replies: 22
Views: 4428
Are the tests for this problem correct?
Fri Aug 26, 2005 5:11 am
Forum: Algorithms
Topic: Seemingly easy DP problem
Replies: 4
Views: 1790

### O(n*log(n)) algorithm

If all number in the sequence are nonegative, then task can be easily solved with linear algorithm like ilovenwd's one. In case of negative values there's following O(n*log(n)) algorithm: #include <vector> #include <algorithm> #include <cassert> using namespace std; struct prefix { int sum,pos; pref...
Fri Jun 10, 2005 11:34 am
Forum: Volume 108 (10800-10899)
Topic: 10864 - The Predator
Replies: 5
Views: 3443
Thank you for test cases. They helped me to understand that my algorithm is wrong.
Wed Jun 08, 2005 7:28 pm
Forum: Volume 108 (10800-10899)
Topic: 10864 - The Predator
Replies: 5
Views: 3443

### 10864 - The Predator

Could anybody tell me what's wrong in my solution? #include <cstdio> #include <cstdlib> #include <cstring> #include <cassert> #include <cmath> #include <vector> #include <string> using namespace std; #define For(i,a,b) for(int i=(a); i<=(b); i++) #define Rep(i,n) for(int i=0; i<(n); i++) #define Rep...