We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • purbanski 4 years ago+ 0 comments

    Above described solution in python:

    def solution(a):
    
        m = {}
        for i in range(len(a)):
            m[a[i]] = i 
            
        sorted_a = sorted(a)
        ret = 0
        
        for i in range(len(a)):
            if a[i] != sorted_a[i]:
                ret +=1
                
                ind_to_swap = m[ sorted_a[i] ]
                m[ a[i] ] = m[ sorted_a[i]]
                a[i],a[ind_to_swap] = sorted_a[i],a[i]
        return ret
    
    raw_input()
    a = [int(i) for i in raw_input().split(' ')]
    
    asc=solution(list(a))
    desc=solution(list(reversed(a)))
    print min(asc,desc)
    
    -51|
    ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature