Bị WA một problem về kỹ thuật two-pointers

#1

Hi mọi người, em có đang làm bài tập sau: https://www.spoj.com/PTIT/problems/P145PROI/
Về cơ bản thì em duyệt for của chỉ số i và search chỉ số j nhỏ nhất (i < j) sao cho đoạn [i, j] an toàn. Nếu an toàn chỉ việc cộng kết quả với (n - j) và dịch “pointer” ở bên trái lên (trong trường hợp này là left).
Kỹ thuật này gần giống như two pointers, và đây là code cài của em:

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string str;
	int num = 0, up = 0, low = 0, left = 0, sum = 0;
	// numeral, uppercase, lowercase, left
	cin >> str;
	int n = str.size();
	for (int i = 0; i < n; ++i) {
		// xét kiểu ký tự uppercase, lowercase hay numeral để tăng loại biến tương ứng
		if ('a' <= str[i] && str[i] <= 'z') ++low;
		else if ('A' <= str[i] && str[i] <= 'Z') ++up;
		else ++num;
		// nếu xâu con trong đoạn [left, i] đã thỏa mãn các điều kiện: Tối thiểu 6 ký tự, có ký tự lowercase, uppercase, numeral
		if (num > 0 && low > 0 && up > 0 && i - left >= 5) {
			sum += (n - i); // là số lượng các xâu thỏa mãn [left, x] với x >= i
			// tiến hành dịch chuyển biến 'left' (left pointer)
			if ('a' <= str[left] && str[left] <= 'z') --low;
			else if ('A' <= str[left] && str[left] <= 'Z') --up;
			else --num;
			++left;
			// tiến hành lùi biến 'i' (lần lặp sau sẽ tính lại)
			if ('a' <= str[i] && str[i] <= 'z') --low;
			else if ('A' <= str[i] && str[i] <= 'Z') --up;
			else --num;
			--i;
		}
	}
	cout << sum;
	return 0;
}

Em submit chấm được khoảng 24 tests thì bị WA ở test #24.
Em vẫn chưa biết bug ở chỗ nào, nên post lên đây nhờ mọi người giúp đỡ ạ!
Em xin cảm ơn trước!

#2

bỏ cái --i đi tại sao lại đi --i?

đừng đặt biến 1 chữ l nhìn loạn cả lên ko biết i hay l mà lần

3 Likes
#3

Dạ để một lát sau ++i thì mình xét lại vị trí i sau khi đã tăng vị trí l ấy anh?
VD: abcABC123
thì khi mình duyệt tới ký tự 1 thì điều kiện if thỏa mãn, tức các xâu: abcABC1, abcABC12, abcABC123 thỏa mãn thì tăng vị trí l lên 1 (bắt đầu từ ký tự b). Dễ thấy xâu bcABC1 cũng thỏa mãn mà nếu mình ko có dòng --i thì gặp điều kiện update của vòng lặp for sẽ tăng i, lỡ mất cái xâu bcABC1 đó ! (có thể hiểu l chính là left pointer và i chính là right pointer).

À, em quên mất điều kiện xâu tối thiểu 6 ký tự nên em chỉnh sửa một xíu lại như sau:

#include <iostream>
#include <string>

using namespace std;

int main()
{
	string str;
	int num = 0, up = 0, low = 0, left = 0, sum = 0;
	// numeral, uppercase, lowercase, left
	cin >> str;
	int n = str.size();
	for (int i = 0; i < n; ++i) {
		// xét kiểu ký tự uppercase, lowercase hay numeral để tăng loại biến tương ứng
		if ('a' <= str[i] && str[i] <= 'z') ++low;
		else if ('A' <= str[i] && str[i] <= 'Z') ++up;
		else ++num;
		// nếu xâu con trong đoạn [left, i] đã thỏa mãn các điều kiện: Tối thiểu 6 ký tự, có ký tự lowercase, uppercase, numeral
		if (num > 0 && low > 0 && up > 0 && i - left >= 5) {
			sum += (n - i); // là số lượng các xâu thỏa mãn [left, x] với x >= i
			// tiến hành dịch chuyển biến 'left' (left pointer)
			if ('a' <= str[left] && str[left] <= 'z') --low;
			else if ('A' <= str[left] && str[left] <= 'Z') --up;
			else --num;
			++left;
			// tiến hành lùi biến 'i' (lần lặp sau sẽ tính lại)
			if ('a' <= str[i] && str[i] <= 'z') --low;
			else if ('A' <= str[i] && str[i] <= 'Z') --up;
			else --num;
			--i;
		}
	}
	cout << sum;
	return 0;
}

Em chú thích thêm cho mọi người dễ hiểu! Nhưng vẫn sai test 24 ạ :(( (bị WA chứ ko lỗi segmentation fault nữa)

OK fixed !

Edit: Em dùng 1 naive algorithm trâu 3 vòng for để làm stress test với cái thuật trên kia thì chạy cả gần nửa tiếng cũng chả phát hiện ra bug, thôi chắc coi như bài này làm gần đúng vậy @@

#4

thử cho sum là long long đi, 10^6 thì có thể sum lên tới 10^12 chẳng hạn

đây: https://rextester.com/SZJ19867
input dài 73728 chữ, output ra số âm :V

3 Likes
#5

Thôi toi, code cả bài logic thế cuối cùng lại bị sai cái datatype!
Cảm ơn anh nhiều nhé!

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