|
|
Show all threads Hide all threads Show all messages Hide all messages | WA #13 | lijian | 1577. E-mail | 30 May 2022 04:00 | 2 | WA #13 lijian 20 Oct 2007 08:03 please give some test data!! Edited by author 20.10.2007 08:04 Mind mod, I had 10^7+7 and it was failing | AC tests | Gleb Dubosarskii | 1577. E-mail | 11 Apr 2021 10:34 | 2 | AC tests Gleb Dubosarskii 24 Apr 2017 01:18 abc cba 6 aba bab 2 abcabc cba 5 abcbaabdca abcada 1 abcabbaca abcabbc 1 thnx a lot for your tests | WA #7 | Tranvick | 1577. E-mail | 3 Jan 2020 16:42 | 3 | WA #7 Tranvick 13 Dec 2011 16:56 What's this test?? My code: #include <string> #include <algorithm> #include <iostream> #define N 2222 #define MOD 1000000007ll using namespace std; long long f[N][N],d[N][N]; int n,m; string s1,s2; void init(){ getline(cin,s1); getline(cin,s2); n=s1.length(),m=s2.length(); } int main(){ init(); for (int i=0;i<=n;i++) d[i][0]=i; for (int i=0;i<=m;i++) d[0][i]=i; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1; else d[i][j]=min(d[i-1][j],d[i][j-1])+1; for (int i=0;i<=n;i++) f[i][0]=1; for (int i=0;i<=m;i++) f[0][i]=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ if (d[i][j]==i || d[i][j]==j) f[i][j]=1; else{ if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]; else f[i][j]=f[i-1][j]+f[i][j-1]; } f[i][j]%=MOD; } cout<<f[n][m]<<endl; } You can try this: dcfc dbf Answer:2 LOL, replying after 7 years. | WA11 - please help | Mescalito | 1577. E-mail | 4 Oct 2017 12:17 | 1 | Could someone provide tests for me? Thank you | Someone just answer "yes" or "no"...... | Jaideva | 1577. E-mail | 28 Apr 2017 23:02 | 2 | Is this a problem for counting the number of shortest common superstrings ??? | Help Needed | Toufik Zaman | 1577. E-mail | 13 Dec 2016 17:53 | 2 | Please help me with test case 16 | Seems like impossible to pass with python | Infoshoc | 1577. E-mail | 30 Sep 2016 22:15 | 1 | Python: 7028591 The same C++: 7028621 Please increase memory limit or disable python. Thanks | Please give some test cases. (WA 9) | Nikunj Banka | 1577. E-mail | 13 Oct 2013 18:53 | 1 | Those who have got AC please provide with some test cases. My program fails at test 9. Dont know why. | Any Hint | qafqaz Xeyyam | 1577. E-mail | 26 Apr 2011 14:02 | 1 | Any Hint qafqaz Xeyyam 26 Apr 2011 14:02 Edited by author 22.09.2012 23:23 | WA #5 | coders1122 | 1577. E-mail | 19 Dec 2010 14:38 | 5 | WA #5 coders1122 28 Oct 2010 20:09 see the second sample on your site. the answer is 2. Any suggestions on improvement of the algorithm i use? Is my approach wrong or can be fine with some tweaking? Ravi Kiran. If in your current state s1[i]==s2[j], you should not assume states i+1,j and i,j+1. Only i+1,j+1. Thanks a lot everyone. I got accepted with the change you suggested. | WA31 | @lexx-B/\/\STU | 1577. E-mail | 9 May 2008 23:39 | 1 | WA31 @lexx-B/\/\STU 9 May 2008 23:39 | wa #14 | Samsonov Ivan (Rybinsk SAAT) | 1577. E-mail | 18 Oct 2007 00:03 | 1 | wa #14 Samsonov Ivan (Rybinsk SAAT) 18 Oct 2007 00:03 pls Give some test data Edited by author 18.10.2007 03:47 |
|
|
|