Solution and Proof: Facebook Hacker Cup: Studious Student# JobHunting - 待字闺中
b*p
1 楼
Previous discussions are available
1. Studious Student Problem Analysis
http://www.ihas1337code.com/2011/01/studious-student-problem-an
2. http://www.mitbbs.com/article_t/Programming/31179801.html
"i has 1337 code" gave a very good sample to explain why the simple sorting
of strings won't work in his port.
The most brilliant and 'SIMPLE' solution is from blaze and "i has 1337 code"
Saying it is 'SIMPLE' because the code is so elegant/short but the most
interesting part is to prove this solution like blaze mentioned in his posts.
Here is my proof.
Before we jump to the formal proof. Let us play with some simple cases.
suppose we have a series of characters:a,b,c,d which satisfy the criteria
mentioned in the solution.
That is: a < b < c < d; therefore we have
ab < ba, ac < ca, ad < da, bc < cb, ...
let us compare cba and abc.
cba
> cab (fix c, exchange a and b, and ba>ab)
> acb (fix b, exchange a and c, and ca>ac)
> abc (fix a, exchange b and c, and cb>bc)
so, we have cba > abc
compare abcd and dbca [the pattern, if you already notice, is I exchange 'a'
(first) with 'd'(last) in the abcd ]
it is almost the same:
dbca
> dbac (fix db, exchange a,c, ca>ac )
> dabc (fix d and c, exchange a,b, ba>ab)
> adbc (fix bc, exchange a,d, db>bd)
> abdc (fix a and c, exchange b,d, db>bd)
> abcd (fix ab, exchange c,d, dc>cd)
the trick is to exchange one pair at a time:
the element 'a' moves from last potion to first position and then move the
element 'd' down from first position to last position.
Then we can conclude a general format
x {Z} y < y {Z} x, if x < y and {Z} is in order. ---> C1
(the proof is straighforward by using the tricky mentioned above)
Now we prove the solution. We use proof of contradiction.
Given the minimum solution X, we prove that there is no single such
pair of x[i], x[j] that x[i] > x[j] and i < j.
Proof by contradiction:
Suppose we have one of such a pair of x[i], x[j], and others are in order
then if we can construct a new solution X' based on X and X' < X, then we
lead to a contradiction : X is not the minimum. This will prove that the
minimum must be kept
in the order.
Obviously, we can construct X' by switching x[i], x[j] in X.
the new solution X' will look like
X' = x[0]..x[i-1] x[j] x[i+1]..x[j-1] x[i] x[j+1]...x[n]
where
X = x[0]..x[i-1] x[i] x[i+1]..x[j-1] x[j] x[j+1]...x[n]
Comparing X and X', they have the same prefix (x[0..i-1]) and suffix(x[j+1..
n]).
We do not need to consider them. The most interesting part is
in X', Y'= x[j]x[i+1]...x[j-1]x[i]
in X, Y = x[i]x[i+1]...x[j-1]x[j]
Notice that we already prove Y' < Y in C1. Therefore X'
1. Studious Student Problem Analysis
http://www.ihas1337code.com/2011/01/studious-student-problem-an
2. http://www.mitbbs.com/article_t/Programming/31179801.html
"i has 1337 code" gave a very good sample to explain why the simple sorting
of strings won't work in his port.
The most brilliant and 'SIMPLE' solution is from blaze and "i has 1337 code"
Saying it is 'SIMPLE' because the code is so elegant/short but the most
interesting part is to prove this solution like blaze mentioned in his posts.
Here is my proof.
Before we jump to the formal proof. Let us play with some simple cases.
suppose we have a series of characters:a,b,c,d which satisfy the criteria
mentioned in the solution.
That is: a < b < c < d; therefore we have
ab < ba, ac < ca, ad < da, bc < cb, ...
let us compare cba and abc.
cba
> cab (fix c, exchange a and b, and ba>ab)
> acb (fix b, exchange a and c, and ca>ac)
> abc (fix a, exchange b and c, and cb>bc)
so, we have cba > abc
compare abcd and dbca [the pattern, if you already notice, is I exchange 'a'
(first) with 'd'(last) in the abcd ]
it is almost the same:
dbca
> dbac (fix db, exchange a,c, ca>ac )
> dabc (fix d and c, exchange a,b, ba>ab)
> adbc (fix bc, exchange a,d, db>bd)
> abdc (fix a and c, exchange b,d, db>bd)
> abcd (fix ab, exchange c,d, dc>cd)
the trick is to exchange one pair at a time:
the element 'a' moves from last potion to first position and then move the
element 'd' down from first position to last position.
Then we can conclude a general format
x {Z} y < y {Z} x, if x < y and {Z} is in order. ---> C1
(the proof is straighforward by using the tricky mentioned above)
Now we prove the solution. We use proof of contradiction.
Given the minimum solution X, we prove that there is no single such
pair of x[i], x[j] that x[i] > x[j] and i < j.
Proof by contradiction:
Suppose we have one of such a pair of x[i], x[j], and others are in order
then if we can construct a new solution X' based on X and X' < X, then we
lead to a contradiction : X is not the minimum. This will prove that the
minimum must be kept
in the order.
Obviously, we can construct X' by switching x[i], x[j] in X.
the new solution X' will look like
X' = x[0]..x[i-1] x[j] x[i+1]..x[j-1] x[i] x[j+1]...x[n]
where
X = x[0]..x[i-1] x[i] x[i+1]..x[j-1] x[j] x[j+1]...x[n]
Comparing X and X', they have the same prefix (x[0..i-1]) and suffix(x[j+1..
n]).
We do not need to consider them. The most interesting part is
in X', Y'= x[j]x[i+1]...x[j-1]x[i]
in X, Y = x[i]x[i+1]...x[j-1]x[j]
Notice that we already prove Y' < Y in C1. Therefore X'
