### Блог пользователя the_redback

Автор the_redback, 3 года назад, ,

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
*/

#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

/**

*/
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;
ll i,c,j,k,l,m,n;
while(tc--)
{

mem(tree,0);

for(i=1;i<=n;i++)
{
}
for(i=1;i<=m;i++)
{
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 года назад, # | ← Rev. 2 →   +3 I think you should also describe the problem here, because most of us don't have Light OJ ID.
•  » » 3 года назад, # ^ | ← Rev. 3 →   0 ok.... give me some time please......Edit: The description have been added now... Thank u :)
 » 3 года назад, # |   +3 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 года назад, # ^ |   0 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 года назад, # ^ |   0 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 года назад, # ^ | ← Rev. 2 →   0 yeah, i can "re-map" the communities actually..... that's a great help.....i am gonna try this idea.... :) thanks a lot.... :)
•  » » » » 3 года назад, # ^ |   0 Got Accepted with this idea. Thanks again. :)
 » 3 года назад, # |   +3 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 года назад, # ^ |   0 ow... Thanx... :) i will let you know if i faced any problem... :)
•  » » 13 месяцев назад, # ^ | ← Rev. 7 →   0 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.