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

ilovely · 24/3/24

freedom.9 đã nói:
Q3 giải trong vòng 5 ph cmnr mà làm cái q2 tới cuối giờ mới ra. Trash quá
Câu 1 thì đọc lộn đề, cứ tưởng chỉ có 1 kí tự xuất hiện 2 lần. Bad contest ever
Câu 4 thì xài cái sortedlist xong luôn rồi.

Python:

class Solution: def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]: frequency = defaultdict(int) maxHeap = [] ans = [] for i in range(len(nums)): frequency[nums[i]] += freq[i] heapq.heappush(maxHeap, (-frequency[nums[i]], nums[i])) while maxHeap[0][0]*-1 != frequency[maxHeap[0][1]]: heapq.heappop(maxHeap) ans.append(maxHeap[0][0]*-1) return ans

Câu 3 của fen đẹp vậy, t không nghĩ ra dùng sortedlist với maxheap nên mò mất gần tiếng mới xong, mà code xấu mù =((

Câu 1 dùng BingAI viết hộ

Câu 2 mất gần 15 phút

Câu 4 chịu

Ngoài lề tí: Tuần trước mới được huy hiệu Knight, không rõ nếu bị tụt điểm có mất huy hiệu không nhỉ?

freedom.9 · 24/3/24

ilovely đã nói:
Câu 3 của fen đẹp vậy, t không nghĩ ra dùng sortedlist với maxheap nên mò mất gần tiếng mới xong, mà code xấu mù
Câu 1 dùng BingAI viết hộ
Câu 2 mất gần 15 phút
Câu 4 chịu

Đẹp thì cũng bị trừ mất 30 điểm rồi vì mình có làm đâu fence :ah:

sau contest mình mới đọc đề rồi làm do xác định làm xong câu 2 bị trừ hết điểm cmnr =((

Nay Q4 cũng dễ, thôi sau rút kinh nghiệm nói không với OT thứ 7.

freedom.9 · 24/3/24

@ilovely bị mất nha, nên ráng cày lên rank cao tầm 2k thì mới ổn định.

humanversion9x · 24/3/24

ilovely đã nói:
Câu 3 của fen đẹp vậy, t không nghĩ ra dùng sortedlist với maxheap nên mò mất gần tiếng mới xong, mà code xấu mù
Câu 1 dùng BingAI viết hộ
Câu 2 mất gần 15 phút
Câu 4 chịu

Ngoài lề tí: Tuần trước mới được huy hiệu Knight, không rõ nếu bị tụt điểm có mất huy hiệu không nhỉ?
Xem tệp đính kèm 2400982

Nếu bị tụt thì huy hiệu bị mờ đi thôi.
Trong voz nhiều cao thủ nhỉ, có mấy bạn mới tham gia vài contest đã có huy hiệu rồi.

itcode · 24/3/24

Bài 3 chưa biết cách lấy nhanh max value từ Counter nên bị TLE tụt quần. Hôm nay học được cái trick heap của bài 3 vui ghê.

freedom.9 · 24/3/24

humanversion9x đã nói:
Nếu bị tụt thì huy hiệu bị mờ đi thôi.
Trong voz nhiều cao thủ nhỉ, có mấy bạn mới tham gia vài contest đã có huy hiệu rồi.

Công nhận, cày 5 cái contests đã có knight rồi đỉnh thật. Mình cày 40 cái rồi, số lần giải được bài 3 hơn chục lần, bài 4 2 lần rồi vẫn ko lên nổi knight =((

freedom.9 · 24/3/24

itcode đã nói:
Bài 3 chưa biết cách lấy nhanh max value từ Counter nên bị TLE tụt quần. Hôm nay học được cái trick heap của bài 3 vui ghê.

Nếu bác ko xài heap thì bác có thể dùng 1 cái sorted list theo frequency, xong rồi binary search rồi remove cái values ra update lại thôi. Cái trick này mình học được ở 1 bài build cái data structure gì đó ko nhớ nữa, hồi đó cũng thấy hay vl nên nhớ mãi.

nahnahinin · 24/3/24

câu 3 em cũng dùng PQueue mà không trick gì cả, thêm 1 cái map track lần cuối cùng thằng nums update, nếu poll từ heap ra thằng max frequent đọ với cái map track lần cuối kia không trùng nhau thì nghĩa là đã cũ, bỏ đi không lấy là được.

itcode · 24/3/24

freedom.9 đã nói:
Nếu bác ko xài heap thì bác có thể dùng 1 cái sorted list theo frequency, xong rồi binary search rồi remove cái values ra update lại thôi. Cái trick này mình học được ở 1 bài build cái data structure gì đó ko nhớ nữa, hồi đó cũng thấy hay vl nên nhớ mãi.

Chắc ý bác là bài này hả? Thấy có dùng binary search trên cái timestamp sau khi tìm key trong hashmap:

https://leetcode.com/problems/time-based-key-value-store/description/

via theNEXTvoz for iPhone

ilovely · 24/3/24

freedom.9 đã nói:
Công nhận, cày 5 cái contests đã có knight rồi đỉnh thật. Mình cày 40 cái rồi, số lần giải được bài 3 hơn chục lần, bài 4 2 lần rồi vẫn ko lên nổi knight

T thì thường làm được 2/4 hoặc 3/4 câu, có 1 lần được 4/4 thôi.
Mấy contest đầu sẽ cộng trừ điểm nhiều hơn, 40 lần dự contest rồi thì điểm lên xuống chậm, nhưng có lẽ fen cũng sẽ lên được knight thôi

humanversion9x · 24/3/24

ilovely đã nói:
T thì thường làm được 2/4 hoặc 3/4 câu, có 1 lần được 4/4 thôi.
Mấy contest đầu sẽ cộng trừ điểm nhiều hơn, 40 lần dự contest rồi thì điểm lên xuống chậm, nhưng có lẽ fen cũng sẽ lên được knight thôi

Quan trọng là xếp hạng của bạn trong contest cao thì sau 5 lần được trên knight.
Mình đoán là những lần bạn giải được 2/4 là những contest có câu 3 khó.

freedom.9 · 24/3/24

ilovely đã nói:
T thì thường làm được 2/4 hoặc 3/4 câu, có 1 lần được 4/4 thôi.
Mấy contest đầu sẽ cộng trừ điểm nhiều hơn, 40 lần dự contest rồi thì điểm lên xuống chậm, nhưng có lẽ fen cũng sẽ lên được knight thôi

Thực ra knight chưa phải target cuối cùng của mình nên vài contests nữa chắc mình cũng lên thôi. Chủ yếu vì tính mình hay cẩu thả nên hay tìm cách rèn nhưng mà chưa cải thiện lắm.
Chắc từ tuần sau mình nhảy qua codeforce, nhiều contests để luyện hơn, có thể upsolve problems được hơn là leetcode.
Leetcode giải nhiều nhưng mà problems nó ko filter theo rank để luyện tập cho dễ, nên dẫn tới trường hợp bài thì giải nhanh, bài thì tịt luôn :sweat:

via theNEXTvoz for iPhone

Violet_7 · 24/3/24

freedom.9 đã nói:
Thực ra knight chưa phải target cuối cùng của mình nên vài contests nữa chắc mình cũng lên thôi. Chủ yếu vì tính mình hay cẩu thả nên hay tìm cách rèn nhưng mà chưa cải thiện lắm.
Chắc từ tuần sau mình nhảy qua codeforce, nhiều contests để luyện hơn, có thể upsolve problems được hơn là leetcode.
Leetcode giải nhiều nhưng mà problems nó ko filter theo rank để luyện tập cho dễ, nên dẫn tới trường hợp bài thì giải nhanh, bài thì tịt luôn

via theNEXTvoz for iPhone

rating (https://zerotrac.github.io/leetcode_problem_rating/#/). Rank thì vào trang này lựa bài cx đc bác :big_smile:

TLE_WA · 24/3/24

Thực ra nếu muốn fast solve và phần tư duy nhạy hơn thì nên luyện trên Atcoder. Hơi ác cảm với codeforces vụ đề dài :surrender:

RTX3090 · 24/3/24

Tuần này ko sắp xếp đc thời gian tham gia, chán :too_sad:

NahSama · 24/3/24

mỗi tuần móc được 3-6 bài từ contest, chẳng mấy mà lên 1k bài

NahSama · 24/3/24

câu 2 dùng toán
câu 3 dùng hashmap + max heap (priorityQueue), trong pq sẽ có những data cũ, poll peak ra so sánh với hashmap nếu freq bằng nhau thì lấy không thì poll tiếp.
câu 4 nhìn vào nghĩ ngay trie nhưng lười code quá :whistle:

edit: cau 4: build trie cho từng word trong wordsContainer rồi lưu luôn possible solution (word và index) tại node đó vào. Trong lúc build trie thì update lại possible solution cho các node được visit mỗi lần thêm word mới.

Java:

class Solution {
    class Trie {
        Trie[] children;
        String solution;
        int index;

        public Trie(String s, int index) {
            this.children = new Trie[26];
            this.solution = s;
            this.index = index;
        }

        public void add(String s, int index) {
            Trie cur = this;

            if (s.length() < cur.solution.length()) {
                cur.solution = s;
                cur.index = index;
            }
           
            for (int i = s.length() - 1; i >= 0; i--) {
                if (cur.children[s.charAt(i) - 'a'] == null) {
                    cur.children[s.charAt(i) - 'a'] = new Trie(s, index);
                }

                cur = cur.children[s.charAt(i) - 'a'];
                if (s.length() < cur.solution.length()) {
                    cur.solution = s;
                    cur.index = index;
                }
            }
        }

        public int search(String s) {
            Trie cur = this;
            int ans = this.index;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (cur.children[s.charAt(i) - 'a'] == null) {
                    return ans;
                }

                cur = cur.children[s.charAt(i) - 'a'];
                ans = cur.index;
            }
            return ans;
        }
    }


    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        Trie root = new Trie(wordsContainer[0], 0);
        for (int i = 0; i < wordsContainer.length; i++) {
            root.add(wordsContainer[i], i);
        }
        int[] ans = new int[wordsQuery.length];
        int index = 0;
        for (String word: wordsQuery) {
            ans[index++] = root.search(word);
        }

        return ans;
    }
}

NahSama · 24/3/24

freedom.9 đã nói:
1791, đm tuần trước làm bài 3 óc heo quá rank hơn 5k rồi 2 contests tăng đc có 19 điểm.
Tuần này bận quá ko cải thiện được skill gì rồi, cần phải giải nhanh hơn mới được. No hope Knight tuần này

via theNEXTvoz for iPhone

tạo acc mới cày contest lại thôi thím :boss:

cứ 3/4 vài lần là knight ngay ấy mà

freedom.9 · 24/3/24

À mấy fence cho mình hỏi thử sao bài 2 giải bằng DFS thì nó throws TLE nhỉ
Time complexity với space complexity chỉ là O(n) thôi mà, vì worst case ở mỗi trường hợp nó tăng lên từ 1 -> 10^5 thôi chứ nhỉ

Python:

from collections import deque

class Solution:
    def minOperations(self, k: int) -> int:
        visited = set()
        queue = deque()
        queue.append((0, 1, 1))
       
        while queue:
            operations, total, lastNum = queue.popleft()
           
            if total >= k:
                return operations
           
            if (total, lastNum) in visited:
                continue
           
            visited.add((total, lastNum))
           
            queue.append((operations + 1, total + lastNum, lastNum))
            queue.append((operations + 1, total + 1, lastNum + 1))
           
        return -1

humanversion9x · 25/3/24

freedom.9 đã nói:
À mấy fence cho mình hỏi thử sao bài 2 giải bằng DFS thì nó throws TLE nhỉ
Time complexity với space complexity chỉ là O(n) thôi mà, vì worst case ở mỗi trường hợp nó tăng lên từ 1 -> 10^5 thôi chứ nhỉ

Python:

from collections import deque class Solution: def minOperations(self, k: int) -> int: visited = set() queue = deque() queue.append((0, 1, 1)) while queue: operations, total, lastNum = queue.popleft() if total >= k: return operations if (total, lastNum) in visited: continue visited.add((total, lastNum)) queue.append((operations + 1, total + lastNum, lastNum)) queue.append((operations + 1, total + 1, lastNum + 1)) return -1

Thuật toán này có Time complexity là 1 + 2 + 4 + 8 + .. + 2^k = 2^(k+1) - 1 = O(2^k) rồi bạn.

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

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này