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

    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?

  • + 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..