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

  • Người tạo chủ đề Người tạo chủ đề freedom.9
  • Ngày bắt đầu Ngày bắt đầu
Q2 em làm dù là O(n) nhưng dài vl, bác nào có cách elegant hơn ko

Python: 
class Solution:
    def numOfSubsequences(self, s: str) -> int:
        # Case add L
        L = [1]
        LC = [0]
        l = 1
        c = 0
        t = 0
        res1 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res1 += LC[-1]
            L.append(l)
            LC.append(c)

        # Case add T
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res2 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res2 += LC[-1]
            L.append(l)
            LC.append(c)
        res2 += LC[-1]

        # Case add C
        prefix_L = [0]
        for char in s:
            if char == "L":
                val = prefix_L[-1] + 1
            else:
                val = prefix_L[-1]
            prefix_L.append(val)
        postfix_T = [0]
        for char in s[::-1]:
            val = postfix_T[-1]
            if char == "T":
                val += 1
            postfix_T.append(val)
        postfix_T = postfix_T[::-1]
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res3 = 0
        plus = 0
        for i, char in enumerate(s):
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res3 += LC[-1]
            L.append(l)
            LC.append(c)
            plus = max(plus, prefix_L[i + 1] * postfix_T[i + 1])
        return max([res1, res2, res3 + plus])
 
Manmapi đã nói:
Q2 em làm dù là O(n) nhưng dài vl, bác nào có cách elegant hơn ko

Python: 
class Solution:
    def numOfSubsequences(self, s: str) -> int:
        # Case add L
        L = [1]
        LC = [0]
        l = 1
        c = 0
        t = 0
        res1 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res1 += LC[-1]
            L.append(l)
            LC.append(c)

        # Case add T
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res2 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res2 += LC[-1]
            L.append(l)
            LC.append(c)
        res2 += LC[-1]

        # Case add C
        prefix_L = [0]
        for char in s:
            if char == "L":
                val = prefix_L[-1] + 1
            else:
                val = prefix_L[-1]
            prefix_L.append(val)
        postfix_T = [0]
        for char in s[::-1]:
            val = postfix_T[-1]
            if char == "T":
                val += 1
            postfix_T.append(val)
        postfix_T = postfix_T[::-1]
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res3 = 0
        plus = 0
        for i, char in enumerate(s):
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res3 += LC[-1]
            L.append(l)
            LC.append(c)
            plus = max(plus, prefix_L[i + 1] * postfix_T[i + 1])
        return max([res1, res2, res3 + plus])
Nhấp để mở rộng...
Em làm 3 trường hợp, chèn L đầu, chèn T cuối và tìm vị trí firstL * backT lớn nhất để chèn C. Hai cái hàm đâu code chung được, xong for thêm tính cái chèn C thôi
 
freedom.9 đã nói:
Mẹ nó cái Q1 type nhanh ăn bug, Q2 type ngu cũng ăn bug, Q3 type chuẩn thì ăn 3 bugs do TLE + MLE, đen vãi =((
Q1 cũng dễ mà nghĩ lâu quá, Q2 thì max dễ mà cũng nghĩ lâu lol, Q3 thì gõ lộn =((
Q3 thì dùng bfs thôi, với nhớ check visited của cái số primes để khỏi bị TLE, vì số primes chỉ có giới hạn thôi.
Giả sử arr là số primes thì từ số primes đó sẽ nhảy đc qua pos khác, nếu có arr j = arr i thì ko cần phải xử lí chỗ arr j nữa
Python: 
MAX = 10**6 + 2
primes = [True]*MAX
primes[0] = primes[1] = False

for i in range(MAX):
    if primes[i]:
        for j in range(i + i, MAX, i):
            primes[j] = False
            
class Solution:
    def minJumps(self, nums: List[int]) -> int:
        queue = deque()
        indexs = defaultdict(list)
        for i, val in enumerate(nums):
            indexs[val].append(i)

        mx = max(nums)
        queue.append((0, 0))
        n = len(nums)
        visited = [False]*n
        visited[0] = True
        primesSet = set()

        while queue:
            current, step = queue.popleft()
            if current == n - 1:
                return step

            if current + 1 < n and not visited[current + 1]:
                visited[current + 1] = True
                queue.append((current + 1, step + 1))

            if current - 1 >= 0 and not visited[current - 1]:
                visited[current - 1] = True
                queue.append((current - 1, step + 1))

            if primes[nums[current]] and nums[current] not in primesSet:
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1

                primesSet.add(nums[current])

        return -1



Xem tệp đính kèm 3161055
Nhấp để mở rộng...
@freedom.9 "check visited của cái số primes" Mình thấy cách này của bạn rất hay.
 
Cái Q3 ban đầu theo hướng DP bị fail
Đổi lại BFS mất thời gian + TLE
Với lại có sẵn cái template cho primes thì sẽ tiết kiệm thời gian debug :ah:
Java: 
class Solution {
    Map<Integer, Set<Integer>> primeFactors = new HashMap<>();
    private static int[] primes100 = new int[] {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
            107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
            227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
            349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
            467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
            613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
            751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
            887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,
            1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097 };

    private Map<Integer, Set<Integer>> primeFactorMap = new HashMap<>();

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, Set<Integer>> indexMap = new HashMap<>();
        for (int i = n - 1; i >= 0; i--) {
            var pList = getFactor(nums[i]);
            for (var p : pList) {
                var m = indexMap.getOrDefault(p, new HashSet<>());
                m.add(i);
                indexMap.put(p, m);
            }
        }

        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[] visited = new boolean[n];
        q.add(new int[] { 0, 0 });
        visited[0] = true;
        while (!q.isEmpty()) {
            var cur = q.poll();
            if (cur[1] == n - 1) {
                return cur[0];
            }
            if (cur[1] + 1 < n && !visited[cur[1] + 1]) {
                q.add(new int[] { cur[0] + 1, cur[1] + 1 });
                visited[cur[1] + 1] = true;
            }
            if (cur[1] - 1 > 0 && !visited[cur[1] - 1]) {
                q.add(new int[] { cur[0] + 1, cur[1] - 1 });
                visited[cur[1] - 1] = true;
            }
            var jums = indexMap.get(nums[cur[1]]);
            if (jums == null)
                continue;
            for (var j : jums) {
                if (cur[1] == j || visited[j])
                    continue;
                q.add(new int[] { cur[0] + 1, j });
                visited[j] = true;
            }
        }

        return 0;
    }

    private Set<Integer> getFactor(int num) {
        if (primeFactorMap.containsKey(num))
            return primeFactorMap.get(num);
        int key = num;
        Set<Integer> res = new HashSet<>();
        int i = 0;
        while (i < primes100.length && num > primes100[i]) {
            while (num % primes100[i] == 0) {
                res.add(primes100[i]);
                num /= primes100[i];
            }
            i++;
        }
        if (num > 1)
            res.add(num);
        primeFactorMap.put(key, res);
        return res;
    }

}
 
dhl001 đã nói:
Cái Q3 ban đầu theo hướng DP bị fail
Đổi lại BFS mất thời gian + TLE
Với lại có sẵn cái template cho primes thì sẽ tiết kiệm thời gian debug :ah:
Java: 
class Solution {
    Map<Integer, Set<Integer>> primeFactors = new HashMap<>();
    private static int[] primes100 = new int[] {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
            107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
            227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347,
            349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
            467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
            613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
            751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
            887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031,
            1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097 };

    private Map<Integer, Set<Integer>> primeFactorMap = new HashMap<>();

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, Set<Integer>> indexMap = new HashMap<>();
        for (int i = n - 1; i >= 0; i--) {
            var pList = getFactor(nums[i]);
            for (var p : pList) {
                var m = indexMap.getOrDefault(p, new HashSet<>());
                m.add(i);
                indexMap.put(p, m);
            }
        }

        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[] visited = new boolean[n];
        q.add(new int[] { 0, 0 });
        visited[0] = true;
        while (!q.isEmpty()) {
            var cur = q.poll();
            if (cur[1] == n - 1) {
                return cur[0];
            }
            if (cur[1] + 1 < n && !visited[cur[1] + 1]) {
                q.add(new int[] { cur[0] + 1, cur[1] + 1 });
                visited[cur[1] + 1] = true;
            }
            if (cur[1] - 1 > 0 && !visited[cur[1] - 1]) {
                q.add(new int[] { cur[0] + 1, cur[1] - 1 });
                visited[cur[1] - 1] = true;
            }
            var jums = indexMap.get(nums[cur[1]]);
            if (jums == null)
                continue;
            for (var j : jums) {
                if (cur[1] == j || visited[j])
                    continue;
                q.add(new int[] { cur[0] + 1, j });
                visited[j] = true;
            }
        }

        return 0;
    }

    private Set<Integer> getFactor(int num) {
        if (primeFactorMap.containsKey(num))
            return primeFactorMap.get(num);
        int key = num;
        Set<Integer> res = new HashSet<>();
        int i = 0;
        while (i < primes100.length && num > primes100[i]) {
            while (num % primes100[i] == 0) {
                res.add(primes100[i]);
                num /= primes100[i];
            }
            i++;
        }
        if (num > 1)
            res.add(num);
        primeFactorMap.put(key, res);
        return res;
    }

}
Nhấp để mở rộng...
Cheatinggg 🤣🤣🤣 đùa tgoi8 bác, trick này hay
 
Manmapi đã nói:
Q2 em làm dù là O(n) nhưng dài vl, bác nào có cách elegant hơn ko

Python: 
class Solution:
    def numOfSubsequences(self, s: str) -> int:
        # Case add L
        L = [1]
        LC = [0]
        l = 1
        c = 0
        t = 0
        res1 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res1 += LC[-1]
            L.append(l)
            LC.append(c)

        # Case add T
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res2 = 0
        for char in s:
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res2 += LC[-1]
            L.append(l)
            LC.append(c)
        res2 += LC[-1]

        # Case add C
        prefix_L = [0]
        for char in s:
            if char == "L":
                val = prefix_L[-1] + 1
            else:
                val = prefix_L[-1]
            prefix_L.append(val)
        postfix_T = [0]
        for char in s[::-1]:
            val = postfix_T[-1]
            if char == "T":
                val += 1
            postfix_T.append(val)
        postfix_T = postfix_T[::-1]
        L = [0]
        LC = [0]
        l = 0
        c = 0
        t = 0
        res3 = 0
        plus = 0
        for i, char in enumerate(s):
            if char == "L":
                l += 1
            elif char == "C":
                c += L[-1]
            elif char == "T":
                res3 += LC[-1]
            L.append(l)
            LC.append(c)
            plus = max(plus, prefix_L[i + 1] * postfix_T[i + 1])
        return max([res1, res2, res3 + plus])
Nhấp để mở rộng...
Có bác, đầu tiên 1 pass để đếm l từ bên trái và t ở bên phải tại mỗi i.
Pass thứ 2 chỉ chạy một phát nữa, nếu gặp C thì ans cho case thêm L vô bên trái là (countL + 1)countT, thêm T vô bên phải là countL(countT + 1), và tìm max của countL*countT cho case thứ 3 để insert c vô giữa
Tìm max của cả 3 là xong.

via theNEXTvoz for iPhone
 
sợ mất rank nên làm virtual tâm lý thoải mái giải cũng ổn ko bug gì:
mqmyNGM.png

1753602534486.png

Java: 
class Solution {
    public long maximumMedianSum(int[] nums) {
        long res =0;
        Arrays.sort(nums);
        int i=0;
        int n = nums.length;
        int j = n-1;
        
        for(;i<n/3;i++ ){
            res+= nums[j-1];
            j-=2;
        }
        return res;
    }
}
C-like: 
func numOfSubsequences(s string) int64 {
    n := len(s)

    cntL := make([]int, n)
    cntT := make([]int, n)
    cnt := 0
    for i, c := range s {
        if c == 'L' {
            cnt++
        }
        cntL[i] = cnt
    }
    cnt = 0
    for i := n - 1; i >= 0; i-- {
        if s[i] == 'T' {
            cnt++
        }
        cntT[i] = cnt
    }

    var (
        maxLT int64 = 0
        addL  int64 = 0
        addT  int64 = 0
        addC  int64 = 0
    )
    for i, c := range s {
        l := int64(cntL[i])
        t := int64(cntT[i])
        if c == 'C' {
            addL += (l + 1) * t
            addT += l * (t + 1)
            addC += l * t
        }
        if l*t > maxLT {
            maxLT = l * t
        }
    }
    addC += maxLT

    return max3(addL, addT, addC)
}

func max3(a, b, c int64) int64 {
    if a >= b && a >= c {
        return a
    }
    if b >= a && b >= c {
        return b
    }
    return c
}
Java: 
class Solution {
    public int minJumps(int[] nums) {
        int n = nums.length;
        int max = 0;

        Map<Integer, List<Integer>> m = new HashMap<>();
        for (int i = 0; i < n; i++) {
            max = Math.max(nums[i], max);
            m.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        boolean[] isPrime = new boolean[max + 1];
        List<Integer> primes = sieve(max + 1, isPrime);

        Map<Integer, List<Integer>> primeTele = new HashMap<>();
        for (int prime : primes) {
            primeTele.put(prime, new ArrayList<>());
            for (int j = 1; prime * j <= max; j++) {
                int val = prime * j;
                if (m.containsKey(val)) {
                    List<Integer> idxList = m.get(val);
                    if (idxList != null) {
                        primeTele.get(prime).addAll(idxList);
                    }
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        int step = 0;
        boolean[] visited = new boolean[n];
        visited[0] = true;

        while (!q.isEmpty()) {
            int len = q.size();
            Queue<Integer> nextQ = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                int idx = q.poll();
                if (idx == n - 1) return step;
                if (idx > 0 && !visited[idx - 1]) {
                    nextQ.add(idx - 1);
                    visited[idx - 1] = true;
                }
                if (idx < n - 1 && !visited[idx + 1]) {
                    nextQ.add(idx + 1);
                    visited[idx + 1] = true;
                }
                if (isPrime[nums[idx]]) {
                    List<Integer> jumps = primeTele.get(nums[idx]);
                    if (jumps != null) {
                        for (int next : jumps) {
                            if (!visited[next]) {
                                nextQ.add(next);
                                visited[next] = true;
                            }
                        }
                        primeTele.put(nums[idx], null);
                    }
                }
            }
            q = nextQ;
            step++;
        }

        return -1;
    }

    public static List<Integer> sieve(int n, boolean[] isPrime) {
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        if (n > 1) isPrime[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }
}
©leetcode
 
Finally :v
1753608945071.png

Java: 
class Solution {
    public static final int STEP = 1;
    public static final int INDEX = 0;
    public static int MAX = 1_000_001;

    int[] spf;

    public void computeSPF() {
        spf = new int[MAX];
        for (int i = 2; i < MAX; i++) {
            if (spf[i] == 0) {
                for (int j = i; j < MAX; j += i) {
                    if (spf[j] == 0) {
                        spf[j] = i;
                    }
                }
            }
        }
    }

    public Set<Integer> getPrimeFactors(int x) {
        Set<Integer> factors = new HashSet<>();
        while (x > 1) {
            int p = spf[x];
            factors.add(p);
            while (x % p == 0) {
                x /= p;
            }
        }
        return factors;
    }

    public int minJumps(int[] nums) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i += 1) {
            max = Math.max(max, nums[i]);
        }
        MAX = max + 1;
        computeSPF();

        int n = nums.length;
        Set<Integer> primes = new HashSet<>();
        for (int i = 0; i < nums.length; i += 1) {
            if (nums[i] == spf[nums[i]]) {
                primes.add(nums[i]);
            }
        }

        Map<Integer, Set<Integer>> jumpingMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            Set<Integer> primeFactors = getPrimeFactors(nums[i]);
            for (int p : primeFactors) {
                if (primes.contains(p)) {
                    jumpingMap.computeIfAbsent(p, k -> new HashSet<>()).add(i);
                }
            }
        }

        return findMinJump(jumpingMap, nums);
    }

    public int findMinJump(Map<Integer, Set<Integer>> jumpingMap, int[] nums) {
        int n = nums.length;
        int[] minStep = new int[n];
        Arrays.fill(minStep, Integer.MAX_VALUE);

        Queue<int[]> queue = new ArrayDeque<>();
        minStep[0] = 0;
        queue.add(new int[]{0, 0});
        Set<Integer> visitedPrimes = new HashSet<>();

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int idx = cur[INDEX];
            int step = cur[STEP];

            if (idx == n - 1) return step;

            if (idx - 1 >= 0 && minStep[idx - 1] > step + 1) {
                minStep[idx - 1] = step + 1;
                queue.add(new int[]{idx - 1, step + 1});
            }

            if (idx + 1 < n && minStep[idx + 1] > step + 1) {
                minStep[idx + 1] = step + 1;
                queue.add(new int[]{idx + 1, step + 1});
            }

            if (nums[idx] == spf[nums[idx]] && !visitedPrimes.contains(nums[idx])) {
                visitedPrimes.add(nums[idx]);
                for (int nextIdx : jumpingMap.get(nums[idx])) {
                    if (minStep[nextIdx] > step + 1) {
                        minStep[nextIdx] = step + 1;
                        queue.add(new int[]{nextIdx, step + 1});
                    }
                }
            }
        }

        return nums.length - 1;
    }
}
FqPSFPf.gif
FqPSFPf.gif
FqPSFPf.gif
 
freedom.9 đã nói:
Mẹ nó cái Q1 type nhanh ăn bug, Q2 type ngu cũng ăn bug, Q3 type chuẩn thì ăn 3 bugs do TLE + MLE, đen vãi =((
Q1 cũng dễ mà nghĩ lâu quá, Q2 thì max dễ mà cũng nghĩ lâu lol, Q3 thì gõ lộn =((
Q3 thì dùng bfs thôi, với nhớ check visited của cái số primes để khỏi bị TLE, vì số primes chỉ có giới hạn thôi.
Giả sử arr là số primes thì từ số primes đó sẽ nhảy đc qua pos khác, nếu có arr j = arr i thì ko cần phải xử lí chỗ arr j nữa
Python: 
MAX = 10**6 + 2
primes = [True]*MAX
primes[0] = primes[1] = False

for i in range(MAX):
    if primes[i]:
        for j in range(i + i, MAX, i):
            primes[j] = False
            
class Solution:
    def minJumps(self, nums: List[int]) -> int:
        queue = deque()
        indexs = defaultdict(list)
        for i, val in enumerate(nums):
            indexs[val].append(i)

        mx = max(nums)
        queue.append((0, 0))
        n = len(nums)
        visited = [False]*n
        visited[0] = True
        primesSet = set()

        while queue:
            current, step = queue.popleft()
            if current == n - 1:
                return step

            if current + 1 < n and not visited[current + 1]:
                visited[current + 1] = True
                queue.append((current + 1, step + 1))

            if current - 1 >= 0 and not visited[current - 1]:
                visited[current - 1] = True
                queue.append((current - 1, step + 1))

            if primes[nums[current]] and nums[current] not in primesSet:
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1

                primesSet.add(nums[current])

        return -1



Xem tệp đính kèm 3161055
Nhấp để mở rộng...
Hình như code này của bác là o(n2) đk

via theNEXTvoz for iPhone
 
đoạn này lỡ gặp c = 2, mx = 10**9 thì chạy nhiều đó thím

Python: 
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1
 
dhl001 đã nói:
đoạn này lỡ gặp c = 2, mx = 10**9 thì chạy nhiều đó thím

Python: 
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1
Nhấp để mở rộng...
Vg e cx nghĩ thế nhẩm nhẩm thì đoạn này vẫn O(n)

via theNEXTvoz for iPhone
 
dhl001 đã nói:
đoạn này lỡ gặp c = 2, mx = 10**9 thì chạy nhiều đó thím

Python: 
                c = nums[current]
                mult = 1
                while c*mult <= mx:
                    nx=c*mult
                    for nxt in indexs[c*mult]:
                        if not visited[nxt]:
                            visited[nxt] = True
                            queue.append((nxt, step + 1))

                    mult += 1
Nhấp để mở rộng...
Ko phải đâu mấy fen, lí do tại sao nó pass đc do cách hoạt động cũng như cái sàng nguyên tố, tính sàng nguyên tố bên trên như thế nào thì ở dưới code nó đi cũng y hệt thế để nhảy qua index tiếp theo.
Với lại số primes chỉ có vài chục K nếu max là 10^6 nên cái step này nó rất thưa

via theNEXTvoz for iPhone
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

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
731
kingvn01
kingvn01
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
205
Lượt xem
28K
martin.nguyen
martin.nguyen
malacat
thảo luận Bóng đá Việt Nam mùa giải 26/27
52 53 54
Trả lời
1K
Lượt xem
48K
LinhLose
LinhLose
B
Tâm sự mỏng
Trả lời
4
Lượt xem
656
aboutU
aboutU

Thống kê chủ đề

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

Chia sẻ trang này

Quay lại
Lên đầu trang