Your solution complexity is roughly O(N^2 + N*Log N), that’s why you are getting TLE.
P.S: Log N factor due to std::multiset.
Did you mean O(n * (n + logn)) ?
1 Like
Thanks.
1 Like
Problem EURON
I have used pbds data structure for the problem.
My code is working fine on sample test cases.
Can anyone tell me where I am going wrong.
Here is link to my code.
the test cases also consist of duplicate elements, so pbds ordered set will not work , you have to change one template of tree from less to less_equal , by this it will work as multiset. You can check my solution, I have also used pbds…
Here is my soln my code
1 Like
I followed the same approach of question 4 as given in hint but still getting TLE. please tell me where it went wrong. CodeChef: Practical coding for everyone
Iam getting wrong answer on problem EURON . Its working correctly on sample test case. Could anyone help me regarding this. Where iam doing wrong?
See my solution here
replace int with ll (long long)
@rishup_nitdgp can you please look at my code …(Giving WA)
https://www.codechef.com/viewsolution/33603451
My logic is since in the given constraints qi ranges form 1 to 10000 that is we are not going to ask the minimum element 100001 or more…so we can just sort the given input array and take the sum of just 100 values from first array with the 100 element of second array and store it in vector effectively I am just caluclating the 10000 sums and then answering the queries in o(1) time.
I am implementing the same approach as given in hints but it’s still giving TLE in problem LOWSUM
Here is my code.
How can I make it more efficient
Can anyone help me in Problem ASHIGIFT . My solution got accepted when i used binary search range [1,sum+5] where sum=sum of y[i] . But i got WA in one test when i used binary search range [1,10^18+5].
Accepted Solution
Wrong solution
Help me in overflow understanding
Can anyone explain why my logic is not working for problem EURON? My solution: CodeChef: Practical coding for everyone
What i am trying to do here is, for every index i am calculating the no. of elements greater than a[i] (which are present at left of a[i]) and adding to the answer and keep inserting a[i] in sorted vector at desired index so that vector remains sorted.
y i am still getting the time limit exceeded in the question LOWSUM although i have implemeented the strategy of the hints The link of my solution is in this link…pls tell me where Iam doing wrong
Can someone say why am i getting TLE for LOWSUM
here is a link to my solutin
https://www.codechef.com/viewsolution/34684326
In the problem EURON, what is the maximum value count can take given the array size int n
Should it not be 2n, in the case of strictly decreasing array?
How to solve LOWSUM using binary search? Getting TLE
Answer = sum of ans[i] from 1 to cnt - sum of ans[i]ans[i] from 1 to (l-1) + (R-k)(R+1) - (R(R+1)/2 - L*(L-1)/2)).
What does "(R-k)(R+1) - (R(R+1)/2 - L*(L-1)/2)).
" this part of the equation accomplish in the problem Count Substring?
1 Like
It’s a very elegant problem. My solution executed in 0.04 seconds. The key to solving it is:
1 ≤ qi ( for i = 1 to Q ) ≤ 10000
This means NO query will be for something greater than 10000 position. Note, it is possible to generate 20000*20000 = 400000000 possible values. We are only interested in the first 10000 or so.
So here is how we proceed.
Step 1: Sort both Inputs.
Step 2: What is the minimum possible number that can be generated - A[0] +B[0]. Max is A[n-1]+B[n-1].
Step 3: Now for a given sum S, try to binary search down the possible ways to generate a number below it. So if we are trying to generate the number 100 or lesser, and the first five elements of array A are 10, 20, 30, 40, 50… we can find out the number of elements in array B less than 90,80,70,60 etc. Add these counts. The moment this count exceeds 10000, we can safely say that “100” is too large and lower our search range.
Step 4: Based on above analysis, let us say we have narrowed down 60 that produces over 10000 numbers - but not MUCH more than that. So now go ahead and generate those 10000 numbers and store them ina vector.
Step 5. Simply do offline queries to get answers.
Operative part of code below:
#define int long long int
pair<int,int> number_elements(int A[], int B[], int n, int qry, int targ, int old_targ)
{
int ans = 0;
int A_lt = lower_bound(A, A+n, targ) - A;
for (int i = 0; i < A_lt; ++i)
{
ans += lower_bound(B, B+n, targ-A[i]) - B;
if(ans > qry)
{
return (number_elements(A, B, n, qry, targ/2, targ));
break;
}
}
return(make_pair(targ, old_targ));
}
vector<int> enumerate_solve(int A[], int B[], int n, int targ, int qry)
{
vector<int> ans;
for(int i = 0; i < n; ++i)
{
if(A[i] > targ)
{
break;
}
for(int j = 0; j <n ; ++j)
{
if(A[i]+B[j] <= targ)
{
ans.push_back(A[i]+B[j]);
}
else
{
break;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
vector<int> solve(int A[], int B[], int n, int qry)
{
int minv = A[0] + B[0];
int maxv = A[n-1] + B[n-1];
int midv = minv + (maxv-minv)/2;
pair<int,int> ans = number_elements(A, B, n, qry, maxv, maxv);
return(enumerate_solve(A, B, n, ans.ss, qry));
}
int32_t main()
{
kpr; int t; cin >> t;
while(t--)
{
int k, q; cin >> k >> q; int A[k], B[k];
for (int i = 0; i < k; ++i)
{
cin >> A[i];
}
for (int i = 0; i < k; ++i)
{
cin >> B[i];
}
sort(A, A+k); sort(B, B+k);
int queries[q];
int maxQ = 0;
for (int i = 0; i < q; ++i)
{
cin >> queries[i];
maxQ = max(maxQ, queries[i]);
}
vector<int> precomp = solve(A, B, k, maxQ);
for (int i = 0; i < q; ++i)
{
print(precomp[queries[i]-1]);
}
}
return 0;
}
1 Like
3 Likes