Search found 584 matches

Mon Jul 24, 2006 11:45 am
Forum: Volume 110 (11000-11099)
Topic: 11055 - Homogeneous squares
Replies: 16
Views: 7839
My solution is even simpler than the one mentioned in the editorial: a square is homogeneous if cell[j] + cell[i-1][j-1] == cell[i-1][j] + cell[j-1] for each 0<i<n, 0<j<n.
Tue Jul 18, 2006 6:35 am
Forum: Algorithms
Topic: Answering ancestor queries in O(1): O(n) preprocessing
Replies: 2
Views: 1591
Yes, it's possible and in fact easy. Hint: preorder and postorder numbers.
Tue Jul 18, 2006 5:30 am
Forum: C++
Topic: flush
Replies: 8
Views: 3338

Code: Select all

``````#include <iostream>

using namespace std;

int main(){
cout << "a" << flush;
while(1){}
}``````
But now it does make a difference, doesn't it?

You should use flush only when you know what you're doing, in very few and specific situations (for instance when you're dealing with pipes).
Tue Jul 18, 2006 3:39 am
Forum: C++
Topic: flush
Replies: 8
Views: 3338
Google for it. It takes less than writing a post.
Sat Jul 08, 2006 9:59 pm
Forum: C++
Topic: Compiling
Replies: 6
Views: 2344
Thu Jun 29, 2006 7:42 pm
Forum: Algorithms
Topic: Euler Cycle on a directed Graph..
Replies: 5
Views: 1601
It has been discussed in the past here and it's not difficult to figure it out on your own. Just think about bipartite matching or search the board if you really have to.
Thu Jun 22, 2006 7:14 pm
Forum: C++
Topic: iterator for a container<Generic> is deprecated...
Replies: 4
Views: 2454
Actually, vectors can have a const_interator non-typedef member: #include <iostream> #include <vector> using namespace std; template<class T> void printv(const vector<T> &somev ){ for(/*typename*/vector<T>::const_iterator e = somev.begin(); e != somev.end(); ++e) cout << *e << ", "; } template<typen...
Thu Jun 22, 2006 7:05 pm
Forum: C++
Topic: iterator for a container<Generic> is deprecated...
Replies: 4
Views: 2454
When vector is std::vector - never. But the compiler is processing the template first, before any instance is actually created and it's that moment when it doesn't know what to do. #include <iostream> #include <vector> using namespace std; template<class Gen> void printv( const vector<Gen> &somev ){...
Wed Jun 14, 2006 5:11 pm
Forum: Volume 110 (11000-11099)
Topic: 11041 - Quarter-Finals with Brazil!? No!!!
Replies: 10
Views: 6965
Nice problem!

My code seemed to be ok right away - it passed a set of 10^7 test cases, but still was getting WA. It took me 10 hours to find the error: using

Code: Select all

``````me -= 'A';
``````

Code: Select all

``````if(isupper(me))me -= 'A';
else me = (me - 'a') + 26;
``````
Tue Jun 13, 2006 5:04 pm
Forum: Volume 110 (11000-11099)
Topic: 11044 - Searching for Nessy
Replies: 11
Views: 7111
I disagree - 1 is the right answer (one sonar in the middle is enough).
Mon Jun 05, 2006 8:05 am
Forum: Volume 109 (10900-10999)
Topic: 10904 - Structural Equivalence
Replies: 13
Views: 5061
They are not equivalent - just draw them and take a look.
Thu Jun 01, 2006 10:14 pm
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3725
After a few adjustments and paying a price of O(n) time factor (now it's O(kmn)) I got MLE on test 6. I'm not sure if this approach can be improved any further in case of simple paths.

Edit: It can be improved, but only to MLE on test 12 so far.
Thu Jun 01, 2006 9:20 pm
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3725
But this is a completely different problem. UVA's 10740 is about any k-th path, SGU's 145 is about k-th *simple* path. I was able to optimize my algorithm to use only O(k * n + m) memory replacing std::priority_queue by std::set, but now I can't see how it can be applied.
Thu Jun 01, 2006 2:17 am
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3725
No, it's very memory consuming, no way to fit into 1 MB. I'll try to solve this problem tomorrow.
Thu Jun 01, 2006 12:51 am
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3725
In SSSP you extract each node from a queue exactly once. Instead extract it exactly k times. Keep inserting it until then. I solved problem 10740 this way. Can you explain the idea of DP solution in a few words? Edit: never mind, I read some papers on that. I admit that I seriously underestimeted th...