|
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
|
FREEAGLELAND26782 Posts
LOL HAMSTER.
(I know that dude)
Grats~
|
|
|
|
|
|
|
|
EPT
