the_redback's blog

By the_redback, 2 years ago, In English,

Problem Link: LightOJ :: 1339 — Strongest Community.

I am getting Wrong Answer but i can't find any bug in my logic. Can someone help me with my idea or provide me some test case please? It will be very helpful for me....

Problem Description, My Idea & My Code has been given below.

Thanks.

Problem Description: In a strange city, houses are built in a straight line one after another. There are several communities in the city. Each community consists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.

Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community. That's why they are seeking your help.

Input: Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing three integers n (1 ≤ n ≤ 105), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.

Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j (inclusive).

Output: For each case, print the case number in a single line. Each of the next q lines should contain the number of houses that belong to the strongest community considering houses from i to j. The result should be listed in the same order as they are given in input.

Sample Input:

2

10 3 4
1 1 1 3 3 3 3 2 2 2
1 5
1 6
1 7
7 9

3 3 1
3 2 1
1 1

Output for Sample Input:

Case 1:
3
3
4
2
Case 2:
1

My Idea: I have implemented segment tree on community id.

I took all the query in a array named 'input' and sorted according the 'second' value. [ if, there are more points where second value is same, then point with lower value of 'first', will go before of other points (u can see in bool comp() function). ]

then I started the solution part: 'j' denotes the current position of input array, 'k' denotes last eliminated house no.
Starting from the house[0], I have increased the value of each house's community by +1. if any input[j].second is equal to 'i'th house then, I increased 'k' so that the value of 'k' is equal to input[j].first. While increasing 'k', I have added -1 to the community of 'k'th point, i.e. i have eliminated that house from consideration.

for each input[j] i took the result from tree[1] and stored it in 'ans' vector.

Then I sorted the answer according to query input id, and printed the answer. The logic should do the job, but yet it is giving me WA.

Can anyone help me finding where am i doing wrong?

My Code:


/** * @author : Maruf Tuhin * @College : CUET CSE 11 * @Topcoder : the_redback * @CodeForces : the_redback * @UVA : the_redback * @link : http://www.fb.com/maruf.2hin */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long llu; #define xx first #define yy second #define mp make_pair #define pb(x) push_back(x) #define all(x) x.begin(),x.end() #define allr(x) x.rbegin(),x.rend() #define mem(a,b) memset(a,b,sizeof(a)) #define inf 1e9 #define eps 1e-9 #define mod 1000000007 #define NN 100002 #define read(a) scanf("%lld",&a) /** */ struct D { ll x,y,in; D(ll X,ll Y,ll I) { x=X; y=Y; in=I; } D(){ } }input[NN]; ll tree[4*NN]; ll house[NN]; vector<pair<ll,ll> >ans; void update(ll node, ll low, ll high, ll in , ll value) { if(low==high && low==in ) { tree[node] =tree[node]+value; return; } ll left = node<<1; ll right = left + 1; ll mid = (low + high)>>1; if(in <= mid) update(left, low, mid,in, value); else update(right, mid+1, high, in, value); tree[node] = max(tree[left] , tree[right]); } bool comp(D a, D b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } int main() { //ios_base::sync_with_stdio(0); cin.tie(0); #ifdef redback freopen("C:\\Users\\Maruf\\Desktop\\in.txt","r",stdin); #endif ll t=1,tc; read(tc); ///Test case ll i,c,j,k,l,m,n; while(tc--) { read(n); read(c); read(m); mem(tree,0); for(i=1;i<=n;i++) { read(house[i]); } for(i=1;i<=m;i++) { read(k); read(l); input[i]=D(k,l,i); } sort(input+1,input+m+1,comp); ans.clear(); j=1; k=1; for(i=1;i<=n;i++) { update(1,1,c,house[i],1); while(j<=m && input[j].y==i) { while(k<input[j].x) { update(1,1,c,house[k],-1); k++; } ll res=tree[1]; ans.pb(mp(input[j].in,res)); j++; } } sort(all(ans)); printf("Case %lld:\n",t++); for(i=0;i<ans.size();i++) { printf("%lld\n",ans[i].yy); } } return 0; }

Read more »

 
 
 
 

By the_redback, 4 years ago, In English,

Hi everyone.....

Recently while practicing in TOPCODER SRM Practice Room , i realized my codes were tested by only PRETESTs.

So, is there any way exist to judge my code by Full System Test?

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it