Thread: Help with implementing an algorithm!

Originally Posted by EVOEx

Are you sure that's the exact version you're using. Without the %lld it will show a 0 for the max, yes, but this version works just fine (on gcc at least). The results will fit in an unsigned int, so you can also convert it back to an unsigned int and display with "%d". But the solution is too slow to work properly. It's been running here for several minutes and the last line it displayed was "40391 57121"
But doing some more maths I managed to make it run in about 5 seconds.

Edit: 2.2 seconds, but I reckon it can be done even better with more math.

Yes, I copied it right from my Dev C++ opened file. Can you give me some hints of your mathematical work so I can do some research later on?

Ok, I got it now. The problem is that your division is including two ints that's why the rsult will be an int. So change all the variables to long double and in the division part change 2 to 2.0 everywhere. This will result in correct outputs.

You mean something like this!

Code:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[]){
             long double sum1, sum2;
             int count = 0;
             long double max = 8;
             long double temp = 0;
             long double house;
             while(count < 10){
                         temp =  (max * (max + 1) / 2.0);
                         for (house = 1.0 ; house <=max ; house++){
                             sum1 = house * (house - 1) / 2.0;
                             sum2 =temp - house - sum1; 
                             if (sum1 == sum2){
                                             printf("%lf\t%lf\n",house,max);
                                             count++;
                                             }
                             }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }

It outputs some very long negative doubles.

Originally Posted by EVOEx

Don't use doubles. It's wrong here. You get zeroes because apparently your compiler doesn't understand %lld. In gcc it works just fine. Find out how it works on your compiler, or convert to normal integers before outputting with %d, as I said before.

About my math, it started with your equation. Then I changed it to be easier to handle:

Code:

(n-1)*n / 2 = (m+1)*m/2 - (n-1)*n/2 - n
(n-1)*n + n = (m+1)*m/2
n*n = (m*m+m)/2

That should reduce the number of loops from two to one...

BEN10: there's no reason here to use floating point numbers. Because all the numbers actually are integers. Floating point numbers will only cause a possible lack in precision.

I have two loops because I need to keep track of how many lines to print, otherwise the program will crash.
Your formula doesn't reduce the number of loops in this case. It simplifies the calculations but doesn't helps outputting correct values.

Anyone?

Originally Posted by Leojeen

Anyone?

Okay, now let's say you square-root both sides of the equation. Then you have a way to calculate n given m. The other way around (calculating m given n) is faster, but a little bit harder to do. I'll leave that bit up to you.
So now you can CALCULATE n given m in stead of looping through all n's given m. That's a big difference.
(as a side note, n is the Number of the house and m is the Maximum number)

Ok, after doing some math, I made it efficient a little bit in terms of time. But still, the program fails to give me right answers after the 6th line. I think the unsigned long long is not enough.

Code:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
int isPerfectSquare(unsigned long long );
int main(int argc, char* argv[]){
             int count = 0;
             unsigned int max = 8;
             unsigned long long temp;
             while(count < 30){
                               temp = (max * (max + 1))/2;
                               if (isPerfectSquare(temp)){
                                  printf("%.0f\t%d\n",sqrt(temp),max);
                                  count++;
                               }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }
int isPerfectSquare(unsigned long long i){
                        int temp = sqrt(i);
                        return (temp*temp == i)?1:0;
    }

Don't mind the parsing warnings. I'm aware of them.

And once again you're doing maths with regular integers and only afterwards converting them to longs...

Yes, my mistake.

Code:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
int isPerfectSquare(unsigned long long );
int main(int argc, char* argv[]){
             int count = 0;
             unsigned long long max = 8;
             unsigned long long temp;
             while(count < 30){
                               temp = (max * (max + 1))/2;
                               if (isPerfectSquare(temp)){
                                  printf("%.0f\t%d\n",sqrt(temp),max);
                                  count++;
                               }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }
int isPerfectSquare(unsigned long long i){
                        int temp = sqrt(i);
                        return (temp*temp == i)?1:0;
    }

still blocks after the 6th lines. I had no idea how you did it in 2 seconds.

Originally Posted by Leojeen

Yes, my mistake.

Code:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>
int isPerfectSquare(unsigned long long );
int main(int argc, char* argv[]){
             int count = 0;
             unsigned long long max = 8;
             unsigned long long temp;
             while(count < 30){
                               temp = (max * (max + 1))/2;
                               if (isPerfectSquare(temp)){
                                  printf("%.0f\t%d\n",sqrt(temp),max);
                                  count++;
                               }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }
int isPerfectSquare(unsigned long long i){
                        int temp = sqrt(i);
                        return (temp*temp == i)?1:0;
    }

still blocks after the 6th lines. I had no idea how you did it in 2 seconds.

I gave you, before, the advice to not use int's in such programs (like programming contests) unless you have a very good reason for that. The reason is that it might be quite difficult to determine whether an integer must be long long or not. In normal programs you have to learn; in contests (if you are going to join a contest), don't bother, don't waste that time.

But my answer remains the same as it was. And I'm not going to repeat another answer in this topic. This is the last time I repeat myself (as I have done many times already):
"And once again you're doing maths with regular integers and only afterwards converting them to longs... "

Ok, I appreciate your help. I don't think repeating the same exact answer is that encouraging but I'll keep working on it. Maybe others will join.
I used unsigned long long everywhere. I don't see myself using integers to do the math.

Originally Posted by Leojeen

Ok, I appreciate your help. I don't think repeating the same exact answer is that encouraging but I'll keep working on it. Maybe others will join.
I used unsigned long long everywhere. I don't see myself using integers to do the math.

Code:

int isPerfectSquare(unsigned long long i){
                        int temp = sqrt(i);
                        return (temp*temp == i)?1:0;
    }

If you don't see an int variable here, then there's not really any help for you.