thảo luận [Học Tập] Topic thuật toán

nashwade said:
Bác có thể giải thích thêm về Arrays.sort được không? Bác sort lại mảng thì ý nghĩa của mảng vẫn là chứa các dữ liệu, chỉ thay đổi vị trí các phần tử. Còn trong bài kia thì dùng mảng input như mảng đánh dấu là thay đổi hoàn toàn ý nghĩa của mảng rồi.
Click to expand...
Hmm, nghĩ kỹ thì việc biến đổi input là 1 cái side-effect của cái function, nên yeah, fen nói cũng có lý 🤔
 
Lập Trình Viên Số Khổ said:
https://codeforces.com/contest/430/problem/C

một bài về đảo bít, mn làm xem
Click to expand...
Lời giải:
https://codeforces.com/blog/entry/12265

There is something to learn from “propagating tree” problem, used in round #225. It’s how the special operation works. I’ll copy paste the explanation from there (with some modification, corresponding to the problem):

Let’s define level of a node the number of edges in the path from root to the node. Root (node 1) is at level 0, sons of root are at level 1, sons of sons of root are at level 2 and so on. Now suppose you want to do a special operation to a node x. What nodes from subtree of x will be flipped? Obviously, x will be first, being located at level L. Sons of x, located at level L + 1 will not be flipped. Sons of sons, located at level L + 2, will be flipped again. So, nodes from subtree of x located at levels L, L + 2, L + 4, ... will be flipped, and nodes located at levels L + 1, L + 3, L + 5 won’t be flipped. Let’s take those values of L modulo 2. All nodes having remainder L modulo 2 will be flipped, and nodes having reminder (L + 1) modulo 2 will not. In other words, for a fixed x, at a level L, let y a node from subtree of x, at level L2. If L and L2 have same parity, y will be flipped, otherwise it won’t. We’ll use this fact later. For now, let’s think what should be our first operation. Let’s consider some nodes {x1, x2, ..., xk} with property that x1 is son of x2, x2 is son of x3, ... xk-1 is son of xk and parity of levels of these nodes is the same. Suppose by now we fixed {x1, x2, ..., xk-1} (their current value is equal to their goal value), but xk is still not fixed. After some time, we’ll have to fix xk. Now, by doing this, all nodes {x1, x2, ..., xk-1} will get flipped and hence unfixed. We’ve done some useless operations, so our used strategy is not the one that gives minimal number of operations.

What we learn from this example? Suppose I want to currently fix a node X. There is no point to fix it now, unless all ancestors Y of X with property level(Y) = level(X) (mod 2) are fixed. But what if an ancestor Y of X is not fixed yet and level(Y) != level(X) (mod 2)? Can I fix node X now? The answer is yes, as future operations done on Y won’t affect X. But, by same logic, I can firstly fix Y and then fix X, because again operations done on Y won’t affect X. We get a nice property: there is no point to make an operation on a node X unless all ancestors of X are fixed.

How can we use this property? What should be the first operation? We know that node 1 is the root, hence it always won’t have any ancestor. All other nodes might have sometimes not fixed ancestors, but we know for sure, for beginning, node 1 won’t have any unfixed ancestor (because it won’t have any). So, for beginning we can start with node 1. More, suppose node 1 is unfixed. The only way to fix it is to make an operation on it. Since it’s unfixed and this is the only way to fix it, you’ll be obligated to do this operation. This means, in an optimal sequence of operations, you’ll be obligated to do this operation, too.

So, if node 1 was unfixed, we did an operation on it. If it was already fixed, we’re done with it. What are next nodes we know for sure that will have all ancestors fixed? Sons of 1, because they have only one ancestor (node 1), which we know it’s fixed. We can only fix them by doing operations of them (doing operations on node 1 / sons of them won’t affect them). Since eventually they have to be fixed and only way to be fixed is to do an operation on them, in an optimal sequence of operations, we’ll have to make operations on them. Let’s move on. What are next nodes that we know for sure all ancestors of them will be fixed? Sons of sons of 1. We can fix them by doing an operation of them, or by doing an operation on 1. But doing an operation on 1 isn’t helpful, because even if it fixes this node, it unfixes 1. Then, you’ll have to do one more operation on 1, which will unfix current node, so we do two useless operations. It turns out, the only way to fix them is to do an operation on them.

Generally, suppose all ancestors of node x are fixed. We get the current value of node x after the operations done on ancestors of x. If the current value is not the expected one, we’ll have to do an operation on node x (this is the only way to fix the node x). Now, after node x is fixed, we can process sons of it. This strategy guarantees minimal number of operations, because we do an operation only when we’re forced to do it.

This leads immediately to an O(N ^ 2) algorithm, by every time we need to do an operation to update it to nodes from its subtree. How to get O(N)? Suppose we are at node x and want to know its current value after operations done for its ancestors. Obviously, it is defined by initial value. If we know number of operations done so far by even levels for its ancestors, number of operations done so far by odd levels and current level, we can determine the current value. Suppose these values are (initial_value, odd_times, even_times, level). We observe that 2 operations cancel each other, so we can take this number modulo 2. If level mod 2 = 0, then only even_times will matter, and current_value = (initial_value + even_times) % 2. Otherwise, current_value = (initial_value + odd_times) % 2.

We can send (even_times, odd_times and level) as DFS parameters, so current_value can be calculated in O(1), and overall complexity is O(N).


C++: 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <iomanip>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <functional>
 
#define pb push_back
#define mk make_pair
#define sqr(N) ((N)*(N))
#define F first
#define S second
#define maxn 101010
 
using namespace std;                         
 
typedef long long ll;
 
vector < int > g[maxn], d;
 
int i, n, b[maxn], e[maxn], add[maxn], ans;
 
void dfs(int x, int pr, int lv, int add1, int add2) {
  if(lv == 0) b[x] = (b[x] + add2) % 2;
  else b[x] = (b[x] + add1) % 2;
  if(b[x] != e[x]) {
    d.pb(x);
    ans++;
    if(lv == 0) add2++;
    else add1++;
  } 
  for(int i = 0; i < g[x].size(); i++)
    if(g[x][i] != pr) {
      dfs(g[x][i], x, 1 - lv, add1, add2);
    }
}
 
int main(){
  #ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
  #endif
  scanf("%d", &n);
  for(i = 1; i < n; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    g[a].pb(b);
    g[b].pb(a);
  }
  for(i = 1; i <= n; i++) scanf("%d", b + i);
  for(i = 1; i <= n; i++) scanf("%d", e + i);
  dfs(1, -1, 0, 0, 0);
  printf("%d\n", ans);
  for(i = 0; i < d.size(); i++) printf("%d\n", d[i]);
  return 0;
}

@clonemasteruwu fen xem cái này giúp với, sao lại cần phải có dòng if(g[x] != pr) là sao nhỉ, tui đọc lời giải với code mãi ko hiểu dòng này
 
Mấy thím cho e xin ý tưởng bài này với:
Giả sử giá trị của một ma trận là hiệu giữa tổng các số trên đường chéo chính và tổng các số trên đường chéo phụ.
Cho ma trận A kích thước N * N, hãy tìm ma trận con của A sao cho ma trận con đó có giá trị lớn nhất.
Input
Dòng đầu ghi số N (2 ≤ N ≤ 400)
N dòng tiếp theo ghi ma trận A. Các số trong đoạn [-1000, 1000].
Output
Ghi ra giá trị lớn nhất tìm được.
Vd:
input:
4
9 -2 -8 0
-6 -2 0 -9
4 -5 6 1
1 3 4 9
output:
26
 
Em thấy ở vn ít cty chú trọng về algo (trừ mấy cty lớn), em cũng đọc nhiều ý kiên trái chiều về việc nhiều người ko giỏi algo nhưng vẫn làm được việc do họ học nhiều về tech. Mấy bác có ý kiến như thế nào về vấn đề này nhỉ, em đang luyện leetcode mà thông tin nhiễu loạn quá.
 
Kennyou said:
Em thấy ở vn ít cty chú trọng về algo (trừ mấy cty lớn), em cũng đọc nhiều ý kiên trái chiều về việc nhiều người ko giỏi algo nhưng vẫn làm được việc do họ học nhiều về tech. Mấy bác có ý kiến như thế nào về vấn đề này nhỉ, em đang luyện leetcode mà thông tin nhiễu loạn quá.
Click to expand...
luyện algo là luyện tư duy lập trình, mindset để có thể tạo hướng đi trong việc giải quyết vấn đề, mấy cái mà mình đang làm hiện tại đều là tư duy lập trình tạo ra solution cho các problems, có thể hiện tại không cần dùng đến những cái cao siêu, nhưng bản chất đều là giống nhau.
 
Kennyou said:
Em thấy ở vn ít cty chú trọng về algo (trừ mấy cty lớn), em cũng đọc nhiều ý kiên trái chiều về việc nhiều người ko giỏi algo nhưng vẫn làm được việc do họ học nhiều về tech. Mấy bác có ý kiến như thế nào về vấn đề này nhỉ, em đang luyện leetcode mà thông tin nhiễu loạn quá.
Click to expand...
Vấn đề nào cũng có nhiều luồng ý kiến trái chiều nhau thôi bạn ơi.
Hơn nữa, ngay cả khi bạn học các công nghệ mới, nếu bạn có nền tảng algo tốt, bạn sẽ nắm bắt vấn đề rất nhanh.
 

Attachments

  • 1633529305726.png
    1633529305726.png
    1.4 MB · Views: 60
Last edited:
Aristides said:
Level: medium
Không sử dụng toán tử nhân, chia, chia lấy số dư, hãy lập trình hàm tính thương của 2 số nguyên đầu vào
Đáp số phải là một số nguyên, nghĩa là toàn bộ phần thập phân (nếu có) của đáp số sẽ bị bỏ
Ví dụ: 8,345 -> 8; -2,7335 -> -2

Lưu ý: giả sử rằng ta đang thực hiện trên nền tảng 32bit, nghĩa là signed int trả về có giới hạn từ [−2^31, 2^31 − 1]. Do đó, hãy quy ước rằng hàm sẽ trả về kết quả "2^31 − 1" nếu kết quả phép chia đi quá giới hạn.

Hạn chế:
số bị chia, số chia sẽ nằm trong khoảng [−2^31, 2^31 − 1]
số chia khác 0

https://leetcode.com/problems/divide-two-integers/

:doubt: Không liên quan chứ dis mạnh thế?
View attachment 741571
Click to expand...
GIỜ THÌ TÔI ĐÃ HIỂU TẠI SAO BÀI TOÁN NHẢM NHÍ NÀY LẠI NHIỀU DISLIKE THẾ
:doubt: Bài toán xàm lông đã chơi giới hạn độ phức tạp thuật toán, giới hạn luôn cả toán tử rồi mà còn giới hạn nốt 32bit int only :doubt: Mà nó giới hạn unsigned không còn đỡ, đây nó đã chơi signed int thì thuật toán trừ trừ Euclid truyền thống các kiểu dẹp hết. Và để thêm phần ức chế thì phải hơn 1/3 test case là xài giá trị INT_MIN, trong khi giá trị tuyệt đối abs(int min) - abs(int max) = 1, nghĩa là nếu convert từ int min sang số dương thì sẽ gặp lỗi, các hàm abs trên ví dụ cho vui chứ thật ra cũng vứt sọt rác với bài toán nhảm nhí này

:shame:Anyway, sau cả 1 buổi chiều rảnh rỗi try hard thì tôi đã dứt điểm được bài toán rẻ rách này với một tý trợ giúp từ wikipedia
C++: 
class Solution {
public:
    int bit_size(int arg)
    {
        // count the number of bits the argument is using
        int count = 0;
        while(arg > 0)
        {
            count++;
            arg = arg >> 1;
        }
        return count;
    }
    void bit_modify(int& arg, int position, int value)
    {
        // change the bit value at #position to value (0 or 1)
        int bitset = 1 << position;
        int val = (value != 0) ? 1 : 0;
        arg = ((arg & ~bitset) | (val << position));
    }
    int bit_value(int arg, int position) // get bit value at #position
    {
        return (arg >> position) & 1;
    }
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == INT_MIN)
        {
            if(dividend == INT_MIN)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        if(dividend == INT_MIN)
        {
            if(divisor == INT_MIN)
            {
                return 1;
            }
            else if(divisor > 0)
            {
                int result = divide(dividend + divisor, divisor);
                return (result > INT_MIN) ? result - 1 : INT_MIN;
            }
            else
            {
                int result = divide(dividend - divisor, divisor);
                return (result < INT_MAX) ? result + 1 : INT_MAX;
            }
        }
        if(std::abs(dividend) < std::abs(divisor))
        {
            return 0;
        }
        bool negative;
        if((dividend >= 0 && divisor < 0) || (dividend < 0 && divisor > 0))
           {
               negative = true;
           }
           else
           {
               negative = false;
           }
        int N = std::abs(dividend); // numerator
        int D = std::abs(divisor); // denominator
        int R = NULL; //remainder
        int Q = NULL; //quotient
        /**************************/
        for(int i = bit_size(N) - 1; i >= 0; i--)
        {
            R = R << 1;
            bit_modify(R, 0, bit_value(N, i));
            if(R >= D)
            {
                R = R - D;
                bit_modify(Q, i, 1);
            }
        }
        return (negative == false) ? Q : -Q;
    }
   
};
Untitled.png

:shame: Edit: nãy đăng lộn bài giải cũ mà sai
Sửa lại rồi nhé
 
Reiyaku said:
GIỜ THÌ TÔI ĐÃ HIỂU TẠI SAO BÀI TOÁN NHẢM NHÍ NÀY LẠI NHIỀU DISLIKE THẾ
:doubt: Bài toán xàm lông đã chơi giới hạn độ phức tạp thuật toán, giới hạn luôn cả toán tử rồi mà còn giới hạn nốt 32bit int only :doubt: Mà nó giới hạn unsigned không còn đỡ, đây nó đã chơi signed int thì thuật toán trừ trừ Euclid truyền thống các kiểu dẹp hết. Và để thêm phần ức chế thì phải hơn 1/3 test case là xài giá trị INT_MIN, trong khi giá trị tuyệt đối abs(int min) - abs(int max) = 1, nghĩa là nếu convert từ int min sang số dương thì sẽ gặp lỗi, các hàm abs trên ví dụ cho vui chứ thật ra cũng vứt sọt rác với bài toán nhảm nhí này

:shame:Anyway, sau cả 1 buổi chiều rảnh rỗi try hard thì tôi đã dứt điểm được bài toán rẻ rách này với một tý trợ giúp từ wikipedia
C++: 
class Solution {
public:
    int bit_size(long int arg)
    {
        // count the number of bits the argument is using
        int count = 0;
        while(arg > 0)
        {
            count++;
            arg = arg >> 1;
        }
        return count;
    }
    void bit_modify(long int& arg, int position, int value)
    {
        // change the bit value at #position to value (0 or 1)
        int bitset = 1 << position;
        int val = (value != 0) ? 1 : 0;
        arg = ((arg & ~bitset) | (val << position));
    }
    int divide(int dividend, int divisor) {
        if(dividend == 0 || std::abs(dividend) < std::abs(divisor)) return 0;
        bool negative;
        if((dividend >= 0 && divisor < 0) || (dividend < 0 && divisor > 0))
           {
               negative = true;
           }
           else
           {
               negative = false;
           }
        long int N = std::abs(dividend); // numerator
        long int D = std::abs(divisor); // denominator
        long int R = N; //remainder
        long int Q = NULL; //quotient
        /**************************/
        D = D << bit_size(N);
        for(int i = bit_size(N) - 1; i >= 0; i--)
        {
            R = R << 1;
            R = R - D;
            if(R >= 0)
            {
                bit_modify(Q, i, 1);
            }
            else
            {
                bit_modify(Q, i, 0);
                R = R + D;
            }
        }
        if(Q >= INT_MAX && negative == false) return INT_MAX;
        if(Q >= INT_MAX && negative == true) return INT_MIN;
        return (negative == false) ? Q : -Q;
    }
};
View attachment 805274
Click to expand...
who are you? :extreme_sexy_girl::extreme_sexy_girl:
 

Similar threads

Miền Tây
Cận cảnh đường ống ngầm khổng lồ, thu gom toàn bộ nước thải làm sống lại sông Tô Lịch
7 8 9
Replies
170
Views
16K
HanamichiFFX
HanamichiFFX
L
thảo luận Một vài chia sẻ có thể hữu ích cho các bạn trẻ trong sự nghiệp ngành IT
2 3 4
Replies
65
Views
3K
dntt_00
dntt_00
Uoc_mo_Tay_Tang
Bắt đầu thảm nhựa tuyến tránh thành phố Long Xuyên
Replies
0
Views
121
Uoc_mo_Tay_Tang
Uoc_mo_Tay_Tang
manoao
Tiêu thụ điện miền Bắc tăng hơn 13 triệu kWh/ngày, thủy điện giữ nước chờ nắng nóng
Replies
4
Views
248
seotopgoole
S
Masterchiefs
Thu nhập của người dân Hà Nội, TP.HCM tăng ra sao trong hơn 10 năm qua
2
Replies
21
Views
921
LamNguyenV2
LamNguyenV2

Share this page

Back
Top