Mukit09's blog

Coder-Strike 2014 — Round 1 (Problem D)
By Mukit09, 11 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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
→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply