Hỏi bài trên HackerRank: Bit Array

ntanh · September 20, 2016, 8:59am

You are given four integers: N, S, P, Q. You will use them in order to create the sequence a with the following pseudo-code.

a[0] = S (modulo 2^31)
for i = 1 to N-1
    a[i] = a[i-1]*P+Q (modulo 2^31)

Your task is to calculate the number of distinct integers in the sequence a.

Input Format

Four space separated integers on a single line N, S, P and Q respectively.

Output Format

A single integer that denotes the number of distinct integers in the sequence a.

Constraints
1 <= N <= 10^8
0 <= S, P, Q < 2^31

Sample Input
3 1 1 1

Sample Output
3

Explanation
a = [1, 2, 3]
Hence, there are 3 different integers in the sequence.
o0o

Bạn nào hiểu thì giải thích lại dùm mình.

tntxtnt · September 20, 2016, 1:38pm

Cho 4 số nguyên N, S, P, Q. Tạo N số a_i với quy luật:

a₀ = S
a_i = ( P×a_i-1 + Q ) % 2³¹

Hỏi trong N số a_i đó có bao nhiêu số khác nhau đôi một (distinct integers)?

Ràng buộc:
1 ≤ N ≤ 10⁸
1 ≤ S, P, Q < 2³¹

cái tên của bài là Bit Array nghĩa là gợi ý xài mảng bit. Với quy luật trên thì ta có 0 ≤ a_i < 2³¹ (vì a_i có % 2³¹) thì tối đa có 2³¹ số khác nhau đôi một. Nếu tạo 1 `set` rồi mỗi lần sinh ra a_i thì cho a_i vào set này thì sẽ ngốn ram rất nhiều vì size của set có thể lên tới 2 tỷ phần tử => vài chục GB RAM. Cách giải là tạo mảng bit `a` gồm 2³¹ phần tử luôn, mỗi phần tử chỉ chiếm 1 bit => 2³¹ phần tử chỉ chiếm 256MB RAM. Mỗi lần sinh a_i thì gán `a[i] = 1`. Sau đó nếu tại vị trí i nào mà `a[i]==0` thì a_i ko xuất hiện trong dãy số trên. Từ đó đếm được số lương số khác nhau đôi một.

ntanh · September 21, 2016, 8:48am

Mình làm mà nó chỉ pass test case mẫu, còn các test case khác thì fail
Bạn có thể coi qua bài mình làm và chỉ ra chỗ sai của mình. Cám ơn !

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef unsigned int UINT;

int main() {
	UINT N, S, P, Q;
	const UINT p231 = static_cast<UINT>(pow(2, 31));
	cin >> N >> S >> P >> Q;
	int *a = new int[p231/32];
	memset(a, 0, sizeof(int)*(p231/32));
	a[0] = S % p231;
	for (int i = 1; i < N; i++)
	{
		a[i] = (a[i - 1] * P + Q) % p231;
	}
	int result = 0;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 1; j < N; j++)
		{
			if (a[i] != a[j])
				result++;
		}
	}
	cout << result << endl;
    return 0;
}

qloved · September 21, 2016, 2:57pm

Bài mình làm bằng code java

public static void main(String[] args) {
    int N = 3;
    int S = 1;
    int P = 1;
    int Q = 1;
    int moduloShift = Integer.MAX_VALUE; // 2^31 - 1
    BitSet bitSet = new BitSet();
    long aiMinus1 = S; // use long to prevent number overflow
    long ai; // use long to prevent number overflow
    bitSet.set(S, true); //because S < 2^31 so S % 2^31 always is equal to S, no need to calculate 
    int count = 1;
    for (int i = 1; i < N; i++) {
        ai = (aiMinus1 * P + Q) & moduloShift;
        if (!bitSet.get((int) ai)){
            bitSet.set((int) ai, true); // mark that number has been exist
            count++;
        }
        aiMinus1 = ai;
    }
    System.out.println(count);
}

tntxtnt · September 23, 2016, 8:09am

đâu có đúng. a trỏ tới mảng int, a[0] là int - 32 bit chứ đâu phải là 1 bit. Mình viết có lẽ chưa kỹ: tính được a_i thì set visited[a_i] = 1 chứ ko phải set visited[i] = 1. Mình viết “set a[i] = 1 khi tính được a_i” là viết tắt cho kiểu này.

C++ có kiểu vector<bool> là bit array đó, lấy nó mà xài.

vector<bool> visited(p231);
int a = S; //bắt đầu
while (N--)
{
    visited[a] = 1; //đánh dấu đã gặp a
    a = (static_cast<long long>(a) * P + Q) % p231; //tính a kế tiếp. Vì int*int có thể tràn số nên cast thành long long
}

rồi sau đó bạn có thể đếm số lượng bit 1 trong bit array visited:

int result = accumulate(begin(visited), end(visited), 0);

nhưng làm kiểu này rất là lâu, vì phải lướt 2³¹ phần tử. Trong khi n < 10⁸, nên đếm trong vòng for ở trên. Mình để bạn tự suy nghĩ vậy ha. Gợi ý là trong vòng lặp trên, chỉ cộng 1 cho result khi chưa gặp a. Nếu đã gặp a rồi (visited[a] == true) thì ko cộng 1.

tntxtnt · September 21, 2016, 2:24pm

thử với input
10000 573272257 859433109 1894136138
output là 10000. Xem nó chạy ná thở luôn vì length lên tới hơn 2 tỷ. N giới hạn là 100 triệu nên đếm ở trong vòng lặp N ấy.

qloved · September 21, 2016, 2:51pm

Ok, thế để mình update, hehe

ntanh · September 22, 2016, 8:14am

100000000 569099406 1607140150 823906344
output 31. Mình bị fail test case, nhưng cuối cùng cũng pass
Cám ơn bạn !

Bạn cho mình hỏi thêm: giả sử mình tính a_i= 123 thì tương ứng với vị trí thứ 123 trong Bit Array và bật lên 1 đúng không?

tntxtnt · September 22, 2016, 1:03pm

đúng rồi. Nhưng trước khi bật xem vị trí thứ 123 có được bật chưa, tức là số 123 đã xuất hiện trước đó chưa, nếu đã có rồi thì đừng đếm nó, nếu chưa có thì mới đếm.