I could not figure out how to solve this question. Can someone give me some clue?
Here is my approach:-
1)create a hash table to store a number corresponding to a particular character of the string.
2)start from left and proceed right. To minimize the total value, numbers occuring earlier should have smaller value. i.e. 0,1,2,…n. Hence the first character will correspond to value 1 (it cant be 0).
3)the next distinct character should correspond to 0 to minimize value (since 0 is the minimum value in the set 0,2,3,4…)
4)from here on check for all the distinct characters that have not been hashed yet. assign them values from 2,3,4… until you encounter the end of the string. your base will be the number of distinct symbols in the string(2 if only 1 symbol is there)
Final step:- you know what value each character corresponds to and you know base. So just move from right to left and multiply each value from hash table with the corresponding power of the base.
eg:- if base is 4, and string is abc, then value is hash[c] * base^0 +hash[b] * base^1 +hash[a] * base^2
here is link to my solution
1 Like
This is my code
http://www.codechef.com/viewsolution/2552794
Not hard and just code simple as possible as we can