I solved this problem but I got TLE Time Limit Exceed on online judge
the output of program is right but i think the way can be improved to be more efficient!
the problem :
Given n integer numbers, count the number of ways in which we can choose two elements such that their absolute difference is less than 32.
In a more formal way, count the number of pairs (i, j) (1 ≤ i < j ≤ n) such that
|V[i] - V[j]| < 32. |X| is the absolute value of X.
Input
The first line of input contains one integer T, the number of test cases (1 ≤ T ≤ 128).
Each test case begins with an integer n (1 ≤ n ≤ 10,000).
The next line contains n integers (1 ≤ V[i] ≤ 10,000).
Output
For each test case, print the number of pairs on a single line.
my code in c++ :
int main() { int T,n,i,j,k,count; int a[10000]; cin>>T; for(k=0;k<T;k++) { count=0; cin>>n; for(i=0;i<n;i++) { cin>>a[i]; } for(i=0;i<n;i++) { for(j=i;j<n;j++) { if(i!=j) { if(abs(a[i]-a[j])<32) count++; } } } cout<<count<<endl; } return 0; } I need help how can I solve it in more efficient algorithm ?
9 Answers
Answers 1
Despite my previous (silly) answer, there is no need to sort the data at all. Instead you should count the frequencies of the numbers.
Then all you need to do is keep track of the number of viable numbers to pair with, while iterating over the possible values. Sorry no c++ but java should be readable as well:
int solve (int[] numbers) { int[] frequencies = new int[10001]; for (int i : numbers) frequencies[i]++; int solution = 0; int inRange = 0; for (int i = 0; i < frequencies.length; i++) { if (i > 32) inRange -= frequencies[i - 32]; solution += frequencies[i] * inRange; solution += frequencies[i] * (frequencies[i] - 1) / 2; inRange += frequencies[i]; } return solution; } Answers 2
#include <bits/stdc++.h> using namespace std; int a[10010]; int N; int search (int x){ int low = 0; int high = N; while (low < high) { int mid = (low+high)/2; if (a[mid] >= x) high = mid; else low = mid+1; } return low; } int main() { cin >> N; for (int i=0 ; i<N ; i++) cin >> a[i]; sort(a,a+N); long long ans = 0; for (int i=0 ; i<N ; i++) { int t = search(a[i]+32); ans += (t -i - 1); } cout << ans << endl; return 0; } Answers 3
You can sort the numbers, and then use a sliding window. Starting with the smallest number, populate a std::deque with the numbers so long as they are no larger than the smallest number + 31. Then in an outer loop for each number, update the sliding window and add the new size of the sliding window to the counter. Update of the sliding window can be performed in an inner loop, by first pop_front every number that is smaller than the current number of the outer loop, then push_back every number that is not larger than the current number of the outer loop + 31.
Answers 4
One faster solution would be to first sort the array, then iterate through the sorted array and for each element only visit the elements to the right of it until the difference exceeds 31.
Sorting can probably be done via count sort (since you have 1 ≤ V[i] ≤ 10,000). So you get linear time for the sorting part. It might not be necessary though (maybe quicksort suffices in order to get all the points).
Also, you can do a trick for the inner loop (the "going to the right of the current element" part). Keep in mind that if S[i+k]-S[i]<32, then S[i+k]-S[i+1]<32, where S is the sorted version of V. With this trick the whole algorithm turns linear.
Answers 5
This can be done constant number of passes over the data, and actually can be done without being affected by the value of the "interval" (in your case, 32). This is done by populating an array where a[i] = a[i-1] + number_of_times_i_appears_in_the_data - informally, a[i] holds the total number of elements that are smaller/equals to i.
Code (for a single test case):
static int UPPER_LIMIT = 10001; static int K = 32; int frequencies[UPPER_LIMIT] = {0}; // O(U) int n; std::cin >> n; for (int i = 0; i < n; i++) { // O(n) int x; std::cin >> x; frequencies[x] += 1; } for (int i = 1; i < UPPER_LIMIT; i++) { // O(U) frequencies[i] += frequencies[i-1]; } int count = 0; for (int i = 1; i < UPPER_LIMIT; i++) { // O(U) int low_idx = std::max(i-32, 0); int number_of_elements_with_value_i = frequencies[i] - frequencies[i-1]; if (number_of_elements_with_value_i == 0) continue; int number_of_elements_with_value_K_close_to_i = (frequencies[i-1] - frequencies[low_idx]); std::cout << "i: " << i << " number_of_elements_with_value_i: " << number_of_elements_with_value_i << " number_of_elements_with_value_K_close_to_i: " << number_of_elements_with_value_K_close_to_i << std::endl; count += number_of_elements_with_value_i * number_of_elements_with_value_K_close_to_i; // Finally, add "duplicates" of i, this is basically sum of arithmetic // progression with d=1, a0=0, n=number_of_elements_with_value_i count += number_of_elements_with_value_i * (number_of_elements_with_value_i-1) /2; } std::cout << count; Working full example on IDEone.
Answers 6
You can sort and then use break to end loop when ever the range goes out.
int main() { int t; cin>>t; while(t--){ int n,c=0; cin>>n; int ar[n]; for(int i=0;i<n;i++) cin>>ar[i]; sort(ar,ar+n); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(ar[j]-ar[i] < 32) c++; else break; } } cout<<c<<endl; } } Or, you can use a hash array for the range and mark occurrence of each element and then loop around and check for each element i.e. if x = 32 - y is present or not.
Answers 7
This solution can be considered O(N) to process N input numbers and constant in time to process the input:
#include <iostream> using namespace std; void solve() { int a[10001] = {0}, N, n, X32 = 0, ret = 0; cin >> N; for (int i=0; i<N; ++i) { cin >> n; a[n]++; } for (int i=0; i<10001; ++i) { if (i >= 32) X32 -= a[i-32]; if (a[i]) { ret += a[i] * X32; ret += a[i] * (a[i]-1)/2; X32 += a[i]; } } cout << ret << endl; } int main() { int T; cin >> T; for (int i=0 ; i<T ; i++) solve(); } Solution explanation: a[i] represents how many times i was in the input series. Then you go over entire array and X32 keeps track of number of elements that's withing range from i. The only tricky part really is to calculate properly when some i is repeated multiple times: a[i] * (a[i]-1)/2. That's it.
Answers 8
You should start by sorting the input.
Then if your inner loop detects the distance grows above 32, you can break from it.
Answers 9
A good approach here is to split the numbers into separate buckets:
constexpr int limit = 10000; constexpr int diff = 32; constexpr int bucket_num = (limit/diff)+1; std::array<std::vector<int>,bucket_num> buckets; cin>>n; int number; for(i=0;i<n;i++) { cin >> number; buckets[number/diff].push_back(number%diff); } Obviously the numbers that are in the same bucket are close enough to each other to fit the requirement, so we can just count all the pairs:
int result = std::accumulate(buckets.begin(), buckets.end(), 0, [](int s, vector<int>& v){ return s + (v.size()*(v.size()-1))/2; }); The numbers that are in non-adjacent buckets cannot form any acceptable pairs, so we can just ignore them.
This leaves the last corner case - adjacent buckets - which can be solved in many ways:
for(int i=0;i<bucket_num-1;i++) if(buckets[i].size() && buckets[i+1].size()) result += adjacent_buckets(buckets[i], buckets[i+1]); Personally I like the "occurrence frequency" approach on the one bucket scale, but there may be better options:
int adjacent_buckets(const vector<int>& bucket1, const vector<int>& bucket2) { std::array<int,diff> pairs{}; for(int number : bucket1) { for(int i=0;i<number;i++) pairs[i]++; } return std::accumulate(bucket2.begin(), bucket2.end(), 0, [&pairs](int s, int n){ return s + pairs[n]; }); } This function first builds an array of "numbers from lower bucket that are close enough to i", and then sums the values from that array corresponding to the upper bucket numbers.
In general this approach has O(N) complexity, in the best case it will require pretty much only one pass, and overall should be fast enough.
0 comments:
Post a Comment