thảo luận Leetcode contest, đường tới Guardian

freedom.9 said:

Hello anh em, tình hình leetcode daily là chỗ thảo luận daily. Chưa có topic về Leetcode contest nên mình lập cái topic cho ae trao đổi kinh nghiệm cho vui như bác @pikachu_1 đang tìm kiếm, hi vọng anh em có kinh nghiệm, các knights, guardians của VOZ vào chỉ cho anh em vài skill để anh em tu luyện ranking của VN thường khá là khiêm tốn trên Leetcode.

Leetcode contest là gì: Leetcode contest là nơi đấm nhau của các anh tài, mỗi tuần sẽ có 1 cuộc thi Weekly, 2 tuần 1 lần sẽ có 1 cuộc thi BiWeekly. Nếu tham gia cả 2 cuộc thi sẽ được 35 points cho anh em đổi áo. Mỗi cuộc thi kéo dài 1 tiếng rưỡi và có 4 câu, thường 4 câu sẽ có độ khó là easy, medium, medium, hard.
Tại sao phải tham gia Leetcode contest: Đề của Leetcode contest thường sẽ là những bài toán mới chưa có lời giải, ko search được trên google. Đề thi rất hay và đa dạng. Quan trọng là chỉ có 90ph để làm 4 bài, nếu mà giải được 3 hoặc 4 bài trong khoảng thời gian thì việc phỏng vấn pass vòng algorithm vào big techs là không khó.
Leetcode contest có giải thưởng gì: Cái mình thích nhất là huy hiệu, để được huy hiệu knight thì rating thường nằm trong khoảng 1k8 hoặc 1k9, guardian thì phải khoảng 2k3 2k4 rating. Việc có cái huy hiệu này thường sẽ rất ha oai, được leetcoder ngưỡng mộ vì trình độ, có khả năng chửi mấy thằng Vozers lẹt đẹt huy hiệu monthly là code ngu nên mình rất thích cày. Rất tiếc là mình chưa có cái huy hiệu nào cả, chắc vì trời không cho ha oai lên mặt với Vozer
Ranking của mình: Sau 20 cái contests thì mình giải được bài 3 khoảng 50/50 thôi nên chưa leo nổi huy hiệu Knight. Lâu lâu động kinh bài 2 giải cũng ko ra, như bài 2 của contests hôm qua. Việc giải được nó còn phụ thuộc vào nhiều yếu tố như con vợ có bắt trả bài hay không nữa mình bắt đầu Leetcode chỉ mới 6 tháng trước nên chắc vẫn còn lâu mới lên được Guardian, chỉ biết cắm đầu cày cuốc thôi. Đây là profile leetcode của mình

nhienle94 - LeetCode Profile

View nhienle94's profile on LeetCode, the world's largest programming community.

leetcode.com

Tới phần thảo luận bài 2 cuộc contests hôm qua ở phần post tiếp theo

Click to expand...

freedom.9 said:

Về bài biweekly hôm qua có 3 bài
Bài 1: Loading... (https://leetcode.com/contest/biweekly-contest-120/problems/count-the-number-of-incremovable-subarrays-i/)
Bài này easy nhưng mà dân tình nó chửi rầm rầm kêu bài này phải là medium, với contrain thấp như này thì cách tốt nhất là brute force, cách giải của mình là với 1 sub arrays từ i - j bất kì thì kiểm tra xem khi xoá sub array đó có strictly increasing hay không.

Spoiler: C#

C#:

public class Solution {
    public int IncremovableSubarrayCount(int[] nums) {
        var length = nums.Length;
        var ans = 0;
        for(int i = 0; i < length; i ++)
        {
            for(int j = i; j < length; j++)
            {
                 if(isRemovable(nums, i, j))
                     ans++;
            }
        }
       
        return ans;
    }
   
    public bool isRemovable(int[]nums, int left, int right)
    {
        for(int i = 0; i < left; i++)
        {
            if(i != 0 && nums[i] <= nums[i - 1])
                return false;
        }
       
        for(int j = right + 1; j < nums.Length; j++)
        {
            if(j == right + 1 && left - 1 >= 0 && nums[j] <= nums[left - 1])
            {
                 return false;
            }
           
            else if(j != right + 1 && nums[j] <= nums[j - 1])
                 return false;
        }
       
        return true;
    }
}

Bài 2 Bài 2 dễ hơn bài 1 Loading... (https://leetcode.com/contest/biweekly-contest-120/problems/find-polygon-with-the-largest-perimeter/) Ý tưởng là sẽ dùng prefix sum với các bài dạng này, nhưng mà để prefix sum được thì đầu tiên phải sort cái đã, vì nếu ko sort thì sẽ ko tìm được 1 optimal solution. Vì longest side must be smaller than sum of other sides, giống như cái định lí của hình tam giác là tổng 2 cạnh phải lớn hơn cạnh thứ 3.

Spoiler: C#

Code:

public class Solution {
    public long LargestPerimeter(int[] nums) {
        Array.Sort(nums);
        if(nums.Length < 3)
             return -1;
       
        var prefixSum = new long[nums.Length];
        prefixSum[0] = 0;
        for(int i = 1; i < nums.Length ; i++)
        {
            prefixSum[i] = (long)nums[i - 1] + (long)prefixSum[i - 1];
        }
       
        for(int i = nums.Length - 1; i >= 2; i--)
        {
            if(nums[i] < prefixSum[i])
                return prefixSum[i] + nums[i];
               
        }
       
        return -1;
    }
}

Bài 3: Khó vl vì mình giải ko ra, phải giải lại sau contest. Mình ko nhìn ra cái trick là để strictly increasing thì phần left phải tăng dần, và phần right phải giảm dần. Hiểu được cái trick này thì code rất dễ với O(n) + O(n)

Spoiler: C#

Code:

public class Solution {
    public long IncremovableSubarrayCount(int[] nums) {
        var lefts = new List<int>();
        var rights = new List<int>();
        var n = nums.Length;
        for(int i = 0; i < n; i++)
        {
            if(i == 0 || i != 0 && nums[i] > nums[i - 1])
             lefts.Add(nums[i]);
            else break;
        }

        for(int i = n - 1; i >=0; i--)
        {
            if(i == n - 1 || i != n - 1 && nums[i] < nums[i + 1])
             rights.Insert(0, nums[i]);
            else break;
        }

        if(lefts.Count == n)
          return n*(n+1)/2;

        long ans = lefts.Count + rights.Count + 1;
        var index = 0;
        foreach(var left in lefts)
        {
            index = search(rights, left, index);
            if(index == -1)
              break;
            ans += rights.Count - index;
        }

        return ans;
    }

    public int search(List<int> rights, int targetValue, int startIndex)
    {
        var left = startIndex;
        while(left < rights.Count)
        {
            if(rights[left] > targetValue)
            {
                return left;
            }
            else left ++;
        }

        return -1;
    }
}

Bài 4: No ideas, chưa đọc đề nữa mà mình cũng ko có ý định tìm hiểu những bài hard thời gian này. Để làm kĩ những bài medium để cải thiện đã

Click to expand...

freedom.9 said:

Về bài biweekly hôm qua có 3 bài
Bài 1: Loading... (https://leetcode.com/contest/biweekly-contest-120/problems/count-the-number-of-incremovable-subarrays-i/)
Bài này easy nhưng mà dân tình nó chửi rầm rầm kêu bài này phải là medium, với contrain thấp như này thì cách tốt nhất là brute force, cách giải của mình là với 1 sub arrays từ i - j bất kì thì kiểm tra xem khi xoá sub array đó có strictly increasing hay không.

Spoiler: C#

C#:

public class Solution {
    public int IncremovableSubarrayCount(int[] nums) {
        var length = nums.Length;
        var ans = 0;
        for(int i = 0; i < length; i ++)
        {
            for(int j = i; j < length; j++)
            {
                 if(isRemovable(nums, i, j))
                     ans++;
            }
        }
    
        return ans;
    }
 
    public bool isRemovable(int[]nums, int left, int right)
    {
        for(int i = 0; i < left; i++)
        {
            if(i != 0 && nums[i] <= nums[i - 1])
                return false;
        }
    
        for(int j = right + 1; j < nums.Length; j++)
        {
            if(j == right + 1 && left - 1 >= 0 && nums[j] <= nums[left - 1])
            {
                 return false;
            }
        
            else if(j != right + 1 && nums[j] <= nums[j - 1])
                 return false;
        }
    
        return true;
    }
}

Bài 2 Bài 2 dễ hơn bài 1 Loading... (https://leetcode.com/contest/biweekly-contest-120/problems/find-polygon-with-the-largest-perimeter/) Ý tưởng là sẽ dùng prefix sum với các bài dạng này, nhưng mà để prefix sum được thì đầu tiên phải sort cái đã, vì nếu ko sort thì sẽ ko tìm được 1 optimal solution. Vì longest side must be smaller than sum of other sides, giống như cái định lí của hình tam giác là tổng 2 cạnh phải lớn hơn cạnh thứ 3.

Spoiler: C#

Code:

public class Solution {
    public long LargestPerimeter(int[] nums) {
        Array.Sort(nums);
        if(nums.Length < 3)
             return -1;
    
        var prefixSum = new long[nums.Length];
        prefixSum[0] = 0;
        for(int i = 1; i < nums.Length ; i++)
        {
            prefixSum[i] = (long)nums[i - 1] + (long)prefixSum[i - 1];
        }
    
        for(int i = nums.Length - 1; i >= 2; i--)
        {
            if(nums[i] < prefixSum[i])
                return prefixSum[i] + nums[i];
            
        }
    
        return -1;
    }
}

Bài 3: Khó vl vì mình giải ko ra, phải giải lại sau contest. Mình ko nhìn ra cái trick là để strictly increasing thì phần left phải tăng dần, và phần right phải giảm dần. Hiểu được cái trick này thì code rất dễ với O(n) + O(n)

Spoiler: C#

Code:

public class Solution {
    public long IncremovableSubarrayCount(int[] nums) {
        var lefts = new List<int>();
        var rights = new List<int>();
        var n = nums.Length;
        for(int i = 0; i < n; i++)
        {
            if(i == 0 || i != 0 && nums[i] > nums[i - 1])
             lefts.Add(nums[i]);
            else break;
        }

        for(int i = n - 1; i >=0; i--)
        {
            if(i == n - 1 || i != n - 1 && nums[i] < nums[i + 1])
             rights.Insert(0, nums[i]);
            else break;
        }

        if(lefts.Count == n)
          return n*(n+1)/2;

        long ans = lefts.Count + rights.Count + 1;
        var index = 0;
        foreach(var left in lefts)
        {
            index = search(rights, left, index);
            if(index == -1)
              break;
            ans += rights.Count - index;
        }

        return ans;
    }

    public int search(List<int> rights, int targetValue, int startIndex)
    {
        var left = startIndex;
        while(left < rights.Count)
        {
            if(rights[left] > targetValue)
            {
                return left;
            }
            else left ++;
        }

        return -1;
    }
}

Bài 4: No ideas, chưa đọc đề nữa mà mình cũng ko có ý định tìm hiểu những bài hard thời gian này. Để làm kĩ những bài medium để cải thiện đã

Click to expand...

pikachu_1 said:

Bài 3 thì trong thời gian contest thì mình nghĩ ra chạy 1 chiều thôi nên mất O(nlogn)
Còn bài 2 chẳng hiểu sao cần dùng prefix.
Sorr xong thì pop dần.
Luôn đảm bảo thằng lớn nhất không quá nửa tổng là xong thôi mà

Click to expand...

from bisect import bisect_left
class Solution(object):
    def incremovableSubarrayCount(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        front = [nums[0]]
        for i in range(1, n):
            if nums[i] <= front[-1]:
                break
            front.append(nums[i])
        back = nums[-1]
        index_back = n-1
        total = min(n, len(front) + 1) + min(index_back, bisect_left(front, back)+1)
        for i in range(n-2, -1, -1):
            if nums[i] >= back:
                break
            back = nums[i]
            total += min(i, bisect_left(front, back)+1)
        return total

pikachu_1 said:

Bài 3 thì trong thời gian contest thì mình nghĩ ra chạy 1 chiều thôi nên mất O(nlogn)
Còn bài 2 chẳng hiểu sao cần dùng prefix.
Sorr xong thì pop dần.
Luôn đảm bảo thằng lớn nhất không quá nửa tổng là xong thôi mà

Click to expand...

Max Flow said:

bác cho em hỏi time của các contest này với

Click to expand...

Takeitiz said:

vào đây hứa tham gia contest đầy đủ

Click to expand...

Violet_7 said:

Hẹn ae năm sau. Cuối năm lắm việc quá ko chơi contest đc

Click to expand...

freedom.9 said:

My fence vô chia sẻ kinh nghiệm cày cuốc cho ae đi cách học như thế nào để lên Guardian

via theNEXTvoz for iPhone

Click to expand...