Search found 584 matches

by Krzysztof Duleba
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.
by Krzysztof Duleba
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.
by Krzysztof Duleba
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).
by Krzysztof Duleba
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.
by Krzysztof Duleba
Sat Jul 08, 2006 9:59 pm
Forum: C++
Topic: Compiling
Replies: 6
Views: 2344

google for it.
by Krzysztof Duleba
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.
by Krzysztof Duleba
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...
by Krzysztof Duleba
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 ){...
by Krzysztof Duleba
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';
instead of

Code: Select all

if(isupper(me))me -= 'A';
else me = (me - 'a') + 26;
by Krzysztof Duleba
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).
by Krzysztof Duleba
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.
by Krzysztof Duleba
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.
by Krzysztof Duleba
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.
by Krzysztof Duleba
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.
by Krzysztof Duleba
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...

Go to advanced search