Yes, actually my first solution was O(N^4) with small constant.
Thanks, krijger, I've understood your algorithm.
Search found 10 matches
- Thu Jan 26, 2006 8:08 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10985 - Rings'n'Ropes
- Replies: 11
- Views: 5281
- Thu Jan 26, 2006 3:16 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10985 - Rings'n'Ropes
- Replies: 11
- Views: 5281
- Mon Jan 23, 2006 8:26 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10982 - Troublemakers
- Replies: 17
- Views: 7925
- Mon Jan 23, 2006 7:05 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10986 - Sending email
- Replies: 65
- Views: 36721
- Mon Jan 23, 2006 5:17 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10986 - Sending email
- Replies: 65
- Views: 36721
- Mon Oct 31, 2005 9:37 am
- Forum: Volume 109 (10900-10999)
- Topic: 10956 - Prime Suspect
- Replies: 24
- Views: 14395
- Sun Oct 30, 2005 8:27 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10952 - Pattern Transformations
- Replies: 22
- Views: 6094
- Fri Aug 26, 2005 5:11 am
- Forum: Algorithms
- Topic: Seemingly easy DP problem
- Replies: 4
- Views: 2308
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: 4204
- Wed Jun 08, 2005 7:28 pm
- Forum: Volume 108 (10800-10899)
- Topic: 10864 - The Predator
- Replies: 5
- Views: 4204
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...