You are not logged in. Please login at www.codechef.com to post your questions!

×

GPTRIPLE - Editorial

PROBLEM LINK:

Practice

Contest

Author: Akshay Venkataramani

Tester: Timothy Jeyadoss

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming, STL, Geometric Progression basics

EXPLANATION:

First up, we have corner case when k=1. For this, we simply have to store each element in a map, and if number of occurences of any value is >=3 , let the no. of occurences be n. We have nC3 (recall combinations formula? ) possible ways to choose our triplet. nC3 = (n(n-1)(n-2))/6.

Otherwise, we need to incorporate dynamic programming into our solution.

Let us have 3 maps, m1, m2 , m3 , each storing the number of possible ways for a value to be the first term of our GP, second term of our GP, and third term of our GP respectively.

For example, if input is N=6, K=2, and the input array A=[1,1,2,2,4,8]

m1

m1 will be equal to {1,2} , {2,2} , {4,1} , {8,1} . i.e., each term along with the number of ways in which it can be the first term of our GP. Each of these pair of values are present inside m1. {1,2} denotes that 1 can be the first term of our GP in 2 distinct ways. {2,2} denotes that 2 can be the first term of our GP in 2 distinct ways. Similarly, 4 and 8 can be the first term of our GP respectively. For this step, m1[a[i]]++ would do the job.

m2

m2 will be equal to {2,4} , {4,2}, {8,1} IMPORTANT STEP : This is because, 2 can be the second term of our GP in the following ways->choosing first 1, first 2; choosing first 1, second 2; choosing second 1,first 2; Choosing second 1, second 2; Hence, we have the pair {2,4} inside m2.

Similarly, we can perform the same steps for first term of our GP being 2 and second term being 4. There are 2 ways in which 4 can be the second term of our GP-> choosing first 2, and 4; choosing second 2, and 4; Hence, we have the pair {4,2} inside m2.

For 8 being the second term in our GP, we have one way -> choosing the only 4 and only 8. Hence we have a pair {8,1} in m2.

This step, can be performed in our code simply by checking if a[i]%k equates to 0. If this is possible, it means a[i] can be the second member of our GP (recall that, if the three terms of our GP are gp[1] , gp[2] and gp[3] , then gp[2]/gp[1] = k and gp[3]/gp[2] = k). Therefore, if a[i]%k is 0, we can have a[i] as the 2nd term of our GP for every a[i]/k being the first term of our GP.

m3

m3 will be equal to {4,4} , {8,2}. This is because, we have 4 ways in which 4 can be the third and final term of our GP , i.e., each combination of {1,2} mentioned in previous step appended with a 4. Similary, 8 can be the third term of our GP in 2 ways , i.e., each combination of {2,4} mentioned in previous step appended with an 8.

This step can again be performed code wise, by checking if (a[i]%(k2)) is 0. If this is the case, we can have a[i] as the third term of our GP, for every a[i]/k being the second term of our GP. This is where dynamic programming comes into picture.

Hence, in the end, we traverse m3 (Since we need a triplet of GP terms) , and add the value to the answer.

Corner case!! When m3 has a value 0, there's a chance that it would have considered the same 0 as first, second and third term of the GP. We need to subtract those possibilities from the overall answer carefully. For example, if our array had only one zero present in the input, there would still be an entry {0,1} in m3. This needs to be taken care of properly. [refer author's solution!]

AUTHOR'S SOLUTION:

Author's solution can be found here.

asked 21 Jan, 17:23

akshayvenkat97's gravatar image

5★akshayvenkat97
1.1k416
accept rate: 0%

edited 05 Feb, 13:55

admin's gravatar image

0★admin ♦♦
19.5k348496535


This can be done with a single map(for co-ordinate compression).

Check my solution

link

answered 21 Jan, 17:51

sdssudhu's gravatar image

6★sdssudhu
992310
accept rate: 14%

Yes ofcourse. But we had to present a simple solution for easy understanding! Good thinking, btw! :)

(21 Jan, 18:47) akshayvenkat975★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,038
×1,912
×1,544
×275
×29
×6

question asked: 21 Jan, 17:23

question was seen: 332 times

last updated: 05 Feb, 13:55