Code jam problem

general
,
1

Welcome to code jam problem: https://code.google.com/codejam/contest/90101/dashboard#s=p2

I have been trying to solve this but have been unable to do so. I think my logic is correct and the dp is right but there is something wrong with my implementation. Suggestions are welcome. Thanks!

#include <iostream>
#include<stdio.h>
#include<string.h>
      
using namespace std;
 
int main() {
	int t;
	cin>>t;
	char str[51] = {"welcome to code jam"};
	str[19]='\0';  //Needed?
	while(t--)
	{
		char inp[501];
		gets(inp);
		int dp[20][501];
		for(int i = 0;i<20;i++)
		{
			for(int j =0;j<501;j++)
			dp[i][j]=0;
		}
		for(int i = 0;i<501;i++)
		{
			dp[0][i]=1;
		}
		for(int i = 0;i<20;i++)
		{
			dp[i][0]=0;
		}
		for(int i = 0;i<20;i++)
		{
			for(int j = 0;j<=strlen(inp);j++)	//Correct?
			{
				if(str[i]==inp[j])
				{
					dp[i+1][j+1]+=dp[i][j]+dp[i+1][j];
				}else
				{
					dp[i+1][j+1]=dp[i+1][j];
				}
			}
		}
		int u =strlen(inp);
		cout<<dp[19][u]<<endl;
	}
	return 0;
}
2

I see one obvious error: you’re completely ignoring the “last 4 digits” part of the statement. The answer can also very large very quickly, so you should do all dp calculations modulo 10000.

You didn’t compile and run the problem on your computer (or some online tools like Ideone), right? If you did, you could spot the incorrect output and guess why it’s incorrect, and wouldn’t need to ask.

And pick one way to code: C or C++. There’s no stdio.h library in C++, and no iostream in C, for example. If you used C++ strings, you wouldn’t need to bother with the terminating zero, too.

3

Actually I did. I didn’t submit it online, I was just checking with the example in the question and getting incorrect output so I left out the 10000 part in case of debugging and posted here. eg. My program gives 128 instead of 256. A %10000 wouldn’t really affect the code here would it. Thanks for your input. Any comment on the DP/logic part?

PS: How do I input a string in C++ then. Do I use gets or is it deprecated?

4

ok then, it just looks like an obvious error :smiley:

also, if strlen(inp)=500, you can access the dp[][] array out of bounds, it’s better to use a strict inequality

the dp logic is ok, but you rewrite dp[0][0] from 1 to 0 on initialization

getline(cin,s) up to the next end of line char, cin >> s up to the next whitespace char