Coder-Strike 2014 — Round 1 (Problem D)

Блог пользователя Mukit09

Автор Mukit09, 10 лет назад, По-английски

I've faced a strange thing when solving this 412D - Выдача премий. My this submission 6417021 has given me "wrong answer" in case 5, while this submission 6417013 is "Accepted". The only difference between these two code is "a variable 'j'".I declared "j" only globally, in the code, which has given me "wrong answer". But in the code , which has given me "Accepted" verdict, I declared "j" both in the dfs() function and globally.

Would anyone please make me known the exact reason behind this ??? As I've faced it for the first time, it seems a strange thing to me... :(

*** Case 5 is big for debugging... I've tried with all other small cases, but they have passed successfully... :(

making me known, coder strike 2014

Mukit09
10 лет назад
4

Комментарии (4)

Написать комментарий?

KonanMentor

10 лет назад, # |

Of course the solution with global "j" variable is wrong.

For example you have a graph:

Call history:

dfs(1) //j = 0
dfs(2) //j = 0
dfs(4) //j = 0
dfs(2) //j = 0, but 4 is visited then j = 1
dfs(5) //j = 0
dfs(2) //j = 0, 4 is visited then j = 1, but 5 is visited too then j = 2
dfs(6) //j = 0
dfs(2) //j = 0 -> j = 1 -> j = 2
dfs(1) //j = 2 we skip 3 vertex here

→ Ответить

Mukit09

10 лет назад, # ^ |

← Rev. 2 →

I have not got this call history... I think it should be like this...

dfs(1) // j = 0

dfs(2) // j = 0

dfs(4) // j = 0

dfs(2) // j = 1 , because of for loop

dfs(5) // j = 0

dfs(2) // j = 2 , because of for loop

dfs(6) // j = 0

dfs(2) // j = 3 , now condition is false

dfs(1) // j = 1 , because of for loop

dfs(3) // j = 0

dfs(1) // j = 2 , now condition is false

My code does exactly same thing .... :/

Then it will be returned to main function. Am I wrong anywhere ???

Humm.. It's right that value of 'j' could be affected, if I did some other thing using 'j'. As 'j' is declared globally, then if I change value of 'j' in any where, in all function value of 'j' will be changed. But here I have not done any thing using 'j' which could affect in dfs() function... :(

→ Ответить

nic11

10 лет назад, # ^ |

No, for each subtree we must have separate j values.

Consider we have following code:

int j, a[2];

void rec(int i) {
    if (i == 2) {
        cout << a[0] << " " << a[1] << "\n";
        return;
    }
    for (j = 0; j < 3; ++j) {
        a[i] = j;
        rec(i + 1);
    }
}

int main() {
    rec(0);
}

It outputs: