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

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á :ah:
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 :ah:
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
 
freedom.9 said:
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á :ah:
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 :ah:
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
Click to expand...
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ộ :D
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ỉ?
1711255135247.png
 
ilovely said:
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ộ :D
Câu 2 mất gần 15 phút :)
Câu 4 chịu :(
Click to expand...
Đẹ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.
 
ilovely said:
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ộ :D
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ỉ?
View attachment 2400982
Click to expand...
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.
 
humanversion9x said:
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.
Click to expand...
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 =((
 
itcode said:
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ê.
Click to expand...
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.
 
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.
 
freedom.9 said:
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.
Click to expand...
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:

via theNEXTvoz for iPhone
 
freedom.9 said:
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 =((
Click to expand...
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 :D
 
ilovely said:
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 :D
Click to expand...
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ó.
 
ilovely said:
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 :D
Click to expand...
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
 
freedom.9 said:
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
Click to expand...
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:
 
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:
 
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;
    }
}
 
Last edited:
freedom.9 said:
1791, đm tuần trước làm bài 3 óc heo quá rank hơn 5k rồi :too_sad: 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 :too_sad:

via theNEXTvoz for iPhone
Click to expand...
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à
 
À 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
 
Last edited:

Similar threads

K
tin tức Cuộc thi “The Next KOC - Thế hệ ai cũng có thể” của MoMo và Schannel: Tìm kiếm nhà sáng tạo nội dung kể chuyện đời thường
Replies
3
Views
197
HoQuangTuan
HoQuangTuan
Con Cưng Nó Cú
Phát động cuộc thi Việt Nam hạnh phúc, tổng giá trị giải thưởng 400 triệu đồng
2 3 4
Replies
66
Views
4K
Wibu Heavy Industries
Wibu Heavy Industries
Bing AI
Viết 'Help' lên cát, 3 người đàn ông được cứu khỏi đảo hoang
Replies
18
Views
2K
trivu11
trivu11
4 More Years
Anh em song sinh đuối nước: Huy động flycam, tìm được thi thể nạn nhân còn lại
Replies
18
Views
898
fotyofot
fotyofot
Tintucmoi.pl
tin tức Chức vô địch Premier League có thể được quyết định bằng trận play-off chưa từng có
Replies
6
Views
631
0388xx8888
0388xx8888

Share this page

Back
Top