ờm thì prob < 1 nên càng nhân vào thì số càng nhỏ -> tìm đường đi cho nó bớt nhân thêm số thì nó sẽ max -> tìm đường ngắn nhấtlàm sao biết Dijkstra chạy đúng với kiểu product max nàyLàm sao biết dùng max heap thay vì min heap
lấy max có phải min đâu huynh bill với cả số nhỏ hơn 1 lớn hơn 0 thì càng nhân càng bé mà nên nhân ít thì sẽ tolàm sao biết Dijkstra chạy đúng với kiểu product max nàyLàm sao biết dùng max heap thay vì min heap
codeforces.com
thớt này nhiều ae tập tành lc tay hơi béHơi lạc platform 1 xíu nhưng cũng là thuật toán, nhờ cao nhân giúp em với được không ạ.
Problem - A - Codeforces
Codeforces. Programming competitions and contests, programming community
Em đang làm cái bài này bên codeforces. Em đọc solution thì họ bảo là khởi tạo giá trị a cực lớn. Xong proccess mấy cái operation từ dưới lên. Sau đó sẽ ra được 1 cái array output nhưng cái đó lại phải process mấy cái operation theo đúng thứ tự từ trên xuống để verify nếu có operation nào không pass thì là không có output nào tồn tại in ra NO. Nhưng mà em đọc mãi vẫn không hiểu làm sao có thể chứng minh được điều này ấy ạ. Em đọc mãi vẫn không hiểu.
solution thì em đang xem code ở đây. Đại loại mấy cái solution khác cũng idea như vậy thôi ạ https://www.programmersought.com/article/28473050299/
voz.vn
đọc thử editorial round 210, problem 360AHơi lạc platform 1 xíu nhưng cũng là thuật toán, nhờ cao nhân giúp em với được không ạ.
Problem - A - Codeforces
Codeforces. Programming competitions and contests, programming community
Em đang làm cái bài này bên codeforces. Em đọc solution thì họ bảo là khởi tạo giá trị a cực lớn. Xong proccess mấy cái operation từ dưới lên. Sau đó sẽ ra được 1 cái array output nhưng cái đó lại phải process mấy cái operation theo đúng thứ tự từ trên xuống để verify nếu có operation nào không pass thì là không có output nào tồn tại in ra NO. Nhưng mà em đọc mãi vẫn không hiểu làm sao có thể chứng minh được điều này ấy ạ. Em đọc mãi vẫn không hiểu.
solution thì em đang xem code ở đây. Đại loại mấy cái solution khác cũng idea như vậy thôi ạ https://www.programmersought.com/article/28473050299/
var maxProbability = function(n, edges, succProb, start_node, end_node) {
const graph = new Array(n).fill(null).map(x => []);
for (let i = 0; i < edges.length; i++) {
graph[edges[i][0]].push([edges[i][1], succProb[i]]);
graph[edges[i][1]].push([edges[i][0], succProb[i]]);
}
const d = new Array(n).fill(0);
d[start_node] = 1;
const pq = new MaxPriorityQueue({ priority: (x) => x[0] });
pq.enqueue([1, start_node]);
const visited = new Set();
while (!pq.isEmpty()) {
const [prob, node] = pq.dequeue().element;
if (visited.has(node)) continue;
visited.add(node);
for (const [nei, neiProb] of graph[node]) {
const newProb = prob * neiProb;
if (newProb > d[nei]) {
d[nei] = newProb;
pq.enqueue([newProb, nei]);
}
}
}
return d[end_node];
};
Không contest đâu có nghĩa là trình kémthớt này nhiều ae tập tành lc tay hơi bé, fen mang sang thớt leetcode contest nhiều gosu ẩn danh giải cho fen nhé.đề cf đọc đã thấy nhức nhức cái đầu
thảo luận - Leetcode contest, đường tới Guardian
Hello anh em, tình hình leetcode daily là chỗ thảo luận daily. Chưa có topic về Leetcode contest nên mình lập cái topic cho ae trao đổi kinh nghiệm cho vui như bác @pikachu_1 đang tìm kiếm, hi vọng anh em có kinh nghiệm, các knights, guardians của VOZ vào chỉ cho anh em vài skill để anh em tu...
bên thớt kia nhiều ô chém hard như chém bún ấy, thấy online mỗi lần có contest thôiKhông contest đâu có nghĩa là trình kém
em đọc r ấy, mà cái editorial đó có vẻ hơi cao siêu với em đọc cũng hơi váng đầu. Mà cái em thắc mắc là cái đoạn "Let's prove that either b satisfied all conditions or there is no such array" ấy. Em đang tự hỏi làm sao nó chắc rằng nếu b không thỏa thì liệu rằng có một mảng b' khác thỏa hay không. Còn solution này em thấy nếu thấy k thỏa thì chốt sổ là NO luôn. Không biết em còn miss cái ý gì trong cái editorial này không
class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<List<Pair<Integer, Double>>> adj = new ArrayList();
for(int i = 0; i < n; i++) {
adj.add(new ArrayList());
}
for(int i = 0; i < edges.length; i++) {
adj.get(edges[i][0]).add(new Pair(edges[i][1], succProb[i]));
adj.get(edges[i][1]).add(new Pair(edges[i][0], succProb[i]));
}
double[] maxProb = new double[n];
maxProb[start] = 1d;
PriorityQueue<Pair<Integer, Double>> pq = new PriorityQueue<>((a, b) -> -Integer.compare(a.getKey(), b.getKey()));
pq.offer(new Pair(start, maxProb[start]));
while(!pq.isEmpty()) {
Pair<Integer, Double> pair = pq.poll();
int current = pair.getKey();
double prob = pair.getValue();
if (prob < maxProb[current]) continue;
maxProb[current] = prob;
for (Pair<Integer, Double> node : adj.get(current)) {
if (node.getValue() * prob > maxProb[node.getKey()]) {
pq.offer(new Pair(node.getKey(), node.getValue() * prob));
}
}
}
return maxProb[end];
}
}tay em như không có luôn ấy chứthớt này nhiều ae tập tành lc tay hơi bé, fen mang sang thớt leetcode contest nhiều gosu ẩn danh giải cho fen nhé.đề cf đọc đã thấy nhức nhức cái đầu
thảo luận - Leetcode contest, đường tới Guardian
Hello anh em, tình hình leetcode daily là chỗ thảo luận daily. Chưa có topic về Leetcode contest nên mình lập cái topic cho ae trao đổi kinh nghiệm cho vui như bác @pikachu_1 đang tìm kiếm, hi vọng anh em có kinh nghiệm, các knights, guardians của VOZ vào chỉ cho anh em vài skill để anh em tu...
) đợt rồi em pv pass đc vòng hackerrank vô nó hỏi cái bài tìm số subarray có tổng bằng k live coding tạch bố nó luôn, cũng may đợt này cũng đậu đc cty thơm thơm thoát khỏi cái nhà F xong 3 năm cống hiến. Xong từ đợt đó mới quyết tâm ôn thuật toán. Mà sẵn ôn nên em choi CP luôn cho máu
subarray có tổng = k đoán là xài cửa sổ trượt + prefix sum phải khum fentay em như không có luôn ấy chứ
đúng rùi bácsubarray có tổng = k đoán là xài cửa sổ trượt + prefix sum phải khum fen
Long tại nhân gian đây rồisubarray có tổng = k đoán là xài cửa sổ trượt + prefix sum phải khum fen
sorry, đọc kỹ lại editorial thì thấy giải thích vớ vẩn thận, và đề có vẻ không rõ ràng lắmem đọc r ấy, mà cái editorial đó có vẻ hơi cao siêu với em đọc cũng hơi váng đầu. Mà cái em thắc mắc là cái đoạn "Let's prove that either b satisfied all conditions or there is no such array" ấy. Em đang tự hỏi làm sao nó chắc rằng nếu b không thỏa thì liệu rằng có một mảng b' khác thỏa hay không. Còn solution này em thấy nếu thấy k thỏa thì chốt sổ là NO luôn. Không biết em còn miss cái ý gì trong cái editorial này không
Đừng có phét, thớt nào đi nữa làm gì có ai qua được bác Maobên thớt kia nhiều ô chém hard như chém bún ấy, thấy online mỗi lần có contest thôi
2 con trỏ là xong mà cửa sổ với prefix gì ở đây, đúng là rồng trong loài người có khác, cách làm cao siêu thậtsubarray có tổng = k đoán là xài cửa sổ trượt + prefix sum phải khum fen
subarray có tổng = k thì phải là hashmap + prefix sum chứ cửa sổ trượt sao làm đc ta?subarray có tổng = k đoán là xài cửa sổ trượt + prefix sum phải khum fen
bác này nói đúng nè, nãy em đọc nhầm. map với ps mới ra.subarray có tổng = k thì phải là hashmap + prefix sum chứ cửa sổ trượt sao làm đc ta?
hehe, dạ thanks bác. chắc đổi sang môn leetcode quá chơi chung với thread này quá, chứ codeforces chơi hại não gớm.
