Bài tập almostIncreasingSequence trên codefight

3. Code bạn sai ở trường hợp [1, 2, 2]. Bạn đếm 2 có 2 lần, Nhưng khi remove 2 đi thì thành 1 2 vẫn là dãy tăng và return true.
4. Code bạn cũng sai ở trường hợp [0, -2, 5, 6], -2 - 0 != 1 nên bạn tăng count lên 1 mặc dù nó vẫn là dãy tăng và trong đề cũng ghi ví dụ là ko nhất thiết phải cách nhau 1 đơn vị.

bài này chỉ cần đếm số cặp (a,b) mà a,b liền kề và a >= b là đủ rồi phải ko nhỉ @_@

1 dòng vậy ko biết đúng ko =)

def almostIncreasingSequence(sequence):
    return 1 >= sum(a >= b for a, b in zip(sequence[:-1], sequence[1:]))

em cám ơn bác, em suy nghĩ hổng nhiều quá.

fail ở trường hợp đầu vào = [1, 2, 1, 2] bác ơi
Input:
sequence: [1, 2, 1, 2]
Output:
true
Expected Output:
false
Console Output:
Empty

ờm, thấy nó đơn giản quá nên thấy kì kì =)

Theo đề “strictly increasing sequence”, dịch tiếng Việt là “dãy tăng nghiêm ngặt”, thì a[i] < a[i+1], với mọi i từ 1, đến N - 1. N là số phần tử của dãy.

Đúng không nhỉ?

đúng rồi, nghĩa là 1 1 1 2 cũng ra giá trị False.

chưa nghĩ ra cách giải 1 dòng =)

chả hiểu thế nào, e thấy test như này
Input: sequence: [1, 2, 5, 3, 5]
Output: false
Expected Output: true

e thấy dãy đó xóa kiểu gì cũng false, mà bọn codefight bảo phải trả về True mới đúng :)))))

xóa số 5 ở giữa là xong mà…

chắc ko có cách 1 dòng…

xóa số 5 ở giữa --> 1 2 3 5 ?? có phải dãy tăng nghiêm ngặt đâu bác

1 < 2 < 3 < 5 ko phải à @_@

Thuật toán đơn giản: Search từ đầu đến cuối, nếu dãy có 1 lần không tăng duy nhất thì là đúng, còn nếu nhiều hơn thì là sai. Sao code lại dài như thế

int DecreasingCount = 0;
for (int i = 0; i < sequence.Length - 1; i += 1)
    if (sequence[i] >= sequence[i + 1])
        DecreasingCount += 1;
return DecreasingCount <= 1;

edit: Phải thêm dòng kiểm tra xem sequence[i + 1] có phải phần tử cuối cùng không, nếu không thì kiểm tra tiếp xem sequence[i + 2] có lớn hơn sequence[i] không, nếu có thì DecreasingCount += 1, không thì DecreasingCount = 2

edit #2: Vẫn sai, thôi dẹp đi -_-

bool almostIncreasingSequence(int[] sequence)
{
int DecreasingCount = 0;
for (int i = 0; i < sequence.Length - 1; i += 1)
    if (sequence[i] >= sequence[i + 1])
        if (i == 0)
            DecreasingCount += 1;
    	else if (i + 1 == sequence.Length - 1)
            DecreasingCount += 1;
	else
        {
                if (sequence[i] < sequence [i + 2] || sequence[i - 1] < sequence [i + 1])
                        DecreasingCount += 1;
                else
                        DecreasingCount = 2;
        }
return DecreasingCount <= 1;
}

1 dòng như vầy có được ko

def almostIncresingSequence(s):
    return 1 >= sum((p[i] >= p[i+1]) * (1 + (p[i] >= p[i+2] and p[i-1] >= p[i+1])) for i in range(1, len(s)) for p in ([-1000000] + s + [1000000],))

sai với input 1 2 1 2 rồi kìa, cách 1 dòng đầu tiên của mình đó =)

Sai cái giề, đây là đáp án của mình hồi mình còn chơi CF, vừa mới lên copy ra đấy

edit: Ơ đm, tại sao vừa chạy thử lại sai nhỉ, hay là hồi đó mình sửa lại rồi

viết 5 dòng chi cho khổ, 1 dòng 1 >= sum(a >= b for a, b in zip(sequence[:-1], sequence[1:])) là được rồi, mà nó ra sai =)

1 2 1 2 chỉ có 2 1 là giảm, nhưng xóa 2 nó ra 1 1 2 hay xóa 1 nó ra 1 2 2 đều là dãy ko tăng dần (có 1 == 1 và 2 == 2)

Code theo phương pháp trâu bò

bool almostIncreasingSequence(int[] sequence)
{
    for (int i = 0; i < sequence.Length - 1; i += 1)
            if (sequence[i] >= sequence [i + 1])
                return (IncreasingSequence(RemoveFromSequence(sequence,i))||IncreasingSequence(RemoveFromSequence(sequence,i + 1)));
    return true;
}
bool IncreasingSequence(int[] sequence)
{
    if (sequence.Length < 2)
        return true;
    for (int i = 0; i < sequence.Length - 1; i += 1)
        if (sequence[i] >= sequence[i + 1])
            return false;
    return true;
}
int[] RemoveFromSequence(int[] sequence, int Position)
{
    var Output = new int[sequence.Length - 1];
    for (int i = 0; i < Position; i += 1)
        Output[i] = sequence[i];
    for (int i = Position + 1; i < sequence.Length; i += 1)
        Output[i - 1] = sequence[i];
    return Output;
} 

Bác nào biết Python port sang cái

Code của mình, đã test qua các test case ở trên.
P/s: Đã thêm điều kiện phần removed_index > 0

bool almost_increasing_sequence(int *sequence, int length)
{
    if (length == 1 || length == 2) return true;

    int removed_index = -1;
    for (int i = 0; i < length - 1; i++)
        if (sequence[i] >= sequence[i + 1])
        {
            removed_index = i;
            break;
        }
    
    if (removed_index == -1)
        return true;
    if (removed_index == length - 2)
        return true;
    
    if (removed_index > 0 && sequence[removed_index - 1] >= sequence[removed_index + 1])
    {
        if (sequence[removed_index] < sequence[removed_index + 2])
            removed_index++;
        else
            return false;
    }
    
    for (int i = removed_index + 1; i < length - 1; i++)
        if (sequence[i] >= sequence[i + 1])
            return false;

    return true;
}

E cám ơn bác, E chuyển code của bác sang python.

def almostIncreasingSequence(sequence):
if 2<=len(sequence)<=10**5:
	if any(-10**5<=sequence[i]<=10**5 for i in range(0,len(sequence)-1)):
		if 1<=len(sequence)<=2:
			return True
		removed_index = -1
		for i in range(0,len(sequence)-1,1):
			if sequence[i]>=sequence[i+1]:
				removed_index=i
				break
		print(removed_index)
		if removed_index == -1:
			return True
		if removed_index == len(sequence)-2:
			return True
		if removed_index > 0 and sequence[removed_index-1]>=sequence[removed_index+1]:
			return False
		for i in range(removed_index+1,len(sequence)-1,1):
			if sequence[i]>=sequence[i+1]:
				return False

		return True

Qua chạy thử em thấy tạch ở case [1, 2, 3, 4, 3, 6] case này đáng lý vẫn là True, nhưng vẫn k thỏa mãn
removed_index > 0 and sequence[removed_index-1]>=sequence[removed_index+1]: và trả về False :((
Hay e chuyển sang python bị sai

Code đúng chạy được. (em đi mượn)

def first_bad_pair(sequence):
"""Tìm vị trí đầu tiên mà phần tử trước lớn hơn phần tử sau. Nếu không tìm thấy, trả về -1, nếu tìm thấy, trả về index của phần tử đó"""
for i in range(len(sequence)-1):
    if sequence[i] >= sequence[i+1]:
        return i
return -1
def almostIncreasingSequence(sequence):
"""Xóa phần tử được tìm thấy bởi hàm trên, sau đó check lại. Nếu vẫn còn thì trả về false, nếu không còn thì trả về True"""
j = first_bad_pair(sequence)
if j == -1:
    return True  # Không tìm thấy phần tử trước > phần tử sau nên dãy đã ngon
if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
    return True #Xóa phần tử được tìm thấy, sau đó kiểm tra chuỗi còn lại.
if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
    return True
return False