UVa 138

From Algorithmist
Jump to: navigation, search

138 - Street Numbers[edit]

Summary[edit]

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.

Explanation[edit]

  • 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)

Note by ocin_lr: This result comes from the fact that:
\sum _{{i=1}}^{{n-1}}{i}=\sum _{{i=n+1}}^{{x}}{i}

\sum _{{i=1}}^{{n-1}}{i}=\sum _{{i=1}}^{{x}}{i}-\sum _{{i=1}}^{{n}}{i}

Now, applying Gauss Formula:
{(n-1)(n) \over 2}={(x)(x+1) \over 2}-{(n)(n+1) \over 2}
{(n-1)(n)}+{(n)(n+1)}={(x)(x+1)}
{(n-1)(n)}+{(n)(n-1+2)}={(x)(x+1)}
{(n-1)(n)}+{(n)(n-1)}+{(2n)}={(x)(x+1)}
{2n(n-1)}+{(2n)(1)}={(x)(x+1)}
{2n(n-1+1)}={(x)(x+1)}

{2{n}^{{2}}}={x^{{2}}+x}

This equation, however, is not very useful if you want a computer to compute it - at least in Java a double variable is overflown because of square of x. However when I ran the program I got first 5 pairs before it overflows, from which it's easy to spot a pattern in the numbers. The first number n of all pairs is always

n_{i}=6n_{{i-1}}-n_{{i-2}}

where n_{{i-1}} is the first number of the preceding pair and n_{{i-2}} is the first number of a pair before the preceding. So the first numbers of first 5 pairs are computed as follow:

(n_{0}=1)
n_{1}=6
n_{2}=6n_{1}-n_{0}=6\cdot 6-1=35
n_{3}=6n_{2}-n_{1}=6\cdot 35-6=204
n_{4}=6n_{3}-n_{2}=6\cdot 204-35=1189
n_{5}=6n_{4}-n_{3}=6\cdot 1189-204=6930
and so on. Like this you can compute all first numbers of the ten pairs without any effort.

The computation of the second number x of any pair is similarly easy:

x_{i}=n_{i}+n_{{i-1}}+x_{{i-1}}

To compute the ith second number of a pair we add up the first number of the current pair with both first and second numbers of the preceding pair. Thus, the first five numbers again are:

x_{1}=8
x_{2}=n_{2}+n_{1}+x_{1}=35+6+8=49
x_{3}=n_{3}+n_{2}+x_{2}=204+35+49=288
x_{4}=n_{4}+n_{3}+x_{3}=1189+204+288=1681
x_{5}=n_{5}+n_{4}+x_{4}=6930+1189+1681=9800
and so on.



Alternatively, brute force attack can be applied.
From the equation {2{n}^{{2}}}={x^{{2}}+x}
we get, n={\sqrt  {{x^{{2}}+x \over 2}}}
So, we'll check every integer (from 8) as the value of x for which n gets an integer value.

Optimizations[edit]

  • Get the output from the program and just format it accordingly and display it. ACM judge wont know the difference.

Output[edit]

6 8 
35 49
204 288

Solution[edit]