You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance:
1)
1 1 1 0 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 1
1 1 1 0 1 1 1
2)
1 1 1 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1
are desired matrices maximum width of which you must find

My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

What means if gear-wheel have only one cog?

Edited by author 26.09.2004 20:25

There is simple O(N+M) algo (core part is like 5 lines), and it's "online" (no preprocessing of queries required)

Edited by author 10.06.2026 04:20

Notice, that you can move duons alongside diagonal (A->F, A->H, G->E, ...)

Who know O(H*W) or, O(H*W*5) algo ???

It is much more interesting to look for good tests for this task than just to solve it.
Here is the AC program (with a small error in order not to publish solutions). I will look for where it will fail.
#include<iostream>
#include<cmath>//too lazy to write sqrt() yourself
int main() {
    unsigned l, h, o;
    std::cin>>l>>h>>o;
    unsigned phase = 0;
    if(l<h*2) phase = o*sqrt((2*h-l)/981)/15+1;
    char const*answer[]{"Butter","Bread\n"};
    std::cout<<answer[(phase>>1)&1]<<std::endl;
}

Tree for minimum is enough.

Input
0
50 10
0 0
100
200
-1
Output
-5.00

I thought at first, that an absolute value has to be printed, which gets WA 3.

Could anyone provide me with an O(n) solution? My works O(n log(n))

Just used STL contaners such as std::map<std::string,T>, std::vector<T>. :)
33 lines of code.

plz help me, i got WA on this test , if someone knows this one help me!.

Use heavy-light decomposition: after O(N) preprocessing, every tree path becomes O(log N) contiguous ranges in the HLD order. Because cave radiation only increases, maintain range maximums with a monotone Fenwick tree, giving O(log N) per update and O(log^2 N) per path query with O(N) memory.

Current #1 AC

Edited by author 06.06.2026 21:24

Edited by author 06.06.2026 21:24

50 38 17 9 9

Heavy-Light-Decomposition -> GOOD data structure! thank you all!

Please I got Crash(Stack Overflow), I implemented my first heavy-light descomposition and tried this problem, but I got this.

I got AC, I had to  convert the DFS to BFS, to evade the StackOverflow.

Edited by author 02.11.2011 04:45

Edited by author 02.11.2011 07:20

Edited by author 02.11.2011 08:20

Likely some rounding issue, e.g. in Python
int(x + 0.5) => WA #8
int(x + 0.5 + 1e-9) => AC

using u32=unsigned;
u32 constexpr M = 9;
u32 n = 0, g[1<<2*M];
template<u32>void solve(u32, u32=0);
template<>void solve<2>(u32 voidXY, u32 BaseXY){
    u32 e = n++, *p = g+BaseXY, q = g[voidXY];
    *p = e, p[1] = e, p += 1<<M, *p = e, p[1] = e, g[voidXY] = q;
}
template<u32 s> void solve(u32 V, u32 B){
    auto constexpr f = solve<s/2>;
    u32 constexpr m = (1<<M)-1;
    bool a = (V&~m)<(B&~m)+(s<<M)/2;
    bool b = (V&+m)<(B&+m)+s/2;
    f(V, B+(!a)*(s<<M)/2+(!b)*s/2);
    f(B-a*(1<<M)+b+((s<<M)+s)/2-1, B-a*(s<<(M-1))+b*s/2+(s<<M)/2);
    f(B+a*(1<<M)+((s<<M)+s)/2-(1<<M)-1, B+a*(s<<M)/2);
    f(B+a*(1<<M)+((s<<M)+s)/2-(1<<M), B+a*(s<<M)/2+s/2);
    u32*c = g+((s<<M)+s)/2-(1<<M)+B;
    c[m+(b&!a)] = c[(a&b)-1] = c[a<<M] = n++;
}
//this is a very funny, but working program code.

Edited by author 03.06.2026 19:49

Input:
3
-6 -9
9 -1
0 5
1.5 -5.0
2
-155
-292

Output:
11.571429
0.000000
0.000000

you can decompose path (i -> j) like (i -> x) + (x -> y) + (y -> j) or like  (i -> y) + (y -> j)