4/10-4/24 Solutions

A - Special Permutation

• Indexes can’t match element, so just rotate the entire array by 1

B - Unique Bid Auction

• Keep track of number and index in pairs and then sort the array
• Numbers that only appear once won’t have adjacent numbers that are the same, so just iterate through

C - Sequence Transformation

• Get rid of duplicates since duplicates don’t matter
• Also able to get rid of the last element
• Then keep track of the number of occurrences of each element
• Answer is the minimum number of gaps, which is equal to the number of occurrences of an element
• Need to add 1 if the element isn’t the first one

​

//There is a variable num that was not needed oops

D - Number into Sequence

• Prime factorize
• a_i is a factor of a_i+1, and since we want the longest sequence, we choose the prime number with the largest exponent as the base sequence
• Stick the extra factors at the end of the sequence to make it work

E - Number of Simple Paths

• There is exactly 1 cycle
• Casework on the number of simple paths that include edges on part of the cycle or not
• Case 1: No edges on cycle
• Think of the graph as a cycle with trees rooted at each vertice of the cycle
• In a tree with k vertices, there are kc2 simple paths
• Case 2: There are edges on the cycle
• Pick 1 vertex on one of the trees and 1 vertex that is not on aforementioned tree
• There are 2 simple paths per pair of vertices due to needing to travel over the cycle
• Implementation: Find vertices on the cycle, compute the size of each tree rooted at each vertex on the cycle, then do math !!!

E - Solution

F - Array Partition

• So, let a = max(1, x) = min(x + 1, x + y) = max(x + y + 1, n)
• Imagine if we increase a from 1 -> n
• And we maintain a set of all things < a, all things > a, and then process the indices = a to see if we can find such a partition
• From here you just work out some cases