FORGETPW - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Gedi Zheng
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

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:

Author’s solution
Tester’s solution
Editorialist’s solution

2 Likes
2

http://www.codechef.com/viewsolution/4105633

I was getting TLE. Where did my solution lose efficiency? Any help would be highly appreciated.

3

@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 :slight_smile:

4

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

1 Like
5

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

6

http://www.codechef.com/viewsolution/4099249
WA anyone tell me how to correct error .

7

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.]

8

Plz help…always getting WA. Tried Several test cases.:frowning:
http://www.codechef.com/viewsolution/4106140

9

What whould hav been optimal way for replacement avoiding multiple replacements in the string

10

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

11

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.

12

@ 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!!!
7 Likes
13

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.

14

@siddv29 I guess you are using too many if statments for comparison resulting into TLE.The question doesn’t require too many comparisons.

15

Getting the right output for every testcase given here but still ‘Wrong Answer’.Please help: http://www.codechef.com/viewsolution/4106245

16

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

17

1 1 k l books not working for this test case, your code

18

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

19

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

20

did the test cases include many mappings to ‘.’ ??

1 Like