Domain Dilemma

All submissions for this problem are available.
One of our businesses involves selling domain names. To that effect, we have an online interface where potential buyers of domain names can check the availability of domain names, and find out how much it is going to cost them.
Domain tasting is a frowned upon practice in our industry wherein people register domain names that are typos of existing domain names in order to make money through displaying ads to the traffic received on these typos. For instance if one were to register "directo.com" one could potentially get traffic from people who were trying to reach "directi.com" but instead mistyped the last character.
In order to disincentivize tasters from registering typos of existing domain names, we wish to levy a surcharge on a domain name which is a typo of an existing domain name. The amount of surcharge would depend on the type and number of transformations required to convert an existing domain to a domain name that someone wishes to register.
The following type of transformations exist alongwith their cost 
 If a transformation requires insertion of one character, it costs 1 point
 If a transformation requires deletion of one character, it costs 1 point
 If a transformation requires replacement of one character, it costs 2 points, except where the character being replaced and its replacement are adjacent to one another on the same line of a qwerty keyboard, in which case it costs 1 point
These operations can be performed in any order, so for example, to transform the domain name "directi" to "iriecti", we can either do a deletion of "d" in directi followed by an insertion of "i" or perform an insertion followed by the deletion. Similarly, "iriecti" can be transformed to "directi" by performing an insertion of "d" followed by a deletion of "i" or viceversa.
For all domain name transformations that use 1 or 2 points, we wish to impose a surcharge of 50 and 25 cents respectively. Any domain name that requires more than 2 points will have no surcharge imposed upon them.
Input
The input starts with a line containing 2 space separated integers m & n followed by a blank line. m is the number of already registered domain names. n is the list of names that a customer wishes to register  (1 =< m =< 2500) (1 <= n <= 7000). The next m lines are the already registered domain names. This is followed by a blank line. The next n lines are the list of names to be registered. There will be no space in the domain names, and they will consist only of a combination of lowercase alphabets from a to z and digits. The length of a domain name will be less than 31 characters.
Output
The output must consist of n lines. You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points. The value printed should be the integral part of the sum in case it has a fractional part. If a domain has already been registered, you should output 1.
Example
Input: 6 7 google yahoo rediff rediffmail direct directi direct gallery speaker yahooo gopgle drect direzti Output: 1 0 0 50 50 50 25
Author:  admin 
Tags  admin 
Date Added:  10062009 
Time Limit:  30 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
Can someone let me know what input the program failed?
Can you provie me the Maximum Length of the Registered Domain ?
@Ketan Read the problem statement.
In the Example above for the transformation of gopgle to google cost 2 point. e.g. replacement for p to o(2nd character). So, the output given above is wrong. it must be 25 for the 5th domain gopgle.
Can anyone provide some tricky inputs to check my program ?
@ketan
#
# If a transformation requires replacement of one character, it costs 2 points, except where the character being replaced and its replacement are adjacent to one another on the same line of a qwerty keyboard, in which case it costs 1 point
in a qwerty keyboard, how do we define adjacency in case of digits ?
Do we look for the row just above "qwertyuiop" or the num pad rows ?
Do not consider the numpad. Consider the digit keys right below the function keys.
Hi Chef,
I couldn't quite understand the statement you made in the 'Output' section of this problem:
"You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points."
What I understand from this statement is that if 'x' is the domain name that is to be registered and 'Y' is the set of domain names already registred, then I need to print maxSurcharge ( x, Y ) logToBase10 ( x ). Here the function maxSurcharge ( x, Y ) returns the highest surcharge incurred for registering 'x' and logToBase10 ( x ) returns the logarithm to base 10 of the number of all domain names that can be made up from the domain name registered with transformations that cost 1 or 2 points.
Hi Chef,
I am sorry my previous post had some typos. Please consider this.
I couldn't quite understand the statement you made in the 'Output' section of this problem: "You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points."
What I understand from this statement is that if 'x' is the domain name that is to be registered and 'Y' is the set of domain names already registred, then I need to print maxSurcharge ( x, Y ) logToBase10 ( x ). Here the function maxSurcharge ( x, Y ) returns the highest surcharge incurred for registering 'x' and logToBase10 ( x ) returns the logarithm to base 10 of the number of all domain names that can be made up from the domain name registered with transformations that cost 1 or 2 points.
Warm Regards
Hi Chef,
I am sorry. My previous post still has the same typos. I am unable to get a PLUS symbol appear in the body of the post. I think the comment section has a limitation of not being able to display a PLUS sign. Neither a newline symbol is displayed. Anyway I wanted to ask whether the output had to be: maxSurcharge ( x, Y ) PLUS logToBase10 ( x ), where PLUS is the addition operation. Please refer to the previous post to know what I refer to by maxSurcharge and logToBase10 functions.
Yes, you are right. PLUS is addition
Admin:
what about abcde > abcdf should we treat it as deletion of e and addition of f so that we get 25 surcharge or should we treat it as replacement of e to f which doesnt incur any surcharge?
From the problem statement, it seems that both the scenarios you suggested have the same surcharge of 25
@Admin:
No if you consider it as replacement of e to f then since e and f are not on same row in qwerty keyboard no rule will apply and surchare remains 0. If you consider it as deletion and addition it will incur surcharge of 25 ( i point for deletion and 1 point for addition)
If a transformation requires replacement of one character, it costs 2 points, except where the character being replaced and its replacement are adjacent to one another on the same line of a qwerty keyboard, in which case it costs 1 point
Ooops..my mistake..misread that clause..thanx admin
You are welcome :)
I guess there should be atleast one more example that includes surchare PLUS log10.. The example in the problem doesn't have any log10 component and I am not sure if my output is correct.
For example is 50 is the maximum surcharge on a domain and there are 11 registered domains which can be transformed to this domain with 1/2 points does that mean I need to output 50 PLUS log10(11) that is 51??
@Pradeep: Yes, you are right. You should print 51.
@Admin: Thanx a lot, seems that worked :P
what should we display if
Another question,should there
@Amol No.
@Amol No.
I am using an efficient
We use this problem for
We use this problem for recruitment purposes and as such we can't help you with this one :(
The last domain "direzti" can
The problem doesn't say it is
The problem doesn't say it is 1 point just if both characters are on the same line. Read it again :)
@Stephen Thanks for the
@Stephen Oops... got it :D
I have two strings tree and
The latter case.
The latter case.
Can some one help me
Can some one help me understanding the problem.
Say for example directi is registered domain name,
There is a new request for the domain name "sirecti"
This can be done in two ways
1) Replace "i" with "s" which will cost 1 point(Adjacent character)
or
1) Insert "d" and then delete "s" which will cost 1+1= 2 points
There may be n ways to derive. Which once should we consider.
The shortest one.
The shortest one.
Thanks Aniruddha, Please can
Thanks Aniruddha,
Please can you help with this query.
I understand that the solution is to correct only once place.
Example
Directi is a registered domain
If there is a request for the name irect,
This can be done by adding D at first and i at last..... This is correction at 2 positions.
Should we consider this case
Your help much appreciated
Nandish
Yes, you have to consider
Yes, you have to consider every possible way of altering the domain. There could be many many ways, and you have to find the way that is shortest.
I have the same question
I have the same question Nischal Shetty had before.
I think direzti needs a replace operation and since c and z are in the same row it will cost 1 point, 50 cents. Please tell me how is it 25 cents?
Thanks
Please reread the problem
Please reread the problem statement. I think you are not interpreting it correctly
Hi admin/moderators "You need
Hi admin/moderators
"You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log"
Forget the log part for simplicity
consider the case of direzti and directi.
here z and c are not adjacent on the same line so with replacement approach they have 2 points. Since it is maximum surcharge no matter what we'll have 2*25 as base surcharge excluding log.
Then how come it is 25 as output for the example?????
Any help will be greatly appreciated!!
Please reread the problem
Please reread the problem statement. You are not interpreting it correctly.
"For all domain name
"For all domain name transformations that use 1 or 2 points, we wish to impose a surcharge of 50 and 25 cents respectively."
Sorry my mistake...the surcharge is 25 for 2 points and 50 for one points..for rest it is nothing.
Got it now...thanks aniruddh
Hi Admin/Mods, Please tell me
Hi Admin/Mods,
Please tell me why my submission is giving compilation error while it compiles fine in my machine. I have compiled and runned using code blocks. It uses g++ only.
In function 'int
In function 'int checkReplacementCase(char*, char*)': /sources/tested.cpp:28: error: 'strlen' was not declared in this scope /sources/tested.cpp:38: error: 'abs' was not declared in this scope /sources/tested.cpp: In function 'int transformCount(char*, char*)': /sources/tested.cpp:63: error: 'strlen' was not declared in this scope /sources/tested.cpp: In function 'void getInput()': /sources/tested.cpp:100: error: 'malloc' was not declared in this scope /sources/tested.cpp:107: error: 'strlen' was not declared in this scope /sources/tested.cpp:108: error: 'strcpy' was not declared in this scope /sources/tested.cpp:115: error: 'strlen' was not declared in this scope /sources/tested.cpp:116: error: 'strcpy' was not declared in this scope /sources/tested.cpp: In function 'void getOutput()': /sources/tested.cpp:132: error: 'strcmp' was not declared in this scope /sources/tested.cpp: In function 'void freeMemory()': /sources/tested.cpp:177: error: 'free' was not declared in this scope /sources/tested.cpp:179: error: 'free' was not declared in this scope
These were the errors I got when I tried to compile your code.
I wish we could get info abt
I wish we could get info abt the test case that resulted in failure.
Hi admin, I am new to this
Hi admin,
I am new to this online judge way to evaluate. what is the meaning of time limit exceeded. Is it that since a program exceeded time limit to return back response it is not evaluated for right or wrong output or time limit exceeded means your output was right and solution is correct but it is not within time constraints.
Pls reply.Thanks in advance
TLE means that your program
TLE means that your program did not print the output within the allotted time period. WA means that the output produced by your program does not match with the correct output.
hey can you answer this
hey can you answer this question too?
"where can I see the compile error? The yellow triangle is not clickable.."
Currently you cannot. If you
Currently you cannot. If you are not getting a compile error on your computer, then you are probably using something nonstandard, so it would pay to install the standard version Codechef uses.
uhh.. well I tried to send my
uhh.. well I tried to send my code to different websites.. to see... if I get the a compile.. before installing I think it might be worth to try SPOJ ACM.
Well I was asking if there is a link like: www.codechef.com/viewrun?id=123123
But thanks for response!
yes... SPOJ is using same
yes... SPOJ is using same compiler version...
I have 2 question Directi
6
6 2
google
yahoo
rediff
rediffmail
direct
directi
redi  cost is 25 one has to add 2 f's at last
rewiffmai cost 0 as d will be replaced by w (not a keyboard replace) and l should be added at last.
final conclusion is one has to add the points if it is > 2 cost is 0 otherwise 25 or 50. correct ???
please give me quick reply. thanks in advance
We will fix this soon.
We will fix this soon.
hello codecheff admins I have
hello codecheff admins I have
What you have written in bold
What you have written in bold seems right.
Many Many thanks Aniruddha
Hi Admin, the email id
Hi Admin,
the email id puzzles@directi.com bounces back the mail sent. How do I sent my submission for interview process
Hi CodeChef Admin, In the
Hi CodeChef Admin,
In the given example shouldn't the surcharge for "drect" be 50.3010299957 (50 + log 2) instead of 50 as it can be transformed to both "direct" and "directi" with 1 and 2 insertions respectively or are we supposed to round off the figure and output. So should the Input and output be the following or the one given?
Read the section of the
Read the section of the problem titled 'Output'.
I have read it as it says
I have read it as it says "plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points.". See my doubt is for the case of "drect" it can be transformed to "direct" by one insertion of "i" i.e. it gets 1 point again it can be transformed to "directi" by 2 insertions of "i"s i.e. it gets 2 points so "drect" can be transformed to 2 domains with 1 or 2 points so shouldn't the output be (50 + log 2) instead of 2. Am i making any wrong assumptions please clarify?
Are we supposed to take the
Are we supposed to take the integral part only?
Ok i got it. I guess I missed
Ok i got it. I guess I missed this statement "The value printed should be the integral part of the sum in case it has a fractional part." sorry for the troouble
Dictionary<T,T'> in
Dictionary<T,T'> in Collections.Generics works with the C# compiler you provide?
I'm getting runtime error and I'm not able to figure out what's wrong. It's working fine with Visual Studio I have.
We use mono. Check if your
We use mono. Check if your code runs when you use it.
@Admins: I would like to see
@Admins: I would like to see some more test cases to be added in the problem description above. Present test cases are not enough to cover all cases and so I am not sure why my solution is being marked as "Wrong Answer"... may be its a presentation error... or wrong answer to a corner case... or whatever... but I can't be sure of it.
Sample test cases aren't
Sample test cases aren't meant to cover all the scenarios; they are solely there to make sure you understood the problem. You are meant to come up with real test cases yourself.
I understand that. But then,
I understand that. But then, there has to be something(I mean it could be anything  but something) that tells us whether we are making presentation error or logical error or somthing else.
If the system says its a wrong answer, then more that anything else, I wanna know where I went wrong. I think I covered all possible scenarios and I tried making all kind of corner cases to cover those. For first 23 tries, I did miss some scenarios but now when am 99.9% sure I have covered all, still wrong answer. Its sort of irritating. Can't stop thinking what I might be missing... and its taking hellp lot of my time. :(
Also, this is a recruitment
Also, this is a recruitment problem so we can't provide any specific help as such. :(
Well, I am also solving this
Well, I am also solving this for recruitment pupose. Just that even in recruitment process not just the final right answer matters, often approches(with minor mistake) are worth a look but unless I submit this 100% correct, no one is gonna look into my resume :)
I just can't think of what I am missing :(
Ok, I think you can tell
Ok, I think you can tell atleast this much...
In C++, cin>>M>>N; will work, whether M and N are on same line(space seperated) or on different lines.
But In Java, if they are on same line, then we need to split by spaces are 1 readline... and if they are on different lines, we need to readline 2 times.
What should the case?
PS:
Problem says "The input starts with a line containing 2 space separated integers m & n followed by a blank line."
But the sample Java solution(http://www.codechef.com/help/#hc_solinjav) reads both number as if they are on different lines.
Thanks
The input is in accordance
The input is in accordance with the input specifications. So if there are 2 integers separated by a space, then that's how they will appear in the input.
Are there any possible cases,
Are there any possible cases, other than:
Insertion 1
Deletion 1
Replacement(adj) 1
Replacement(n.adj) 2
InsertionInsertion 2
InsertionDeletion 2
InsertionReplacement(adj) 2
DeletionInsertion 2
DeletionDeletion 2
DeletionReplacement(adj) 2
Replacement(adj)Insertion 2
Replacement(adj)Deletion 2
Replacement(adj)Replacement(adj) 2
Just a simple yes/no will help.
Thanks
Hi All, I do not understand
Hi All,
I do not understand the last test casedirezti
All score is zero except direct,directi.
For direct score is (1 insertion+1 substitution of 1 pt)= 25
For directi 1 sub only ie 50
so score should be 50
The latter substitution costs
The latter substitution costs 2 points = 25, not 1 point = 50.
Do we need to check the
Do we need to check the domain names for any other values in the name other than low case alphabets & numbers?
The second to last sentence
The second to last sentence in 'Input' tells you this.
@stephen how later
@stephen
how later substituion 2 points c & z in the same row of keyboard
They are on the same row.
They are on the same row. That isn't what it says makes it only 1 point.
is this the right way of
is this the right way of taking the i/p & givin the o/p ?
m<space>n<enter>
<blank line>
1
. [domain names]
.
.
m
<blank line>
1
. [typo domain names]
.
.
n
<blank line>
1
. [cost for regisitring each domain name]
.
.
n_ [and my program ends here]
Yeah. Also make sure that you
Yeah. Also make sure that you test your code against the test input output provided.
Hi admin, My solution is
Hi admin,
My solution is working correctly on my system.but I am getting runtime error when I submit the solution.
I tested it for many test cases and it seems to be working fine.may I know the exact error, or is it exceeding the memory limit.
You probably have some issues
You probably have some issues with the way you handle memory.
@Codechef i have tested my
No, as this is a recruitment
No, as this is a recruitment problem, we cannot give out such information.
Hi Admin, I am very new to
Hi Admin,
I am very new to this codechef. I have submitted a solution to the Domain Dilemma problem. The class name and the file name are given the same name by me ... but when i submit the solution i am getting a compilation error :
/sources/Main.java:4: class DomainDilemma is public, should be declared in a file named DomainDilemma.java public class DomainDilemma { ^ 1 error
Though my file name is DomainDilemma.java
can you please let me know why is it happening so?
Thanks
Class name should be Main.
Class name should be Main. Please read the FAQ and the Sample Solutions
Hi Admin, Is there any line
Hi Admin,
Is there any line after given "n" number of domains(required domains)?
Hi all, I solved the problem
Hi all,
I solved the problem NeedlemenWunsch algorithm. I am getting timeout solution.
1. Is it possible to get accepted solution through NeedlemenWunsch algorithm?
I optimised my code enough. Please give me a hints.
Hi all, I am waiting for your
Hi all,
I am waiting for your valuable comments.
Is it possible to get accepted solution through NeedlemenWunsch algorithm?
As mentioned many times
As mentioned many times already in the above comments, this is a recruitment problem. You will not be given hints.
wat do we mean by adjacency?
wat do we mean by adjacency? are 'h' and 'y' adjacent?
"You need to print the
"You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points."
Please help me understand the output:
for the input drect, we could transform it using any of the following ways:
a) delete any character: 5 ways
b) insert a new character anywhere: 6*36 ways (because there are 36 new characters and we could insert it in any of the 6 positions.
c) delete any two characters: C(5,2) ways
d) insert any two characters :
e) replace any two characters with their adjacent characters on a keyboard.
f) replace a single character with a non adjacent character.
So, the answer should be 50 plus log(sum of all these possibilities) which sure will be greater than 100, so , the answer should be at least 52.
Please clarify whether the answer or my understanding is flawed.
h and y are adjacent, but
h and y are adjacent, but they aren't on the same line.
It doesn't tell you to take the log of the number of ways you could transform it, but the number of domains you could transform it to. There is only one; 'direct'.
ok. thanks for the help
ok. thanks for the help
i am not able to submit a
i am not able to submit a solution. it is sayin contest_problem_id required??
Log out and login
Log out and login
Is the empty string a valid
Is the empty string a valid string that the customer can try to register? Technically the problem description does not rule this case out :)
There will be no space in the
There will be no space in the domain names, and they will consist only of a combination of lowercase alphabets from a to z and digits. The length of a domain name will be less than 31 characters.
"You need to print the
"You need to print the maximum surcharge incurred for registering a particular domain when compared with all the already registered domain names plus the log to the base 10 of the number of domain names that this domain name could be transformed to by using 1 or 2 points." If the no. of domain names that this domain name could be transformed to by using 1 or 2 points is zero (e.g. speaker and gallery in test input) then log to the base 10 of zero is I hope not something we are looking forward to.
So perhaps problem statement needs a mention of the fact that in case where there is not a possible transformation with even one registered domain, then log has to be avoided and surcharge has to be 0. I understand that test example does hint that.
Please correct me if I have misunderstood something.
I have tried two solutions for this problem, using dynamic programming that exceeds time limit and non DP solution that gives "wrong answer" although it runs successfully on my machine for all possible test cases that I can imagine. Please help.
That is clear from the
That is clear from the example test cases that have been provided.
Does "time limit exceeded"
Does "time limit exceeded" mean that code ran suceessfully for all test cases and produced correct output, but did not run in time limit ? or it does not guarantee correct output for all test cases.
It means the time limit was
It means the time limit was exceeded. If it didn't finish running, how could it know whether it was correct or not?
Hi, can the admin tell
Hi,
can the admin tell whether there is an error in the format of my inputoutput or is there something wrong with the answer??
the output is correct on my compiler and its working for the sample test cases given in the problem.
Plz tell whether my solution
Plz tell whether my solution has problem in the format of inputoutput or is there problem with some testcase.
I hv tried so many times and my code is giving the correct output for any testcase in my compiler.
High quality low price,all
High quality low price,all types of High Heel Shoes , Jimmy Choo Shoes is one of classic Manolo Blahnik boots chapa gtx. can lose your weight juse by walking.Come on and try YSL Shoes now!