869 - Airline Comparison

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
miollnyr
New poster
Posts: 2
Joined: Mon Feb 08, 2010 8:44 pm

869 - Airline Comparison

Post by miollnyr » Mon Feb 08, 2010 8:52 pm

Hi,

I got WA on this problem, although I have solved similar problems on this site.

Could anybody explain whats wrong with my code and / or provide some inputs / outputs?

Thanks in advance!

Code: Select all

#include <iostream>
#include <map>
#include <vector>
#include <list>

using namespace std;

typedef vector<bool> line;
typedef vector<line> matrix;
typedef pair<char,char> pcc;
typedef list<pcc> lpcc;

map<char, int> c2i;
map<int, char> i2c;
lpcc roads;
int cities = 0;
matrix E;

#ifdef WIN32
ostream& operator<<(ostream& out, const line& in)
{
	int i;

	for(i = 0; i < in.size(); ++i)
	{
		out << (in[i] ? 1 : 0);
	}

	return out;
}

ostream& operator<<(ostream& out, const matrix& in)
{
	int i;

	out << " ";
	for(i = 0; i < cities; ++i)
	{
		out << i2c[i];
	}
	out << '\n';

	for(i = 0; i < cities; ++i)
	{
		out << i2c[i] << in[i] << '\n';
	}

	return out;
}
#endif

line& operator+=(line& lhs, const line& rhs)
{
	int i;
	for(i = 0; i < lhs.size(); ++i)
	{
		lhs[i] = (lhs[i] || rhs[i]);
	}

	return lhs;
}

line& operator-=(line& lhs, const line& rhs)
{
	int i;
	for(i = 0; i < lhs.size(); ++i)
	{
		lhs[i] = (lhs[i] && !rhs[i]);
	}

	return lhs;
}

bool operator==(const matrix& lhs, const matrix& rhs)
{
	int i, j;

	for(i = 0; i < lhs.size(); ++i)
	{
		for(j = 0; j < lhs[i].size(); ++j)
		{
			if(lhs[i][j] != rhs[i][j])
			{
				return false;
			}
		}
	}

	return true;
}

void addCity(const char c)
{
	if(c2i.find(c) == c2i.end())
	{
		c2i[c] = cities;
		i2c[cities] = c;
		
		++cities;
	}
}

void readFirstMatrix(matrix& in)
{
	int n, i;
	char a, b;

	cin >> n;

	for(i = 0; i < n; ++i)
	{
		cin >> a >> b;

		addCity(a); 
		addCity(b);

		roads.push_back( pcc(a, b));
	}

	n = cities;
	in.resize(n);
	for(i = 0; i < n; ++i)
	{
		in[i] = line(n, false);
	}
	
	for(lpcc::iterator it = roads.begin(); it != roads.end(); ++it)
	{
		a = it->first;
		b = it->second;

		in[ c2i[a] ][ c2i[b] ]  =  true;
	}
}

bool readSecondMatrix(matrix& in)
{
	int n, i, size = cities;
	char a, b;

	cin >> n;

	in.resize(cities);
	for(i = 0; i < cities; ++i)
	{
		in[i] = line(cities, false);
	}

	for(i = 0; i < n; ++i)
	{
		cin >> a >> b;

		if(c2i.find(a) == c2i.end() || c2i.find(b) == c2i.end())
		{
			return false;
		}

		in[ c2i[a] ][ c2i[b] ]  = true;
	}

	return true;
}

void closure(matrix& in)
{
	matrix tmp(E);

	int i, j, size = in.size();
	
	for(i = 0; i < size; ++i)
	{
		for(j = 0; j < size; ++j)
		{
			if(i != j && tmp[i][j] && in[i][j])
			{
				in[i] += in[j];

				tmp[i][j] = false;

				if(i > j)
				{
					tmp[i] -= in[j];
				}
				
				--i; break;
			}
		}
	}
}

void createE(const int size)
{
	int i;

	E.resize(size);

	for(i = 0; i < size; ++i)
	{
		E[i] = line(size, true);
	}
}

int main()
{
	int num;

	cin >> num;

	while(num--)
	{
		matrix matrix1, matrix2;
		
		c2i.clear();
		i2c.clear();
		roads.clear();
		cities = 0;

		readFirstMatrix(matrix1);
		
		if(readSecondMatrix(matrix2))
		{
			createE(matrix1.size());
	
			closure(matrix1);
			closure(matrix2);

			//cout << matrix1 << "\n\n" << matrix2 << "\n\n";///

			cout << (matrix1 == matrix2 ? "YES" : "NO") << (num == 0 ? "" : "\n\n");
		}
		else
		{
			cout << "NO" << (num == 0 ? "" : "\n\n");
		}
	}

	return 0;
}


Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 869 - Airline Comparison

Post by Shafaet_du » Thu Sep 16, 2010 8:21 pm

Code: Select all

5

0
0

0
2
a b
b c

4
a b
b c
d e
e f
4
a e
b c
d e
e f

4
a b
b c
D e
e F
5
e D
a b
b c
E F
a c

6
a b
a c
b e
c d
g h
h i
6
a b
b e
a c
c d
d i
g h
output from my ac code:

Code: Select all

YES

NO

NO

YES

NO
I used floyd warshall to solve this. it took .004 sec.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 869 - Airline Comparison

Post by Imti » Mon Oct 31, 2011 11:58 pm

I don't understand why the cities are not case sensitive as problem description didn't cleared it.
How to get that point 'case insensitive' from this problem?

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 869 - Airline Comparison

Post by SyFy » Thu Jun 28, 2012 2:34 pm

:D this should help others

input:

Code: Select all

1

5
# $
A 0
D #
* B
@ F

3
A D
h &
0 8
output:

Code: Select all

NO
good luck!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 869 - Airline Comparison

Post by Scarecrow » Tue Aug 14, 2012 3:35 pm

for other's convenience, judge I/O set doesn't contain any character other than 26 capitals letters. 'cause my AC code handled only these 26 characters.
Do or do not. There is no try.

hquilo
New poster
Posts: 13
Joined: Fri May 02, 2014 9:45 pm

Re: 869 - Airline Comparison

Post by hquilo » Mon Dec 15, 2014 4:40 pm

Hi,

I find the problem statement confusing or incomplete. In particular, it is not clear from the statement if the trip relation is reflexive. Also, it does not mention if N and M can be zero.

Consider the following test cases:

Code: Select all

3

0
1
a a

1
a a
0

1
a a
1
b b
In these three cases the answer should be YES if the relation is reflexive; otherwise in all cases it should be no.

As a matter of fact my AC code outputs YES for all these three test cases. However, this output is not consistent for other AC solutions I found online. Then, the judge input does not contain such test cases but, anyway, it would be nice to have a clearer problem statement (at least annotated in this forum).

Regards.

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

Re: 869 - Airline Comparison

Post by brianfry713 » Tue Dec 16, 2014 12:49 am

The judge's input doesn't contain any test cases where N or M equals 0 or a flight has the same origin and destination cities.
Check input and AC output for thousands of problems on uDebug!

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 869 - Airline Comparison

Post by predicate » Sun Jun 28, 2015 8:37 am

Shafaet_du wrote:

Code: Select all

4
a b
b c
D e
e F
5
e D
a b
b c
E F
a c
The output for this test case give above is wrong. It should be No.

Post Reply

Return to “Volume 8 (800-899)”