the_redback's blog

By the_redback, 3 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; }
 
 
 
 

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I think you should also describe the problem here, because most of us don't have Light OJ ID.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    ok.... give me some time please......

    Edit: The description have been added now... Thank u :)

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think that you can answer queries online: for each query find the rightmost community that is completely inside the range, find the leftmost community that is completely inside the range(both with binary search), with a segment tree find the strongest community between the two communities that you have just found and check if the communities on the extremes of the range are stronger then those inside the range.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After getting the rightmost and leftmost community [completely inside the range], how to get the strongest community withing that range? suppose the houses community are: 4 4 4 4 1 1 2 2 3 3 5 5 6 6 . and, the query range are [2 3 3 5 5 6]. then taking 3 and 5 in consideration, how to get answer from seg tree without taking 4 in account?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You have to maintain communities in the order you read them from the input (I thought to compress them) and build the segment tree on the array of communities.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        yeah, i can "re-map" the communities actually..... that's a great help.....

        i am gonna try this idea.... :) thanks a lot.... :)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got Accepted with this idea. Thanks again. :)

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hacking test for your solution is:

1  
3 1 2  
1 1 1  
1 3  
2 2    

I tried another approach, more specifically this. My implementation. Hope it helps.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ow... Thanx... :) i will let you know if i faced any problem... :)

  • »
    »
    5 months ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    Even I use Mo's algorithm to solve this question, in addition, I do a binary search to find the larger number of occurrences, but I'm getting a W.A. I tried all the t.c. given in the forums and also in the U.V.Debug and my code satisfies for all those inputs. Here is my Code. Can u please tell me where I am going wrong or provide me a t.c. Thanks in advance.

    Edit: -Sorry I was doing a small mistake.Thanks for t.c. given.