[sudorooot]

Good evening. I really hope i write in the proper section and do not cause any troubles.
I am a second year Student and the first time I faced Algorithms and programming languages was an year ago
I recently found a task in the web, i will retell it in few words:

Imagine a word. It is ciphered by inserting two identical letters at an arbitrary place.

example: ciphered: abbcadv
real word: acadv

example2: ssssstdvvgpooreer
real word: stdgp

example3: abba
real word would be empty string here

The input line contains a ciphered word, the output is the restored word. The word is made of lowercase English letters and its length is at most 200 000.
Time limit is 1.0 second and 64MB memory;

Two of my codes managed to make it in 1.046seconds which leads to failure (Time limit exceeded(for execution)=1.046; (Memory limit exceeded)=67 960KB)
The other lead to 67MB memory used... :S

I do totally realise that my code is lame and i will really appriciate some tips on optimizing it by either reducing its size or the time for execution.
Or any other kind of advice. Or even worthy literature to read.

Once again sorry if that is not in the proper section or not an appropriate question for here.

One code:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void main()
{	
	vector<string> str;
	str.push_back("");
	str.push_back("");
	getline(cin,str[0]);
	bool flag=true;
	bool fin=false;
	int index=0;
	do
	{
		fin=false;
		flag=true;
	for(int i=1;i<str[index].size();i++)
	{
		fin=false;
		if(str[index][i]==str[index][i-1] && i+2==str[index].size())
		{
			flag=false;
			fin=false;
			str[index+1]+=str[index][i+1];
			break;
		}
		else if(str[index][i]==str[index][i-1])
		{
			flag=false;
			i++;
			fin=false;
		}
		else
		{
			str[index+1]+=str[index][i-1];
			fin=true;
		}
			
	}
	int c=str[index].size();
	if(fin==true)
		str[index+1]+=str[index][c-1];
	index++;
	str.push_back("");
	}
	while(flag==false);
	cout<<str[index-1]<<endl;
}

Other code:

#include <iostream>
using namespace std;
void main()
{
	char A[200000];
	cin>>A;
	bool flag=false;
	unsigned k;
	while(flag==false)
	{
		flag=true;
		for(unsigned i=1;i<strlen(A);i++)
		{
			if(A[i]==A[i-1] && i+1<strlen(A))
			{
				flag=false;
				k=i+1;
				unsigned pos=i-1;
				while(k<strlen(A))
					A[pos++]=A[k++];
				A[k-1]='\0';
				A[k-2]='\0';
			}
			else if(A[i]==A[i-1] && i+1==strlen(A))
			{
				flag=false;
				A[i]='\0';
				A[i-1]='\0';
			}
		}
	}
	cout<<A<<endl;
}

[JackOfAllTrades]

For starters, void main() is ALWAYS WRONG in C++. It's int main().

[sudorooot]

I have been always using it the way you say i should do but a friend, more skilled than me, told me i should do it that way as an optimising thing
Thanks

This post has been edited by sudorooot: 04 November 2010 - 09:47 AM

[JackOfAllTrades]

Is your friend more skilled than the creator of C++ himself?

[sudorooot]

Definetly not but he has helped me alot when i had problems with cout-like stuff
Thanks again m8! I really appriciate your tip

[sudorooot]

Any other ideas, please?

[janotte]

I don't understand your requirements.

Your examples don't match your description of the process nor do they match one another.

Without knowing the rule/s you are applying I can't help you.

--------
Send your friend this link
http://www.gidnetwork.com/b-66.html
so he can read up on why he is wrong.

[n8wxs]

Well I would create a second array after getting the user's input.

Then as I scanned the input array for paired characters I would copy the singleton characters to the second array, keeping track of how many characters I copied.

When done copying, I would copy the second array back to the first and start over.

When I had copied the first array characters to the second array without detecting any pairs I would be done.

Here's a snippet:

...
char a[200000];

cin >> a;

int limit = strlen(a); // loop limit for scanning a[]

char * b = new char[limit];
int bsize = 0; // keeps track of char count in b[]

bool flag = true; // keeps track of whether we copied any chars
bool pairs;	// indicates pair was seen

unsigned i; // index in a[]
unsigned bi; // index into b[]

while (flag) {
...

Here's the output of my code:

Quote

ssssstdgpooreer
stdgp

Hit ENTER to continue...

This post has been edited by n8wxs: 04 November 2010 - 11:13 PM