10066 - The Twin Towers

[kier.guevara]

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
		int n, m;
		vector <int> twin_1;
		vector <int> twin_2;
		vector <int> numTiles;
		int input, testC = 1;
		while(cin >> n >> m )
		{
		
			if(m == 0 && n ==0)
				break;
			
			for(int i = 0; i < n; i++)
			{
				cin >> input;
				twin_1.push_back(input);
			}
			
			for(int i = 0; i < m; i++)
			{
				cin >> input;
				twin_2.push_back(input);
			}
	
			if(n < m)
			{
				swap(n, m);
				swap(twin_1, twin_2);
			}
		
	
			for(int i = 0; i < n; i++)
			{
						int temp = 0;
				int counter = 0;
				int p = 0;
			
				for(int k = i; k < n; k++)
				{
					p = temp;
					for(; p < m; p++)
					{
						if(twin_1[k] == twin_2[p])
						{
							counter++;
							p++;
							temp = p;
							break;
						}
					}
				}
			
				numTiles.push_back(counter);
				
			}
			
			swap(n, m);
				swap(twin_1, twin_2);
			
			for(int i = 0; i < n; i++)
			{
						int temp = 0;
				int counter = 0;
				int p = 0;
			
				for(int k = i; k < n; k++)
				{
					p = temp;
					for(; p < m; p++)
					{
						if(twin_1[k] == twin_2[p])
						{
							counter++;
							p++;
							temp = p;
							break;
						}
					}
				}
			
				numTiles.push_back(counter);
				
			}
			
			int maxTiles = 0;
			for(int i = 0; i < numTiles.size() - 1; i++)
			{
				numTiles[i+1] = max(numTiles[i], numTiles[i+1]);
			}
			
			cout << "Twin Towers #" << testC << endl << "Number of Tiles : " <<   numTiles[numTiles.size()-1]  << endl << endl;
				
			twin_1.clear();
			twin_2.clear();
			testC++;
			numTiles.clear();
		}
		return 0;
}

Tried a lot test cases in uva toolkit and it matches mine but I still got WA..why?

[shuvokr]

@kier.guevara try this I/O

Code: Select all

100 100
1 2 3 4 5 6 5 4 8 5 4 5 4 5 8 6 5 4 8 4 5 6 8 5 1 2 3 1 5 1 4 5 6 5 8 5 2 1 4 5 5 6 4 5 6 5 8 5 4 5 1 2 3 4 5 6 5 4 8 5 4 5 4 5 8 6 5 4 8 4 5 6 8 5 1 2 3 1 5 1 4 5 6 5 8 5 2 1 4 5 5 6 4 5 6 5 8 5 4 5 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 

Code: Select all

Ac code output is : 6123088
It is a sequence problem.
Hope that its help you ....

[Testment]

isn't this a straight LCS !?
can any one help with my code
i already had it tested with no bugs

Code: Select all

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>
#include <set>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <complex>
#include <sstream>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <bitset>
using namespace std;
//
#define lp(i, n)			for(int (i)=0;		(i)<(int)(n);	(i)++)
#define MAX 109
#define dex [i][j]
int DP[MAX][MAX];
int ST[MAX][MAX] = {0};
//
int mark = 0;
int n, m;
int *s1, *s2;
//
int doit(int i = 0, int j = 0)
{
	if(i == n || j == m)
		return 0;

	if(ST dex == mark)
		return DP dex;
	ST dex = mark;

	if(s1[i] == s2[j])
		return DP dex = 1 + doit(i+1, j+1);

	int c1 = doit(i+1, j);
	int c2 = doit(i, j+1);
	return DP dex = max(c1, c2);
}
//
int main()
{
	while( scanf("%d %d", &n, &m) && !(n == 0 && m == 0) )
	{
		s1 = new int[n];
		s2 = new int[m];
		lp(i, n)
			scanf("%d", &s1[i]);
		lp(i, m)
			scanf("%d", &s2[i]);
		printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", ++mark, doit());
	}
}

[lighted]

Your code doesn't match first case of sample. http://ideone.com/riv1Zf

[Testment]

Your code doesn't match first case of sample. http://ideone.com/riv1Zf

appreciate your help
that was really unfair
it was just a difference in compiling the printf() function
with this little edit it works fine with the judge

Code: Select all

mark++;
printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", mark, doit());

[brianfry713]

http://stackoverflow.com/questions/1790 ... tions-in-c
Evaluation order of function parameters is not specified - it is left up to the implementation.
One reason to use the same compiler (g++) to test your code that the judge uses.