×

# FORGETPW - Editorial

Author: Gedi Zheng
Editorialist: Praveen Dhinwa

Simple

# PREREQUISITES:

processing of strings and arrays.

# PROBLEM:

Given a string s, You have to replace some characters of it by a predefined mapping. After application of the mapping, it is guaranteed that you can read the string as a real number in base 10 notation. For a given number, you need to find its shortest notation. Please Have a look at explanation section to understand the definition of shortest notation.

# EXPLANATION

Lets take some cases to understand what shortest notation of a real number means.

• For 5.50, Last 0 is irrelevant. Shortest representation of it will be 5.5.
• Similarly for 5.00, it will be 5.
• For 00.5 it will be .5
• For 00.00500 it will be .005
• For 0000 it will be 0
• For 500 it will be 500
• For 00500 it will be 500

Now let us divide the situation into two cases.

• If the number contains decimal mark.

• Remove the starting few zero digits until we get a non zero digit (ie starting irrelevant digits).
eg.
In the case of 05, we need to remove starting 0 only. Its shortest representation will be 5
In the case of 0.5, we need to remove starting 0 only. Its shortest representation will be .5

• Find the point of occurrence of decimal mark, Remove the last irrelevant digits (zero digits) occurring after the decimal.
eg.
- If we are left with cases like 5.5550, then we need to remove the last zeros, So shortest representation will be 5.555

• When the decimal is itself irrelevant, then we will remove the decimal too. You can see that decimal will be irrelevant if your number doesn't contain any relevant digit after the decimal point. eg.
- In case of 5.00, We will remove both the zeros and decimal. Its shortest representation will be 5
- In case of 5., We will remove the decimal. Its shortest representation will be 5

• If the number does not contain decimal mark.

• Remove the starting irrelevant digits. eg 0055500 will become 555000.
• Note that lase zeros in this case are always relevant, You can not convert 550 to 55.
• Special case: You need to take care of the case when the number is all 0's. Answer in that case will be a single 0.

Few Tricky Test Cases

• Shortest representation for 0.00, .00, 0., 000, ., will be just a single 0
• Shortest representation for 0, 00, 0(repeated x times) will be just a single 0
• Shortest representation for 500.0, 500 will be 500
• Shortest representation for 0.5, 00.50 will be .5

Complexity:
O(N), You just need to check above given conditions. You just need constant amount of passes over the string s.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

1

did the test cases include many mappings to '.' ??

(17 Jun '14, 11:25)

http://www.codechef.com/viewsolution/4102031 please any one find error in my code it runs on all expected test cases but still get wrong answer.....

(18 Jun '14, 17:46)

I have checked all the test cases. but i am still not able to get successful submission. http://www.codechef.com/viewsolution/5135021

(12 Oct '14, 22:59)

 8 @ praveen dhinwa,How one would know answer for '.' and '000.000' is 0 I was thinking that answer should be nothing but string should not be empty so this should not be the test case...(and I thought my codes were BAD!!!hehehehe ROFLMAO!!! )  P.S. in the question, there was a statement:"If the number contains only non-zero fractional part, the integral part should be omitted." what i meant: e.g. 123.5=.5 @ praveen dhinwa,May i ask why i shouldn't mean this? (FROM YOUR STATEMENT, 123.5=.5 IS CORRECT(i know it is weird!!)) And I was astonished why no one pointed this :( So, please don't write such misleading statements!!!  answered 16 Jun '14, 17:35 336●2●11●19 accept rate: 9% 1 Shortest representation of 000.000 should be 0. Empty string can not be a valid representation. (17 Jun '14, 12:29) and it was a decimal number ultimately.. (17 Jun '14, 16:48) sanzzzay2★ The question says shortest representation for 0.5 is .5 and for 5.0 it is 5. The question didn't mention about any order that we have to follow... So keeping both things in mind how can shortest representation of 0.0 be 0 (17 Jun '14, 17:38) @rudra_nitpsarraf ,No one mentioned it because "only" is written i.e, only factional part is present with no integral part... they also showed it using leading examples {(0.5=.5) and (5.0=5)}... (18 Jun '14, 20:57) @ PARTNER( :) ),If the number contains "only" non-zero fractional part, the integral part should be omitted." Then THAT "ONLY" itself means that there will be no integral part...isn't it??!!and if there is no integral part then what is the need of stating to delete integral part!!! (19 Jun '14, 12:24)
 1 I got the expected output for all the test cases given here.still i got wrong answer repeatedly. somebody plz help me out http://www.codechef.com/viewsolution/4057067 count1 and count2 denotes the number of digits to be removed from left side and right side respectively answered 16 Jun '14, 15:53 505●2●3●11 accept rate: 10% @minato_namikaz: 1 0 00. the o/p should be "0". ur code prints '.' - it is not a valid decimal number.. (17 Jun '14, 18:47)
 1 My solution is giving right answer for all the corner cases http://www.codechef.com/viewsolution/4099745 Can any one tell me why I was getting a WA. Any help would be appreciated. answered 16 Jun '14, 17:32 16●2 accept rate: 0% 1 1 k l books not working for this test case, your code (17 Jun '14, 00:02) @brobear1995 1 1 k l Where is the encrypted string? (17 Jun '14, 19:25) 4 @brobear1995 okay i understood that encrypted string is books. but it was clearly mentioned in the problem "After all the character replacements, the string is guaranteed to be a positive decimal number." So as far as I understood, Test cases should be such that, after replacements it will be giving a decimal number. Please correct me if i'm wrong. (17 Jun '14, 23:38) 1 This should return 333, right? http://ideone.com/V5PZ7B (19 Jun '14, 22:07) @betlista: Thanks! will correct it now! (21 Jun '14, 22:07) Yeah, just as @codename007 said, the statement stated that the number will be positive. I am quite certain, 0000.0000 or 0 is not a positive number. Right? (24 Jun '14, 13:16) showing 5 of 6 show all
 1 http://www.codechef.com/viewsolution/4046876 hey, guyz .. i am new here .. my solution is giving right answer for every test case but still WA . plzz can any one tell me my mistake or test case which i am missing .. . please help me friends . answered 18 Jun '14, 18:21 1★nikunj08 16●1 accept rate: 0%
 1 All the sample test cases are passing. Also the corner case of ".". However it is still giving wrong answer. Could somebody help? http://www.codechef.com/viewsolution/4108137 answered 19 Jun '14, 08:47 16 accept rate: 0%
 0 http://www.codechef.com/viewsolution/4105633 I was getting TLE. Where did my solution lose efficiency? Any help would be highly appreciated. answered 16 Jun '14, 15:31 1 accept rate: 0% @ar7thecoder you could have wrote it better. you are calculating leading and trailing zeroes for every string element which will give you a TLE. you can first decrypt the string and then calculate leading and trailing zeroes for the whole decrypted string. hope you get it now :) (16 Jun '14, 15:41)
 0 hi i got the expected output as above mentioned but still showed my answer as WA . Can you please help me with this and let me know which test case it was not woking . Any help is appreciated . http://www.codechef.com/viewsolution/4073838 answered 16 Jun '14, 16:19 2★anisdube 16●1 accept rate: 0% @dpraveen can u please check for which test cases , it is not working . i m not able to debug any further . (18 Jun '14, 23:37) anisdube2★
 0 http://www.codechef.com/viewsolution/4099249 WA anyone tell me how to correct error . answered 16 Jun '14, 16:22 2★rkm123 1●1 accept rate: 0% @rkm123: Ur program works fine when there is only 1 test case.. but when 2 or more are given.. the results are wrong. 2 3 0 . . 9 5 0 95.0 0 01800 try the above one.... You will understand where you went wrong :) (17 Jun '14, 18:58)
 0 I was continuously getting SEGABRT error for my answer.What may be the cause?In FAQ section,they say it may be occurring because STL elements are using too much memory.[I hadn't used any assert statement.] answered 16 Jun '14, 16:25 2★tj2807 1 accept rate: 0% i think your case is not covering for the test case 000000000000 or 00000.000 (17 Jun '14, 17:10) sanzzzay2★
 0 Plz help..always getting WA. Tried Several test cases.:( http://www.codechef.com/viewsolution/4106140 answered 16 Jun '14, 17:00 0●2 accept rate: 0% 1 2 e 9 i 8 8 0 ei for this test case your answer outputs 57 it should be 98. also it gives WA for many of the test cases. Try a bit more, you can get it correct. (24 Jun '14, 14:12)
 0 What whould hav been optimal way for replacement avoiding multiple replacements in the string answered 16 Jun '14, 17:02 16●2 accept rate: 0% just after one replacement flag them like for str[i] u have done replacement then take another bool array foo[100000] and at foo[i] make it equal to 1 and at the end of the loop again initialise all elements of array foo = 0; (17 Jun '14, 17:13) sanzzzay2★
 0 http://www.codechef.com/viewsolution/4106125 TLE....someone please help me out of this.i could not find out..and really want to know where am i crossing time bounds answered 16 Jun '14, 17:29 1 accept rate: 0% 1 In this line of your code(this can be a problem if your logic is correct..i haven't checked yet..maybe there can be any other reason) for(i=0;i
 0 Can anybody help me why i got a TLE in this code? I did the mapping using an array. And while decryption, i kept a track of left-most-non-zero-digit, decimal-point-occurrence and right-most-non-zero-digit. And later according to cases, displayed the output. Why does it cause a TLE? http://www.codechef.com/viewsolution/4090668 How was it inefficient? Thank you. answered 16 Jun '14, 17:36 2★siddv29 1●1●2●4 accept rate: 0%
 0 @siddv29 I guess you are using too many if statments for comparison resulting into TLE.The question doesn't require too many comparisons. answered 16 Jun '14, 17:49 0●2 accept rate: 0%
 0 Getting the right output for every testcase given here but still 'Wrong Answer'.Please help: http://www.codechef.com/viewsolution/4106245 answered 16 Jun '14, 18:08 1 accept rate: 0% 1 you have not used newline in printf as"\n" like for printf("0") u have to write like printf("0\n") (17 Jun '14, 17:19) sanzzzay2★
 0 http://www.codechef.com/viewsolution/4057659.. giving correct for test and tricky cases also http://ideone.com/4EA9kD but still wrong answer.. can some1 help answered 16 Jun '14, 22:09 2★ab9999 1●1 accept rate: 0% what is your output for test case 1: 0 case 2 : 000000000000000000000 (17 Jun '14, 17:26) sanzzzay2★ its gives 0.. gives correct for tricky and normal tests.. the tested program is up on ideone link provided (18 Jun '14, 00:16) ab99992★ it is showing runtime error in ideone see here http://ideone.com/zHklFb (18 Jun '14, 00:35) sanzzzay2★ if u give 'space' instead of n.. it fails.. how should i correct it? (19 Jun '14, 19:54) ab99992★ 0 ≤ N ≤ 94 this constraint is given and u have used char x[30],y[30];that means to accomodate max 95 char u need array of atleast 95 size (21 Jun '14, 10:53) sanzzzay2★
 0 Can someone please tell me why I am getting a TLE? I have spent hours on this question but couldn't do it.. It clears all the tricky cases too btw http://www.codechef.com/viewsolution/4099816 answered 17 Jun '14, 01:25 2★parash93 1●2 accept rate: 0%
 0 http://www.codechef.com/viewplaintext/4064994 Hey Guys, I was getting TLE for the above solution, can someone tell what was wrong? Help would really be appreciated. Thank You answered 17 Jun '14, 09:57 2★vgshetty 1●1●1●2 accept rate: 0%
 0 A small correction, 0. and . themselves hold no meaning, as the question itself suggests that After all the character replacements, the string is guaranteed to be a positive decimal number. answered 17 Jun '14, 13:17 2★wiseboy 129●1●10 accept rate: 0%
 0 my all test cases are working properly and have checked each and every possibility of test case that can be possible but it is still showing wrong answer. Here is my code. please someone go through it and help me out. #include #include int main() { int t,n,i,j,a,k,e,d,flag,flag1,b; char s[1000001],c[127],p[127],m[1000001]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i'0' && flag==0) { flag=1; j=i; } if(s[i-1]>'0' && s[i]=='0') k=i-1; else if(s[i-1]>'0' && s[i]=='\0') k=i; if(s[i]=='.' && flag==0) { flag1=0; e=i; } if(s[i]=='.' && flag==1) { d=i; flag1=1; } } if(flag1==2) { for(i=j;id) for(i=j;i<=k;i++) m[i-j]=s[i]; else for(i=j;i
 0 Check this....It works perfect. Give all the required solution. But give wrong ans. http://www.codechef.com/viewsolution/4065063 answered 17 Jun '14, 19:52 3★srswain2 139●5●6●12 accept rate: 0% check this. its correct...but give WA in codechef (21 Jun '14, 11:54) srswain23★ check your code here http://ideone.com/gXgNOa dont you think output of string 001800 should be 1800 ....:) (24 Jun '14, 15:14) grvana1★
 0 I am getting Runtime error for my java code. Can anybody help me with this? http://www.codechef.com/viewsolution/4044062 answered 17 Jun '14, 20:39 1 accept rate: 0%
 0 http://www.codechef.com/viewsolution/4110336 Can you please tell me for what case does this solution fail because it passes all the tricky cases mentioned here. Thanks in advance. answered 17 Jun '14, 22:05 2★scrooge 1 accept rate: 0% what are you getting for test case 00.00100 ? once try to check it (17 Jun '14, 22:13) sanzzzay2★ I am getting .001 only...... You can check on this: http://ideone.com/EyaibO (18 Jun '14, 14:52) scrooge2★ http://ideone.com/ZtEEzT it is showing runtime error .. (18 Jun '14, 15:10) sanzzzay2★ It will show runtime error because you have to enter N not the actual string after number of test cases. (19 Jun '14, 10:26) scrooge2★
 0 we can also used linked list for removing 0 answered 18 Jun '14, 01:24 1 accept rate: 0%
 0 Hi, My solution is http://www.codechef.com/viewsolution/4079595.My solution passed all the testcases successfully. Can you please help me to find the error with my solution. answered 18 Jun '14, 14:59 2★rajes42 1 accept rate: 0% try for n=0 and s="000000000" you have not handled this case. It should give answer as 0 try to work on this case too. good luck..!!! (19 Jun '14, 17:47)
 0 hi...I usually code in java..and I referred to the Editorialist's solution for this problem. With all due respect, I think there is one case where the output's not valid... Input: 1 1 z . 343z.89 Output: 343..89 Well, is it or is it not a valid output ? P.S. : No disrespect to anyone considering I'm just a newbie. answered 18 Jun '14, 15:52 2★aadya 1●1 accept rate: 0% the input itself is invalid!!! (18 Jun '14, 16:03) kunal3614★ The constraint actually states : " All characters in S and ci may be any ASCII printable character except space and pi is a digit ("0" - "9") or a decimal point "." "....I'm confused. How's the input invalid ? Pls elaborate. (18 Jun '14, 16:34) aadya2★ 1 "After all the character replacements, the string is guaranteed to be a positive decimal number" (18 Jun '14, 19:13) kunal3614★
 0 Why does this get tle? FORGETPW my solution answered 18 Jun '14, 19:29 161●1●4 accept rate: 20% I not have much knowledge of java but I think u are using s.length in loop condition so It increse your complexity to O(s.length^2). so separate calculate s.length and store in local variable and use as condition. For tle may be anY other reason..... (18 Jun '14, 20:16) Thanks for answering but as far as I know the length function of a java string is O(1) because java's string class stores the length as a field. (18 Jun '14, 21:25)
 0 Is there any way to find out which test case a solution failed on? This was a pretty straight forward implementation but it got WA. http://www.codechef.com/viewsolution/4081801 answered 19 Jun '14, 01:54 3★mikkanu 1●1 accept rate: 0% try for 4 different cases which are mainly important n=0 s=0.0 , n=0 s=00000 , n=0 s=0000.120030000 and n=0 s=0000120000.0000 Still you want any case then try for '.' only good luck..!!! (19 Jun '14, 17:52) @pmbhumkar - I'm getting expected result on all those tests: 0, 0, .12003, 0 Any other suggestions? It would really help to see exactly which test cases the code failed on. (19 Jun '14, 21:11) mikkanu3★ Same situation here. Got 0, 0, .12003, 120000 and 0.But still gives wrong answer in system test. (20 Jun '14, 08:04)
 0 Please help.Tried every possible case mentioned here.Still getting WA. http://www.codechef.com/viewsolution/4114405 https://ideone.com/Em8m9I answered 19 Jun '14, 03:22 15●3 accept rate: 0% Your code has the same problem. http://discuss.codechef.com/questions/45391/forgot-password-input-test-cases is the answer that i have posted. Unfortunately you have down-voted my answer for no reason :( (21 Jun '14, 08:56) bipin23★
 0 this is my solution. can anybody tell me what's wrong with this solution. it passed all tricky test cases but still showing wrong answer. http://www.codechef.com/viewsolution/4119925 answered 20 Jun '14, 22:37 1 accept rate: 0%
 0 My code works fine for all the input cases, I also tried my code with the tricky cases mentioned in the editorial but i am still getting WA. Can anyone please explain to me what the problem is. Code answered 21 Jun '14, 01:55 45●3 accept rate: 0% @dpraveen ♦♦ could you please help me here......thanxxx.. (23 Jun '14, 02:32) 1 check your code http://ideone.com/vwfLid output should be 100 earlier i was also doing the same mistake....@sanzzzay pointed it out (24 Jun '14, 15:20) grvana1★ @grvana for your help...i corrected the mistake you pointed out...but there still seems to be some prob as the code still gives WA on submitting....Revised code http://www.codechef.com/viewsolution/4139033 (24 Jun '14, 22:29)
 0 I'm getting a correct answer for every corner case, for every cases I read in the comments, yet getting a WA. Code Can someone help me to tell where is it that I am going wrong? answered 22 Jun '14, 10:52 1 accept rate: 0%
 0 getting WA after trying several test cases... http://www.codechef.com/viewsolution/4102057 ...can someone help..!! answered 22 Jun '14, 15:13 1●1 accept rate: 0%
 0 I am getting all test cases correct on my system still it is giving wrong answer ..please suggest what i am doing wrong.. http://www.codechef.com/viewsolution/4124811 answered 22 Jun '14, 16:37 1●1●1●5 accept rate: 0% check your code here http://ideone.com/aPoddj dont u think output should be 100 instead of 0 (24 Jun '14, 14:32) grvana1★
 0 I'm just doing these for practice, but its really hard to call "." a "positive decimal number". Arguably its also hard to call "0" and "0.0" as a "positive decimal number" ("non-negative decimal number" would have been more appropriate), but I don't think that "." passes as a "positive decimal number" in any culture I'm aware of. answered 23 Jun '14, 00:40 121●5 accept rate: 0%
 0 plz can anyone point out the error... http://ideone.com/5l8Jy2 i spent lot of time over it..(>_<) answered 23 Jun '14, 20:02 1★grvana 152●2●12 accept rate: 5%
 0 @m1sterzer0 after reading your answer above...out of curiosity i checked your submission for the problem.... i dont know why its giving the wrong output instead of being accepted as right answer http://ideone.com/z1YyRR answered 24 Jun '14, 15:51 1★grvana 152●2●12 accept rate: 5%
 0 http://www.codechef.com/viewsolution/3999376 This is my solution it is passing every case mentioned in the problem and every corner case as well. What is the problem here? answered 25 Jun '14, 20:20 0●1 accept rate: 0%

# include < string>

using namespace std;

int main() {

int n;
cin>>n;
string  enPass,Pass;
while(n>0)
{
int r,counter=0;
cin>>r;   //  no. of rules.
char c[r],p[r];
for(int i=0;i<r;i++)
{
cin>>c[i]>>p[i];  // taking each rule as input
}
cin>>enPass;  // taking encrypted password as input
Pass = enPass;
for(int j=0;j<enPass.size();j++)
{
for(int s=0;s<r;s++)
{
if(c[s] == enPass[j])
{
Pass[j] = p[s];
}

}
}

int str_Size = Pass.size();
for(int q = str_Size-1; q >= 0; q--)
{
if(Pass[q] == '0') Pass.erase(q);
else if(Pass[q] == '.')
{
Pass.erase(q);
break;
}
else break;
}

for(int t=0;t<str_Size;t++)
{
if(Pass[t] == '0') counter++;
else break;
}
Pass.erase(0,counter);
cout<<Pass<<"\n";
n--;
}
return 0;


}

1
accept rate: 0%

 0 I cracked this after trying different print techniques for the output. First, I print the op as separate characters(i.e every single S[i] using loop). This didn't work out. Secondly, I print the op as integers(using S[i]-'0' except for '.'). This didn't work out as well. Finally after going through the solution of @pummy02(https://www.codechef.com/viewsolution/7934954) I got a hint. I assigned the 'last+1'th char as null and printed the op as a string. This worked out! answered 28 Sep '15, 22:02 2★vivekram 31●3 accept rate: 0%
 0 Can somebody help me with this solution, this gives correct answer for all the given tc but on submission gives wa. https://www.codechef.com/viewsolution/14346300 answered 26 Jun '17, 15:18 41●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,191
×968
×47
×21

question asked: 16 Jun '14, 15:01

question was seen: 5,911 times

last updated: 26 Jun '17, 15:18