335 - Processing MX Records

All about problems in Volume 3. 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
pem3v78
New poster
Posts: 1
Joined: Fri Jul 11, 2003 11:30 am

#335 Test cases

Post by pem3v78 » Fri Jul 11, 2003 11:40 am

Hello,

Could you provide test data (extreme conditions would be helpful also) ?

Thanks

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

335 - Processing MX Records

Post by junbin » Wed Feb 04, 2004 5:26 am

I am trying to solve q335 (Processing MX Records) and I keep getting WA for some reasons.

I've tried handling cases where there are wildcards in the first string and so on, but still no success.

Can anyone with AC please answer some of my queries?

1) Is the judge case-sensitive?
2) If the judge is case-sensitive, should we print the result as upper case, lower case or original case?
3) If there are multiple choices with the same priorities, how do we determine which one to choose?
4) If there's a record for mail.a.com and *.a.com and *.com and *, which one do we choose?



If it is not too inconvenient, can someone just run the following test data through their AC program please?

test data:

Code: Select all

31
a.com  0  b.com
a.com  0  c.com
a.com  0  d.com
y.com  0  G.com
Z.com  0  e.com
mail.b.edu 0 server1.com
*.b.edu 0 server2.com
*.edu 0 server3.com
*il.b.edu 0 server4.com
*edu 0 server5.com
mail.b.org 5 server1.org
*.b.org 4 server2.org
*.org 3 server3.org
*il.b.org 2 server4.org
*org 1 server5.org
*net 1 server5.net
*il.b.net 2 server4.net
*.net 3 server3.net
*.b.net 4 server2.net
mail.b.net 5 server1.net
*ws 5 server5.ws
*il.b.ws 4 server4.ws
*.ws 3 server3.ws
*.b.ws 2 server2.ws
mail.b.ws 1 server1.ws
mail.b.biz 1 server1.biz
*il.b.biz 2 server2.biz
*.b.biz 3 server3.biz
*.biz 4 server4.biz
*biz 5 server5.biz
* 100 catchall
A a.com
D c.com
A a.com
D b.com
A a.com
U c.com
A a.com
D d.com
A a.com
A A.com
A z.com
A y.com
A Y.com
A mail.b.edu
A grail.b.edu
A home.b.edu
A c.edu
A cedu
A mail.b.org
A grail.b.org
A home.b.org
A c.org
A corg
A mail.b.net
A grail.b.net
A home.b.net
A c.net
A cnet
A mail.b.ws
A grail.b.ws
A home.b.ws
A c.ws
A cws
A mail.b.biz
A grail.b.biz
A home.b.biz
A c.biz
A cbiz
A g.com.sg
A microsoft.com
A uva.edu.es
A onlinejudge.uva.es
X

My output:

Code: Select all

a.com => d.com
a.com => d.com
a.com => d.com
a.com => d.com
a.com => c.com
a.com => c.com
z.com => e.com
y.com => G.com
y.com => G.com
mail.b.edu => server1.com
grail.b.edu => server4.com
home.b.edu => server2.com
c.edu => server3.com
cedu => server5.com
mail.b.org => server5.org
grail.b.org => server5.org
home.b.org => server5.org
c.org => server5.org
corg => server5.org
mail.b.net => server5.net
grail.b.net => server5.net
home.b.net => server5.net
c.net => server5.net
cnet => server5.net
mail.b.ws => server1.ws
grail.b.ws => server2.ws
home.b.ws => server2.ws
c.ws => server3.ws
cws => server5.ws
mail.b.biz => server1.biz
grail.b.biz => server2.biz
home.b.biz => server3.biz
c.biz => server4.biz
cbiz => server5.biz
g.com.sg => catchall
microsoft.com => catchall
uva.edu.es => catchall
onlinejudge.uva.es => catchall

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Wed Feb 04, 2004 6:12 pm

i think there is no test data with multiple choices.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Wed Feb 04, 2004 6:17 pm

my ACed program ran out with the following

Code: Select all

a.com => 
a.com => 
a.com => d.com
a.com => c.com
a.com => c.com
A.com => catchall
z.com => catchall
y.com => G.com
Y.com => catchall
mail.b.edu => server1.com
grail.b.edu => server2.com
home.b.edu => server2.com
c.edu => server3.com
cedu => server5.com
mail.b.org => server5.org
grail.b.org => server5.org
home.b.org => server5.org
c.org => server5.org
corg => server5.org
mail.b.net => server5.net
grail.b.net => server5.net
home.b.net => server5.net
c.net => server5.net
cnet => server5.net
mail.b.ws => server1.ws
grail.b.ws => server2.ws
home.b.ws => server2.ws
c.ws => server3.ws
cws => server5.ws
mail.b.biz => server1.biz
grail.b.biz => server2.biz
home.b.biz => server3.biz
c.biz => server4.biz
cbiz => server5.biz
g.com.sg => catchall
microsoft.com => catchall
uva.edu.es => catchall
onlinejudge.uva.es => catchall
It looks funny :lol:

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Feb 05, 2004 2:09 pm

I managed to get AC'ed. Apparently, my code was correct.. I just had to remove the case-insensitive bit... and then change the input.

I think they are putting tabs in the input because when I did manual parsing of the input, I skipped all the spaces and got WA.. but when I use gets and sscanf, I get AC.

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Wed Mar 10, 2004 9:52 pm

I'm also getting Wrong Answer, but i cannot understand your correct outputs. The input of the example posted by junbin starts saying:

Code: Select all

a.com  0  b.com 
a.com  0  c.com 
a.com  0  d.com 
y.com  0  G.com 
Z.com  0  e.com
So, why the first lines writted by your programs tells this one in junbin's version:

Code: Select all

a.com => d.com 
a.com => d.com 
a.com => d.com 
a.com => d.com 
a.com => c.com 
a.com => c.com
and this one in sjn's version:

Code: Select all

a.com => 
a.com => 
a.com => d.com 
a.com => c.com 
a.com => c.com
My output is the following one. I don't understand why a.com is redirected to d.com or (blank) in your versions if the first MX records redirects this machine to b.com (like my versions' output)

Thanks in advance!

Joan

Code: Select all

a.com => b.com
a.com => d.com
a.com => catchall
a.com => c.com
a.com => 
A.com => 
z.com => 
y.com => G.com
Y.com => 
mail.b.edu => server1.com
grail.b.edu => server2.com
home.b.edu => server3.com
c.edu => server5.com
cedu => 
mail.b.org => server5.org
grail.b.org => server4.org
home.b.org => server3.org
c.org => 
corg => 
mail.b.net => server5.net
grail.b.net => server4.net
home.b.net => server3.net
c.net => 
cnet => 
mail.b.ws => server1.ws
grail.b.ws => server2.ws
home.b.ws => server3.ws
c.ws => server5.ws
cws => 
mail.b.biz => server1.biz
grail.b.biz => server2.biz
home.b.biz => server3.biz
c.biz => server4.biz
cbiz => server5.biz
g.com.sg => 
microsoft.com => 
uva.edu.es => 
onlinejudge.uva.es =>

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Mar 11, 2004 12:25 am

If I remmeber right, there's no case where multiple answers are possible
eg

a.com 0 b.com
a.com 0 c.com


but anyway, a quick look at the answers:

A a.com
D c.com
A a.com
D b.com
A a.com
U c.com
A a.com
D d.com
A a.com


You can see that for the last A a.com, c.com is up.. so a.com should redirect to c.com

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Thu Mar 11, 2004 4:05 pm

so you are saying me that

Code: Select all

2
a.com 0 machineA.com
a.com 0 machineB.com
A    a.com
X
will output this one:

Code: Select all

a.com => machineA.com
or

Code: Select all

a.com => machineB.com
??


Thanks in advance, Joan

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Mar 12, 2004 12:16 am

There won't be a case where there's a possibility of ambiguity.. so there won't be a :

x a y
x a z


where x y z are server names and a is a prioirty number

Kadaver
New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:

Still not working

Post by Kadaver » Sat Oct 23, 2004 12:22 pm

Good morning,

I tried to solve this problem, but I'm still getting WAs. I have changed my program according to information from this forum, but still it isn't working. I tried to run my program on the input from this page and the output was:

a.com => b.com
a.com => b.com
a.com => d.com
a.com => c.com
a.com => c.com
A.com => catchall
z.com => catchall
y.com => G.com
Y.com => catchall
mail.b.edu => server1.com
grail.b.edu => server4.com
home.b.edu => server2.com
c.edu => server3.com
cedu => server5.com
mail.b.org => server5.org
grail.b.org => server5.org
home.b.org => server5.org
c.org => server5.org
corg => server5.org
mail.b.net => server5.net
grail.b.net => server5.net
home.b.net => server5.net
c.net => server5.net
cnet => server5.net
mail.b.ws => server1.ws
grail.b.ws => server2.ws
home.b.ws => server2.ws
c.ws => server3.ws
cws => server5.ws
mail.b.biz => server1.biz
grail.b.biz => server2.biz
home.b.biz => server3.biz
c.biz => server4.biz
cbiz => server5.biz
g.com.sg => catchall
microsoft.com => catchall
uva.edu.es => catchall
onlinejudge.uva.es => catchall

It is simillar to sjn's version, but still, I can't convince the judge, that this is right. I wrote it in Java and I skipped all whitespaces in reading the input (not only space characters), but it didn't help.

I'm really hopeless here. Can you help me please?

Thanks in advance...

Kadaver

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Tue Jan 02, 2007 12:42 am

Would anybody tell me what can be possibly wrong with my code? I print lexicographically smallest web site if there are multiple choices. I check "If the first field is not present" by using isspace()...

Code: Select all

#include <cctype>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
using namespace std;

map < string, vector < pair < int, string > > > data, datax;

int main(){
    
    string s, a, b;
    int n, p; cin >> n; getline(cin, s);
    while(n-- && getline(cin, s)){
	istringstream sin(s);
	if(isspace(s[0])) sin >> p >> b;
	else sin >> a >> p >> b;
	if(a[0] == '*') datax[a.substr(1)].push_back(make_pair(p, b));
	else data[a].push_back(make_pair(p, b));
    }
    
    set < string > down;
    while(cin >> a >> b && a != "X")
	if(a == "D") down.insert(b);
	else if(a == "U") down.erase(b);
	else{
	    cout << b << " => ";
	    vector < pair < int, string > > all;
	    if(data.count(b)) all = data[b];
	    for(int i = 0; i <= (int)b.size(); i++)
		if(datax.count(b.substr(i))){
		    vector < pair < int, string > > &add = datax[b.substr(i)];
		    for(int i = 0; i < (int)add.size(); i++)
			all.push_back(add[i]);
		}
	    sort(all.begin(), all.end());
	    string ans = "";
	    for(int i = 0; i < (int)all.size(); i++)
		if(!down.count(all[i].second)){
		    ans = all[i].second;
		    break;
		}
	    if(ans.size()) cout << ans;
	    cout << endl;
	}
    

    return 0;
}

igorsk
New poster
Posts: 1
Joined: Tue Jan 02, 2007 7:00 am

Post by igorsk » Tue Jan 02, 2007 7:14 am

The input seems to contain commands different from D, U, A and X. When I change your solution so that it ignores bad commands, it gets ACC.

I had the same problem with my code - I was throwing an exception on bad input and kept getting RE.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 335 - Processing MX Records

Post by metaphysis » Thu Jul 07, 2016 3:38 am

I dont't think so, my AC solution assumes that there is no other commands rather than U, D, A, X.

Post Reply

Return to “Volume 3 (300-399)”