From last couple of days I am seeing that people are asking same questions related to LOC July2017 again and again. I have answered all of them here or there, So Here I am just attaching link of questions where I have already answered them because official editorial is taking too much time. Hope It will help people: Problem 1: Boss and his Brother BOSSLOSS There are two ways from which this problem can be approached:
I am not sure if this code is taking some corner cases.. But it's pretty much gist of what I was saying in 2nd approach. Here I am using DP to solve this problem. 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:
If same element has not come till now then he can only come from last element so cost would be: costMap[ s[i1] ] + abs( ord(s[i])  ord(s[i1]) ), same as 1 and hence answer would be equal to cost of last element in string.
Problem 3: Amit And Nitin AMITNITI Just click on above link and find my solution in answers. Problem 4: Region of Calabria MAAFIA (I have added another explanation below in answers for this problem) Problem 5: Magical Cave And Horse CAVECOIN Just click on above link and find my solution in answers. Here are my codes for different problems, if it helps: Problem 1: Boss and his Brother BOSSLOSS Problem 3: Amit And Nitin AMITNITI Problem 4: Region of Calabria MAAFIA Problem 5: Magical Cave And Horse CAVECOIN This solution is for 50 Points, for explanation for 100 Points you can follow this link where I have tried to explain it. You have any doubt regarding above problems and need an explanation for same, You can ask them below.. :) asked 02 Aug '17, 01:50

Problem 4: Region of Calabria MAAFIA Question: Given Graph with n nodes, m paths and k special nodes. You have to find out number of nodes whose distance from atleast one special node is less than or equal to radius, where radius should be such that not a single node would belong to two special nodes. Answer: It's clear that if we know radius(which would be equal for all special nodes) then to find number of inrange nodes can be find out by just using BFS on each special node till depth of radius in O(n), because of radius will not let two bfs overlap on different special nodes. Now, Radius would be just minimum of shortest distance between two special nodes divide by 2. To find radius(minimum of shortest distance between two special nodes) we can follow these steps: Let's say minDisTillNow stores value of minimum distance that we have found till now.
At first we think that it's O(n^2) but it would be of O(nLog(n)), because we are terminating our search at minDisTillNow. This logic can be further explained using n/2 logic, as by taking two cases:
Hence at every iteration we are reducing depth by n/2 so Complexity would be O(nLog(n)). Hope this answer would help you guys to understand Logic and Time Complexity of answer. You can find my answer here. EDIT: This is actually O(n^2). Thanks @meooow for pointing this out with an example. Note: I found out one solution by @sai_rathan here which could complete above task in 1 sec. for test case generated by this file. answered 02 Aug '17, 02:52
Your solution is not correct.
(02 Aug '17, 04:17)
Once you know radius then it does not matter if you are doing bfs or dfs.Because distance between nodes that will come from DFS >= distance that will come from BFS.And if I am terminating DFS(not going further) at radius then nodes whose shortest distance is greater than radius will not come into picture from DFS and nodes which are coming under radius in DFS,their shortest distance would obviously be less than radius in BFS.From above logic,it's not considering wrong nodes and nodes that it's considering are not wrong so nodes found out from both methods are same. Please correct me I am Wrong
(02 Aug '17, 04:37)
Yup.. I should have considered single don case.. I will update that part of answer.. :)
(02 Aug '17, 04:51)
Yup.. It's O(n^2) solution.. Updated my answer.. But your solution is also taking indefinite time for worst case generated by this file https://ideone.com/RVcJyU . Please look into it.. :)
(02 Aug '17, 05:09)
