|
contest is over, winner is hamster1800
Original problem was taken from here: http://projecteuler.net/index.php?section=problems&id=290
Solution:
+ Show Spoiler +ok, the key is yours: xxxxxx-xxxx-xxxxxx-xxxx-xxxxxx have fun ----------------------------------------- Original Message: Sure thing 9090754242258600 1710153888867000 ----------------------------------------- Original Message: could you give me 2 examples for x for which ds(x) = ds(x * 137)? ----------------------------------------- Original Message: Answer = 20444710234716473 Solution is a dynamic programming algorithm. State is based on the last k digits of the number, lazily computing the digit sum of 137*x digit by digit, storing the next 4 digits to the left of the last k digits (using the fact that 9*137 + 99 < 10000). I iterate through the values of k from 0 to 17, increasing it by one each time (so that at the end we have the values for 18), computing the number of numbers x for which the next 4 digits to the left are "a" and the difference between ds(x) and ds(137*x) (up to the last k digits) is "b". Code below: #include<cstdio> #include<cstdlib>
using namespace std;
int main() { long long **now, **next; now = new long long*[10000]; next = new long long*[10000]; for(int i = 0; i<10000; i++) { now[i] = new long long[401]; next[i] = new long long[401]; now[i] += 200; next[i] += 200; for(int j = -200; j<=200; j++) { now[i][j] = next[i][j] = 0; } } now[0][0] = 1; for(int i = 0; i<18; i++) { for(int j = 0; j<10000; j++) { for(int k = -200; k<=200; k++) { next[j][k] = 0; } } for(int a = 0; a<10000; a++) { for(int b = -162; b<=162; b++) { for(int d = 0; d<=9; d++) { int na = a/10 + 137*d, nb = b - a%10 + d; next[na][nb] += now[a][b]; } } } long long **t = now; now = next; next = t; } long long ans = 0; for(int i = 0; i<10000; i++) { for(int j = -200; j<=200; j++) { int a = i, b = j; while(a != 0) { b -= a%10; a/=10; } if(b == 0) { ans += now[i][j]; } } } printf("%lld\n",ans); }
----------------------
I dont know whether there is still a high demand for beta keys, but I received another friend invite key, which you can win by solving the following challenge:
Let x be an integer equal to or greater than 0 and smaller than 1000000000000000000 (10^18).
Let ds(x) be the digit sum of x, i.e. ds(123) = 1 + 2 + 3 = 6
For how many distinct x is ds(x) = ds(137 * x)?
The first one to pm me a) the correct answer and b) a little explanation (e.g. source code) how to find the solution will receive a beta key.
Once I receive a solution, I'll reply whether it's correct or not. If it's not correct you can try again.
Good luck!
edit 1: The solution is NOT 1! edit 2: ds(solution) = 59
   
|
can't you just give me the key? i skiped school to play BW so i don't know math, could i just beat you 1v1 Destination BW for the key? its all i got
|
On May 02 2010 07:21 zealing wrote:can't you just give me the key? i skiped school to play BW so i don't know math, could i just beat you 1v1 Destination BW for the key? its all i got 
unfortunately, beating me in bw is anything but a challenge and thus I can't reward you with a beta key for that 
|
Bah, I wish a java SDE lying around, i could tell you in less than a minute :/
This is so easy if you have any programming thing lying around.
|
I might try to write a program to do this.
|
|
yes, writing a program is a good idea, but be aware that 10^18 is really big
|
Yeah, I'm not sure that would even fit in a long int.
|
On May 02 2010 07:27 Sadistx wrote: Bah, I wish a java SDE lying around, i could tell you in less than a minute :/
This is so easy if you have any programming thing lying around.
Nah it takes forever to do it, would have to find a complicated way of doing it, then rather just learn maths.
|
On May 02 2010 07:37 Shrine wrote: 11
wrong
|
|
|
On May 02 2010 08:00 Sharkified wrote: Is it a one try thing ?
On May 02 2010 07:18 yh8c4 wrote: Once I receive a solution, I'll reply whether it's correct or not. If it's not correct you can try again.
|
no, this is not limited to 1 try, but stop just posting or pming a single number. to receive the key you must have the correct answer AND an explanation why your answer is correct.
|
here's a little hint:
let cs be the correct solution. ds(cs) = 59.
|
|
On May 02 2010 08:08 Synthesis wrote:42. Source
That joke got old the first 1000 times people used it.
|
Hmmm, 137 | 10001, 99999999, and 10^12 + 1.
Might be useful?
Might be able to use that to cut down the numbers you have to search...
|
|
From what I understand, it will be a pretty big number, around 29000000000000000.
I have no means of actually solving this without getting a programming language that handles huge numbers and writing code for it.
I'm sure one of the math majors on here has a better way than brute forcing it.
|
|
On May 02 2010 08:24 Sadistx wrote: From what I understand, it will be a pretty big number, around 29000000000000000.
I have no means of actually solving this without getting a programming language that handles huge numbers and writing code for it.
I'm sure one of the math majors on here has a better way than brute forcing it.
that's a good start, the correct solution has the same number of digits 
|
On May 02 2010 08:26 Nemesis wrote: the answer is 59!
59! gives you a number that's more than 10^18 so its obviously wrong.
|
|
i think you can solve it by splitting it up into two overlapping pieces, an 10^11 size piece and a 10^10 size piece, write arrays for "certain values", and then calculate the number that sum to 0....
That shouldn't take too long...
edit: I forgot my comp can't store int arr[10000000000] 
Does anyone know how to store that?
edit2: nvm you only need to store long long arr[199];
|
just to be sure: do you mean the digital sum or the reduced digital sum (that is, applying the digital sum until the number is in the range 0-9)?
|
My source code is running but is taking quite some time
|
On May 02 2010 09:01 jannis wrote: just to be sure: do you mean the digital sum or the reduced digital sum (that is, applying the digital sum until the number is in the range 0-9)?
it says ds(solution) = 59, so I'm pretty sure it's digit sum...
|
On May 02 2010 09:01 jannis wrote: just to be sure: do you mean the digital sum or the reduced digital sum (that is, applying the digital sum until the number is in the range 0-9)?
ds(999) = 27
|
k I finished writing the program, and it should run in time, but it crashes...
do you accept it if we send you the code, without the answer, but with a description of how we tried to find the answer and why it should run in < a minute?
|
I PMed my answer and a description. Code runs in 1.128s on my box
|
On May 02 2010 09:18 Hamster1800 wrote:I PMed my answer and a description. Code runs in 1.128s on my box 

What was your code btw?
Mine:
#include<iostream> #include<stdlib.h>
using namespace std;
int digitSum(long long num);
int main(){ long long arr1[301][137]; long long arr2[301][137]; for(int i = 0; i < 301; i++){ for(int j = 0; j < 137; j++){ arr1[i][j] = arr2[i][j] = 0; } } for(long long i = 0; i < 100000000; i++){ long long num = digitSum((137 * i) % 1000000000) - digitSum(i); long long num2 = (137 * i) / 1000000000; arr1[150+num][num2]++; } for(long long i = 0; i < 1000000000; i++){ for(int j = 0; j < 137; j++){ int num = digitSum(137 * i + j) - digitSum(i); arr2[150+num][j]++; } } long long answer = 0; for(int i = 0; i <= 1000; i++){ for(int j = 0; j < 137; j++){ answer += arr1[i][j]*arr2[300 - i][j]; } } cout << answer << endl; return 0; }
int digitSum(long long num){ if(num == 0)return 0; return (num%10) + digitSum(num/10); }
|
On May 02 2010 09:11 Nehsb wrote: k I finished writing the program, and it should run in time, but it crashes...
do you accept it if we send you the code, without the answer, but with a description of how we tried to find the answer and why it should run in < a minute?
why do you think it should run in < 1 minute?
|
On May 02 2010 09:18 Hamster1800 wrote:I PMed my answer and a description. Code runs in 1.128s on my box 
I doubt it's your box, you either have an amazing or amazingly bad code. I have an i7-860 and it takes forever to run my code.
|
On May 02 2010 09:22 yh8c4 wrote:Show nested quote +On May 02 2010 09:11 Nehsb wrote: k I finished writing the program, and it should run in time, but it crashes...
do you accept it if we send you the code, without the answer, but with a description of how we tried to find the answer and why it should run in < a minute? why do you think it should run in < 1 minute?
NVM, sorry for some reason I thought my comp ran 200 billion operations per second.
my code probably is more efficient if you replace the arr1 thing with 10^10 and the arr2 thing witih 10^8
edit: that should be like.... (10^10 + 10^8 * 137) * a small number about efficiency?,
|
I calculated mine would take appromatively 1000 hours lol
Need to find a way to optimize this...
|
Okay, I got the key, so I'll just put the solution up for people who want to see + Show Spoiler + Answer = 20444710234716473
Solution is a dynamic programming algorithm. State is based on the last k digits of the number, lazily computing the digit sum of 137*x digit by digit, storing the next 4 digits to the left of the last k digits (using the fact that 9*137 + 99 < 10000). I iterate through the values of k from 0 to 17, increasing it by one each time (so that at the end we have the values for 18), computing the number of numbers x for which the next 4 digits to the left are "a" and the difference between ds(x) and ds(137*x) (up to the last k digits) is "b".
Code below: #include<cstdio> #include<cstdlib>
using namespace std;
int main() { long long **now, **next; now = new long long*[10000]; next = new long long*[10000]; for(int i = 0; i<10000; i++) { now[i] = new long long[401]; next[i] = new long long[401]; now[i] += 200; next[i] += 200; for(int j = -200; j<=200; j++) { now[i][j] = next[i][j] = 0; } } now[0][0] = 1; for(int i = 0; i<18; i++) { for(int j = 0; j<10000; j++) { for(int k = -200; k<=200; k++) { next[j][k] = 0; } } for(int a = 0; a<10000; a++) { for(int b = -162; b<=162; b++) { for(int d = 0; d<=9; d++) { int na = a/10 + 137*d, nb = b - a%10 + d; next[na][nb] += now[a][b]; } } } long long **t = now; now = next; next = t; } long long ans = 0; for(int i = 0; i<10000; i++) { for(int j = -200; j<=200; j++) { int a = i, b = j; while(a != 0) { b -= a%10; a/=10; } if(b == 0) { ans += now[i][j]; } } } printf("%lld\n",ans); }
|
Hamster1800 is the winner, his solution:
ok, the key is yours: xxxxxx-xxxx-xxxxxx-xxxx-xxxxxx have fun ----------------------------------------- Original Message: Sure thing 9090754242258600 1710153888867000 ----------------------------------------- Original Message: could you give me 2 examples for x for which ds(x) = ds(x * 137)? ----------------------------------------- Original Message: Answer = 20444710234716473 Solution is a dynamic programming algorithm. State is based on the last k digits of the number, lazily computing the digit sum of 137*x digit by digit, storing the next 4 digits to the left of the last k digits (using the fact that 9*137 + 99 < 10000). I iterate through the values of k from 0 to 17, increasing it by one each time (so that at the end we have the values for 18), computing the number of numbers x for which the next 4 digits to the left are "a" and the difference between ds(x) and ds(137*x) (up to the last k digits) is "b". Code below: #include<cstdio> #include<cstdlib>
using namespace std;
int main() { long long **now, **next; now = new long long*[10000]; next = new long long*[10000]; for(int i = 0; i<10000; i++) { now[i] = new long long[401]; next[i] = new long long[401]; now[i] += 200; next[i] += 200; for(int j = -200; j<=200; j++) { now[i][j] = next[i][j] = 0; } } now[0][0] = 1; for(int i = 0; i<18; i++) { for(int j = 0; j<10000; j++) { for(int k = -200; k<=200; k++) { next[j][k] = 0; } } for(int a = 0; a<10000; a++) { for(int b = -162; b<=162; b++) { for(int d = 0; d<=9; d++) { int na = a/10 + 137*d, nb = b - a%10 + d; next[na][nb] += now[a][b]; } } } long long **t = now; now = next; next = t; } long long ans = 0; for(int i = 0; i<10000; i++) { for(int j = -200; j<=200; j++) { int a = i, b = j; while(a != 0) { b -= a%10; a/=10; } if(b == 0) { ans += now[i][j]; } } } printf("%lld\n",ans); }
|
Congratz, you sir are a better programmer than I am.
|
Argh, I managed to hand count that number using combinatorics and on the verge of victory refresh to see a dynamic algorithm win.
edit: I used the ds(x) = 59 hint though. Good job hamster
|
|
congratulations, although the method is still not so clear to me
|
FREEAGLELAND26781 Posts
LOL HAMSTER. (I know that dude) Grats~
|
|
|
|
|