Page 1 of 1
10737 - The Difference Engine
Posted: Wed Oct 06, 2004 12:06 pm
by BiK
Could somebody post an idea for the solution of this problem?
Thanks
Big Hint (Spoiler?)
Posted: Wed Oct 06, 2004 12:49 pm
by gvcormac
The important thing to note is that when you try to reconstruct a sequence from first differences, you have one arbitrary value you have to fill in. That is, the nth first difference value tells you nothing at all and can be reconstructed from the other n-1. How? Simply pick an arbitrary value for the first element of the original sequence, and add successive differences to reconstruct the original. Then you can check the nth difference to determine that it makes sense.
When you take second differences, you can reproduce all-but-one of the first differences, or all-but-two of the original sequence. In general, with n-th differences you can reproduce all but n of the original sequence.
So here's a method: assume that n (the first n will do) of the original values have arbitrary values (0 will do) and solve for the rest. This requires that you solve p-n equations in p-n unknowns. Then construct the differences.
Posted: Thu Oct 07, 2004 1:15 am
by BiK
Thank you very much for your explanation prof. Cormack. We delved into finite differences, interpolating polynomials and numerical analysis stuff like that.
P.S.: I like your problems and the way you guide the Waterloo team. You're definitely one of the most rare coaches. I wish I had someone like you lead me into the field.
10737 WA please help
Posted: Thu Jan 20, 2005 4:54 am
by ranjit
Can anyone verify these i/o and tell if there are any mistakes. I have been getting WA for tihis problem
Thanks in advance.
Input
Code: Select all
23 23
? ? ? 1 17 16 ? 6 17 9 17 ? 15 10 ? 8 12 16 11 2 3 1 16
41 28
38 18 9 13 3 ? ? 22 33 25 1 40 10 15 30 1 ? 31 ? ? ? 26 ? 29 ? 11 7 ? ? 27 ? 7 ? 36 16 29 ? ? ? 3 34
73 69
? ? ? ? ? ? ? 47 ? ? 4 54 ? ? ? 70 ? ? ? 50 6 14 23 ? ? ? ? ? ? ? ? ? 21 ? 16 ? ? ? ? ? ? ? ? 69 63 ? ? ? 37 ? ? 59 71 ? ? 45 19 ? 61 ? ? 71 ? 60 28 ? ? ? ? ? ? 33 ?
43 5
16 14 24 18 5 40 3 37 8 21 26 17 14 42 13 20 28 35 14 25 14 26 20 ? 12 3 19 6 38 32 41 19 40 12 35 15 9 33 10 4 33 31 30
13 4
10 8 9 ? 2 5 6 5 2 3 1 3 12
97 71
16 70 17 25 50 8 84 45 12 ? 90 9 96 78 1 26 21 ? 84 6 44 11 90 31 6 58 3 2 49 20 69 62 61 19 36 ? 78 44 20 86 62 0 2 56 40 32 68 41 58 24 60 95 2 5 22 33 12 80 36 45 63 87 48 60 51 67 30 63 46 ? 81 53 11 81 86 1 25 21 70 ? 0 13 94 60 43 96 66 65 ? 63 12 80 2 ? 88 77 23
71 69
19 57 ? 6 ? ? ? ? 52 ? 15 68 69 54 ? 12 ? 5 1 70 35 ? ? ? 3 ? 3 18 40 ? ? ? 25 ? ? ? 48 0 ? ? 54 43 ? 12 66 5 ? 15 62 7 40 17 ? 30 19 ? 3 ? 68 0 ? ? ? ? ? 18 ? 25 69 ? ?
5 5
4 2 3 ? ?
7 3
5 3 ? 2 5 ? 2
61 21
29 22 37 7 21 42 ? ? 37 48 4 6 40 0 31 ? 51 44 26 23 ? 57 45 50 38 31 19 60 ? 9 16 6 24 52 48 ? 31 ? 22 9 ? 9 29 31 51 5 20 58 12 60 60 45 52 43 13 15 39 60 ? 6 18
53 24
? ? 31 36 52 41 14 34 18 13 ? 17 ? ? 29 19 42 8 ? 34 32 31 22 26 41 44 21 21 8 52 12 ? 34 ? 33 23 14 25 ? 41 46 8 19 13 22 1 ? 31 35 50 39 33 19
29 3
26 1 11 5 24 13 3 5 23 3 4 22 22 11 ? 14 20 18 17 19 16 11 26 6 10 8 20 19 0
59 8
11 42 55 ? 8 6 42 48 ? ? 30 ? 9 55 ? 6 13 16 54 2 38 51 4 23 5 ? 13 52 57 34 11 6 45 19 15 37 49 26 24 49 39 31 32 28 6 45 ? 28 12 3 44 12 9 24 4 17 51 14 30
19 18
17 7 8 13 12 12 14 ? ? 1 5 13 17 9 10 12 17 10 3
61 7
27 8 19 18 37 58 9 5 16 31 60 22 14 19 54 41 9 29 43 6 31 21 12 54 18 37 12 4 57 12 42 24 20 2 42 59 1 ? 51 5 18 23 5 40 37 26 35 19 36 6 3 44 37 25 57 30 45 33 42 52 ?
83 87
? 15 20 ? 65 ? ? ? 38 ? 69 68 10 40 25 35 ? 34 ? 44 ? 29 18 ? ? ? 32 ? 25 ? ? 24 ? ? ? ? ? ? 7 13 52 ? ? 40 58 ? ? 48 72 ? ? ? 17 72 ? ? 8 ? ? 13 26 65 ? ? ? 55 45 ? ? ? ? ? 5 37 ? 0 ? 74 ? ? ? 25 ?
19 2
18 11 1 10 2 15 0 4 10 13 17 ? 3 5 11 18 4 11 5
23 17
3 ? 11 22 ? 8 5 ? ? 0 ? ? 12 7 ? ? ? ? 20 ? ? ? 13
67 48
44 8 23 1 51 62 33 ? 47 ? 28 40 20 22 53 ? 56 66 23 45 ? 48 15 40 55 48 1 49 ? ? 42 59 ? 29 24 ? ? 13 38 9 57 ? 63 49 ? 58 48 44 41 ? 45 5 31 66 44 ? 18 55 43 ? 58 ? ? 50 24 23 23
5 3
4 4 1 ? ?
29 15
12 1 24 6 7 11 6 24 ? ? 12 10 27 6 14 ? 20 ? ? ? ? ? 21 ? ? ? 18 ? 14
53 38
15 12 9 25 ? ? ? 49 ? ? ? ? ? 6 ? ? ? ? 10 49 5 ? 51 9 49 29 ? 34 41 1 ? ? 30 ? ? 28 ? ? ? 10 ? 21 13 ? ? ? ? ? ? ? ? ? ?
37 33
? ? 35 22 35 ? ? 22 10 ? ? 26 36 26 1 5 ? ? 32 ? ? 6 ? 8 ? ? ? ? ? 18 ? ? ? ? ? 10 ?
2 2
? 0
59 60
? 24 ? ? 49 12 3 53 14 23 8 ? 7 2 ? ? ? 51 ? ? ? 30 32 ? 30 ? 20 ? 48 37 ? ? 37 ? 49 20 20 ? ? ? 6 18 ? 39 9 ? 17 41 ? 1 18 ? ? 13 30 42 ? 7 ?
61 21
46 ? 25 40 43 35 15 59 45 23 55 ? 20 11 40 22 25 3 39 36 40 57 45 16 53 48 53 28 21 4 31 5 52 19 32 31 1 6 49 60 51 11 ? 56 12 24 ? 38 35 52 41 13 27 23 10 14 41 4 3 33 34
2 2
1 1
3 2
1 2 2
71 73
? ? 65 ? 61 8 30 7 42 28 20 49 60 15 36 61 ? ? 63 60 50 21 9 44 ? 8 ? ? 28 ? 46 69 ? 53 35 32 53 12 ? 0 49 62 ? 65 39 30 55 7 2 43 ? 27 11 32 2 7 53 66 68 ? ? ? 33 47 ? ? ? 6 37 56 35
73 27
27 35 14 10 49 40 66 68 15 60 19 59 54 46 70 37 3 69 0 25 53 40 8 62 57 41 68 22 9 11 55 36 31 ? 69 30 7 21 23 2 36 10 5 6 64 36 3 29 39 56 13 48 20 53 56 10 21 9 62 43 18 58 10 38 16 6 68 23 11 18 10 31 12
83 56
? 11 20 ? ? 61 27 59 49 ? ? 59 48 8 0 22 ? 34 ? 78 ? ? 68 ? 8 ? ? ? 66 ? 53 ? ? 66 25 65 3 57 ? ? 56 ? ? ? 24 81 66 72 ? 4 41 37 35 ? ? ? 52 60 ? 16 82 ? 39 69 62 ? 4 ? ? ? 77 ? ? ? 62 29 32 60 ? 15 ? 40 43
59 47
? ? ? ? 14 54 ? ? ? ? ? ? ? ? ? 40 9 ? ? 43 ? ? ? ? ? ? ? ? ? 6 ? 26 ? ? 49 ? 26 ? ? 54 ? ? ? ? 17 ? ? ? ? ? ? ? ? 40 ? ? ? ? 17
31 1
21 5 14 17 2 27 17 30 23 16 28 7 13 11 6 25 24 25 8 1 21 24 16 26 0 0 22 11 16 17 12
19 13
14 17 18 18 1 1 10 ? ? 9 ? 13 17 0 1 ? 8 16 ?
5 1
4 2 3 0 1
3 3
0 2 ?
71 51
? ? 9 20 ? ? 51 56 ? 36 16 ? ? 18 ? ? 16 6 ? 11 36 18 ? ? 38 ? 27 34 ? 29 ? ? ? ? ? 5 26 12 28 58 ? ? 55 33 66 ? 49 ? ? 19 14 ? 6 27 29 36 ? 36 9 ? ? 16 ? 53 45 32 ? ? 0 ? 21
71 58
45 51 39 50 38 11 39 25 66 1 51 44 51 65 51 8 54 47 4 63 63 57 68 25 17 49 24 28 67 10 38 41 22 37 51 60 48 19 45 4 52 25 8 32 19 59 0 3 66 ? 36 26 59 22 24 44 40 ? 2 68 28 29 38 26 70 60 63 11 9 1 30
73 53
31 46 14 ? 22 ? ? 10 66 15 25 14 41 54 ? 62 10 51 49 33 15 48 58 4 27 41 33 25 ? 32 7 20 38 55 62 26 13 19 40 ? 35 ? 30 33 50 39 48 ? 3 21 21 70 56 ? 54 30 ? 71 ? 13 72 ? 59 ? 40 24 19 ? ? ? 65 56 ?
61 13
35 46 36 20 15 39 58 25 40 59 54 5 ? 11 16 0 12 8 12 5 36 24 57 31 19 32 17 24 56 50 38 53 26 ? 25 29 46 41 9 45 7 49 43 2 54 56 18 56 9 28 7 14 5 33 11 36 ? 53 45 55 16
97 82
42 ? 55 67 5 5 19 ? 26 96 70 17 71 42 11 5 33 76 55 41 48 89 13 67 91 20 22 53 ? 9 75 60 89 46 36 48 16 ? 42 84 66 2 84 39 19 58 15 62 94 ? 48 72 ? ? ? 52 23 23 76 36 90 70 88 15 57 31 24 51 23 70 88 71 86 64 90 86 66 77 60 19 69 75 15 66 58 ? 88 53 15 45 32 52 39 36 74 85 93
53 49
46 ? 39 ? ? ? ? ? ? ? 7 3 ? ? ? ? ? ? ? ? ? ? 44 10 ? ? 52 ? ? 25 16 14 ? ? 50 24 52 ? ? ? 45 35 22 ? 29 ? ? ? 49 31 27 1 36
41 27
40 37 27 32 14 23 26 14 28 6 1 33 3 12 34 ? ? 23 33 14 3 10 34 11 29 38 38 24 14 16 39 32 12 0 28 ? 39 34 3 23 21
31 31
? ? ? ? 26 ? ? ? ? 30 11 11 ? 6 ? 28 ? 9 18 ? 29 ? ? 4 ? ? 23 ? 30 ? 4
71 5
51 10 22 11 58 25 32 37 6 68 17 2 69 62 51 22 ? 35 42 34 20 59 8 37 33 21 25 30 56 3 39 33 14 9 55 56 67 40 17 33 7 46 10 40 44 1 20 26 67 22 60 17 11 28 14 4 49 39 35 66 2 34 28 47 44 43 33 0 13 10 65
41 22
32 7 35 ? 19 21 17 16 13 24 23 36 29 16 32 ? 24 30 38 14 28 25 16 ? ? 38 10 5 0 ? ? 40 30 36 ? 16 21 35 9 ? 29
71 15
11 54 26 43 27 63 ? 70 10 15 21 54 59 9 27 49 30 63 66 22 53 7 ? 39 10 14 8 32 20 35 ? 42 44 25 53 28 11 26 15 4 ? 56 56 19 37 39 8 46 26 17 ? 36 49 12 59 31 20 58 2 65 26 34 15 22 ? 37 19 ? 47 19 7
17 10
14 7 3 1 5 5 7 11 16 7 1 7 10 4 2 15 2
59 37
1 52 1 7 8 30 53 43 21 52 2 53 45 40 33 31 7 25 19 46 30 ? 37 10 1 15 54 19 19 51 55 44 ? 53 53 49 1 2 21 58 49 46 51 51 40 41 33 18 13 44 48 37 31 23 19 45 24 39 44
79 32
66 78 15 72 ? 71 ? 33 58 45 25 27 34 33 77 43 71 74 ? 55 30 44 ? 15 6 33 2 77 8 6 70 5 54 43 11 16 42 1 10 9 9 43 30 35 70 64 43 ? 44 29 36 ? 14 59 ? 41 58 75 23 12 77 75 74 58 66 1 33 30 66 25 ? 47 43 35 57 52 78 8 62
0 0
Output
Code: Select all
Invalid message!
38 18 9 13 3 21 4 22 33 25 1 40 10 15 30 1 0 31 0 0 0 26 0 29 0 11 7 0 0 27 0 7 0 36 16 29 0 0 0 3 34
7 11 25 46 34 42 10 47 45 24 4 54 52 56 1 70 70 62 35 50 6 14 23 0 0 0 0 0 0 0 0 0 21 0 16 0 0 0 0 0 0 0 0 69 63 0 0 0 37 0 0 59 71 0 0 45 19 0 61 0 0 71 0 60 28 0 0 0 0 0 0 33 0
16 14 24 18 5 40 3 37 8 21 26 17 14 42 13 20 28 35 14 25 14 26 20 39 12 3 19 6 38 32 41 19 40 12 35 15 9 33 10 4 33 31 30
10 8 9 9 2 5 6 5 2 3 1 3 12
16 70 17 25 50 8 84 45 12 7 90 9 96 78 1 26 21 76 84 6 44 11 90 31 6 58 3 2 49 20 69 62 61 19 36 0 78 44 20 86 62 0 2 56 40 32 68 41 58 24 60 95 2 5 22 33 12 80 36 45 63 87 48 60 51 67 30 63 46 0 81 53 11 81 86 1 25 21 70 0 0 13 94 60 43 96 66 65 0 63 12 80 2 0 88 77 23
19 57 24 6 0 0 0 0 52 0 15 68 69 54 0 12 0 5 1 70 35 0 0 0 3 0 3 18 40 0 0 0 25 0 0 0 48 0 0 0 54 43 0 12 66 5 0 15 62 7 40 17 0 30 19 0 3 0 68 0 0 0 0 0 0 18 0 25 69 0 0
Invalid message!
5 3 4 2 5 0 2
29 22 37 7 21 42 54 55 37 48 4 6 40 0 31 58 51 44 26 23 55 57 45 50 38 31 19 60 50 9 16 6 24 52 48 29 31 29 22 9 56 9 29 31 51 5 20 58 12 60 60 45 52 43 13 15 39 60 0 6 18
27 27 31 36 52 41 14 34 18 13 50 17 16 45 29 19 42 8 28 34 32 31 22 26 41 44 21 21 8 52 12 31 34 30 33 23 14 25 0 41 46 8 19 13 22 1 0 31 35 50 39 33 19
26 1 11 5 24 13 3 5 23 3 4 22 22 11 20 14 20 18 17 19 16 11 26 6 10 8 20 19 0
11 42 55 10 8 6 42 48 1 46 30 13 9 55 45 6 13 16 54 2 38 51 4 23 5 22 13 52 57 34 11 6 45 19 15 37 49 26 24 49 39 31 32 28 6 45 17 28 12 3 44 12 9 24 4 17 51 14 30
17 7 8 13 12 12 14 0 0 1 5 13 17 9 10 12 17 10 3
27 8 19 18 37 58 9 5 16 31 60 22 14 19 54 41 9 29 43 6 31 21 12 54 18 37 12 4 57 12 42 24 20 2 42 59 1 1 51 5 18 23 5 40 37 26 35 19 36 6 3 44 37 25 57 30 45 33 42 52 0
Invalid message!
18 11 1 10 2 15 0 4 10 13 17 9 3 5 11 18 4 11 5
3 6 11 22 9 8 5 15 1 0 15 5 12 7 0 0 0 0 20 0 0 0 13
44 8 23 1 51 62 33 65 47 33 28 40 20 22 53 12 56 66 23 45 2 48 15 40 55 48 1 49 0 0 42 59 0 29 24 0 0 13 38 9 57 0 63 49 0 58 48 44 41 0 45 5 31 66 44 0 18 55 43 0 58 0 0 50 24 23 23
4 4 1 0 0
12 1 24 6 7 11 6 24 28 21 12 10 27 6 14 12 20 3 16 1 12 24 21 0 0 0 18 0 14
15 12 9 25 50 7 45 49 36 0 6 3 9 6 41 24 7 28 10 49 5 36 51 9 49 29 48 34 41 1 0 0 30 0 0 28 0 0 0 10 0 21 13 0 0 0 0 0 0 0 0 0 0
11 6 35 22 35 31 4 22 10 0 0 26 36 26 1 5 0 0 32 0 0 6 0 8 0 0 0 0 0 18 0 0 0 0 0 10 0
0 0
Invalid message!
46 32 25 40 43 35 15 59 45 23 55 57 20 11 40 22 25 3 39 36 40 57 45 16 53 48 53 28 21 4 31 5 52 19 32 31 1 6 49 60 51 11 18 56 12 24 0 38 35 52 41 13 27 23 10 14 41 4 3 33 34
Invalid message!
Invalid message!
Invalid message!
27 35 14 10 49 40 66 68 15 60 19 59 54 46 70 37 3 69 0 25 53 40 8 62 57 41 68 22 9 11 55 36 31 14 69 30 7 21 23 2 36 10 5 6 64 36 3 29 39 56 13 48 20 53 56 10 21 9 62 43 18 58 10 38 16 6 68 23 11 18 10 31 12
20 11 20 39 37 61 27 59 49 53 57 59 48 8 0 22 9 34 56 78 44 45 68 27 8 19 17 13 66 36 53 10 70 66 25 65 3 57 10 19 56 71 2 78 24 81 66 72 67 4 41 37 35 0 0 0 52 60 0 16 82 0 39 69 62 0 4 0 0 0 77 0 0 0 62 29 32 60 0 15 0 40 43
47 35 6 53 14 54 13 31 12 19 7 42 2 1 43 40 9 0 14 43 32 6 31 5 53 30 1 55 36 6 38 26 18 1 49 56 26 12 41 54 20 50 42 32 17 14 44 0 1 18 40 5 1 40 33 0 4 47 17
Invalid message!
14 17 18 18 1 1 10 0 0 9 0 13 17 0 1 0 8 16 0
4 2 3 0 1
Invalid message!
14 65 9 20 40 42 51 56 30 36 16 24 50 18 51 5 16 6 24 11 36 18 7 55 38 48 27 34 15 29 65 66 43 3 26 5 26 12 28 58 0 0 55 33 66 0 49 0 0 19 14 0 6 27 29 36 0 36 9 0 0 16 0 53 45 32 0 0 0 0 21
45 51 39 50 38 11 39 25 66 1 51 44 51 65 51 8 54 47 4 63 63 57 68 25 17 49 24 28 67 10 38 41 22 37 51 60 48 19 45 4 52 25 8 32 19 59 0 3 66 0 36 26 59 22 24 44 40 0 2 68 28 29 38 26 70 60 63 11 9 1 30
31 46 14 65 22 33 50 10 66 15 25 14 41 54 47 62 10 51 49 33 15 48 58 4 27 41 33 25 0 32 7 20 38 55 62 26 13 19 40 0 35 0 30 33 50 39 48 0 3 21 21 70 56 0 54 30 0 71 0 13 72 0 59 0 40 24 19 0 0 0 65 56 0
35 46 36 20 15 39 58 25 40 59 54 5 46 11 16 0 12 8 12 5 36 24 57 31 19 32 17 24 56 50 38 53 26 47 25 29 46 41 9 45 7 49 43 2 54 56 18 56 9 28 7 14 5 33 11 36 0 53 45 55 16
42 33 55 67 5 5 19 59 26 96 70 17 71 42 11 5 33 76 55 41 48 89 13 67 91 20 22 53 0 9 75 60 89 46 36 48 16 0 42 84 66 2 84 39 19 58 15 62 94 0 48 72 0 0 0 52 23 23 76 36 90 70 88 15 57 31 24 51 23 70 88 71 86 64 90 86 66 77 60 19 69 75 15 66 58 0 88 53 15 45 32 52 39 36 74 85 93
46 0 39 34 1 1 0 0 10 4 7 3 33 28 5 17 11 20 45 25 11 4 44 10 0 0 52 0 0 25 16 14 0 0 50 24 52 0 0 0 45 35 22 0 29 0 0 0 49 31 27 1 36
40 37 27 32 14 23 26 14 28 6 1 33 3 12 34 0 0 23 33 14 3 10 34 11 29 38 38 24 14 16 39 32 12 0 28 0 39 34 3 23 21
Invalid message!
51 10 22 11 58 25 32 37 6 68 17 2 69 62 51 22 63 35 42 34 20 59 8 37 33 21 25 30 56 3 39 33 14 9 55 56 67 40 17 33 7 46 10 40 44 1 20 26 67 22 60 17 11 28 14 4 49 39 35 66 2 34 28 47 44 43 33 0 13 10 65
32 7 35 31 19 21 17 16 13 24 23 36 29 16 32 35 24 30 38 14 28 25 16 0 0 38 10 5 0 0 0 40 30 36 0 16 21 35 9 0 29
11 54 26 43 27 63 5 70 10 15 21 54 59 9 27 49 30 63 66 22 53 7 46 39 10 14 8 32 20 35 29 42 44 25 53 28 11 26 15 4 3 56 56 19 37 39 8 46 26 17 13 36 49 12 59 31 20 58 2 65 26 34 15 22 0 37 19 0 47 19 7
Invalid message!
1 52 1 7 8 30 53 43 21 52 2 53 45 40 33 31 7 25 19 46 30 58 37 10 1 15 54 19 19 51 55 44 0 53 53 49 1 2 21 58 49 46 51 51 40 41 33 18 13 44 48 37 31 23 19 45 24 39 44
66 78 15 72 66 71 12 33 58 45 25 27 34 33 77 43 71 74 7 55 30 44 37 15 6 33 2 77 8 6 70 5 54 43 11 16 42 1 10 9 9 43 30 35 70 64 43 33 44 29 36 8 14 59 0 41 58 75 23 12 77 75 74 58 66 1 33 30 66 25 0 47 43 35 57 52 78 8 62
Posted: Thu Jan 20, 2005 5:15 pm
by Cho
My output:
Code: Select all
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
5 3 4 2 5 0 2
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
0 0
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
4 2 3 0 1
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!
Invalid message!