LOC July2017 - Editorial (UnOfficial)

editorial
, ,
1

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:

  1. Use simple inequality method and solve this quadratic as i(i+1)/2 <= m => i^2+i-2m <= 0 ; You can follow my solution here.

  2. Second approach can be using binary search over [1,10^18] for n. Assume you answer is n (mid value in range) then simply calculate n*(n+1)/2 if it’s less than m then move lower pointer if greater then move upper pointer, then choose mid point again, until lower and upper value are equal are equal.

    lower = 1  
upper = 10^18
mid = None
while(upper - lower > 1):
    mid = (lower+upper)/2
    if mid*(mid+1)/2 < m:
        lower = mid 
    elif mid*(mid+1)/2 > m:
        upper = mid
    else:
        break
print mid

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.

Problem 2: At The End SCHAR

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:

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

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 answer would be equal to cost of last element in string.

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

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 2: At The End SCHAR

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

2 Likes
2

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 at-least 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 in-range 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.

  1. Let’s pick first special node and perform a BFS on it till minDisTillNow depth.
  2. If we find any special node before minDisTillNow depth then we would update minDisTillNow variable.
  3. Repeat these steps on all special nodes.

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:

  1. We find special node before n/2 (then on next special node iteration bfs will end before n/2 depth)
  2. We find special node after n/2 (It implies that all other special nodes lie after n/2 nodes from this special node then for next special node bfs again will find a special node in depth <= n/2)

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.

1 Like
3

Your solution is not correct.
1. You are using dfs to count instead of bfs.
2. You are not considering the case of a single don.
There may be other bugs. Even if you fix them your solution is still \mathcal{O}(n^2). I have discussed this here.

4

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

5

Yup… I should have considered single don case… I will update that part of answer… :slight_smile:

6

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