HackerEarth - Gotta catch 'em all! Solution

HackerEarth - Gotta catch 'em all! Solution

Little Arihant has always wanted to be the best Pokemon trainer in this world. And he thinks he has achieved his goal, so he wants to quickly go and meet Professor Oak and verify this fact. But like all Pokemon trainers, he has a weird habit, too. He catches Pokemons which can go through evolution to become a better one. After roaming in the Pokeworld for days, he has finally managed to catch k such Pokemons.

The way he can make a Pokemon go through evolution is NOT by making them fight battles, but by using an evolution stone. Since he has k Pokemons, he naturally needs k evolution stones for every one of them, as well.

Now it takes little Arihant one complete day, to use the evolution stone on one Pokemon. And for each Pokemon, he knows how many days will they take to evolute after the evolution stone has been used on them.

He will go to meet Professor Oak, the very next day, once all his Pokemons have gone through evolution. He can select the order of applying evolution stones as he likes, so he wants to do it in such a way that he gets to meet Professor Oak as soon as possible!

Input Format:
The input has two lines. The first line will contain an integer k, which denotes the number of Pokemons. Then, a line with k integers follows, where the i-th integer denotes the number of days it takes for the i-th Pokemon to evolve.

Output Format:
You need to print the earliest day when little Arihant can go meet Professor Oak.

Constraints:
The days are numbered 1, 2, 3, 4, 5, 6...
1 ≤ k ≤ 10^5.
1 ≤ Number of days ≤ 10^6.

SAMPLE INPUT

2
3 1

SAMPLE OUTPUT

5 

Explanation

Here's how it happens: Day 1: He uses the evolution stone on the Pokemon which takes 3 days. Day 2: 3 days Pokemon's first day. He uses the evolution stone on the Pokemon which takes 1 day. Day 3: 3 days Pokemon's second day. 1 day Pokemon's first and final day. It goes through evolution. Day 4: 3 days Pokemon's third day. It goes through evolution. All Pokemons done with, he can go to Professor Oak, now. Day 5: He goes to Professor Oak.

Solution in Python

n = int(input())
a = list(map(int,input().split()))
a = enumerate(sorted(a,reverse=True),2)
print(max(x+y for x,y in a))

First thing we should know that, it requires a total of n+2 days for a pokemon taking n days from giving evolution stone to evolving and going to professor.

Day 1 - Giving Evolution Stone

n Days - Evolving period

Day 1 - To go to professor

Total = 1 + n + 2 = n+2

So a pokemon taking 3 days to evolve takes a total of 3+2 = 5 days.

Let's assume we have the following pokemons

a = [7, 2, 7, 3, 6, 2, 6, 2, 1]

Now one thing is obvious that we will always give evolution stone in descending order to not waste unnecessary days giving smaller evolution first.

First we will sort our list in descending order.

>>> sorted(a,reverse=True)
[7, 7, 6, 6, 3, 2, 2, 2, 1]

Days taken by each pokemon

7 +2 days
7 +2 days
6 +2 days
6 +2 days
3 +2 days
2 +2 days
2 +2 days
2 +2 days
1 +2 days

Now since only one evolution stone can given per day the first pokemon will take 7+2 days but 2nd pokemon will take 1 + 7+2 days (1 day already passed), 3rd pokemon will take 2+ 6+2 days(2 days already passed and so on.

0 days + 7 + 2 days = 7 + 2 days = 9 days
1 days + 7 + 2 days = 7 + 3 days = 10 days
2 days + 6 + 2 days = 6 + 4 days = 10 days
3 days + 6 + 2 days = 6 + 5 days = 11 days
4 days + 3 + 2 days = 3 + 6 days = 9 days
5 days + 2 + 2 days = 2 + 7 days = 9 days
6 days + 2 + 2 days = 2 + 8 days = 10 days
7 days + 2 + 2 days = 2 + 9 days = 11 days
8 days + 1 + 2 days = 1 + 10 days = 11 days

That's why we write

(enumerate(sorted(a,reverse=True),2)
>>> list(enumerate(sorted(a,reverse=True),2))
[(2, 7), (3, 7), (4, 6), (5, 6), (6, 3), (7, 2), (8, 2), (9, 2), (10, 1)]

At last we add each key value pairs.

2+7, 3+7, 4+6 etc and the maximum value is our required answer

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe