@Tian tanx
On Tue, Jul 9, 2013 at 5:55 PM, abhishek sharma <abhishek.p...@gmail.com>wrote: > Okay let me explain my approach - > > 1. Read numbers from the input stream and create an array of lists.. i > started with hashmaps and hashsets etc .. but they greatly killed > performance > > 2. Each index in the array holds the positions of that particular index(in > the stream) in a list..(I simply insert these positions in the list at > array[index]..) > > 3. Any such list (at any index in the array) is sorted at any given point > of time since the positions are only going to increase as we keep reading > input from stream.. > > 4. Once the input is read, iterate over this data store in the following > manner - > > Let result holds the answer > > for i: 1 to 300001 //>>>>>> Loop A > if(array[i].size > 2) > result += S(S-1)(S-2)/6 > for(j: 2*i-1 to i+1) > listRight = array[j] > listLeft = array[i - (j-i)] > for int x: array[i] > //use Collections.binarySearch > a = number of elements greater than x in listRight > c = listRight.size - a > b = number of elements less than x in listLeft > d = listLeft.Size - b > result += a*b > result += c*d// Explanation E > > return result once Loop A is done.. > > E = Suppose 6,.....,4.....,2 occur in the stream as well as 2...,4...,6 .. > I need to capture both these as they both form an AP > > To improve time, it is recommended(on CodeChef, it uses SPOJ) to use > BufferedReader when reading long inputs from console.. Hence I am using > that .. > > My SkypeID: abhishekpc87iit.. Feel free to contact me .. always online.. > > > On Tue, Jul 9, 2013 at 5:32 PM, Tian Guo <tian....@epfl.ch> wrote: > >> Can you just briefly describe your algorithm and time complexity? Then we >> could know the problem and think about from which perspective to improve it. >> >> Thx! >> >> >> 2013/7/9 abhishek sharma <abhishek.p...@gmail.com> >> >>> >>> Given *N* integers *A1, A2, …. AN*, Dexter wants to know how many ways >>> he can choose three numbers such that they are three consecutive terms of >>> an arithmetic progression. >>> >>> Meaning that, how many triplets *(i, j, k)* are there such that *1 ≤ i >>> < j < k ≤ N* and *Aj - Ai = Ak - Aj*. >>> >>> So the triplets (2, 5, 8), (10, 8, 6), (3, 3, 3) are valid as they are >>> three consecutive terms of an arithmetic progression. But the triplets (2, >>> 5, 7), (10, 6, 8) are not. >>> Input >>> >>> First line of the input contains an integer *N (3 ≤ N ≤ 100000)*. Then >>> the following line contains *N* space separated integers *A1, A2, …, AN*and >>> they have values between >>> *1* and *30000* (inclusive). >>> Output >>> >>> Output the number of ways to choose a triplet such that they are three >>> consecutive terms of an arithmetic progression. >>> Example >>> >>> *Input:* >>> 10 >>> 3 5 3 6 3 4 10 4 5 2 >>> *Output:* >>> 9 >>> >>> *I am attaching my solution..* I reached this solution after improving the >>> performance 10 times.. but it is still not accepted as the time limit >>> exceeds 3 seconds. >>> >>> >>> >>> Can anyone please please suggest how to improve this ... >>> (I do not want a different approach .. I want to improve my approach) >>> >>> PS: This is a practice problem .. So I am not cheating :) >>> >>> >>> -- >>> Nice Day >>> >>> Abhishek Sharma >>> Bachelor of Technology >>> IIT Kanpur (2009) >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+unsubscr...@googlegroups.com. >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> > > > > -- > Nice Day > > Abhishek Sharma > Bachelor of Technology > IIT Kanpur (2009) > -- Nice Day Abhishek Sharma Bachelor of Technology IIT Kanpur (2009) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
