MRTRAVEL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author, Tester & Editorialist: Hritik Seth

DIFFICULTY:

EASY

PREREQUISITES:

Arrays, MATH

PROBLEM:

https://www.codechef.com/problems/MRTRAVEL

EXPLANATION:

The Basic Approach for this problem was to find the number divisible by the element starting from minimum element and remove the element and it’s divisible number. So the number of times you remove the minimum element is the number of Bus passes required.

This approach would take O(n^2) time at worst and works for the problem.

SOLUTIONS:

Editorialist's Solution 
n = int(input())
cities = list(map(int, input().split()))
cities.sort()
passes = 0
for i in range(n):
    if cities[i] == 0:
        continue
    passes += 1
    t = cities[i]
    cities[i] = 0
    for j in range(i + 1, n):
        if cities[j] % t == 0:
            cities[j] = 0
print(passes)

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.

2 Likes
2

Looking at the constraints of this problem, I think O(n^2) should not work(which is working). If I was a contestant I would try it in O(nlogn) or O(nsqrt(n)) looking at the constraints and be upset after contest that we can solve it in O(n^2).

Collectively, I am saying that Constraints should show the traits of what maximum expected complexity should be. Peace.