Project Euler #228: Minkowski Sums

Sort by

recency

|

9 Discussions

|

  • + 1 comment

    Pretty weird problem. The failing tests, to be more specific. Similarly to jasonaboatman's situation, my solution works well for the original Project Euler problem#228. But for this (HackerRank) version, my solution solves only the first three (open) tests. Is there any chance that the remaining tests are wrong?

    • + 0 comments

      As a hint - do you happen to be allocating some amount of memory where the size is based on the inputs to the program? If you allocate too much memory the test will just fail as if though it produced the wrong answer.

  • + 0 comments

    You can graph your results in wolfram alpha if you want a quick way to visualize your progress (only works for 10 vertices, so only good for basics)

    polygon with vertices [(2.00,0.00),(1.00,1.00),(-0.50,1.87),(-1.50,0.87),(-1.50,-0.87),(-0.50,-1.87),(1.00,-1.00)]

    displays as: https://www.wolframalpha.com/input/?i=polygon+with+vertices+%5B(2.00,0.00),(1.00,1.00),(-0.50,1.87),(-1.50,0.87),(-1.50,-0.87),(-0.50,-1.87),(1.00,-1.00)%5D

    Python pseudocode:

    link = 'https://www.wolframalpha.com/input/?i=polygon+with+vertices+'+str(vertices).replace(" ", "")
    

    where vertices are an array of objects that have:

        def __repr__(self):
            x = '{:6.2f}'.format(self.x)
            y = '{:6.2f}'.format(self.y)
            return "("+x+","+y+")"
    
  • + 1 comment

    Like others, failing all but first 3 cases. I even tried to validate my process geometrically - seems right (but obviously issues exist).

    Any chance to get just one more semi-extreme test case to look at? Or, is not having those available part of the fun?

    • + 1 comment

      I'm in a similar, but slightly different situation -

      My solution written in Julia (and python3) solves the basic cases listed as well as the original Project Euler problem (compute the sum of S_1864 + ... S_1909), but fails most of the test cases. Some of them pass, some of them time-out, and most fail.

      Not quite sure what is wrong...

      • + 0 comments

        I figured it out - failures were due to using an integer type with too few bytes. Time outs are just simply due to my algorithm taking too long to compute. Now to come up with a better solution...

  • + 0 comments

    Greetings Khalid,

    Could you please upload an explaination with different number of quries to help better explain the problem.

    Regards.

  • + 2 comments

    result = (summation from L to R) - (R - L); = ((R(R + 1)/ 2) - ((L - 1)(L)/2)) - (R - L); = (R(R-1)/2) - (L(L - 1)/ 2) + L; = L + ((R(R-1) - L(L-1))/2);

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    
    int main()
    {
        int q;
        unsigned long L, R;
        unsigned long result = 0;
        scanf("%d", &q);
        
        while(q > 0)
        {
            scanf("%ld %ld", &L, &R);
            if(L >= 3 && R > 3 && L < R)
                result = L + (((R * (R - 1)) - (L * (L - 1))) / 2);
            printf("%ld\n", result);
            q--;
        }
        return 0;
    }
    

    Only the testcase 0, 1, 2 are passing.. All other testcases are failing.. Please let us know the usecases..

    • + 0 comments

      i got through the sample test cases just with this code -_- i know its not the logic but i just used image explanation to formulate the idea.

      #include <stdio.h>
      #include <string.h>
      #include <math.h>
      #include <stdlib.h>
      
      int main() {
      
          /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
          unsigned long n,a,b;
          unsigned long sum=0;
          scanf("%lu",&n);
          for(unsigned long i=0;i<n;i++)
          {
              scanf("%lu %lu",&a,&b);
        
              for(unsigned long j=a;j<=b;j++)
              {
                  sum+=j;
              }
              printf("%lu",(sum-(b-a)));
          }
          return 0;
      }
      
    • + 0 comments

      I am also facing the same problem