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

Coder-Strike 2014 — Round 1 (Problem D)
Автор Mukit09, 11 лет назад, По-английски

I've faced a strange thing when solving this 412D - Giving Awards. 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... :(

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

For example you have a graph:

    1
   / \
  2   3
 /|\
4 5 6

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
→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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... :(

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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:

      0 0
0 1
0 2

      If we add int j; definition before for, this will work as you expect. Same thing in your dfs

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks... Now I've got this... your given code nicely has explained the difference between these two declaration.... :)

        → Ответить