thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

freedom.9 đã nói:

Cái này là tính năng của Python ở Leetcode rồi. Có đợt mình đc rejudge về rank 263 luôn. Lúc làm thì TLE xong nó rejudge ko TLE


via theNEXTvoz for iPhone

Nhấp để mở rộng...

Husqvarna701SM đã nói:

Cứ nghĩ mỗi codeforce bị mà lc cũng bị, hơi oải, đợt này đang quen làm algo = python r

Nhấp để mở rộng...

athxzz đã nói:

trình cùi k làm contest nhưng được cái chăm copy paste để solve daily problems, thế lày là chuẩn bị có áo rồi à các tiền bối
Xem tệp đính kèm 3118470

Nhấp để mở rộng...

athxzz đã nói:

trình cùi k làm contest nhưng được cái chăm copy paste để solve daily problems, thế lày là chuẩn bị có áo rồi à các tiền bối
Xem tệp đính kèm 3118470

Nhấp để mở rộng...

aNotHeRNo0b đã nói:

Q3 tuần vừa rồi đúng là không khó thật, lúc làm không nhìn ra DP, cứ greedy mãi

Nhấp để mở rộng...

freedom.9 đã nói:

xor thì sao mà greedy đc vì càng xor nó lật bit sẽ có case tăng dần mà. Lúc đầu mình cũng Greedy vì nhớ lộn xor và and
Chỉ Dp là ăn thôi


via theNEXTvoz for iPhone

Nhấp để mở rộng...

dhl001 đã nói:

cho mình tham khảo công thức DP bài đấy với. mình bị ngu DP

Nhấp để mở rộng...

class Solution {
    public int minXor(int[] nums, int k) {
        int[][] memo = new int[nums.length + 1][k + 1];
        for (int i = 0; i < nums.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return tryToPartition(0, k, nums, memo);
    }

    public int tryToPartition(int index, int remainPartition, int[] nums, int[][] memo) {
        if (index == nums.length && remainPartition == 0) {
            return 0;
        }

        if (index == nums.length || remainPartition == 0) {
            return Integer.MAX_VALUE;
        }

        if (memo[index][remainPartition] != -1) {
            return memo[index][remainPartition];
        }

        int curXor = 0;
        int maximumXor = curXor;
        int answer = Integer.MAX_VALUE;
        for (int i = index; i <= nums.length - remainPartition; i++) {
            curXor ^= nums[i];
            maximumXor = Math.max(
                curXor,
                tryToPartition(i + 1, remainPartition - 1, nums, memo)
            );

            answer = Math.min(answer, maximumXor);
        }

        memo[index][remainPartition] = answer;
        return answer;
    }


}

aNotHeRNo0b đã nói:

À mình ko làm bottom-up, làm top-down

Spoiler: Java - O(n^3)

Java:

class Solution {
    public int minXor(int[] nums, int k) {
        int[][] memo = new int[nums.length + 1][k + 1];
        for (int i = 0; i < nums.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return tryToPartition(0, k, nums, memo);
    }

    public int tryToPartition(int index, int remainPartition, int[] nums, int[][] memo) {
        if (index == nums.length && remainPartition == 0) {
            return 0;
        }

        if (index == nums.length || remainPartition == 0) {
            return Integer.MAX_VALUE;
        }

        if (memo[index][remainPartition] != -1) {
            return memo[index][remainPartition];
        }

        int curXor = 0;
        int maximumXor = curXor;
        int answer = Integer.MAX_VALUE;
        for (int i = index; i <= nums.length - remainPartition; i++) {
            curXor ^= nums[i];
            maximumXor = Math.max(
                curXor,
                tryToPartition(i + 1, remainPartition - 1, nums, memo)
            );

            answer = Math.min(answer, maximumXor);
        }

        memo[index][remainPartition] = answer;
        return answer;
    }


}

Nhấp để mở rộng...

athxzz đã nói:

Bác rating bao nhiêu thế? trông DP sướng z

Nhấp để mở rộng...

athxzz đã nói:

Bác rating bao nhiêu thế? trông DP sướng z

Nhấp để mở rộng...

dhl001 đã nói:

Q2 còn 2 testcase không pass đc, mình dùng dijkstra
Xem tệp đính kèm 3126822

Nhấp để mở rộng...

LmaoSuVuong đã nói:

này là dính edge case chứ có phải giải sai đâu bác

Nhấp để mở rộng...

freedom.9 đã nói:

Con mẹ bài 3 làm kĩ thế mà quên set visited ăn 2 bug

Nhấp để mở rộng...

dhl001 đã nói:

2 bài mình dùng dijkstra nên không có dùng mảng visited. Nghĩ lại 2 bài này dùng BFS tốt hơn nhỉ

Nhấp để mở rộng...