roman28's blog

Can Someone Explain This?
By roman28, 9 years ago, In English

Look at the following two codes Accepted Wrong Anwer

the only difference in the above two codes is that accepted code has the declaration char c[105][105] while the wrong answer code has the declaration char c[n][m]. Can someone explain me the reason behind why second one is wrong?

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

Comments Comments (13)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Its weird for the same test case your code gives correct ans on Ideone. See this link : http://ideone.com/wAtjBk I tried submitting it on CF, got WA on 15th test case for which again your code is giving correct result. Really weird stuff. o.O

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

    I've got WA in submission, look at test five, it's much weirder... 9549558

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You don't initialize all entries of your array (specifically, entries with i%2 == 1, j > 0 and j < m-1 are left uninitialized). This doesn't hurt your algorithm unless a random uninitialized value of one of those entries is '#'. It so happened that this is the case for one of your solutions but not for the other one.

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

    How is declaring char c[n][m] and char c[105][105] different in terms of initialization?

    I guess both are used as uninitialized, it is just the dynamic size and the constant size that is affecting the output. Correct me if I am wrong.

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

      Well it may have some influence, but it's an implementation detail anyway and probably depends on the compiler and how it optimized the code. I've just tested it by declaring two uninitialized arrays of the same size (one constant length, another variable length). Both had non-zero (uninitialized) entries.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Have a look at this. here i have declared char c[n+50][m+50] and it acceped. I dont have a clue why. have a look at this. here i have declared char c[60][60] while the maximum input could only be of size 50, still it is giving WA and if i declare char c[65][65], it is accepted. why?

    I am asking all this, so that i don't fall into this trap during one of the live contests.

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

Size of your array must be bigger than n,m. Don't actually know why, but I guess you trying to access to place in your array that does not exist. (When I use arrays I make maximal size for them, in order to don't have any trouble with them. Sorry for bad english, correct me if I am wrong)

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

    Have a look at this Wrong Answer

    here if have declared char c[n+5][m+5], but the solution is still wrong.

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

      maximal size (c[1000][1000]) or try c[n+50][m+50], works

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

        Yeah it does!! But what is the reason? If i see such solution during the live contest, can i design a test case to hack it?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          Well, I think it's very hard, because you don't know what Codeforces computers are like. My teacher has told us that we shouldn't declare arrays like that or something unexpected may happen. If you really want to do so, you can just do this:

          vector<vector<char> > c(n);
for(int i=0;i<n;i++)c[i].resize(m);

          or

          const int maxn=105,maxm=105;
char c[maxn][maxm];
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            In the second option the array will be also uninitialized, unless it's a global variable.

            → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        OH!!!!!!!!!!!! come on man ! Extra spaces isn't solution for this problem .

        As slycelote said , this problem is because of uninitialized array.

        It is very simple , when you don't initialize array , random values filled the array. So imagine I want to create an uninitialized array with 5 items and then fill odd positions with '#'. then I do that with what roman28 did in his code for fill and print array .

        Sample uninitialized array :           0Fu^9

-> Fill odd positions :                #F#^#

-> Print it (s[i]=='#' ? '#' : '.') -> #.#.#

---------------------------------------------------

Another Sample ->                      9#oQp

-> Fill odd positions :                ###Q#

-> Print it (s[i]=='#' ? '#' : '.') -> ###.#

        I think this samples are clear enough .

        → Reply