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 :slight_smile:

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.

Here is the link to my solution: link.
There is also another solution given by kilicars in the “Discussions” tab which appears simple enough. Hope this helps :slight_smile:

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 :confused: XD

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

any penalities or score based ranking tommorow?

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

-@admin

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 :slight_smile: