Bài tập trên codefight

dongocanh96 · March 14, 2020, 2:43pm

Trên codefight có bài tập thế này

Given a sequence of integers, check whether it is possible to obtain a strictly increasing sequence by erasing no more than one element from it.

Example

For sequence = [1, 3, 2, 1], the output should be almostIncreasingSequence(sequence) = false;
For sequence = [1, 3, 2], the output should be almostIncreasingSequence(sequence) = true.
Input/Output

[time limit] 500ms (cpp)
[input] array.integer sequence

Constraints:
2 ≤ sequence.length ≤ 10^5,
-10^5 ≤ sequence[i] ≤ 10^5.

[output] boolean

true if it is possible, false otherwise.

Tạm dịch đề bài: Cho một dãy số bất kì, kiểm tra xem nếu xóa 1 số thuộc dãy số đó thì ta có thu được 1 dãy tăng dần không. Yêu cầu các số trong dãy thu được sau khi xóa phải khác nhau (cái này sau khi xem test case của nó thì em mới biết)

Em làm bài này bằng cách:

Kiểm tra xem dãy cho trước có phải dãy tăng dần và các phần tử đều khác nhau không, nếu có thì dãy thỏa mãn
Nếu dãy cho trước không phải tăng dần thì xóa từng phần tử đi rồi kiểm tra dãy thu được xem có tăng dần và có các phần tử khác nhau không. Nếu có thì thỏa mãn.

code của em đây

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
    {
        std::vector<int>::iterator iter;
        for(int i=0;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;
    }
}

Code của em thỏa mãn tất cả các sample test nhưng lại không thỏa mãn 1 cái hidden test do tốc độ xử lý chậm hơn bài ra. Vậy em muốn hỏi mọi người có thuật toán nào khác nhanh hơn không hoặc giúp em tối ưu code để xử lý nhanh hơn.
Em xin cảm ơn!

nguyenchiemminhvu · February 28, 2017, 1:07pm

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).

dongocanh96 · February 28, 2017, 1:13pm

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

rogp10 · February 28, 2017, 1:17pm

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.

nguyenchiemminhvu · February 28, 2017, 1:16pm

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.

dongocanh96 · February 28, 2017, 1:17pm

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

rogp10 · February 28, 2017, 1:18pm

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?.

dongocanh96 · February 28, 2017, 1:19pm

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

dongocanh96 · February 28, 2017, 1:19pm

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

dongocanh96 · February 28, 2017, 1:23pm

Ờ 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

monkey · February 28, 2017, 2:32pm

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

banhmisg9509 · March 1, 2017, 6:18am

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);
}

nxphuc · March 1, 2017, 10:02am

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ử.

tienganh1247 · January 17, 2018, 9:09am

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;
}

Pi_Logan · May 5, 2018, 3:27pm

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;
    }
}

rogp10 · March 14, 2020, 11:18am

rogp10() has 9 correct over 9
ndh() WRONG: true MUST EQUAL: false  ARG0 = [1,2,1,2]
ndh() WRONG: true MUST EQUAL: false  ARG0 = [40,50,60,10,20,30]
ndh() has 7 correct over 9
h() WRONG: true MUST EQUAL: false  ARG0 = [1,2,1,2]
h() has 8 correct over 9
khanhvm() has 9 correct over 9