Friendly Imran - Editorial

Practice
Encoding February 2020 Finals Contest

Author: arnie8991
Tester: nutella
Editorialist: arnie8991

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Maths, Sorting, Greedy

EXPLANATION:

We have been asked to find the order of the cities that Imran should visit so that he gets to visit the maximum number of his friends in ascending order. The easiest and intuitive approach is to choose the diagonal with the biggest sum and sort number of friends that Imran has in that diagonal and then print them in the order as mentioned in the input grid. For that sake of convenience, a priority queue has been used here to sort all the diagonal elements automatically.

SOLUTIONS:

[details=“Setter’s Solution”]

import heapq

row = col = int(input())

grid = []*row 

for i in range(row):
    grid.append([int(x) for x in input().split()])

dictionary = {}

for i in range(row):
    for j in range(col):
        if i-j not in dictionary:
            dictionary[i-j] = [0,[]]
            heapq.heapify(dictionary[i-j][1])

for i in range(row):
    for j in range(col):
        dictionary[i-j][0]+=grid[i][j]
        heapq.heappush(dictionary[i-j][1],grid[i][j])

maxi = None
high = -1000
key = None
for items in dictionary:
    if dictionary[items][0]>high:
        maxi = dictionary[items][1]
        high = dictionary[items][0]
        key = items


original = []
for i in range(row):
    for j in range(col):
        if i-j == key:
            original.append([grid[i][j],i,j])

while(len(maxi)>0):
    ele = heapq.heappop(maxi)
    for items in original:
        if items[0] == ele:
            print(items[1],items[2])

[details=“Tester’s Solution”]