30/09/2018, 23:56

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

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.

viết 02:04 ngày 01/10/2018

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

  • a0 = S
  • ai = ( P×ai-1 + Q ) % 231

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

Ràng buộc:
1 ≤ N ≤ 108
1 ≤ S, P, Q < 231



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 ≤ ai < 231 (vì ai có % 231) thì tối đa có 231 số khác nhau đôi một. Nếu tạo 1 `set` rồi mỗi lần sinh ra ai thì cho ai 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 231 phần tử luôn, mỗi phần tử chỉ chiếm 1 bit => 231 phần tử chỉ chiếm 256MB RAM. Mỗi lần sinh ai thì gán `a[i] = 1`. Sau đó nếu tại vị trí i nào mà `a[i]==0` thì ai ko xuất hiện trong dãy số trên. Từ đó đếm được số lương số khác nhau đôi một.
Nguyễn Tuấn Anh viết 01:59 ngày 01/10/2018

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;
}
Quân viết 02:01 ngày 01/10/2018

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);
}
viết 02:03 ngày 01/10/2018

int *a = new int[p231/32];

a[0] = S % p231;

đâ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 ai thì set visited[ai] = 1 chứ ko phải set visited[i] = 1. Mình viết “set a[i] = 1 khi tính được ai” 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 231 phần tử. Trong khi n < 108, 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.

viết 02:03 ngày 01/10/2018

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.

Quân viết 02:11 ngày 01/10/2018

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

Nguyễn Tuấn Anh viết 02:09 ngày 01/10/2018

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 ai= 123 thì tương ứng với vị trí thứ 123 trong Bit Array và bật lên 1 đúng không?

viết 01:57 ngày 01/10/2018

đú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.

Bài liên quan
0