Solved the Salary problem on CodeChef January 2013 challenge. This is simply a very interesting problem. My trials with O(n^2log(n)) and O(n^2) came up with TLE (Time Limit Exceeded). The time available is just 1 second. I had to find an O(nlog(n)) or O(n) solution at least. Found an O(nlog(n)) solution. Realized that I had used one of the hints stated in multiple books: Algorithm Design Manual, Algorithms For Interviews.

I will post the details after the challenge ends.

My solution:

The hint that I used is to take a small example and solve it by hand. This is a pretty neat hint. Go ahead and try it.

Here't the set of comments from my code:

//Example: 33 100 1 9 40

//1 9 33 40 100 <- font="font" salaries="salaries" sorted="sorted">

//61 69 93 100 100 <- 60="60" add="add" all="all" font="font" to="to">

//68 76 100 107 100 <- 7="7" add="add" all="all" font="font" to="to">

//75 83 107 107 107 <- 7="7" add="add" all="all" font="font" to="to">

//99 107 107 131 131 <- 24="24" add="add" all="all" font="font" to="to">

//123 131 131 131 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)

//147 155 155 155 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)

//155 163 163 163 155 <- 8="8" font="font" nbsp="nbsp">(add 8 to all)

//163 171 171 163 163 <- 8="8" font="font"> (add 8 to all)

//171 179 171 171 171 <- 8="8" font="font"> (add 8 to all)

//179 179 179 179 179 <- 8="8" font="font"> (add 8 to all)

//Steps:

//1. Sort the list of salaries

//2. Add the diff of last 2 numbers 1 time

//3. Add the diff of n-1 and n-2 2 times

//4. Add the diff of n-2 and n-3 3 times

//5. Add the diff of n-3 and n-4 4 times

//6. ...

//n-1. Add the diff of n-(n-2) and n-(n-1) n-1 times

**Update:**the challenged ended 15th Jan and here's the official editorial: http://discuss.codechef.com/questions/5144/salary-editorialMy solution:

The hint that I used is to take a small example and solve it by hand. This is a pretty neat hint. Go ahead and try it.

Here't the set of comments from my code:

//Example: 33 100 1 9 40

//1 9 33 40 100 <- font="font" salaries="salaries" sorted="sorted">

//61 69 93 100 100 <- 60="60" add="add" all="all" font="font" to="to">

//68 76 100 107 100 <- 7="7" add="add" all="all" font="font" to="to">

//75 83 107 107 107 <- 7="7" add="add" all="all" font="font" to="to">

//99 107 107 131 131 <- 24="24" add="add" all="all" font="font" to="to">

//123 131 131 131 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)

//147 155 155 155 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)

//155 163 163 163 155 <- 8="8" font="font" nbsp="nbsp">(add 8 to all)

//163 171 171 163 163 <- 8="8" font="font"> (add 8 to all)

//171 179 171 171 171 <- 8="8" font="font"> (add 8 to all)

//179 179 179 179 179 <- 8="8" font="font"> (add 8 to all)

//Steps:

//1. Sort the list of salaries

//2. Add the diff of last 2 numbers 1 time

//3. Add the diff of n-1 and n-2 2 times

//4. Add the diff of n-2 and n-3 3 times

//5. Add the diff of n-3 and n-4 4 times

//6. ...

//n-1. Add the diff of n-(n-2) and n-(n-1) n-1 times

*The editorial seems to have a simpler solution, but does not explain the process of arriving at the solution.*
## No comments:

## Post a Comment