Demo entry 6783347

complimentary1

   

Submitted by AWright on Feb 09, 2019 at 22:38
Language: Python. Code size: 5.0 kB.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 15:29:22 2019

@author: ruier
"""

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 14:56:48 2019

@author: ruier
"""

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 12:42:26 2019

@author: ruier
"""

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Feb  8 14:38:52 2019

@author: ruier
"""
#take in inputs for the pset
stuff = raw_input().split()
numPPL = int(stuff[0])
number_majors = int(stuff[1])

n = raw_input().split()
theMajors = raw_input().split()

# Small test
#n = [1,5,3,2,4]
#theMajors = [1,2,1,2,1]
#number_majors = 2
#numPPL = 5    


######################################################################
#   Tracking Parts
#######################################################################
cryCounter = 0
invalids = 0
tupler=[]

######################################################################
 # ***calculating TOTAL inversions ***##
#######################################################################

#Count the number of inversions total possible from the given set of tenacities
def merge(left, right):
    # counter for the number of inversions
    global cryCounter

    # merge on the heads using O index    
    left_index, right_index = 0, 0
    
    # store the resulting sorted list 
    result = []
    
    # while the traversing has not reached  the end of each list
    while left_index < len(left) and right_index < len(right):
       
        # if the head of the left is smaller than the head of the right
        if left[left_index] <= right[right_index] :
            #put the head of the left into the new array first (no inversion)
            result.append(left[left_index])
            #go to next value in list
            left_index += 1
        
        # find an inversion here! when left is bigger than right, 
        # then place right in list first(invert)
        else:
            result.append(right[right_index])
            right_index += 1
            # tracking for inversions
            #cryCounter += 1
            cryCounter += (len(left) - left_index)

    result += left[left_index:]
    result += right[right_index:]
    return result

def merge_sort(array):
#def merge_sort(array,numPPL):

    if len(array) <= 1:  # base case
        return array

    # divide array in half and do inversion check 
    #TODO: CHANGE THIS TO numPPL
    half = len(array) // 2
    left = merge_sort(array[:half])
    right = merge_sort(array[half:])
    

    return merge(left, right)

######################################################################
 # *** Calucluating INVALID inversions ***
#######################################################################
 
# count the number of invalid inversions in a subset
def mergeInvalid(left, right):
    global invalids
    
    left_index, right_index = 0, 0
    result = []
    while left_index < len(left) and right_index < len(right):
       

        if left[left_index] <= right[right_index] :
            result.append(left[left_index])
            left_index += 1
        
        # find an inversion
        else:
            result.append(right[right_index])
            right_index += 1
            
            # tracking swaps for inversions
            invalids += (len(left) - left_index)

    result += left[left_index:]
    result += right[right_index:]
    return result, invalids

def merge_sortINVALIDS(array):
    if len(array) <= 1:  # base case
        return array

    # divide array in half and do inversion check  
    half = len(array) // 2
    left = merge_sort(array[:half])
    right = merge_sort(array[half:])
    
    return mergeInvalid(left, right)

def invalidchecker(array, majors, number_majors, numPPL):
    
    tenacities = array
    
    # track invalid merges
    invalidMerges = 0 
    
    # make the list of list for majors 
    majorListofList= [[] for i in range(number_majors)]

    # seperate tenacities into their majors--  O(n) time
    for k in range(numPPL):   
    # index to the major list and put the tenacity into their major list
        majorListofList[int(majors[k])-1].append(tenacities[k])
    
    #Count invalids per list of list 
    for p in range(number_majors):
        dummie, doneCountingInvalids = merge_sortINVALIDS(majorListofList[p])
        invalidMerges = invalidMerges + doneCountingInvalids
    
    return invalidMerges
        
        
##############################################################
    #**STANDARD OUTPUT***
##############################################################

# calling functions to calculate stuff on the script
    
dummyHelper  = merge_sort(n)
invalidThings = invalidchecker(n, theMajors, number_majors, numPPL) #correct
answer =  cryCounter - invalidThings
print(answer)



#-----THROW AWAYS-----

#print ("crycounter:" ,  cryCounter)
#print("invalids:", invalidThings)
#check3= mergeinvalid()
#z3 = merge(n,m)

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).