Bài tập almostIncreasingSequence trên codefight

#1

#Codefight almostIncreasingSequence
Chào các bác, em đang ngồi mò mẫm làm bài tập python trên codefight, và đang dừng ở bài này

almostIncreasingSequence

Mô tả yêu cầu của em nó:

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

[execution time limit] 4 seconds (py3)

[input] array.integer sequence

Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

Tạm dịch (em mượn bản dịch của 1 bạn em google đc)

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

Đây là code của em:

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 len(sequence) ==2:
			return True
		else:
			count=0
			# list(sequence)
			# counta=0
			for i in range(0,len(sequence)-1,1):
				if sequence.count(sequence[i]) >1:
					count=100
			for i in range(0,len(sequence)-2,1):
				if sequence[i+1]-sequence[i] != 1:
					count+=1
			print(count)
			if count >1:
				return False
			else:
				return True

Thuật toán em k biết sau đâu ko, nhưng chạy test thì toàn báo tạch :((( nhờ các cao nhân cho em ít ánh sáng, em cám ơn

Input:
sequence: [0, -2, 5, 6]
Output:
false
Expected Output:
true
Console Output:
2

Input:
sequence: [1, 2, 5, 3, 5]
Output:
false
Expected Output:
true
Console Output:
102

1 Like
#2
  1. 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.
  2. 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ị.
5 Likes
#3

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:]))
2 Likes
#4

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

1 Like
#5

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

2 Likes
#6

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

2 Likes
#7

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

3 Likes
#8

đú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 =)

2 Likes
#9

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

1 Like
#10

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

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

2 Likes
#11

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 Like
#12

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

2 Likes
#13

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ế :expressionless:

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 -_-

Summary

C#

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

C#

3 Likes
#14

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],))
2 Likes
#15

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

2 Likes
#16

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 :expressionless:

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

3 Likes
#17

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)

2 Likes
#18

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

C# 
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

3 Likes
#19

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;
}
6 Likes
#20

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 :confused:

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