Gold Balanced Lineup [Brian Dean, 2007]

Farmer John's N cows (1 <= N <= 100,000) share many similarities. In fact, FJ has been able to narrow down the list of features shared by his cows to a list of only K different features (1 <= K <= 30). For example, cows exhibiting feature #1 might have spots, cows exhibiting feature #2 might prefer C to Pascal, and so on. FJ has even devised a concise way to describe each cow in terms of its "feature ID", a single K-bit integer whose binary representation tells us the set of features exhibited by the cow. As an example, suppose a cow has feature ID = 13. Since 13 written in binary is 1101, this means our cow exhibits features 1, 3, and 4 (reading right to left), but not feature 2. More generally, we find a 1 in the 2^(i-1) place if a cow exhibits feature i. Always the sensitive fellow, FJ lined up cows 1..N in a long row and noticed that certain ranges of cows are somewhat "balanced" in terms of the features the exhibit. A contiguous range of cows i..j is balanced if each of the K possible features is exhibited by the same number of cows in the range. FJ is curious as to the size of the largest balanced range of cows. See if you can determine it. PROBLEM NAME: lineup INPUT FORMAT: * Line 1: Two space-separated integers, N and K. * Lines 2..N+1: Line i+1 contains a single K-bit integer specifying the features present in cow i. The least-significant bit of this integer is 1 if the cow exhibits feature #1, and the most-significant bit is 1 if the cow exhibits feature #K. SAMPLE INPUT (file lineup.in): 7 3 7 6 7 2 1 4 2 INPUT DETAILS: The line has 7 cows with 3 features; the table below summarizes the correspondence: Feature 3: 1 1 1 0 0 1 0 Feature 2: 1 1 1 1 0 0 1 Feature 1: 1 0 1 0 1 0 0 Key: 7 6 7 2 1 4 2 Cow #: 1 2 3 4 5 6 7 OUTPUT FORMAT: * Line 1: A single integer giving the size of the largest contiguous balanced group of cows. SAMPLE OUTPUT (file lineup.out): 4 OUTPUT DETAILS: In the range from cow #3 to cow #6 (of size 4), each feature appears in exactly 2 cows in this range: Feature 3: 1 0 0 1 -> two total Feature 2: 1 1 0 0 -> two total Feature 1: 1 0 1 0 -> two total Key: 7 2 1 4 Cow #: 3 4 5 6

Gold Balanced Lineup – ბადურ კერძაიას თარგმანი

ფერმერი ჯონის N (1 <= N <= 100,000) ძროხას აქვს ბევრი მსგავსება. ფაქტობრივად, ფერმერ ჯონს შეუძლია შეამციროს საკუთარი ძროხების მსგავსების სია K (1 <= K <= 30) განსხვავებულ მახასიათებლების სიით. მაგალითად, #1 თვისებას წარმოადგენენ ძროხები, რომელსაც აქვთ ლაქები, #2 -ს ისეთი ძროხები, რომლებსაც C ურჩევნიათ Pascal-ს და ა.შ. თითოელი ძროხის "მახასიათებელი ID"-ის ასაღწერად, ფერმერმა ჯონსმა მოიფიქრა შემდეგი გზა, K-ბიტური მთელი რიცხვი, რომლის ორობითი ჩანაწერი წარმოადგენს ძროხის მახასიათებლების სიმრავლეს. მაგალითად ძროხას აქვს მახასიათებელი ID = 13, რომლის ორობითი ჩანაწერი არის 1101, რაც ნიშნავს, რომ ჩვენ ძროხას აქვს მახასიათებლები 1, 3 და 4 (მარჯვნიდან მარცხნივ), მაგრამ არა მე-2 მახასიათებელი. უფრო ზოგადად, თუ ძროხას აქვს i მახასიათებელი, მაშინ ორობითი ჩანაწერის 2^(i-1) ადგილას იქნება 1. მუდამ მგრძნობიარე ფერმერი ჩაამწკრივებდა ხოლმე ძროხებს 1-დან N-მდე და ამჩნევდა, რომ გარკვეული რაოდენობა ძროხებისა დაბალანსებული იყო მათი მახასიათებლების მიხედვით. მოსაზღვრე ძროხების ჯგუფი i..j დაბალანსებულია იმ შემთხვევაში თუ თითოეული ამ K შესაძლო მახასიათებლიდან ვლინდება ერთსა და იმავე რაოდენობის ძროხაში. იპოვეთ უდიდესი ბალანსირებული ჯგუფის ზომა. სახელი: ჩამწკრივება შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ორი მთელი რიცხვი N და K. შემდეგ N სტრიქონში შემოდის K-ბიტური მთელი რიცხვი, რომელიც წარმოადგენს მე-i ძროხის მახასიათებლებს. ყველაზე მარჯვნიმ მდებარე ბიტი არის 1 თუ ძროხას აქვს #1 მახასიათებელი, და ყველაზე მარცხნივ მდებარე ბიტი არის 1 თუ ძროხას აქვს #K მახასიათებელი. შესატანი მონაცემის ნიმუში (ფაილი lineup.in): 7 3 7 6 7 2 1 4 2 შესატანი მონაცემების დეტალები: მოცემულია 7 ძროხა 3 მახასიათებლით. მახასიათებელი 3: 1 1 1 0 0 1 0 მახასიათებელი 2: 1 1 1 1 0 0 1 მახასიათებელი 1: 1 0 1 0 1 0 0 სია: 7 6 7 2 1 4 2 ძროხა #: 1 2 3 4 5 6 7 გამოსატანი მონაცემები: ერთი მთელი რიცხვი, უდიდესი მოსაზღვრე ბალანსირებული ძროხების ჯგუფის ზომას. შესაბამისი გამოსატანი მონაცემი (ფაილი lineup.out): 4 გამოსატანი მონაცემების დეტალები: ჯგუფში ძროხა #3 -დან ძროხა #6 -მდე (4 ზომის) თითოეული მახასიათებელი აქვს ზუსტად 2 ძროხას ამ ჯგუფში: მახასიათებელი 3: 1 0 0 1 -> ჯამში ორი მახასიათებელი 2: 1 1 0 0 -> ჯამში ორი მახასიათებელი 1: 1 0 1 0 -> ჯამში ორი სია: 7 2 1 4 ძროხა #: 3 4 5 6

lineup

Consider the partial sum sequence of each of the k features built by taking the sum of all the values up to position i. The problem is equivalent to: Given an array s[n][k], find i,j, with the biggest separation for which s[i][l]-s[j][l] is constant for all l. The problem is now to do this efficiently. Notice that s[i][l]-s[j][l] being constant for all l is equivalent to s[i][l]-s[j][l]=s[i][1]-s[j][1] for all l, which can be rearranged to become s[i][l]-s[i][1]=s[j][l]-s[j][1] for all l. Therefore, we can construct another array a[n][k] where a[i][j]=s[i][j]-s[i][1] and the goal is to find i and j with the biggest separation for which a[i][l]=a[j][l] for all l. This can be done by sorting all the a[i] entries, which takes O(nklogn) time (although in practice rarely will all k elements be compared). Another alternative is to go by hashing, giving an O(nk) solution. Both solutions are fairly straightforward once the final array is constructed. Here is a hashing solution (by Richard Peng): #include <stdio.h> #include <string.h> int h[1000000],hsize,lis[100001][30],n,k; int findid(int v[30]){ int i,p,can,i1; for(p=0,i=0;i<k;i++) p=((p<<2)+(v[i]>>4))^(v[i]<<10); p=p%hsize; if(p<0) p+=hsize; for(can=0;(!can)&&(h[p]!=-1);p++) for(i1=h[p],can=1,i=0;(can)&&(i<k);i++) can=(v[i]==lis[i1][i]); if(can) p--; return p; } main(){ int i,i1,j,ans,p,same,tem,shif,a; freopen("lineup.in","r",stdin); freopen("lineup.out","w",stdout); hsize=997001; for(i=0;i<1000000;i++) h[i]=-1; for(scanf("%d%d",&n,&k),k--,i=0;i<k;lis[0][i]=0,i++); h[findid(lis[0])]=0; for(ans=0,i=1,i1=0;i<=n;i++,i1++){ scanf("%d",&a); for(shif=a%2,a=(a>>1),j=0;j<k;j++,a=(a>>1)) lis[i][j]=lis[i1][j]+(a%2)-shif; p=findid(lis[i]); if(h[p]==-1) h[p]=i; if((tem=i-h[p])>ans) ans=tem; } printf("%d\n",ans); return 0;

Lineup – ბადურ კერძაიას თარგმანი

ვთქვათ, ნაწილობრივი ჯამის მიმდევრობა თითოეული k მახასიათებლისთვის აიგება i პოზიციამდე ყველა სიდიდის ჯამით. ეს პრობლემა ექვივალენტულია შემდეგის: მოცემულია მასივი s[n][k], იპოვე უდიდესი დაშორების i,j, რომლისთვისაც s[i][l]-s[j][l] არის მუდმივი ყველა l-სთვის. ახალი პრობლემა არის ის რომ ეს უნდა გაკეთდეს გონივრულად. s[i][l]-s[j][l] რომ იყოს მუდმივი ყველა l-ისთვის იგივეა, რაც s[i][l]-s[j][l]=s[i][1]-s[j][1] ყველა l-სთვის, რომელიც რომ გადანავაცვლოთ მივიღებთ s[i][l]-s[i][1]=s[j][l]-s[j][1] ყველა l-სთვის. ასე რომ, შეგვიძლია ავაგოთ სხვა მასივი a[n][k] სადაც a[i][j]=s[i][j]-s[i][1] და მიზანი არის ვიპოვოთ უდიდესი დაშორების i, j, სადაც a[i][l]=a[j][l] ყველა l-სთვის. ეს შეიძლება გაკეთდეს ყველა a[i] წევრის დალაგებით, რომელიც იმუშავებს O(nklogn) დროში (თუმცა პრაქტიკულად იშვიათად შედარდება ყველა k ელემენტი). ალტერნატიული გზა არის ჰეშირება, რომელიც გვაძლევს O(nk) ამოხსნას. ქვემოთ მოცემულია ამოხსნა სორტირების გამოყენებით. #include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; pair<unsigned long long, int> a[100001]; int main(){ int N,K; scanf("%d %d",&N,&K); vector<int> aux(K,0); a[0] = make_pair(0,0); for(int i = 0,x;i < N;++i){ scanf("%d",&x); for(int j = 0;j < K;++j) if(x & (1 << j)) ++aux[j]; int mn = aux[0]; for(int j = 1;j < K;++j) mn = min(mn,aux[j]); for(int j = 0;j < K;++j) aux[j] -= mn; unsigned long long H = 0; for(int j = 0;j < K;++j) H = H * 100005 + aux[j]; a[i + 1] = make_pair(H,i + 1); } sort(a,a + (N + 1)); int ans = 0; for(int i = 0;i < N + 1;){ int e = i; while(e < N + 1 && a[e].first == a[i].first) ++e; ans = max(ans,a[e - 1].second - a[i].second); i = e; } printf("%d\n",ans); return 0; }

Here is a hashing solution (by Richard Peng)

#include <stdio.h>
#include <string.h>

int h[1000000],hsize,lis[100001][30],n,k;

int findid(int v[30]){
	int i,p,can,i1;
	for(p=0,i=0;i<k;i++)
		p=((p<<2)+(v[i]>>4))^(v[i]<<10);
	p=p%hsize;
	if(p<0)	p+=hsize;
	for(can=0;(!can)&&(h[p]!=-1);p++)
		for(i1=h[p],can=1,i=0;(can)&&(i<k);i++)
			can=(v[i]==lis[i1][i]);
	if(can)	p--;
	return p;
}

main(){
	int i,i1,j,ans,p,same,tem,shif,a;
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	hsize=997001;
	for(i=0;i<1000000;i++)	h[i]=-1;
	for(scanf("%d%d",&n,&k),k--,i=0;i<k;lis[0][i]=0,i++);
	h[findid(lis[0])]=0;
	for(ans=0,i=1,i1=0;i<=n;i++,i1++){
		scanf("%d",&a);
		for(shif=a%2,a=(a>>1),j=0;j<k;j++,a=(a>>1))
			lis[i][j]=lis[i1][j]+(a%2)-shif;
		p=findid(lis[i]);
		if(h[p]==-1)	h[p]=i;
		if((tem=i-h[p])>ans)	ans=tem;
	}
	printf("%d\n",ans);
	return 0;
}