tech-pandit's blog

By tech-pandit, 6 years ago, , plz help me with this D-query problem .  Comments (34)
 » 6 years ago, # | ← Rev. 5 →   there is simple NlogN offline solution: int posOfLast[2e6] = {-1, -1 ....}; int a[n]; int cnt[n]; // input for (int i = 0; i < n; ++i) { if (posOfLast[a[i]] != -1) cnt[posOfLast[a[i]]]--; posOfLast[a[i]] = i; cnt[posOfLast[a[i]]]++; for (all q in Queries where q.R == i) { sum = 0; // { this part can be done in O(Log(n)) // using Range Sum Query structure, or fenvick tree, or segment tree for (int j = q.L; j <= q.R; j++) sum += cnt[j]; // } ans[q.Id] = sum; } }
•  » » are you sure this will work ? like for input- 1 2 3 4 1 2after preprocessing cnt array will be like this cnt- 0 0 1 1 1 1so for query [1,5] your answer will be sum=0+0+1+1+1=3 but actual anser will be 4
•  » » » if indexes starts since 0, the sum will be 0+1+1+1+1==4. it seems it's right code.
•  » » » » What if the query was [1,1] — answer 0?!
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   just try it. implement & run code above, if you can't understand it. my version
•  » » wow,simple wow! such a beauty! :*
•  » » Thats a beautiful solution. Thanks
•  » » fokkinir put segment tree er code implement kore de -_- oi sob bal sal ami i pari
•  » » How can someone possibly think of such a solution unless he has solved a similar problem in past?
•  » » e-maxx.ru has it also
 » Since the problem's name contains the word "query" u had better use query-oriented language like SQL
 » Does anybody know how to solve this if you can change elements also?
•  » » Something similar to this.
•  » » It can be done in per query, for every two indices l, r such that l < r, al = ar and there is no such index x such that al = ax and l < x < r, store the 2D point (l, r) in some 2D data structure. The answer to a query is the length of the segment minus the number of points inside some rectangle. Which one, you may ask? This is left as an exercise for the reader!
•  » » this is the same problem that u are asking https://www.hackerrank.com/contests/algoelite-v18/challenges/escaping-black-holes-v18
 »
 » It can be solved online too with the same NLogn method using persistent segment tree that's how i did it
•  » » Can you provide some links where I can learn Persistent Segment Trees ??
•  » » »
 » Mo's Algorithm which runs in O(NsqrtN) works in time and is fairly easy to code. I used C++, so some slower languages may get TLE.
»

i am still getting tle

include<bits/stdc++.h>

using namespace std;

int main() { int n,p,count; scanf("%d",&n);

int a[n+1]; int pos={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; for(int m=1;m<=p;m++) { count=0; if(q[m].second==i) { for(int k=q[m].first;k<=q[m].second;k++) count+=cnt[k]; ans[m]=count; } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

•  » » you need to use a segment tree or a Fenwick tree to calculate sum from q[m].first to q[m].second in O(log n) time.
• »
»
»

it still is giving tle.

include<bits/stdc++.h>

using namespace std; int tree; void build(int node, int start, int end,int *cnt) { if(start == end) { // Leaf node will have a single element tree[node] = cnt[start]; } else { int mid = (start + end) / 2; // Recurse on the left child build(2*node, start, mid,cnt); // Recurse on the right child build(2*node+1, mid+1, end,cnt); // Internal node will have the sum of both of its children tree[node] = tree[2*node] + tree[2*node+1]; } } int query(int node, int start, int end, int l, int r) { if(r < start or end < l) { // range represented by a node is completely outside the given range return 0; } if(l <= start and end <= r) { // range represented by a node is completely inside the given range return tree[node]; } // range represented by a node is partially inside and partially outside the given range int mid = (start + end) / 2; int p1 = query(2*node, start, mid, l, r); int p2 = query(2*node+1, mid+1, end, l, r); return (p1 + p2); } int main() { int n,p,count; scanf("%d",&n);

int a[n+1]; int pos={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; build(1,1,i,cnt); for(int m=1;m<=p;m++) { if(q[m].second==i) { ans[m]=query(1,1,i,q[m].first,q[m].second); } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

•  » » » » 3 years ago, # ^ | ← Rev. 2 →   MO's algorithm + printf/scanf gives AC. Here is my code
 » I referred this article to make an editorial on the problem. It uses Mo's algorithm, which is offline query processing, to solve the problem in N*sqrt(N). Here is the video link.
•  » » gkcs with the help of your video link and the article you mentioned in your post I came up with a solution to this problem. I tried optimizing it further since its giving me TLE can you please look into my code and tell me where am I going wrong.
•  » » » Hi Prabal, I tried to submit my Java solution to this problem also, and it gave a TLE. The reason, I think, is not to do with the code being optimised. Spoj has very strict time limits, and so java code is difficult to get an AC with.I suggest you try another problem on codechef using the same Mo's algorithm: https://www.hackerearth.com/problem/algorithm/substrings-count-3/
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   Okay, Thanks! Any idea how can we solve Dquery xD
•  » » » » » it can be solved using both offline and online programming . i solved this problem using MO's algorithm and BIT .
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   If you have coded the solution in Java using MO's algorithm I would appreciate your help! :)
•  » » » » » » » i coded in c++ :) AC using Mo'S https://paste.ubuntu.com/24957700/ AC using BIT https://paste.ubuntu.com/24957711/ happy coding :) hope it'll help you .