wonderful_trip's blog

By wonderful_trip, history, 5 weeks ago, In English

I just made a mistake while participating in a coding contest in Vietnam and I came across a simple dp problem, the problem was: https://lqdoj.edu.vn/problem/dutpc2a : test of the contest organizers that I participated in, https://atcoder.jp/contests/dp/tasks/dp_h: The problem I encountered is the same as the one on atcoder

But I accepted this problem on atcoder but when I submitted the test from the contest organizer that I joined, I was wrong. And the problem I have is when I compare with the character '.' I got wrong but compare with '#' then accepted. Can someone explain to me why when I compare the character '.' wrong?

I think there are a few caveats when compared to the '.' and some other special characters, if my thinking is correct, someone can explain it to me.

this my code wrong:

char v[nax][nax]; int dp[nax][nax];

int32_t main() {

FASTIO

int n, m;

cin >> n >> m;

for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= m; ++j) {
    cin >> v[i][j];
  }
}
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= m; ++j) {
    if (i == 1 && j == 1)
    {
      dp[i][j]=1;
    }
    else
      if (v[i][j] == '.')
      {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
      }
  }
}
cout << dp[n][m];
return 0;

}

and my code accepted:

char v[nax][nax]; int dp[nax][nax];

int32_t main() {

FASTIO

int n, m;

cin >> n >> m;

for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= m; ++j) {
    cin >> v[i][j];
  }
}
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= m; ++j) {
    if (i == 1 && j == 1)
    {
      dp[i][j]=1;
    }
    else
    {
      if (v[i][j] != '#')
      {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
      }
    }
  }
}
cout << dp[n][m];
return 0;

}

Thanks for the help and sorry for my english!

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Your code seems correct. If the judging results differ between AtCoder and the lqdoj.edu.vn judge, maybe lqdoj.edu.v has mistakes in their test cases?

Also, ensure nax is big enough (should be at least 100).

Could you share the entire code?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My nax: #define nax (int) (1005) and it's completely enough. I think the test case on lqdoj.edu.vn judge is not wrong because there is another code that is correct when used with '.' but they use dp while input and when I save it in the character array it is wrong . Here is accepted code from dp while input:

    int  main()
    {
        cin >> h >> w;
        f[1][0] = 1;
        for ( long long  i = 1 ; i <= h ; i ++ )
        {
            for ( long long  j = 1 ; j <= w ; j ++ )
            {
                char g;
                cin >> g;
                if (g == '.')
                    f[i][j] = (f[i - 1][j] + f[i][j - 1]) % N;
                else
                {
                    f[i][j] = 0;
                }
            }
        }
        cout << f[h][w];
    }
    

    Is it possible that when saving in the character array there will be a trouble when comparing it?