UVa 138
From Algorithmist
Contents |
[edit] 138 - Street Numbers
[edit] Summary
Find the numbers for a person's house and a block assuming that houses are consecutively numbered. The house is the starting point so the difference between the sum of all houses between the first and the person's house and the sum of all houses after the person's house until the block length is 0.
[edit] Explanation
- This is impossible to solve within the time limit if you use a very naive O(n^3) algorithm which for each number between 1 and INTEGER_MAX find, a divisor such that sum of (house 1 to person's house-1) = sum (person's house+1 to end of block). This took a really long time I didnt have any luck getting past the fourth answer with this implementation!
- Another approach is to minimize the number of operations so we can get this very close to n. This approach requires keeping track of the difference between the first partition and the second partition and manipulating the divider of the partition properly. So for each number between 1 and INTEGER_MAX manipulate calculate the difference of adding the new integer. Manipulate the divisor until the difference is not positive.
- Remember not to include the dividing house.
- Remember you have to end the program when you reach the 10th element!
- The formula for computing this is 2N^2 = X^2 + X, where N is the low number in the pair and X is the high one. (2(6^2) = 8^2 + 8)
[edit] Optimizations
- Get the output from the program and just format it accordingly and display it. ACM judge wont know the difference.
[edit] Output
6 8 35 49 204 288
