853 - DVD Subtitles

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

853 - DVD Subtitles

Post by erdos » Tue Feb 04, 2003 2:22 am

Hi,

I just want to warn people who may be doing this problem that the input file does NOT have blank lines after each sentence as it may look from the html. That was a presentation problem.

Hope this helps people avoiding wrong answers.

Regards,


Jose Santos

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri May 07, 2004 2:17 pm

After 10 or so WAs I'm getting quite fed up about this problem, mainly because the weak description and the way the input and output expamples are formatted (extra newlines as erdos noted).

- What does the phrase "words contain letters and hyphens only" exactly mean? Can a word only contain 53 different chars ('A'-'Z', 'a'-'z and '-') or are there other chars (digits, underscore, etc.)?

- Can the 'ambiguous case' contain different numbers of words for both languages? ("gas station/tankstelle") What is the order of words in the ambiguous case ("station master/bahnhofsvorsteher" or "master station/bahnhofsvorsteher")? The sample output hints to the second alternative (alphabetic), but it's not stated in the description.

- When are empty lines inserted? The description says only in between cases, but the sample output has them between every line.

Is this input/output combination correct? (sorry for my terrible German...)

Code: Select all

4
8
In de jaren vijftig leerden de kinderen
in Nederland schrijven met het zogenaamde leesplankje.
Dit leesplankje bevatte de woorden:
Aap, Noot, Mies, Teun, Vuur, etc.
Mies en Teun zijn eigennamen die niet meer zoveel voorkomen
in het hedendaagse Nederland,
daarom zou je nu beter kunnen zeggen:
Aap, Noot, Sharon, Kevin, Vuur.
Im fuenfziger Jahren lernten die Kinder
im Holland schreiben an Hande des sogenanntes Lesebrettchen.
Auf diesen Lesebrettchen standen die Woerter:
Affe, Nuss, Mies, Teun, Feuer, usw.
Mies und Teun sind Nahmen die nicht mehr so ueblich
sind im heutzutaglichen Holland,
deshalb kann man besser sagen:
Affe, Nuss, Sharon, Kevin, Feuer.
2
Zenuwinzinking?
zenuwinzinking!
Nervenzusammenbruch?
Nervenzusammenbruch!
3
neem een aardgasmonster
#&@^#%%&
weg aardgasmonster
take a natural gas sample

the natural gas sample is gone...
2
honderd-twee-en-zeventig=172
172=honderd-twee-en-zeventig
hundert-zwei-und-siebzig=172
172=hundert-zwei-und-siebzig

Code: Select all

aap noot vuur/affe feuer nuss
het nederland/holland
leesplankje/lesebrettchen
mies teun/mies teun

zenuwinzinking/nervenzusammenbruch

aardgasmonster/gas natural sample

honderd-twee-en-zeventig/hundert-zwei-und-siebzig
Are there any more critical cases/pitfalls?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun May 09, 2004 11:18 pm

Your output is correct.
By the way, your German is not bad :)

Here some other test cases (but perhaps they are already covered by your test cases):
3
2
Test Test
test
test
test
3
test
bla
test
test
test
test
3
test
test
test
test
bla
test
my output is:
test/test


User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 10, 2004 10:45 am

Thanks for your reply. That gave me the assurance that my interpretation of the problem statement was correct.

Found a stupid bug in my bitfield handling routines and got accepted. I used an array of 32 unsigned ints to store 1024 bits, but in my sorting routine they were implicitly treated as signed ints :(. Stupid, hard to find errors.

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

853 - DVD Subtitles

Post by mntamim » Sat Nov 16, 2013 1:00 am

i keep getting runtime error when i upload this,
everything working fine on my computer and getting correct results for every testcase i can think of

even tried compiling it at http://www.compileonline.com/compile_cpp_online.php and its working just fine
any clues ?

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <map>
#include <vector>
#include <string.h>
#include <stdlib.h>

using namespace std;

map<string,vector<int> > A;
map<string,vector<int> > B;

struct SandV
{
	string s;
	string v;
};

bool myAlpha(char c)
{
	if(c=='-')
		return true;
	else if(c>='a'&&c<='z')
		return true;
	else if(c>='A'&&c<='Z')
		return true;

	return false;
}

string GetWord(string &x)
{
	int i = 0;
	for( ; myAlpha(x[i]) || x[i]=='-' ; i++);

	if(i==0) i=1;

	string temp = x.substr(0,i);
	x.erase(0,i);

	string ret = "";
	for(int j=0 ; j<i ; j++)
	{
		ret+=tolower(temp[j]);
	}

	return ret;
}

void addA(string word,int line)
{
	vector<int> x = A[word];
	bool has = false;
	for(int i=0 ; i<x.size() && !has ; i++)
	{
		if(x[i] == line)
			has = true;
	}

	if(!has)
		A[word].push_back(line);
}
void addB(string word,int line)
{
	vector<int> x = B[word];
	bool has = false;
	for(int i=0 ; i<x.size() && !has ; i++)
	{
		if(x[i] == line)
			has = true;
	}

	if(!has)
		B[word].push_back(line);
}
string VtoS(vector<int> x)
{
	string ret = "";
	char temp[512];

	for(int i=0 ; i<x.size() ; i++)
	{
		sprintf(temp,"%d ",x[i]);
		//ret += itoa(x[i],temp,10);
		ret += temp;
		//ret += " ";
	}
	return ret;
}

int SandVcompareV (const void * a, const void * b)
{
  return strcmp( (*(SandV*)a).v.c_str(),(*(SandV*)b).v.c_str() );
}
int SandVcompareS (const void * a, const void * b)
{
  return strcmp( (*(SandV*)a).s.c_str(),(*(SandV*)b).s.c_str() );
}

pair<SandV*,int> murge(SandV* x, int size)
{
	pair<SandV*,int> ret;
	ret.first  = new SandV[size];
	ret.second = 0;

	int i=0;
	int end = 0;

	string temp;
	string collection;
	
	while(i<size)
	{
		temp = x[i].v;

		while(end<size && strcmp( temp.c_str(),x[end].v.c_str() )==0 )
			end++;

		if(end-i > 1)
		{
			qsort(&x[i],end-i,sizeof(SandV),SandVcompareS);
			collection = "";
			for(int j=i ; j<end ; j++)
			{
				if(j!=i)
					collection += " ";
				collection += x[j].s;
			}
			
			ret.first[ret.second].s = collection;
			ret.first[ret.second].v = x[i].v;
		}
		else
		{
			ret.first[ret.second].s = x[i].s;
			ret.first[ret.second].v = x[i].v;
		}

		ret.second++;
		i = end;
	}

	return ret;
}

int main()
{
	//freopen("input.txt","r",stdin);

	int    n;
	int    lines;
	string line;


	cin >> n;
	while(n--)
	{
		A.clear();
		B.clear();

		cin>>lines;
		getline(cin,line);

		// language A
		for(int i=0 ; i<lines ; i++)
		{
			getline(cin,line);
			while(line.empty()==false)
			{
				string x = GetWord(line);
				if(x.size() > 2)
				{
					addA(x,i);
				}
			}
		}

		// language B
		for(int i=0 ; i<lines ; i++)
		{
			getline(cin,line);
			while(line.empty()==false)
			{
				string x = GetWord(line);
				if(x.size() > 2)
				{
					addB(x,i);
				}
			}
		}


		//
		// work with A and B
		//


		// empty words mentioned only once
		map<string,vector<int> >::iterator it;
		vector<string> temp;

		
		it = A.begin();
		while(it != A.end())
		{
			if(it->second.size()<2)
				temp.push_back(it->first);
			it++;
		}
		for(int i=0 ; i<temp.size() ; i++)
			A.erase(temp[i]);

		it = B.begin();
		temp.clear();
		while(it != B.end())
		{
			if(it->second.size()<2)
				temp.push_back(it->first);
			it++;
		}
		for(int i=0 ; i<temp.size() ; i++)
			B.erase(temp[i]);

		
		SandV SVtemp;
		SandV* AA = new SandV[A.size()];
		SandV* BB = new SandV[B.size()];

		int counter = 0;
		for(it=A.begin() ; it!=A.end() ; it++,counter++)
		{
			SVtemp.s = it->first;
			SVtemp.v = VtoS(it->second);
			AA[counter] = SVtemp;
		}
		qsort(AA,A.size(),sizeof(SandV),SandVcompareV);
		pair<SandV*,int> retA = murge(AA,A.size());


		counter = 0;
		for(it=B.begin() ; it!=B.end() ; it++,counter++)
		{
			SVtemp.s = it->first;
			SVtemp.v = VtoS(it->second);
			BB[counter] = SVtemp;
		}
		qsort(BB,B.size(),sizeof(SandV),SandVcompareV);
		pair<SandV*,int> retB = murge(BB,B.size());

		qsort(retA.first,retA.second,sizeof(SandV),SandVcompareS);

		for(int i=0 ; i<retA.second ; i++)
		{
			for(int j=0 ; j<retA.second ; j++)
			{
				if(strcmp( retA.first[i].v.c_str() , retB.first[j].v.c_str() )==0)
				{
					cout << retA.first[i].s << "/" << retB.first[j].s << endl;
				}
			}
		}
	}	
	
	return 0;
}

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

Re: 853 - DVD Subtitles

Post by mntamim » Sat Nov 16, 2013 11:30 am

fixed the runtime error, i was copying full std::strings which compiler didnt like i guess
changed them to char[] and no runtime error but im getting wrong answer now !!, how come ?

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <map>
#include <vector>
#include <string.h>
#include <stdlib.h>

using namespace std;

map<string,vector<int> > A;
map<string,vector<int> > B;

struct SandV
{
	char s[512];
	char v[512];

	SandV()
	{
		memset(s,0,512);
		memset(v,0,512);
	}
	SandV( const SandV& other )
	{
		strcpy(s,other.s);
		strcpy(v,other.v);
	}
};

bool myAlpha(char c)
{
	if(c=='-')
		return true;
	else if(c>='a'&&c<='z')
		return true;
	else if(c>='A'&&c<='Z')
		return true;

	return false;
}

string GetWord(string &x)
{
	int i = 0;
	for( ; myAlpha(x[i]) || x[i]=='-' ; i++);

	if(i==0) i=1;

	string temp = x.substr(0,i);
	x.erase(0,i);

	string ret = "";
	for(int j=0 ; j<i ; j++)
	{
		ret+=tolower(temp[j]);
	}

	return ret;
}

void addA(string word,int line)
{
	vector<int> x = A[word];
	bool has = false;
	for(int i=0 ; i<x.size() && !has ; i++)
	{
		if(x[i] == line)
			has = true;
	}

	if(!has)
		A[word].push_back(line);
}
void addB(string word,int line)
{
	vector<int> x = B[word];
	bool has = false;
	for(int i=0 ; i<x.size() && !has ; i++)
	{
		if(x[i] == line)
			has = true;
	}

	if(!has)
		B[word].push_back(line);
}
string VtoS(vector<int> x)
{
	string ret = "";
	char temp[512];

	for(int i=0 ; i<x.size() ; i++)
	{
		sprintf(temp,"%d ",x[i]);
		ret += temp;
	}
	return ret;
}
int SandVcompareV (const void * a, const void * b)
{
  return strcmp( (*(SandV*)a).v , (*(SandV*)b).v );
}
int SandVcompareS (const void * a, const void * b)
{
  return strcmp( (*(SandV*)a).s , (*(SandV*)b).s );
}
pair<SandV*,int> murge(SandV* x, int size)
{
	pair<SandV*,int> ret;
	ret.first  = new SandV[size];
	ret.second = 0;

	int i=0;
	int end = 0;

	char* temp;
	string collection;
	
	while(i<size)
	{
		temp = x[i].v;

		while(end<size && strcmp( temp ,x[end].v )==0 )
			end++;

		if(end-i > 1)
		{
			qsort(&x[i],end-i,sizeof(SandV),SandVcompareS);
			collection = "";
			for(int j=i ; j<end ; j++)
			{
				if(j!=i)
					collection += " ";
				collection += x[j].s;
			}
			
			strcpy(ret.first[ret.second].s,collection.c_str());
			strcpy(ret.first[ret.second].v,x[i].v);
		}
		else
		{
			strcpy(ret.first[ret.second].s,x[i].s);
			strcpy(ret.first[ret.second].v,x[i].v);
		}

		ret.second++;
		i = end;
	}

	return ret;
}

int main()
{
	//freopen("input.txt","r",stdin);

	int    n;
	int    startn;
	int    lines;
	string line;


	cin >> n;

	for(startn = 0 ; startn<n ; startn++)
	{
		if(startn>0 && startn<n)
			cout << "\n";

		A.clear();
		B.clear();

		cin>>lines;
		getline(cin,line);

		// language A
		for(int i=0 ; i<lines ; i++)
		{
			getline(cin,line);
			while(line.empty()==false)
			{
				string x = GetWord(line);
				if(x.size() > 2)
				{
					addA(x,i);
				}
			}
		}

		// language B
		for(int i=0 ; i<lines ; i++)
		{
			getline(cin,line);
			while(line.empty()==false)
			{
				string x = GetWord(line);
				if(x.size() > 2)
				{
					addB(x,i);
				}
			}
		}


		//
		// work with A and B
		//


		// empty words mentioned only once
		map<string,vector<int> >::iterator it;
		vector<string> temp;

		
		it = A.begin();
		while(it != A.end())
		{
			if(it->second.size()<2)
				temp.push_back(it->first);
			it++;
		}
		for(int i=0 ; i<temp.size() ; i++)
			A.erase(temp[i]);

		it = B.begin();
		temp.clear();
		while(it != B.end())
		{
			if(it->second.size()<2)
				temp.push_back(it->first);
			it++;
		}
		for(int i=0 ; i<temp.size() ; i++)
			B.erase(temp[i]);


		// empty from map into struct array and sort them based on 'v' , their order they come in
		
		SandV SVtemp;
		SandV* AA = new SandV[A.size()];
		SandV* BB = new SandV[B.size()];

		int counter = 0;
		for(it=A.begin() ; it!=A.end() ; it++,counter++)
		{
			strcpy(SVtemp.s, it->first.c_str());
			strcpy(SVtemp.v, VtoS(it->second).c_str());
			AA[counter] = SVtemp;
		}
		qsort(AA,A.size(),sizeof(SandV),SandVcompareV);
		pair<SandV*,int> retA = murge(AA,A.size());


		counter = 0;
		for(it=B.begin() ; it!=B.end() ; it++,counter++)
		{
			strcpy(SVtemp.s, it->first.c_str());
			strcpy(SVtemp.v, VtoS(it->second).c_str());
			BB[counter] = SVtemp;
		}
		qsort(BB,B.size(),sizeof(SandV),SandVcompareV);
		pair<SandV*,int> retB = murge(BB,B.size());
		
		// after calling murge all the words that come on the same lines are in the same array index
		// look for matching array index inside both arrays and print

		// to be alphabatical
		qsort(retA.first,retA.second,sizeof(SandV),SandVcompareS);

		for(int i=0 ; i<retA.second ; i++)
		{
			for(int j=0 ; j<retA.second ; j++)
			{
				if(strcmp( retA.first[i].v , retB.first[j].v )==0)
				{
					cout << retA.first[i].s << "/" << retB.first[j].s << endl;
				}
			}
		}
		


	}	
	
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 853 - DVD Subtitles

Post by brianfry713 » Mon Nov 18, 2013 11:08 pm

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 8 (800-899)”