===== Practices 04 ===== ===== Sliding window, prefix sum, binary search, sorts ===== import time # practices 04 # Common input format # ------------------- # (Read the tasks descriptions below before reading this paragraph.) # All tasks in practices 04 set share common data input format: # The first line contains the number of the task (1 - 5). # The second line contains the number N of lists in the input. # In tasks 1-4, 0 < N < 6. In task 5, 0 < N < 12 and N is even. # Next, there are N lines of input, each contains one input list. # Each list consists only of integers. List entries are separated by single space, # there are no other symbols on the input line . # The input always contain exactly one data set of one task. # In the evaluation system, the code is run repeatedly, each time with different input. # Solution code structure # ----------------------- # The code reads the input data, including the number of the task. # Next, it runs a function or a block of code which accepts the input data # and computes and prints the solution to it. # It is recommended to wrap the solution of each task in a separate function, # an example (not obligatory!) structure of the code # is illustrated by the contents of this file. # ================================================================================ # Task 01 ''' Importances of Local Minima A **local minimum** in a list of integers L is an item which value is smaller than the value of both of its immediate neighbours. The first and the last item in the list cannot be a local minimum, in this task. A **global maximum** of the list is an item which value is maximum in the whole list. Note that there may be more local minima and more global maxima in one list. Example: L = [10, 9, 8, 7, 10, 1, 4, 9, 7, 8]. Local minima are 7, 1, 7, at indexes 3, 5, 8, respectively, global maxima are 10 and 10 at indexes 0, 4, respectively. The **distance** between two items in the list is equal to the absolute value of the difference of their indexes in the array. For example, the distance between two adjacent items is 1, the distance between the first and the last item in a list L is len(L)-1. An **importance** of an item in the list is its minimum distance to a global maximum. Example: L = [10, 9, 8, 7, 10, 1, 4, 9, 7, 8], the importances of particular items are [ 0, 1 2, 1, 0, 1, 2, 3, 4, 5]. The task: Compute the total value of importances of all Local minima in the list. For each given list, print the total value of importances on a separate line. If there is no Local minimum in the list, output 0. The length of each input list is at most 10000. Example Input 1 3 10 9 8 7 10 1 4 13 7 8 2 4 2 4 2 4 2 4 40 30 20 10 20 30 40 30 20 10 20 30 40 Output 7 3 6 Sentinels hint: If your solutions stores the locations of global minima in a separate list, you may add sentinels representing imaginary non-existing maxima beyond the scope of the list, far to the left and far to the right of the list. Sliding window hint: As you move through the local minima in the list you may incorporate the sliding window idea The window would slide through the list and it would contain two current global maxima between which the current local minimum is located. ''' def task01( L ): # your solution here pass ''' # ------------------------------------------------------------------------------ Task02 Qualities of Local Minima The notion of a local minimum and its importance is defined in the previous task. This task uses the same definitions. When a local minimum in a list L appears at index k, its depth is equal to the smaller of the two differences a[k-1] - a[k], a[k+1] - a[k]. Each local minimum M is associated with a tuple of three parametres: The depth of M, the importance of M, the value of M. This tuple associated with M is called quality of M. Comparison of the qualities of two local minima M1 and M2 is done be the following scheme The minimum with bigger depth has a bigger quality than the other one. When the depths M1 and M2 are equal, the minimum with the bigger importance has a bigger quality than the other one. When depths and importances of the minima are equal, the minimum with smaller value has a bigger quality than the other one. When depths, importances, and values of the minima are equal, the qualities of the minima are considered to be equal. The task: For a given list L of integers, print the list of its local minima sorted in non-descending order of their quality. When the quality of two minima is the same, the minima should appear in the output list in the same order as they appear in L. Each minimum M is printed on a separate line as a 4-tuple consisting of: index of M in L, depth of M, importance of M, value of M. The entries on a line are separated by single spaces and the line contains no other symbols. Print one empty line after the output list. Example Input 2 3 10 9 8 7 10 1 4 13 7 8 2 4 2 4 2 4 2 4 40 30 20 10 20 30 40 30 20 10 20 30 40 Output 8 1 1 7 3 1 4 7 5 3 2 1 2 2 1 2 4 2 1 2 6 2 1 2 3 10 3 10 9 10 3 10 # Note the last empty line, at the end of the output. ''' def task02( L ): # your solution here pass # ------------------------------------------------------------------------------ ''' Task 03 A **subarray** S of an array A is a slice of array A. (The term subarray is more general then the term slice used mostly in scripting languages like Python, JavaScript and other.) A subarray S of an array A is a **dense** subarray when the sum of all elements in S is bigger or equal to the half of the sum of all elements in A. The task: Find the shortest dense subarray S in input array A. Print three values: The indices of the first and the last item in S and the sum of all items in S. When there are more shortest dense subarrays in A, print the output related only to the leftmost one. The entries on a line are separated by single spaces and the line contains no other symbols. Example Input 3 3 1 0 2 0 0 0 3 4 0 1 1 2 1 3 5 7 9 2 4 6 8 10 0 0 0 39 0 41 0 Output 6 7 7 6 9 28 5 5 41 ''' def task03( L ): # your solution here pass # ------------------------------------------------------------------------------ ''' Task 04 An subarray S in array A array is loosely ascending when it contains at most one item which value is bigger then the value of its immediate successor (to the right) in S. The task: In the given array A, find the longest loosely ascending subarray. Print, on a separate line, the indices of the first and the last item in S. All values are to be printed on single line, separated by single spaces, and the line contains no other symbols. If there are more than one longest loosely ascending subarrays of A, print the output related only to the leftmost one. If there is no Loosely ascending subarray in A, print string 'None'. Example Input 4 1 12 10 8 6 4 2 1 3 7 8 9 11 Output 5 11 ''' def task04( L ): # your solution here pass # ------------------------------------------------------------------------------ # Task 05 ''' **Targets** and **shots** are points with integer coordinates on an infinite horizontal axis. We are given a list of target coordinates and a list of shot coordinates. A shot is a **hit** if the shot range contains at least half of the targets. The shot is always exactly in the middle of the shot range, the width of the shot range is maximum possible but not bigger than half of the span of the targets. The span of the targets is one plus the distance from the leftmost target to the rightmost target. A target exactly at the border of the shot range is counted as contained in the shot range. Shot quality is the number of targets in the shot range, if the shot is a hit. Otherwise, shot quality is 0. All coordinates are positive integers less than 10**6. Both input lists, of targets and of shots, are sorted in ascending order. There are no two targets with the same coordinate and no two shots with the same coordinate. Note: A shot range may be located partially outside the range of targets, For example, its left border may be at negative index. Example: Symbols 'o' represent targets, symbols '*' represent shots. 10 20 30 40 50 60 0123456789012345678901234567890123456789012345678901234567890 indexes -----o-o---------oo---o---o--o------oo----------o---oo------- targets ---*----*------*-------**------------*-----*--***------------ shots There are 12 targets and 10 shots. The span of the targets is 1+53-5 = 49. The width of the shot interval is 23. (It cannot be 24 because then the shot could not be in its middle.) Examples of some shots qualities: 10 20 30 40 50 60 0123456789012345678901234567890123456789012345678901234567890 indexes -----o-o----o--o-oo---o---o---------o-----------o---oo------- |..........*..........| 8 Shot C range and quality 8 |..........*..........| 6 Shot D range and quality 6 |..........*..........| 0 Shot E range and quality 0 |..........*..........| 0 Shot G range and quality 0 ---*----*------*-------**------------*-----*--***------------ shots A B C DE F G HIJ In the picture, only few shots and their shot ranges are depicted. The complete list of shot ranges and their qualities would be the following shot coord: 3 range coords[ -8 14 ], targets in Range: 3 , quality: 0 shot coord: 8 range coords[ -3 19 ], targets in Range: 6 , quality: 6 shot coord: 15 range coords[ 4 26 ], targets in Range: 8 , quality: 8 shot coord: 23 range coords[ 12 34 ], targets in Range: 6 , quality: 6 shot coord: 24 range coords[ 13 35 ], targets in Range: 5 , quality: 0 shot coord: 37 range coords[ 26 48 ], targets in Range: 3 , quality: 0 shot coord: 43 range coords[ 32 54 ], targets in Range: 4 , quality: 0 shot coord: 46 range coords[ 35 57 ], targets in Range: 4 , quality: 0 shot coord: 47 range coords[ 36 58 ], targets in Range: 4 , quality: 0 shot coord: 48 range coords[ 37 59 ], targets in Range: 3 , quality: 0 The task Calculate the total of all shot qualities. Print it on a separate line. The coordinates of targets and shots are presented in the input in ascending order. Hint: (It is a hint, not a cook-book recipe to follow mindlessly!) Think how the function indexOfClosestBiggerValueTo() from the lectures, based on binary search principle, may be useful when applied to the list of targets and the left border of a particular range. Would you need to apply similar reasoning and appropriately modified binary search also to the right border of the same range? May prefix sum idea help somehow a bit? Example Input 5 2 5 7 12 15 17 18 22 26 36 48 52 53 3 8 15 23 24 37 43 46 47 48 Output 20 ''' def task05( targets, shots ): # your solution here pass # * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * # I N P U T R E A D I N G taskNo = int(input()) Nlists = int(input()) inputLists = [] for k in range(Nlists): oneList = list(map(int, input().split())) inputLists.append(oneList) # * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * # P R O C E S S I N G t1 = time.time() if taskNo in [1, 2, 3, 4]: for aList in inputLists: if taskNo == 1: task01(aList) if taskNo == 2: task02(aList) if taskNo == 3: task03(aList) if taskNo == 4: task04(aList) if taskNo == 5: for i in range(0, len(inputLists), 2): # targets and shots task05(inputLists[i], inputLists[i + 1]) t2 = time.time() # print( 'time', str(t2-t1)[:5] )