Greedy algorithm is described as an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. Thus, it is always interesting to find a problem, which can be solved with a greedy algorithm – mainly because one does not need an advanced data structure or data structure of data structures for it. The codeforces problem Platform Jumping could be solved with a greedy algorithm quite nicely.
The problem could be defined in short like this:
You stay on a river with a given width. There are given numbers of with different size platforms, which could be moved before the jump without changing their initial order. The max length of jump is given as well. The output is consisting of printing YES, if it is possible to cross the river and a position of the platforms, as they are put in order to facilitate the passing. The position of the platforms is printed as their sequential number. E.g., on the picture below, the output should look like this:
|
1 2 |
YES 0 1 0 2 2 0 3 |
The solution looks like “Greedy” could be implemented in the following way – put the platforms exactly in such a way, that they facilitate the maximum jump. If it is possible to reach the opposite bank of the river – then there is a solution. In the code, the decision, whether there is a possible solution is taken in the following lines:
|
1 2 |
max_length = max_jump * (number_of_platforms + 1) + platform_size_total if max_length >= width_of_river: |
Once there is a way to pass through, the greedy algorithm continues – it says that all the jumps should be of equal size, but 1. Thus, it will be easy to print the solution.
|
1 2 |
minimum_jumps_count = total_jump_length_needed // max_jump smallest_jump = total_jump_length_needed % max_jump |
Once the number of jumps and their size is known, “feeding” the data into a list is quite straight forward, writing “0” for the “water” and platform_counter for the consecutive platform units:
|
1 2 3 4 5 6 7 8 9 10 11 |
while (minimum_jumps_count > 0): if (minimum_jumps_count == 1) and (smallest_jump != 0): jumping_size = [0] * smallest_jump else: jumping_size = [0] * max_jump result_list.extend(jumping_size) if platform_counter < number_of_platforms: platform_needed = [platform_counter + 1] * line_2[platform_counter] result_list.extend(platform_needed) platform_counter += 1 minimum_jumps_count -= 1 |
The whole solution is present here:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import math def main(): line_1 = list(map(int,input().split())) line_2 = list(map(int,input().split())) width_of_river = line_1[0] number_of_platforms = line_1[1] max_jump = line_1[2] - 1 platform_size_total = sum(line_2) max_length = max_jump * (number_of_platforms + 1) + platform_size_total if max_length >= width_of_river: total_jump_length_needed = width_of_river - platform_size_total if max_jump > 0: minimum_jumps_count = total_jump_length_needed // max_jump smallest_jump = total_jump_length_needed % max_jump else: minimum_jumps_count = 0 smallest_jump = 0 if smallest_jump != 0: minimum_jumps_count += 1 result_list = [] platform_counter = 0 while (minimum_jumps_count > 0): if (minimum_jumps_count == 1) and (smallest_jump != 0): jumping_size = [0] * smallest_jump else: jumping_size = [0] * max_jump result_list.extend(jumping_size) if platform_counter < number_of_platforms: platform_needed = [platform_counter + 1] * line_2[platform_counter] result_list.extend(platform_needed) platform_counter += 1 minimum_jumps_count -= 1 while(platform_counter < number_of_platforms): platform_needed = [platform_counter+1] * line_2[platform_counter] result_list.extend(platform_needed) platform_counter += 1 result = " ".join(str(number) for number in result_list) print("YES") print(result) else: print("NO") if __name__== "__main__": main() |
That’s all folks!