Thảo luận bài toán: Liệt kê xâu nhị phân

#1

Yêu cầu: Cho 1 số nguyên dương n. Đưa ra xâu nhị phân độ dài n thứ k trong thứ tự từ điển mà không có i số 0 liên tiếp.
Dữ liệu vào: Một dòng ghi 3 số nguyên dương n,k,i ≤ 10000.
Kết quả: Ghi ra xâu nhị phân độ dài n thứ k mà không có i số 0 liên tiếp trên một dòng duy nhất, các thành phần cách nhau bởi dấu cách. Nếu không tồn tại thì ghi ra -1.
Ví dụ:
Input: 6 4 2 -> Output: 0 1 1 0 1 0
Input: 8 9000 2 -> Output: -1
Lưu ý: Giới hạn thời gian thực hiện: 1s, Giới hạn bộ nhớ: 512MiB.

Mọi người cùng vào bàn luận xem có cách nào thực hiện nhanh nhất có thể không? Nếu chơi Brute Force liệt kê hết từ đầu đến chân thì dính TLE ngay :cry:.

#2

note: Lần sau thêm Thảo luận: vào đầu topic nếu bạn muốn mọi người vào thảo luận nhé :smile:
Mà bộ nhớ sao là 512MiB được nhỉ? 512MB chứ?

Mình hơi nghiêng về phía brute force + 1 tí tổ hợp.
Để cho nhanh, ta không xét số 0 đứng độc lập mà ta tạo thành khối các số 0 liên tiếp, các số 1 liên tiếp cũng thành 1 khối, kiểu như số 1100101 khi chia thành các khối sẽ là 11, 00, 1, 0, 1. Như vậy, coi như sau một khối các số 0 sẽ chỉ là khối các số 1.
Đến đây, ta nhận thấy rằng: sau mỗi 1 khối các số 0 sẽ chỉ có 1 khả năng là đặt tiếp khối các số 1 vào ngay sau đó.
Ta định nghĩa F(pos, prev, len_prev, cnt, ok) với pos là số phần tử của xâu đã xây dựng xong trước đó, prev là giá trị của khối ta vừa đặt cuối cùng (prev = 0 hoặc 1), len_prev là độ dài của khối ta vừa đặt cuối cùng (nếu prev = 0 thì ta chú ý len_prev < i), cnt là số xâu nhị phân hoàn chỉnh ta đã xây dựng được, và ok là bool (nếu ta dựng được xong 1 dãy, khi đó pos = n (ta đã xây xong cả dãy), cnt = k và ok=true thì ra return cái dãy này (nhớ có 1 mảng truy vết)
Sẽ có 1 chút mẹo để giảm tiếp thời gian chạy. Tạm thời mình mới nghĩ đến đây @@ Chắc như trên cũng ăn được khối test đấy, mong là được 1/3 :v

*p/s: klq nhưng thớt cho mình xin link submit bài này với :v bài này trông quen quen nhưng mà mình chưa nhớ ra đã nhìn thấy ở đâu :v

2 Likes
#3

Cái bài này là bài trong 1 private course, có tài khoản riêng cho học viên trong course, không Submit public được nên bạn nếu muốn Submit thử thì cứ viết code ra xong gửi mình Submit hộ cho :wink:.
Cái trên cũng giảm được 1 kha khá thời gian nhưng không biết bộ Test với n,k,i ≤ 10000 thế kia sợ cũng không trụ nổi. Để chiều tối rảnh rảnh ngồi code thử xong Submit xem có qua không :slight_smile: .

1 Like
#4

1 MiB = 2^20 bytes.

Bài này rất thường thấy vì phát biểu ngắn gọn.

#5

Bạn ơi mình muốn nhờ bạn submit hộ code… mình inb bạn nhé?

#6

Mình có 1 idea khác, nhưng đang muốn nhờ thớt submit hộ =))

Mình sẽ không làm như kiểu trên, mình sẽ backtrack 15 chữ số cuối (nếu n < 15 thì backtrack toàn bộ). Khi làm kiểu này thì mình nghĩ rằng:

  • Nếu i > 15 thì luôn tồn tại đáp số (cũng chỉ có <= 15 chữ số cuối được duyệt, kiểu gì thì kiểu cũng tạo ra đến > 10000 dãy thỏa mãn)
  • Nếu i <= 15: tạm thời chưa chứng minh được :’(
    Chưa biết kết quả ra sao khi submit; nhưng chắc chắn ăn được hết test bé (n < 15) và có thể là ăn được kha khá test với i > 15.
#7

Bạn cứ inbox mình submit thử xem nhé.

1 Like
#8

là sao ta, không hiểu, ai giải thích giumf mình với

#9

Xâu (nhị phân) thứ k có độ dài n.

#10

Thứ k có nghĩa là sao ? không hiểu lắm, tối nghĩa quá.

#12

Đề rất sáng rõ mà bạn :v
Mình giải thích luôn 1 lần và mình không muốn thấy bất kì 1 cmt nào hỏi câu này nữa:
Khi bạn liệt kê tất cả các xâu thoả mãn đề bài theo thứ tự từ điển, vị trí thứ k là phần tử thứ k trong nhóm các xâu bạn vừa liệt kê.

Trong các câu hỏi của Competitive Programming, câu hỏi dạng xâu thứ k rất phổ biến. Bao nhiêu năm nay có rất nhiều người vẫn hiểu câu hỏi này.

#13

Bạn đã làm được bài này chưa? Mình đã thử nhiều trường hợp rồi nhưng đều bị lỗi thời gian.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?