# Can anyone explain the problem Geometric Trick ?

In the recent Week of Code contest of Hackerrank, there was a problem Geometric Trick . Can anyone explain to me his/her approach, way of thinking and implementation? I was able to figure out the O(N^2) algorithm to pass 25% of test cases. But the O(NlogN) and O(N) solutions are going over my head. I cant understand the editorial either. I will appreciate if one of you guys can help me here

EDIT: One final bump before this thread gets lost in deep depths XD

1 Like

The editorial’s approach is rather complicated, I could not understand much either. Maybe I’ll sit with it later and try to figure it out, but here is my solution for now.

We have to find triples of (i, j, k), i < j < k such that j/i=k/j (1-indexed). Now let’s say that k/j=j/i=p/q, where p/q is the fraction in its lowest terms. Because k is an integer and i\times p^2/q^2=k, i must be divisible by q^2! So for each i I try to generate values q such that q^2 divides i. The next step is to generate values for p, with p>q. If k=i \times p^2/q^2 is within the array bounds and the S values at (i,\; i \times p/q,\; i \times p^2/q^2) have values (‘a’, ‘b’, ‘c’) or (‘c’, ‘b’, ‘a’), then we have a satisfactory triple. The only catch is that sometimes duplicate triples will be generated since some p/q obtained will be reducible. To deal with this we can use gcd to check whether p/q can be reduced further, and only increment the answer counter when it cannot.

There is also another solution given by kilicars in the “Discussions” tab which appears simple enough. Hope this helps

NOTE: Updated the answer, checking divisibility of i by q^2 now instead of q, don’t know why I didn’t think of this earlier. It’s much faster now.

2 Likes

Thanks a lot dear!!

That editorial gave me horrifying chills *shivers’

1 Like

i have one query can i ask regarding snackdown? @vijju123

Yeah, it mentions primes, sieve, hashes, what not!

@meooow -Exactly!! And the problem was said “Medium”. I felt my brain freeze when i read the second paragraph. IT was like…saying 'do this then hash that ’ and stuff as if its eating a cake XD

Whats your query vivek? You can always create a thread for yourself

any penalities or score based ranking tommorow?

“Hi, the Pre-Elimination Rounds will use Score Based Ranking system.”

Thats the official words. I think it will be similar to qualifier round in this case.

then what is role of penalities?
code submission time will not matter in round b?

I feel that penalities should not matter. They didnt matter even in qualifier. Well, if @admin said it, then its certainly official, and will be followed. Prepare likewise

//