10737 - The Difference Engine

[BiK]

Could somebody post an idea for the solution of this problem?

Thanks

[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.

[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.

[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

[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!