UVA Problem 913 – Joana and the Odd Numbers Solution:
Click here to go to this problem in uva Online Judge.
Solving Technique:
Todo: 1. Reorganize. 2. check for mistakes.
This problem can be solved in quite a few ways. Brute force won’t work. I have given the brute force code anyway. It will give correct answer from 1 < n < 199999999 but the requirement is 1 < N < 1000000000, which is way way larger.
Another approach is to do mathematical calculation to come up with a formula to solve this. Multiple formula can be generated such as a single formula or, one formula complementing other or, multiple formula's combined. I have provided two formula in the codes below.
One thing to mention, the output or input must be long long data type. Other data types will give incorrect output.
Unfortunately I won’t be elaborate more than this. It took 5 pages to solve this many way with proof, but that’s a lot to write. I will try to explain a way for coming up with these formula.
The brute force way:
A simple way to do this is, for values greater than 1 set offset 10 and start multiplying with 5. For each step increase offset by 4 and add value to previous multiplying value.
Input -> Sum
3 -> 3 * 5
5 -> 3 * 15, [ 15 = 5 + 10 ]
7 -> 3 * 29, [ 29 = 15 + 14 ]
9 -> 3 * 47, [ 47 = 29 + 18 ]
11 -> 3 * 69, [ 69 = 47 + 22 ]
13 -> 3 * 95, [ 95 = 69 + 26 ]
Although this approach will not work since the range is huge. It is possible to pre-calculate for a certain range and anything outside that calculate with formula.
Trying to Come up with a Closed Form Expression:
First thing is to notice is that the numbers differ by 2 and are odd. So, if the first number is n, then the sum of n and next two numbers is,
Ex:
If n was 67, then result of 3n + 6 = 207.
The opposite is also true. For example, given sum of three numbers we can find the first number by,
if sum was 141 then,
Expanding and writing the sequence in format below,
Input – Values in the Row(Last three numbers bracketed) – Sum
1 - [ 1 ] - 1 3 - [ 3 5 7 ] - 15 5 - 9 11 [ 13 15 17 ] - 45 7 - 19 21 23 25 [ 27 29 31 ] - 87 9 - 33 35 37 39 41 43 [ 45 47 49 ] - 141 11 - 51 53 55 57 59 61 63 65 [ 67 69 71 ] - 207 13 - 73 75 77 79 81 83 85 87 89 91 [ 93 95 97 ] - 285
This means for a given value there are that many numbers in that row.
Trying to come up with a Brute Force Approach:
This is extra and not required to solve this problem but it will understand creation of the formula.
The first numbers of every row can be generated and memoized in a table sequentially using the formula below,
row – number break down – first number
1 -> 1 -> 1
3 -> 1 + ( 1 * 2 ) -> 3
5 -> 3 + ( 3 * 2 ) -> 9
7 -> 9 + ( 5 * 2 ) -> 19
9 -> 19 + ( 7 * 2 ) -> 33
Let n1 be equal to 1 and n2, n3 …, nk be next generated sequences. So the formula is,
n1 = n1
n2 = n1 + (1 * 2)
n3 = n2 + (3 * 2)
n4 = n3 + (5 * 2)
n5 = n4 + (7 * 2)
……………..
……………..
nk = n(k-1) + (i * 2)
this can be converted to an algorithm,
Let, T be table to store value of the first number.
n1 = 1
T[n1] = n1
i = 3
for i to size
T[i] = T[i-2] + (i-2) * 2
increment i by two
End
Generating Solution From the Output:
Similarly, The sum can also be calculated in terms of input by creating a sequence and finding out the formula.
1 -> 1
3 -> 15
5 -> 45
7 -> 87
9 -> 141
11 -> 207
13 -> 285
when they are written in a sequence,
1 + 15 + 45 + 87 + 141 + 207 + 285 + …………..
So, for 11 the output should be 207. The formula can be calculated from the picture above
207 = 141 + 66
207 = 141 + (54 + 12)
207 = 141 + ((12 * 5) – 6 + 12)
207 = 141 + ((12 * 6) – 6)
207 = 87 + 54 + ((12 * 6) – 6)
207 = 87 + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 45 + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 15 + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 1 + ((12 * 2 – 6) – 4) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = (12 * 2 – 6) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6) – 3
this can be written as summation formula,
this can be rewritten as,
The input for this formula is the input for the program,
for, n = 17 the sum of last three numbers should be 477.
Setting n = 17 in following the formula it will give,
-3 + 6 * ( 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 ) = 477
The formula above doesn’t quite work out for 1. Although we know for 1 output is 1 but it should be included in the formula. Expanding and changing values the summation will get the formula for all values.
Similarly, this is the formula to calculate the first number to sum from a row. It was calculated making a sequence of first summing numbers and find out the the summation formula,
First number,
Separating the summation,
I won’t simplify anymore.
Put the value of summation in the equation,
because i only expanded the summation. Multiply result with 2 and add 3 to get the first number.
From, the equation above place the value of first number in 3n + 6 to get the summation of last three numbers for a given number.
The 3n + 6 and the summation formula can be combined into a single formula.
Generating Solution based on First Number of Last Three:
Similarly the first number to sum from every row can be calculated. If the first number from every row are written in a sequence,
1 + 3 + 13 + 27 + 45 + 67 + ………………..
The first number can be generated following this,
For input n = 11, task is to generate first number from the graphical representation above. Then the value can be placed in equation, 3N + 6 to generate sum of that value and next two (basically the answer).
67 = 45 + 22
67 = 45 + ( 18 + 4 )
67 = 45 + ( 14 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 27 + 18 + ( 10 + 4 + 4 + 4 )
67 = 27 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + 14 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
this way the formula can be,
This can be further simplified.
For n = 15 the first number should be 123. Setting n = 15 in equation above,
first number = 3 + 10 * ( 7 – 1 ) + 2 * ( 7 – 2 ) * ( 7 – 1 )
first number = 3 + 60 + 60 = 123
That’s it. There are other approaches but it will take a long time to write.
Important: Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.
More Inputs of This Problem on uDebug.
Input:
3 5 7
Output:
15 45 87
Formula Generate sequence sum, first number & sum Code:
/**
* Author: Asif Ahmed
* Site: https://quickgrid.wordpress.com
* Problem: UVA 913 Joana and Odd numbers
* Technique: Generate Sequence Sum, First number
* then generate sum of next numbers
* including the generated number.
*/
#include<stdio.h>
#include<string.h>
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
long long n;
while( scanf("%lld", &n) == 1 ){
long long m = n >> 1;
long long part = ( (n * (n + 1)) >> 1 ) - ( m * ( m + 1 ) ) - 4;
long long firstNum = 2 * part + 3;
printf("%lld\n", 3 * firstNum + 6);
}
return 0;
}
Reduced Formula Code:
/**
* Author: Asif Ahmed
* Site: https://quickgrid.wordpress.com
* Problem: UVA 913 Joana and Odd numbers
* Technique: Reduced formula.
*/
#include<stdio.h>
#include<string.h>
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
unsigned long long n;
while( scanf("%lld", &n) == 1 ){
long long ans = 3 * ( (n + 1) * ( n - (n >> 1) ) ) - 9;
printf("%lld\n", ans);
}
return 0;
}
Brute Force Code( Won’t be Accepted ):
/**
* Author: Asif Ahmed
* Site: https://quickgrid.wordpress.com
* Problem: UVA 913 - Joana and the odd numbers
* Technique: Brute Force. Won't get Accepted.
* This is just for demonstration. This
* won't get accepted due to huge size that
* array can't process. But it will give correct
* answer till N.
*/
#include<stdio.h>
#include<string.h>
#define N 100000000
//#define M 1000000000
static long long value[N];
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
value[0] = 1;
value[1] = 15;
long long offset = 30;
for( long long i = 2; i < N; ++i ){
value[i] = value[i-1] + offset;
offset = offset + 12;
}
long long n;
while( scanf("%lld", &n) == 1 ){
printf("%lld\n", value[n/2] );
}
return 0;
}
Quickgrid 