Bài tập trên codefight

Mình nghĩ bạn chỉ cần sắp xếp mảng theo chiều tăng dần, sau đó kiểm tra từng cặp phần tử kề nhau trong mảng có trường hợp nào sequence[i] == sequence[i + 1] hay không? Đếm số trường hợp đó, nếu số trường hợp lớn hơn 1 thì trả về false (nghĩa là phải xóa nhiều hơn 1 phần tử để đạt được mảng tăng dần).

Nhưng nếu họ cho dãy 1 2 3 1 10 4 6 7, như vậy cần xóa ít nhất hai số 1 và 10 đi để đạt được dãy tăng dần, còn thuật toán của anh nó chỉ phát hiện ra được số 1 thôi

Yêu cầu các số trong dãy thu được sau khi xóa phải khác nhau

Strictly increasing mà bạn nó bắt vậy đúng rồi.

Bài này sắp xếp chắc tiêu vì test toàn dãy gần tăng (nếu ko phải thì sút luôn rồi). Big-O của code bạn quá cao (bản chất là 2 for lồng) nên TLE thôi.

Bạn có thể đưa thêm testcase ko, chỉ một test case như bạn ghi ở đề nên không rõ ràng lắm.

À vâng, vậy anh có thể giúp em không ạ ?

Giờ bạn suy nghĩ đơn giản. Coi như không có “ông kẹ” ở giữa một dãy tăng ngặt. Sau đó đặt vài “ông kẹ” vào giữa. Giờ chạy dọc theo mảng. Bạn đã nhìn ra chưa?.

1, 3, 2, 1 =>false
1, 3, 2=> true
1, 2, 1, 2=>false
1, 4, 10, 4, 2=>false
10, 1, 2, 3, 4, 5=>true
1, 1, 1, 2, 3=>false
0, -2, 5, 6=>true
40, 50, 60, 10, 20, 30=>false
1, 1=>true

À, có nghĩa là mình chỉ cần tìm số ông kẹ trong dãy phải không ạ?

Ờ ha. Em hiểu rồi. Có nghĩa bây giờ mình tìm được phần tử nào làm mất tính tăng ngặt thì cứ xóa nó đi, nếu phải xóa hơn 1 lần thì return false Có thế mà nghĩ mãi
Cám ơn hai anh

Thuật toán như sau:
For i từ 1 đến sequence.length:

   if s[i] <= s[i-1]:
            thử xóa vị trí thứ i - 1 (O(n)).
            if checkTangDanvsSoKhacNhau(s) == true: O(n)
                    print true
                    break
            thử xóa vị trí thứ i (O(n)).
            if checkTangDanvsSoKhacNhau(s) == true: O(n)
                    print true
                    break
            break

print false

Bài này thực ra chỉ cần kiểm tra xem 2 phần tử liền kề có theo thứ tự tăng dần hay không nếu không thì tăng biến đếm lên 1, cứ như vậy cho tới hết dãy . Nếu biến đếm lớn hơn hay bang 2 là false rồi vì khi đó ta phải xóa đi 2 phần tử để dãy tăng chứ không phải 1 như đề cho.

boolean almostIncreasingSequence(int[] sequence) {
    if(sequence.length <= 2) return true;
    int count = 0;
    for(int i = 0; i < sequence.length - 1;i++){
        if(sequence[i] >= sequence[i+1]){
            count++;
        }
    }
    return (count < 2);
}

có trường hợp biến đếm = 1 nhưng vẫn ra false đấy bạn
Ví dụ: [1, 2, 4, 1, 3, 5]
Rõ ràng chỉ có cặp (4, 1) là sai nhưng cũng không thể tạo thành dãy tăng dần nếu xóa đi 1 phần tử.

Lúc đầu mình cũng nghĩ đơn giản như bạn. Nhưng có case [1,2,1,2] là fail.

Giải thuật tham khảo:

bool almostIncreasingSequence(int[] sequence)
{
	bool foundOne = false;
 
	for (int i = -1, j = 0, k = 1; k < sequence.Length; k++)
	{
		bool deleteCurrent = false;
		if (sequence[j] >= sequence[k])
		{
			if (foundOne)
			{
				return false;
			}
			foundOne = true;
 
			if (k > 1 && sequence[i] >= sequence[k])
			{
				deleteCurrent = true;
			}
		}
 
		if (!foundOne)
		{
			i = j;
		}
 
		if (!deleteCurrent)
		{
			j = k;
		}
	}
 
	return true;
}

bool increasingTest(std::vector<int> sequence){
    for(int j=0;j<sequence.size()-1;j++){
        if(sequence[j]>sequence[j+1]||sequence[j]==sequence[j+1])
        {
            return false;}
    }
    return true;
}
bool almostIncreasingSequence(std::vector<int> sequence) {
    if(increasingTest(sequence))
    {
        return true;
    }
    else
    {
        int j;
        for(int k =0;k< sequence.size()-1;k++){
            if(sequence[k]<sequence[k+1]){
                continue;
            }else{
                j = k;
                break;
            }
        }
        std::vector<int>::iterator iter;
        for(int i=j;i<sequence.size();i++)
        {
            iter = sequence.begin()+i;
            int temp=sequence[i];
            sequence.erase(sequence.begin()+i);
            if(increasingTest(sequence))
            {
                return true;
            }
            sequence.insert(iter, temp);
        }
        return false;
    }
}