Transcript Document

HKOI 2012 (Senior)
Q4 - Gene Mutation
Gary Wong
For any question, please ask via
Email: [email protected]
MSN: [email protected]
Problem Statement
1
3
2
4
5
• Given a ring of N integers (range
from 1 to N), with bonds between
adjacent numbers
• One of the N bonds is cut
• Free to swap any pairs of adjacent
numbers
• Bond is formed again, and no more
bond can be broken
• Find the minimum number of swaps
to form a ring such that 1 to N are
arranged in clockwise direction
Problem Statement
• For the example in previous slide,
1
2
3
2
4
3
1
5
4
2
2
3
1
5
5
4
3
1
5
4
Statistics
•
•
•
•
Max. score: 50
No. of max: 2
Std. dev: 12.1
Mean: 5.36
• Disappointed…
Statistics
• Disappointed…
No. of contestants
20
15
10
5
0
0
5
10
15
20
25
30
35
40
45
50
Score
55
60
65
70
75
80
85
90
95 100
Solution – 30%
• N <= 8
• For each of the N cleavages, exhaust
all the possible swaps can be taken
• O(N*N!)
• Very difficult to code…
Solution – 50%
• N <= 60
• Consider a simpler problem first:
• Given a list of integers, find the
minimum number of adjacent
swaps needed to sort them in
ascending order
• E.g. {1 3 5 4 2} needs 4 swaps
• If you know bubble sort/insertion
sort, then the number of swaps used
in such sorting is exactly the
minimum!
Solution – 50%
• Even if you do not know bubble
sort/insertion sort…
• {1 3 5 4 2}
• You could also note that:
• Number of swaps needed to put
element x in correct position =
number of elements on LHS that
greater than x
• Adding up these number of swaps
is also correct!
Solution – 50%
• This simpler problem is also known
as “finding total number of inversion”
• Inversion: a pair of numbers ai and aj
in a sequence that ai > aj for i < j
• E.g. {1 3 5 4 2} has inversions {3 2},
{5 4}, {5 2} and {4 2}.
Solution – 50%
• If one of the mentioned algorithms is
used to find the number of inversions,
• Complexity: O(N2)
• Let us go back to original problem…
Solution – 50%
• When one bond is cleaved, a chain is
formed
1
3
2
4
5
• {2 1 3 5 4}
• 2 swaps needed!
• Looks similar to finding inversions!
Solution – 50%
• Do the procedure of finding
inversions for N times!
• O(N3)
• It is a WRONG algorithm!
Solution – 50%
• For the algorithm just mentioned, we
deal with following cases only:
• {2 1 3 5 4} => {1 2 3 4 5}
• {1 3 5 4 2} => {1 2 3 4 5}
•…
• {4 2 1 3 5} => {1 2 3 4 5}
• How about:
• {2 1 3 5 4} => {2 3 4 5 1}?
• {2 1 3 5 4} => {3 4 5 1 2}?
•…
Solution – 50%
• Do the procedure of finding
inversions for N2 times!
• Complexity: O(N4)
• Okay for N <= 60
• Time Limit Exceeded for N <= 300
Solution – 70%
• N <= 300
• Use a[] = {3 1 5 4 2} as example
• Consider the following table:
• a[] 3 1 5 4 2
• p[] 0 1 0 1 3
• p[i] is the number of elements on
LHS that greater than a[i]
Solution – 70%
• a[] 3 1 5 4 2
• p[] 0 1 0 1 3
• Adding up the numbers in p[] gives
you number of adjacent swaps for
{3 1 5 4 2} => {1 2 3 4 5}
• If you want to find
{3 1 5 4 2} => {5 1 2 3 4}
Equivalent to replacing 5 by 0!!
Solution – 70%
• After replacing 5 by 0, the table
changes from
• a[] 3 1 5 4 2
• p[] 0 1 0 1 3
• To
• a[] 3 1 0 4 2
• p[] 0 1 2 0 2
• Can you notice how it changes?
• p[i] is replaced by i
• All numbers on RHS of p[i] are
reduced by 1
Solution – 70%
• O(N2) to find the initial p[]
• For i: from N to 1
• O(N) to find the element i
• Replace p[] by index of i, i.e. id
• O(N) to subtract all the p[j] by 1,
where id < j <= N
• O(N) to sum up all values in p[] to
obtain the new “total no of swaps"
• O(N) to move the last element in a[]
to the front
• Repeat above steps for N times
Solution – 70%
• Complexity?
• O(N[(N2+N(N+N+N))+N])=O(N3)
Calculate p[]
Search for
element i
Do the
Sum up
action
values in
“minus 1”
p[]
Move the
last element
to the front
• Surely acceptable for N <= 600
Solution – 100%
• N <= 3000
• Complexity for 70% solution
• O(N[(N2+N(N+N+N))+N])=O(N3)
• If we can change those N2 and
N(N+N+N) into N or smaller, then
very good!
• In fact, we can!
Solution – 100%
• In 70% solution, after moving last
element to the front, the sequence
changes from
• a[] 3 1 5 4 2
• To
• a[] 2 3 1 5 4
• Then we use O(N2) for re-calculation
of p[]
Solution – 100%
• But actually, if we want to know how
p[] changes from
• a[] 3 1 5 4 2
• p[] 0 1 0 1 3
• To
• a[] 2 3 1 5 4
• p[] 0 0 2 0 1
• We only need to compare the last
element (2) with other elements (3,
1, 5 and 4)!
Solution – 100%
• Shift the last element to the front
• a[] 2 3 1 5 4
• p[] 0 0 1 0 1
• Compare the other elements with
this element, if this element is
greater, add 1 to the corresponding
p[], that is,
• a[] 2 3 1 5 4
• p[] 0 0 2 0 1
• This can be done in O(N)
Solution – 100%
• That means after doing O(N2) to find
p[] once, we can use O(N) to modify
the p[] later on!
Solution – 100%
• Complexity
• O(N2+N[N(N+N+N)+N+N])
For initial
calculation of p[]
Search
for
element i
Do the
Sum up
action
values in
“minus 1”
p[]
Modify a[]
and p[]
Move the
last element
to the front
• Still O(N3)… 
• N(N+N+N) seems too slow, so let’s
deal with it!
Solution – 100%
• id 0 1 2 3 4
• a[] 3 1 5 4 2
• When we search for element i, we
always check one by one
• In fact you can pre-compute their
positions:
•
1 2 3 4 5
• pos[] 1 4 0 3 2
• This can be done in O(N)
• After this, we can “search for
element i” in O(1)!
Solution – 100%
• Complexity
• O(N2+N[N+N(1+N+N)+N+N])
Modify a[]
and p[]
For initial
calculation of p[]
Do the Sum up
Move the
action values in
PreGet pos of “minus 1”
p[]
last element
compute element i
to the front
positions
of 1 to N
• Improved!
Solution – 100%
• id 0 1 2 3 4
• a[] 3 1 5 4 2
• p[] 0 1 0 1 3
• Number of swaps = 0+1+0+1+3 = 5
• a[] 3 1 0 4 2
• p[] 0 1 2 0 2
• Number of swaps?
• 0+1+2+0+2 = 5, or alternatively,
• 5+(id of 5)-(N - id of 5 + 1)=5
• Why?
Solution – 100%
• If we replace x (with index id), and
the number of swaps for previous
case is T,
• Number of swaps after replacement:
• T+id–(N–id+1) = T+2*id–N-1
• You still need O(N) to add up the
values in p[] once, BUT,
• With this formula, no need to
waste time to do “minus 1” stuff
and summing up values in p[]!
Solution – 100%
• Complexity
• O(N2+N[N+N+N(1+1)+N+N])
Modify a[]
and p[]
For initial
calculation of p[]
Use
Get pos of
Preelement i formula!
Sum
up
compute
Move the
positions values in p[]
last element
once only
of 1 to N
to the front
• O(N2)!!! Hurray!!!
Sounds complicated…
• Not really…
• My official solution in C++/Pascal has
less than 40 lines of codes
• (Without compressing the code
statements, of course =P)
Common mistakes
• Wrong greedy algorithms
• Still remember “slow and correct
solutions” vs “fast but wrong
solutions”?
• Missed out some cases
• Used the WRONG algorithm
mentioned earlier
Any question?