853 - DVD Subtitles

[erdos]

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

[little joey]

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]

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

[little joey]

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]

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]

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]

http://acm.uva.es/board/viewtopic.php?t=2252