Transcript Count 1s

Who moved my cheese?
Solution for HKOI2008 Junior Q4
Background

[The book] describes change in one's work
and life, and four typical reactions to said
change with two mice, two "little people", and
their hunts for cheese.

Who Moved My Cheese?. (2008, January 9). In
Wikipedia, The Free Encyclopedia. Retrieved
15:13, January 9, 2008, from
http://en.wikipedia.org/w/index.php?title=Who_Mo
ved_My_Cheese%3F&oldid=183069019
Problem Description



Given N columns by N rows of numbers.
Define “original arrangement” to be “every
number is smaller than the one on its right
and all numbers in the row below.
For example, when N=3,
1
2
3
2
5
8
4
5
6
11 12 19
7
8
9
30 40 50
Problem Description

Two types of operation



Swap adjacent columns
Swap adjacent rows
You are asked to find a sequence of
operations to restore the N×N numbers into
the original arrangement.
Illustrated Example
7
6
5
8
2
3
1
4
1
2
3
4
3
2
1
4
6
7
5
8
5
6
7
8
11
10
9
12
10
11
9
12
9
10
11
12
15
14
13
16
14
15
13
16
13
14
15
16
C1
R1
C2
C1
6
7
5
8
2
1
3
4
2
3
1
4
6
5
7
8
10
11
9
12
10
9
11
12
14
15
13
16
14
13
15
16
Statistics






#Att: 47
Max: 95
#Max: 1
Min: 0
Std Dev(Att): 21.94
Mean(Att): 19.79
Premise



Assume there is a solution.
We want to find any solution.
We will deal with the requirements later.
Solution 1




Brute Force
Exhaust the sequence of operations
Time Complexity: non-polynomial
Expected Score: 30

Provided that the program can terminate within
time limit and output the solution or “No solution”
Solution 2


To simplify the problem, we can always
reduce the set of numbers into the set of
integers from 1 to N2.
For example, when N=3,
5
2
8
12 11 19
40 30 50
≡
2
1
3
5
4
6
8
7
9
Solution 2

Column swaps are independent of row swaps.
R1
6
7
5
2
3
1
4
6
7
5
8
10
11
9
12
C2
8
14
15
13
2
1
3
4
16
2
3
1
4
6
5
7
8
10
11
9
12
10
9
11
12
14
15
13
16
14
13
15
16
C2
6
5
6
8
2
1
3
4
10
9
11
12
14
13
15
16
R1
Solution 2

So, the solution [C1,R1,C2,C1] is
equivalent to [C1,C2,C1,R1].

In general, this allows us to column swaps
first, and row swaps later.
Solution 2


We can define a comparison between the
columns.
Column A < Column B if and only if
kth integer in A < kth integer in B



This comparison defines an ordering, and the
original arrangement obeys the ordering.
By assuming a solution exist, the choice of k is
independent of the definition.
In the actual implementation, the program should
fix the choice of k throughout the execution.
Solution 2

Reduce the set of numbers to [1,N2]
Bubble sort by columns
Bubble sort by rows
Check result against the original

Time Complexity: O(N4)
Expected Score: 50

Solution 3





Observe that reducing the set of numbers to
[1,N2] is inefficient.
Although it simplifies our thinking, it is not
necessary for our algorithm to work
Bubble sort by columns
Bubble sort by rows
Check result against the original
Time Complexity: O(N3)
Expected Score: 70
Solution 4


Swapping columns is expensive.
Implement swapping by pointers.
7
6
5
8
3
2
1
11
10
15
14
C1
7
6
5
8
4
3
2
1
4
9
12
11
10
9
12
13
16
15
14
13
16
Solution 4

Bubble sort by columns. [pointers]
Bubble sort by rows [pointers]
Check result against the original

Time Complexity: O(N2)
Expected Score: 100

Mistakes

Make sure you have the definition of “original
arrangement” correctly.
Skills

Sorting




Data set
Comparison and ordering
Behaviour of differenting sorting algorithm
Pointers
Miscellaneous


How to account for the two premises?
What if there is no solution at all?


Then, the arrangement after sorting must be
different from the original arrangement.
What if the solution sequence of operation
needs more than 3,000,000 operations?

Each bubble sort guarantees the number of
swaps is at most N(N-1)/2.