# POJ3274-Gold Balanced 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.

sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=.....=sum[i][k-1]-sum[j][k-1] (j<i)

sum[i][1]-sum[i][0] = sum[j][1]-sum[j][0]

sum[i][2]-sum[i][0] = sum[j][2]-sum[j][0]

......

sum[i][k-1]-sum[i][0] = sum[j][k-1]-sum[j][0]

C[i][]==C[j][] 即二维数组C[][]第i行与第j行对应列的值相等，

`7 3`
`7`
`6`
`7`
`2`
`1`
`4`
`2`
` `

7 à 1 1 1

6 à 0 1 1

7 à 1 1 1

2 à 0 1 0

1 à 1 0 0

4 à 0 0 1

2 à 0 1 0

（行数为cow编号，自上而下从1开始；列数为特征编号，自左到右从0开始）

1 1 1

1 2 2

2 3 3

2 4 3

3 4 3

3 4 4

3 5 4

0 0 0 à 第0行

0 0 0

0 1 1

0 1 1

0 2 1

0 1 0

0 1 1

0 2 1

Source修正：

USACO 2007 March Gold

http://www.cppblog.com/Felicia/archive/2007/12/29/39923.html

官方对Hint的解释：

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.

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

*********************************************************************

` 1 //Memory Time 2 //44152K 1141MS  3  4 #include<iostream> 5 #include<cmath> 6 using namespace std; 7  8 const int size=100001; 9 const int mod=99991; 10  11 int feature[size][30]; //feature[i][j]标记第i只牛是否有特征j 12 int sum[size][30]; //从第1到第i只牛，特征j总共出现了sum[i][j]次 13 int c[size][30]; //c[i][j]=sum[i][j]-sum[i][0] , 即所有列都减去第一列后，值保存在c[][] 14 int N; //牛数量 15 int K; //特征数 16 int MaxLen; //最大距离 17  18 typedef class HASH 19 { 20 public: 21 int pi; //保存c[i][j]的行地址c[i]的下标i 22 class HASH* next; 23 HASH() 24 { 25 next=0; 26 } 27 }HashTable; 28  29 HashTable* hash[mod]; 30  31 /*检查c[ai][]与c[bi][]是否对应列相等*/ 32 bool cmp(int ai,int bi) 33 { 34 for(int j=0;j<K;j++) 35 if(c[ai][j]!=c[bi][j]) 36 return false; 37 return true; 38 } 39  40 void Hash(int ci) 41 { 42 int key=0; //生成关键字 43 for(int j=1;j<K;j++) 44 key+=c[ci][j]*j; 45 key=abs(key)%mod; //由于c[][]有正有负，因此key值可能为负数 46  47 if(!hash[key]) //新key 48 { 49 HashTable* pn=new HashTable; 50  51 pn->pi=ci; 52 hash[key]=pn; 53 } 54 else //key值冲突 55 { 56 HashTable* pn=hash[key]; 57  58 if(cmp(pn->pi,ci)) 59 { 60 int dist=ci-(pn->pi); 61 if(MaxLen<dist) 62 MaxLen=dist; 63 return; //由于pi与ci对应列数字相等，且pi地址必定比ci小 64 } //而要求的是最大距离，因此不需要保存ci，判断距离后直接返回 65 else 66 { 67 while(pn->next) 68 { 69 if(cmp(pn->next->pi,ci)) 70 { 71 int dist=ci-(pn->next->pi); 72 if(MaxLen<dist) 73 MaxLen=dist; 74 return; 75 } 76 pn=pn->next; 77 } 78  79 //地址冲突但c[][]各列的值不完全相同 80  81 HashTable* temp=new HashTable; 82 temp->pi=ci; 83 pn->next=temp; 84 } 85 } 86 return; 87 } 88  89 int main(void) 90 { 91 freopen("in.txt","r",stdin); 92 while(cin>>N>>K) 93 { 94 /*Initial*/ 95  96 for(int p=0;p<K;p++) 97 { 98 c[0][p]=0; //第0只牛的特征默认为全0 99 sum[0][p]=0;100 }101 102 memset(hash,0,sizeof(hash));103 Hash(0); //把第0只牛先放入哈希表104 MaxLen=0;105 106 /*Input*/107 108 for(int i=1;i<=N;i++)109 {110 int Dexf; //十进制特征数111 cin>>Dexf;112 113 for(int j=0;j<K;j++)114 {115 feature[i][j]=Dexf%2; //Dexf转换为逆序二进制116 Dexf/=2;117 118 sum[i][j]=sum[i-1][j]+feature[i][j];119 c[i][j]=sum[i][j]-sum[i][0];120 }121 122 Hash(i);123 }124 125 /*Output*/126 127 cout<<MaxLen<<endl;128 }129 return 0;130 }`

Sample Input

7 3
7
6
7
2
1
4
2

7 3
7 7 7 7 7 7 7

4 4
1
2
4
8

4 4
8
1
2
4

5 4
3
1
2
4
8

1 5
3

1 2
3

1 3
7

6 5
16
8
4
2
31

Sample Output

4
7
4
4
4
0
1
1
2