HackerRank Goldman Sachs CodeSprint : F. Transaction Certificates

なんだこりゃ。
https://www.hackerrank.com/contests/gs-codesprint/challenges/transaction-certificates

問題

素数pと2の累乗である数mが与えられる。
n要素の数列aのハッシュ値はで計算できる。

p,mに加え、n,kが与えられる。
aをn要素でかつ各要素が[1,k]の範囲であるような数列とする。
ハッシュ値が衝突する数列を2つ生成せよ。

解法

適当に乱択しているとO(√m)回程度の試行で衝突するはずである。
数列生成の手間も加えても計算量はO(n√m)。

あとは何度かsubmitしていたら5回目ぐらいで通った。

int N,K,P;
ll M;

map<ll,vector<int>> V;
ll pp[1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	srand(time(NULL));
	cin>>N>>K>>P>>M;
	pp[0]=1;
	M--;
	FOR(i,N) pp[i+1]=(pp[i]*P)&M;
	
	
	while(1) {
		ll tot=0;
		ll p=1;
		vector<int> A;
		FOR(i,N) {
			x=rand()%(K-1)+1;
			A.push_back(x);
			ll y=(x*pp[i])&M;
			tot=(tot+y)&M;
		}
		reverse(ALL(A));
		if(V.count(tot)) {
			if(A==V[tot]) continue;
			FOR(i,N) _P("%d%c",A[i],(i==N-1)?'\n':' ');
			A=V[tot];
			FOR(i,N) _P("%d%c",A[i],(i==N-1)?'\n':' ');
			return;
		}
		V[tot]=A;
	}
}

まとめ

GSの業務と結び付けたかったのかもしれないけど、全体的に問題設定が回りくどくて好みではなかった…。