Solutions not available for LoC July 2017 contest

general
, ,
1

The contest has already ended before an hour yet the solutions of the problems are not made available. Why?? Can anyone please provide me the solutions for the question “At the End”. Thanks in advance :slight_smile:

1 Like
2

Here is my solution:

for _ in range(input()):
    s = raw_input()
    l = len(s)
    costMap = {}
    costMap[s[0]] = 0
    for i in range(1,l):
        if not(s[i] in costMap):
            costMap[s[i]] = costMap[s[i-1]] + abs(ord(s[i])-ord(s[i-1]))
        else:
            costMap[s[i]] = min(costMap[s[i]], costMap[s[i-1]] + abs(ord(s[i])-ord(s[i-1])))

    print costMap[s[-1]]

Logic is simple, at every point person can either come from previous checkpoint or it’s similar last checkpoint. here I am iterating through string and taking minimum of both cost:

  1. Cost to come from last element = costMap[ s[i-1] ] + abs( ord(s[i]) - ord(s[i-1]) )
  2. Cost to come from similar last element, costMap[ s[i] ]
  3. If same element has not come till now then he can only come from last element so cost would be: costMap[ s[i-1] ] + abs( ord(s[i]) - ord(s[i-1]) ), same as 1

and hence would be equal to cost of last element in string.

2 Likes
3

My code: https://ideone.com/KCiiqu

Explanation: I solved it using a DP. States I have taken as the index of the string. So, dp[i] stores the cost it took to come to the ith character of the string. In my code sc[i] is a set(sc is an array of sets) where sc[i] stores the costs of reaching the indexes with the character with ascii value i(I compensated it by doing i-‘a’). For each index, you can have two options, you can either take the previous index(i-1) and add the difference of ascii values to get d[i], i.e, dp[i] = dp[i-1]+abs(s[i-1]-s[i])Or else you can take the minimum cost in the set sc[s[i]]. You need to consider both the options and consider the minimum of both. And then you get dp[n-1] as answer. Don’t forget to add the cost of s[i] to sc[s[i]]

I made it slightly more unnecessarily complex, you can just stor a normal array sc, where sc[i] is the minimum cost to reach the ith character. Update it by doing sc[s[i]] = min(sc[s[i]], dp[i]);

1 Like
4

I have also implemented the same logic using map! And getting the same output. But I don’t know why my solution was correct for only two cases. Also we can’t see the solutions yet.

Why the access is still denied?

Link to Question : At The End - SCHAR

Here is the link to my solution :
https://ideone.com/LcJ9lI

Does it have any kind of flaw??

5

I solved this ques using bfs where edges of a character can be with other characters of same type or to the neighboring left character and neighboring right character character and each time updating the cost required.You can see my solution here.