Domain Dilemma

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

@Amol No.

We use this problem for recruitment purposes and as such we can't help you with this one :(

The problem doesn't say it is 1 point just if both characters are on the same line. Read it again :)

The latter case.

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.

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 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 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 re-read the problem statement. I think you are not interpreting it correctly

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 re-read the problem statement. You are not interpreting it correctly.

"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 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 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 the test case that resulted in failure.

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 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 question too?

"where can I see the compile error? The yellow triangle is not clickable.."

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 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 compiler version...

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.

What you have written in bold seems right.

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 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?

Input:
6 7

google
yahoo
rediff
rediffmail
direct
directi

direct
gallery
speaker
yahooo
gopgle
drect
direzti

Output:
-1
0
0
50
50
50.3010299957
25

Please reply asap

Read the section of the problem titled 'Output'.

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 integral part only?

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 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 code runs when you use it.

@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 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, 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 2-3 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 problem so we can't provide any specific help as such. :(

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 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 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, other than:

Insertion                1

Deletion                1

Replacement(adj)            1

Replacement(n.adj)            2

Insertion-Insertion            2

Insertion-Deletion            2

Insertion-Replacement(adj)        2

Deletion-Insertion            2

Deletion-Deletion            2

Deletion-Replacement(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 the last test case-direzti

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 2 points = 25, not 1 point = 50.

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 in 'Input' tells you this.

@stephen

how later substituion 2 points c & z in the same row of keyboard

They are on the same row. That isn't what it says makes it only 1 point.

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 test your code against the test input output provided.

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 with the way you handle memory.

No, as this is a recruitment problem, we cannot give out such information.

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. Please read the FAQ and the Sample Solutions

Hi Admin,

Is there any line after given "n" number of domains(required domains)?

Hi all,

I solved the problem Needlemen-Wunsch algorithm. I am getting time-out solution.

1. Is it possible to get accepted solution through Needlemen-Wunsch algorithm?

I optimised my code enough. Please give me a hints.

Hi all,

I am waiting for your valuable comments.

Is it possible to get accepted solution through Needlemen-Wunsch algorithm?

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? are 'h' and 'y' adjacent?

"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 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

i am not able to submit a solution. it is sayin contest_problem_id required??

Log out and login

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 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 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 example test cases that have been provided.

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 exceeded. If it didn't finish running, how could it know whether it was correct or not?

Hi,

can the admin tell whether there is an error in the format of my input-output 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 has problem in the format of input-output or is there problem with some test-case.

I hv tried so many times and my code is giving the correct output for any test-case in my compiler.

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!