Unfortunately entirely deterministic version of this algorithm fails on Test #10. So I'm very curious about this Test #10. Because I've done a lot of testing in MATLAB of varoius modification of Floyd-Steinberg dithering algo, including zig-zag proseccing and edge attending. In all cases constraint in statement can be hardened from 20 to 10 and even less. On normal images error is about 6-8.

I guess Test #10 some kind of periodic image, that has bad compatibility with that unnatural restriction put in the problem. I mean it square form and discontinuous nature. I think dithering yield much more better image than that which can be produced by uniform minimization of constrain function.

I solve this issue whit Test #10 by adding a little bit of randomness in my dithering algo. I mean in place of this threashold function:

int quantize(int value) {
    if (127 < value) {
        return 255;
    }
    return 0;
}

I'm using this function:

int quantize(int value, int randomness) {
    if (127 - randomness + rng.nextInt(2 * randomness + 1) < value) {
        return 255;
    }
    return 0;
}

This provides me with magical parameter "randomness" varying which and playing tambourine I got my AC. 8-] I think I should add constraints checking and reprocessing in case the check was a fail, but I'm too lazy, I guess in case of possible future rejudging everything will be fine. :)

I express my sincerest thanks to authors of this beautiful problem. It has bugged me a lot in era of matrix printers how can they do this funny dotted images. Finally I have my answer and I can even do it myself!!!

Edited by author 17.01.2018 02:43

first using Heuristic search,  a[x][y]<255-a[x][y] first search 0, else first serach 255,

times>1e5  break;

if ok==false  using random search,  if(rand()%2==0) first search 0 else first search 1,

if you use rand()%2==1 first search 0 it will tle...

Edited by author 18.08.2012 20:30

The testcases, after rejudgement, are harder than before. So I really wonder if simply randomization could get AC.

I first wrote a program WHOLLY random, and got WA at 4.
Then I added the checking part of my program. When one-round randomization failed, I will start another, and so on. Then I got TLE at 14, 15 or 19 (I have tried about 10 times).
Finally, I realised that I must modify the random part. So I made a improvement: when I try to find the value of one pixel, I will take the PROCESSED pixel which could have the impression on that pixel into consideration. And I will adjust the random argument basing on these infos. This time I got AC.

Wish my method will be helpful.

Why this problem has no forum.
It is interesting question of image processing
but I could'n find in internet similar description.
After some thinking 20-string prog was created.

Problem validator was found to be incorrect. Now it is fixed.

while solving this problem I realized that changing the direction of moving led to the new answer.

for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{...some code...}
It is WA3

for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{...some code...}
It is WA25

for(int i = n; i >= 1; i--)
for(int j = m; j >= 1; j--)
{...some code...}
It is also WA25

for(int i = m; i >= 1; i--)
for(int j = n; j >= 1; j--)
{...some code...}
It is AC.

So, if you have wa25 or wa3 you may try to change indexe's direction )

Limitation N, M >= 100 was changed to N, M >= 75