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

  • Người tạo chủ đề Người tạo chủ đề freedom.9
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
freedom.9 đã nói:
11^10 thì TLE chứ sao mà ăn đc fence. Cho mình xem sol với
via theNEXTvoz for iPhone
Nhấp để mở rộng...
JavaScript: 
function maxScore(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;

  const a: Set<number>[] = new Array(m).fill(0).map(() => new Set());
  const sumM: number[] = new Array(m).fill(0);
  sumM[m - 1] = Math.max(...grid[m - 1]);
  for (var i = m - 2; i >= 0; i--) {
    sumM[i] = sumM[i + 1] + Math.max(...grid[i]);
  }
  for (var i = 0; i < m; i++) {
    for (var j = 0; j < n; j++) {
      a[i].add(grid[i][j]);
    }
  }

  var sum = 0;
  var res = 0;
  var set: Set<number> = new Set();

  const loop = (row: number) => {
    if (row === m) {
      return;
    }
    if (sum + sumM[row] <= res) {
      return;
    }
    for (var val of a[row]) {
      if (set.has(val)) {
        continue;
      }
      set.add(val);
      sum += val;
      if (res < sum) {
        res = sum;
      }
      loop(row + 1);
      sum -= val;
      set.delete(val);
    }
    loop(row + 1);
  };
  loop(0);
  return res;
}
 
thanhdonguyen01 đã nói:
Mấy thím cho hỏi bài hôm qua của Biweekly:
Q3. Find the Count of Good Integers

Em làm theo hướng này:

Gen hết palindrome chia hết cho k trước
Sau đó thì đếm số hoán vị của đống palindrome đấy mà không có chữ số 0 nào đứng đầu
Lúc đầu em chạy dùng cái gen permutation của Python thì bị TLE, sau đấy đếm bằng công thức toán thì bị sai ở n = 5, k = 6:

Python: 
    def count_valid_permutations(self, digits):
        n = len(digits)

        digit_counts = Counter(digits)

        total_permutations = factorial(n)
        for count in digit_counts.values():
            total_permutations //= factorial(count)

        if digit_counts[0] > 0:
            permutations_with_leading_zero = factorial(n - 1)
            for digit, count in digit_counts.items():
                if digit == 0:
                    count -= 1
                permutations_with_leading_zero //= factorial(count)
        else:
            permutations_with_leading_zero = 0

        valid_permutations = total_permutations - permutations_with_leading_zero
       
        return valid_permutations

Mọi người cho em hỏi không rõ hướng này của em có sai chỗ nào không ạ, em cảm ơn ạ :too_sad:
Nhấp để mở rộng...
Cho mình xem code gen ra palindrome thử, đoạn count đúng mà nhỉ

via theNEXTvoz for iPhone
 
lilleboybk đã nói:
JavaScript: 
function maxScore(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const a: Set<number>[] = new Array(m).fill(0).map(() => new Set());
  const sumM: number[] = new Array(m).fill(0);
  sumM[m - 1] = Math.max(...grid[m - 1]);
  for (var i = m - 2; i >= 0; i--) {
    sumM[i] = sumM[i + 1] + Math.max(...grid[i]);
  }
  for (var i = 0; i < m; i++) {
    for (var j = 0; j < n; j++) {
      a[i].add(grid[i][j]);
    }
  }

  var sum = 0;
  var res = 0;
  var set: Set<number> = new Set();

  const loop = (row: number) => {
    if (row === m) {
      return;
    }
    if (sum + sumM[row] <= res) {
      return;
    }
    for (var val of a[row]) {
      if (set.has(val)) {
        continue;
      }
      set.add(val);
      sum += val;
      if (res < sum) {
        res = sum;
      }
      loop(row + 1);
      sum -= val;
      set.delete(val);
    }
    loop(row + 1);
  };
  loop(0);
  return res;
}
Nhấp để mở rộng...
Fence dùng backtrack sao ăn đc hay thế ta.
Code fence thử chạy với testcase từ 1 đến 100 cho 10*10 grid thử

via theNEXTvoz for iPhone
 
freedom.9 đã nói:
Cho mình xem code gen ra palindrome thử, đoạn count đúng mà nhỉ

via theNEXTvoz for iPhone
Nhấp để mở rộng...

Python: 
    def generate_palindromes(self, n, k):
        palindromes = set()
       
        if n == 1:
            palindromes.update(i for i in range(1, 10) if i % k == 0)
            return sorted(list(palindromes))

        if n % 2 == 0:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                full_str = half_str + half_str[::-1]
                palindrome = int(full_str)
                if palindrome % k == 0:
                    palindromes.add(palindrome)
        else:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                for mid in range(10):
                    full_str = half_str + str(mid) + half_str[::-1]
                    palindrome = int(full_str)
                    if palindrome % k == 0:
                        palindromes.add(palindrome)

        return sorted(list(palindromes))

Đây thím ơi :too_sad:

Em duyệt trâu thì code này vẫn cho ra output đúng, nhưng dùng đoạn code tính số hoán vị ở trên thì output sai :too_sad:
 
freedom.9 đã nói:
Fence dùng backtrack sao ăn đc hay thế ta.
Code fence thử chạy với testcase từ 1 đến 100 cho 10*10 grid thử

via theNEXTvoz for iPhone
Nhấp để mở rộng...
Em thử rồi bác, với bảng từ 1->100, các ô được chọn đều là ô cuối mỗi hàng (10, 20,...) mà nó vẫn ko TLE, chạy nhanh là khác. Ko biết có case nào để TLE không.
 
thanhdonguyen01 đã nói:
Python: 
    def generate_palindromes(self, n, k):
        palindromes = set()
       
        if n == 1:
            palindromes.update(i for i in range(1, 10) if i % k == 0)
            return sorted(list(palindromes))

        if n % 2 == 0:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                full_str = half_str + half_str[::-1]
                palindrome = int(full_str)
                if palindrome % k == 0:
                    palindromes.add(palindrome)
        else:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                for mid in range(10):
                    full_str = half_str + str(mid) + half_str[::-1]
                    palindrome = int(full_str)
                    if palindrome % k == 0:
                        palindromes.add(palindrome)

        return sorted(list(palindromes))

Đây thím ơi :too_sad:

Em duyệt trâu thì code này vẫn cho ra output đúng, nhưng dùng đoạn code tính số hoán vị ở trên thì output sai :too_sad:
Nhấp để mở rộng...
Kì thật nhỉ, fen cho mình cái link submission mình debug xem thử, mình thấy tính đúng mà ta :pudency:

Cách của mình đây cũng tương tự mà, bác xem thử chứ mình ôm đt rồi
via theNEXTvoz for iPhone
 
lilleboybk đã nói:
Em thử rồi bác, với bảng từ 1->100, các ô được chọn đều là ô cuối mỗi hàng (10, 20,...) mà nó vẫn ko TLE, chạy nhanh là khác. Ko biết có case nào để TLE không.
Nhấp để mở rộng...
Hay do fence early return nhỉ? chứ rõ ràng cách này 10^10 thì sao pass được ta. Sợ nó rejudge fence đó.
Fence bỏ cái early return đi xem thử có TLE ko
via theNEXTvoz for iPhone
 
freedom.9 đã nói:
Hay do fence early return nhỉ? chứ rõ ràng cách này 10^10 thì sao pass được ta. Sợ nó rejudge fence đó.
Fence bỏ cái early return đi xem thử có TLE ko
via theNEXTvoz for iPhone
Nhấp để mở rộng...
Bỏ early return thì TLE là cái chắc rồi bác. Mà dị vl, để nguyên thì bảng 100x50 vẫn chạy dưới 1s. Bác thử xem.
 
Cố Trường Ca đã nói:
Đơn giản thế mà không nghĩ ra, contest không dành cho số đông rồi
4gmOAMB.png
6f4YXpQ.gif
Nhấp để mở rộng...
học gạo r
Java: 
class Solution {
    public int[] resultsArray(int[][] queries, int k) {
        int n = queries.length;
        int[] res = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b)->{
            return Math.abs(b[0])+Math.abs(b[1])- Math.abs(a[0])-Math.abs(a[1]);
        });
        int index=0;
        for(int[] query:queries){
            pq.offer(query);
            if(pq.size()<k) {
                res[index++] = -1;
            }else{
                while(pq.size()>k) pq.poll();
                int[] coordinate = pq.peek();
                res[index++]=Math.abs(coordinate[0]) + Math.abs(coordinate[1]);
            }
        }
        return res;
    }
}

bài này 4 point thôi, bth 5 point e làm mất cả tiếng :confident: bài này làm 5 phút thì 4p
 
LmaoSuVuong đã nói:
học gạo r
Java: 
class Solution {
    public int[] resultsArray(int[][] queries, int k) {
        int n = queries.length;
        int[] res = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b)->{
            return Math.abs(b[0])+Math.abs(b[1])- Math.abs(a[0])-Math.abs(a[1]);
        });
        int index=0;
        for(int[] query:queries){
            pq.offer(query);
            if(pq.size()<k) {
                res[index++] = -1;
            }else{
                while(pq.size()>k) pq.poll();
                int[] coordinate = pq.peek();
                res[index++]=Math.abs(coordinate[0]) + Math.abs(coordinate[1]);
            }
        }
        return res;
    }
}

bài này 4 point thôi, bth 5 point e làm mất cả tiếng :confident: bài này làm 5 phút thì 4p
Nhấp để mở rộng...
zFNuZTA.png
Nhân tổ chuyển thế
 
lilleboybk đã nói:
function maxScore(grid: number[][]): number { const m = grid.length; const n = grid[0].length; const a: Set<number>[] = new Array(m).fill(0).map(() => new Set()); const sumM: number[] = new Array(m).fill(0); sumM[m - 1] = Math.max(...grid[m - 1]); for (var i = m - 2; i >= 0; i--) { sumM = sumM[i + 1] + Math.max(...grid); } for (var i = 0; i < m; i++) { for (var j = 0; j < n; j++) { a.add(grid[j]); } } var sum = 0; var res = 0; var set: Set<number> = new Set(); const loop = (row: number) => { if (row === m) { return; } if (sum + sumM[row] <= res) { return; } for (var val of a[row]) { if (set.has(val)) { continue; } set.add(val); sum += val; if (res < sum) { res = sum; } loop(row + 1); sum -= val; set.delete(val); } loop(row + 1); }; loop(0); return res; }
Nhấp để mở rộng...
Á đù mình chạy lại vẫn ok, chắc do cái hàm early return của fence viết nó làm cho ko chạy tới 10^10 rồi :ah:
thanhdonguyen01 đã nói:

Đây thím ơi :too_sad:
Em đọc thấy cách cũng giống mà k biết sao sai :beat_brick:
Nhấp để mở rộng...
Hàm generate palindrome của fence bị sai nên dẫn tới nó bị duplicated palindromes nhà fence
Mình sửa lại thế này, lúc đầu fence chỉ add nó vô list nhưng mà lỡ có trường hợp 23432 hoặc 32423 thì nó add vô cái list đó 2 lần. Fence phải sort mấy cái digits nữa mới ok

Python: 
def generate_palindromes(self, n, k):
        palindromes = set()
        
        if n == 1:
            palindromes.update(i for i in range(1, 10) if i % k == 0)
            return sorted(list(palindromes))

        if n % 2 == 0:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                full_str = half_str + half_str[::-1]
                palindrome = int(full_str)
                if palindrome % k == 0:
                    palindromes.add("".join(sorted(list(full_str))))
        else:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                for mid in range(10):
                    full_str = half_str + str(mid) + half_str[::-1]
                    palindrome = int(full_str)
                    if palindrome % k == 0:
                        palindromes.add("".join(sorted(list(full_str))))
 
freedom.9 đã nói:
Á đù mình chạy lại vẫn ok, chắc do cái hàm early return của fence viết nó làm cho ko chạy tới 10^10 rồi :ah:

Hàm generate palindrome của fence bị sai nên dẫn tới nó bị duplicated palindromes nhà fence
Mình sửa lại thế này, lúc đầu fence chỉ add nó vô list nhưng mà lỡ có trường hợp 23432 hoặc 32423 thì nó add vô cái list đó 2 lần. Fence phải sort mấy cái digits nữa mới ok

Python: 
def generate_palindromes(self, n, k):
        palindromes = set()
      
        if n == 1:
            palindromes.update(i for i in range(1, 10) if i % k == 0)
            return sorted(list(palindromes))

        if n % 2 == 0:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                full_str = half_str + half_str[::-1]
                palindrome = int(full_str)
                if palindrome % k == 0:
                    palindromes.add("".join(sorted(list(full_str))))
        else:
            start, end = 10**(n//2 - 1), 10**(n//2)
            for i in range(start, end):
                half_str = str(i)
                for mid in range(10):
                    full_str = half_str + str(mid) + half_str[::-1]
                    palindrome = int(full_str)
                    if palindrome % k == 0:
                        palindromes.add("".join(sorted(list(full_str))))
Nhấp để mở rộng...
Tks thím :adore: , bảo sao dùng cái count tay thì nó ra kết quả đúng (vì set trong Python lọc hộ), mà tính bằng công thức toán thì nó ra kết quả sai :adore:

Tiếc quá, mất đoạn này nên k làm gỏi được 4 bài :too_sad:
 
thanhdonguyen01 đã nói:
Tks thím :adore: , bảo sao dùng cái count tay thì nó ra kết quả đúng (vì set trong Python lọc hộ), mà tính bằng công thức toán thì nó ra kết quả sai :adore:

Tiếc quá, mất đoạn này nên k làm gỏi được 4 bài :too_sad:
Nhấp để mở rộng...
Contest mình cũng ngáo vl, mấy bài gần đây tiếc vãi nhưng join đều đều chắc sẽ cải thiện nhiều =((
 
thanhdonguyen01 đã nói:
Mấy thím cho hỏi bài hôm qua của Biweekly:
Q3. Find the Count of Good Integers

Em làm theo hướng này:

Gen hết palindrome chia hết cho k trước
Sau đó thì đếm số hoán vị của đống palindrome đấy mà không có chữ số 0 nào đứng đầu
Lúc đầu em chạy dùng cái gen permutation của Python thì bị TLE, sau đấy đếm bằng công thức toán thì bị sai ở n = 5, k = 6:

Python: 
    def count_valid_permutations(self, digits):
        n = len(digits)

        digit_counts = Counter(digits)

        total_permutations = factorial(n)
        for count in digit_counts.values():
            total_permutations //= factorial(count)

        if digit_counts[0] > 0:
            permutations_with_leading_zero = factorial(n - 1)
            for digit, count in digit_counts.items():
                if digit == 0:
                    count -= 1
                permutations_with_leading_zero //= factorial(count)
        else:
            permutations_with_leading_zero = 0

        valid_permutations = total_permutations - permutations_with_leading_zero
      
        return valid_permutations

Mọi người cho em hỏi không rõ hướng này của em có sai chỗ nào không ạ, em cảm ơn ạ :too_sad:
Nhấp để mở rộng...
cái digits đưa vào có thể trùng nhau nên bạn chỉ cần unique chỗ này nữa là được
 
lilleboybk đã nói:
Leetcode rejudge làm cách của em bị TLE rồi bác, xuống rank 17k luôn
😂.
Nhấp để mở rộng...
Vl, nó thêm test case nào thế bác :sweat:
Cho mình cái test cases với, cười vãi.
Đm bài này đúng dễ mà sao hôm đó mình ko làm đc, dùng dp quá dễ luôn :too_sad: bài 6 điểm có khác
Đang ở Guardian mà ăn rank 17k về luôn vozliz mất :sweat:
via theNEXTvoz for iPhone
 
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

kaiany
thảo luận Đi NVQS 2 năm, cơ hội nào cho Kỹ sư Phần mềm quay lại IT?
Trả lời
18
Lượt xem
2K
kaiany
kaiany
atomwaffen
Huyền thoại Toán học Việt Nam: Cần xem các kỳ thi mang lại gì cho học sinh
Trả lời
7
Lượt xem
716
kingvn01
kingvn01
ChatGPT AI
Choáng ngợp với nam sinh mang 156 tấm huy chương lên nhận bằng tốt nghiệp
2
Trả lời
39
Lượt xem
2K
sangbuif
sangbuif
condao
thảo luận Sóng gió ập tới, nghề lập trình đang thay đổi ra sao với AI.
9 10 11
Trả lời
202
Lượt xem
27K
hoangphi1650
hoangphi1650
BlueGecko
[Hoa Kỳ] 'Nhan sắc' của chú chó xấu nhất thế giới
2 3
Trả lời
45
Lượt xem
40K
Lee Sin Cướp Rừng
L

Thống kê chủ đề

Ngày tạo
freedom.9,
Người trả lời cuối
freedom.9,
Trả lời
2.480
Lượt xem
130.261

Chia sẻ trang này

Quay lại
Lên đầu trang