HKOI 2014 Senior
Given a random distributed cycle with N members, determine the number of methods to cut the cycle into two strands that, when rearranged and merged, form a cycle with consecutive labels. Solutions involve exhaustive permutation and careful observation of consecutive elements. Utilize maximum and minimum values to identify consecutive sets efficiently. Categorize cases for thorough analysis and solution refinement.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
HKOI 2014 Senior Gene Mutation 2 Problem Prepared By Gary Wong
Problem Given a random distributed cycle with N members(From 1 to N) Count the number of methods to cut the cycle into two strands, such that After rearranging each strand and merge it again, it is possible to obtain a cycle with consecutive label
Solution 1 Exhaust all possible places to perform the cut Exhaust all possible permutation of the two strands Check if the configuration fulfill the requirements Complexity = O(N^2 * N!) Score = 30%
Observation 1 After extracting a strand of DNA by exhaustion, how can we decide whether it is a valid case to be counted? If the set of elements in that strand is consecutive, then it is possible Why?
Solution 2 Exhaust all possible places to perform the cut Create a empty hash table Store the occurrence of all elements in that strand Check whether it is consecutive Tricky Case : if 1 and N have appeared in the strand, you have to be careful, why? Complexity = O(N^3) Score = 50%
Observation 2 It is too slow to create an empty hash table and run it through But I could just store the max and min element in the strand very fast! What can I make use of max and min value? If max min + 1 = number of element in the strand, then the set of element must be consecutive! Why?
Observation 3 However, not only consecutive element should be counted For example, N = 5, when we look at strand with element 1, 2, 5 The max, min value is quite meaningless But this is one of the answer too! However, it is not necessary to abandon the previous observation
Observation 3 To use the observation 2 to solve the problem, we can categorize the valid cases into two types First type : Extracting strand excluding N Second type : Extracting strand including N In terms of where the cutting is performed Each case in the first type is identical to one case in second type Our algorithm misses some cases in the second type, but each case in the first type is identical to one case in second type
Solution 3 Exhaust all possible places to perform the cut Only counting the case of first type using max, min value Complexity = O(N^2) Score = 100%
