thảo luận Leetcode mỗi ngày

Kankute said:
ngồi xóa bớt mấy hàm ko cần thiết còn 44 50 dòng
JSxuR2w.gif


đo đạc lại thấy nếu bỏ operator*= khỏi SqrtSum thì MSVC nó ko optimize được hay sao ấy mà chạy mất 0.6s thay vì 0.36s đành phải cho vào lại cộng thêm 6 dòng
4gmOAMB.png

C++: 
template <uint32_t Order>
struct IntMod {
    uint32_t val = 0;
    explicit constexpr IntMod(uint64_t n) : val{static_cast<uint32_t>(n % Order)} {}
    constexpr IntMod operator-() const { return IntMod{Order - val}; }
    constexpr IntMod operator+(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) + rhs.val}; }
    constexpr IntMod operator*(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) * rhs.val}; }
    constexpr IntMod operator/(const IntMod& rhs) const { return *this * rhs.inv(); }
    constexpr IntMod inv() const {
        IntMod res{1}, a{*this};
        for (uint32_t p = Order - 2; p; p >>= 1, a = a * a) if (p & 1) res = res * a;
        return res;
    }
};

template <class T, size_t SqrtValue>
struct SqrtSum {
    T rp{0}; // rational part
    T ip{0}; // irrational part
    constexpr SqrtSum(T rp, T ip = T{0}) : rp(rp), ip(ip) {}
    constexpr SqrtSum& operator*=(const SqrtSum& rhs) { // faster in MSVC
        const T temp = rp * rhs.rp + ip * rhs.ip * T{SqrtValue};
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    constexpr SqrtSum operator+(const SqrtSum& rhs) const { return SqrtSum{rp + rhs.rp, ip + rhs.ip}; }
    constexpr SqrtSum operator*(const SqrtSum& rhs) const { return SqrtSum{*this} *= rhs; }
    constexpr SqrtSum pow(uint32_t p) const {
        SqrtSum res = T{1}, a = *this;
        for (; p; p >>= 1, a *= a) if (p & 1) res *= a;
        return res;
    }
};

struct Solution {
    using Mint = IntMod<1'000'000'007>;
    using Sqrt5Sum = SqrtSum<Mint, 5>;
    int knightDialer(int n) {
        if (n == 1) return 10;
        constexpr Sqrt5Sum e1{Mint{3}, Mint{1}};
        constexpr Sqrt5Sum e3{Mint{3}, -Mint{1}};
        constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
        constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
        constexpr Sqrt5Sum d3a{Mint{1}, -(Mint{2} / Mint{5})};
        constexpr Sqrt5Sum d3b{Mint{9} / Mint{8}, -(Mint{19} / Mint{40})};
        constexpr Sqrt5Sum kTwo{Mint{2}};
        return (kTwo * (n % 2 ? e1.pow(n/2) * d1b * e1 + e3.pow(n/2) * d3b * kTwo : e1.pow(n/2) * d1a + e3.pow(n/2) * d3a)).rp.val;
    }
};
Click to expand...
Mà càng đọc càng thấy giống bài Fibonacci nhỉ. Cuối cùng cũng hiểu hết.
Đống template với Operator cho thành hàm bình thường ok mà, nhưng chắc chạy chậm hơn tí.
 
pikachu_1 said:
Mà càng đọc càng thấy giống bài Fibonacci nhỉ. Cuối cùng cũng hiểu hết.
Đống template với Operator cho thành hàm bình thường ok mà, nhưng chắc chạy chậm hơn tí.
Click to expand...
overload +-*/ viết cho nó đẹp
osCpCsi.png
code ban đầu tính fibo của toy thế lày, y như viết công thức: (pow(phi, n) - pow(psi, n)) / sqrt5
C++: 
constexpr Mint half{Mint{1} / Mint{2}};
constexpr Sqrt5Sum phi{half, half};
constexpr Sqrt5Sum psi{half, -half};
constexpr Sqrt5Sum sqrt5{Mint{0}, Mint{1}};

const int n = 1'000'000;
const auto fn = (pow(phi, n) - pow(psi, n)) / sqrt5;
C/Java hạ lẳng could never
osCpCsi.png
osCpCsi.png
 
Đang lấn cấn chỗ IntMod inv()
Thực chất nó là pow(-1)
Có thể viết hàm pow nhận vào số âm luôn.

pow(-1) -> pow(order - 2)
pow(-100) -> pow(order - 101)

tổng quát
pow(x) -> pow(x%(order-1))

Tuy nhiên pow do thằng SqrtSum phụ trách rồi, cùng là logN nhưng đang nhẩm lại xem thế nào thì hạn chế ít phép logn hơn
 
pikachu_1 said:
Đang lấn cấn chỗ IntMod inv()
Thực chất nó là pow(-1)
Có thể viết hàm pow nhận vào số âm luôn.

pow(-1) -> pow(order - 2)
pow(-100) -> pow(order - 101)

tổng quát
pow(x) -> pow(x%(order-1))

Tuy nhiên pow do thằng SqrtSum phụ trách rồi, cùng là logN nhưng đang nhẩm lại xem thế nào thì hạn chế ít phép logn hơn
Click to expand...
inv() đó ko có tính vào runtime đâu, nó để tính ba cái hằng số kia thì đặt nó là constexpr thì nó tính ở compile time hết rồi, có viết chậm tới cỡ nào cũng ko xao
osCpCsi.png
osCpCsi.png


cái chậm nhất là SqrtSum::pow() đó. Cũng đúng vì nó là logn, O(logn) ở đây. Toy bỏ *= viết là a = a * a thay vì a *= a mà nó thành 0.6s thay vì 0.36s
UKiCiKh.png
muốn lẹ hơn thì vì chỉ gọi có e1.pow() và e3.pow() thì có thể tính trước 31 a[] cho e1 và 31 a[] cho e3, đỡ được phân nửa số phép nhân/chia mod
1BW9Wj4.png


tính trước:
C++: 
template <uint32_t Order>
struct IntMod {
    uint32_t val = 0;
    explicit constexpr IntMod(uint64_t n) : val{static_cast<uint32_t>(n % Order)} {}
    constexpr IntMod operator-() const { return IntMod{Order - val}; }
    constexpr IntMod operator+(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) + rhs.val}; }
    constexpr IntMod operator*(const IntMod& rhs) const { return IntMod{static_cast<uint64_t>(val) * rhs.val}; }
    constexpr IntMod operator/(const IntMod& rhs) const { return *this * rhs.inv(); }
    constexpr IntMod inv() const {
        IntMod res{1}, a{*this};
        for (uint32_t p = Order - 2; p; p >>= 1, a = a * a) if (p & 1) res = res * a;
        return res;
    }
};

template <class T, size_t SqrtValue>
struct SqrtSum {
    T rp{0}; // rational part
    T ip{0}; // irrational part
    constexpr SqrtSum() = default;
    constexpr SqrtSum(T rp, T ip = T{0}) : rp(rp), ip(ip) {}
    constexpr SqrtSum& operator*=(const SqrtSum& rhs) { // faster in MSVC
        const T temp = rp * rhs.rp + ip * rhs.ip * T{SqrtValue};
        ip = rp * rhs.ip + ip * rhs.rp;
        rp = temp;
        return *this;
    }
    constexpr SqrtSum operator+(const SqrtSum& rhs) const { return SqrtSum{rp + rhs.rp, ip + rhs.ip}; }
    constexpr SqrtSum operator*(const SqrtSum& rhs) const { return SqrtSum{*this} *= rhs; }
    constexpr SqrtSum pow(uint32_t p) const {
        SqrtSum res = T{1}, a = *this;
        for (; p; p >>= 1, a *= a) if (p & 1) res *= a;
        return res;
    }
};

struct Solution {
    using Mint = IntMod<1'000'000'007>;
    using Sqrt5Sum = SqrtSum<Mint, 5>;
    static constexpr array<Sqrt5Sum, 32> precomputePow(Sqrt5Sum a) {
        array<Sqrt5Sum, 32> res{};
        for (size_t i = 0; i < res.size(); ++i, a *= a) res[i] = a;
        return res;
    }
    int knightDialer(int n) {
        if (n == 1) return 10;
        constexpr Sqrt5Sum e1{Mint{3}, Mint{1}};
        constexpr auto e1powArr = precomputePow(e1);
        constexpr Sqrt5Sum e3{Mint{3}, -Mint{1}};
        constexpr auto e3powArr = precomputePow(e3);
        constexpr Sqrt5Sum d1a{Mint{1}, Mint{2} / Mint{5}};
        constexpr Sqrt5Sum d1b{Mint{1} / Mint{2}, Mint{3} / Mint{20}};
        constexpr Sqrt5Sum d3a{Mint{1}, -(Mint{2} / Mint{5})};
        constexpr Sqrt5Sum d3b{Mint{9} / Mint{8}, -(Mint{19} / Mint{40})};
        constexpr Sqrt5Sum kTwo{Mint{2}};
        auto fasterPow1 = [&](uint32_t p) {
            Sqrt5Sum res = Mint{1};
            for (size_t i = 0; p; p >>= 1, ++i)
                if (p & 1) res *= e1powArr[i];
            return res;
        };
        auto fasterPow3 = [&](uint32_t p) {
            Sqrt5Sum res = Mint{1};
            for (size_t i = 0; p; p >>= 1, ++i)
                if (p & 1) res *= e3powArr[i];
            return res;
        };
        const auto e1n2 = fasterPow1(n / 2);
        const auto e3n2 = fasterPow3(n / 2);
        return (kTwo * (n % 2 ? e1n2 * d1b * e1 + e3n2 * d3b * kTwo : e1n2 * d1a + e3n2 * d3a)).rp.val;
    }
};
kết quả:
Elapsed: 0.37706s
Elapsed: 0.2097955s
0.21s vs 0.38s
JEWoIdl.png
 
Last edited:
Bài hnay là sao thế các bác
ví dụ 10 dịch ra bit là 1010 thì sẽ tốn 6 step để convert thành 0 chứ nhỉ, sao test case lại trả 12 :waaaht:chắc em đang hiểu sai mong các bác chỉ giáo
1701311628502.png
 
Đề ngắn mà đọc đi đọc lại k hiểu, nhất là cái operation #2. Cả cái example #2 nữa
1701313934827.png


Các bác cho hỏi cái dòng: "011" -> "001" with 2nd operation since 0th bit is 1??? em hơi ngáo đoạn này, 0th bit rõ ràng = 0 mà nhỉ
 
anoldvozer1710.v2 said:
Bài khó vl. Không tìm được pattern 2^(k+1) - 1 thì có làm đến năm sau :go:
Click to expand...
đọc hiểu cái đề là 1
tìm được n=2^k là 2
tìm được quy luật +-+-... là 3
cái 3 khó nhứt lịt pẹ cứ như cho cái test iq 1 3 2 6 7 5 4 làm sao biết index của từng số trong O(logn)
osCpCsi.png


toy bó tay ở bước 1
irGoYrZ.gif
 
Kankute said:
đọc hiểu cái đề là 1
tìm được n=2^k là 2
tìm được quy luật +-+-... là 3
cái 3 khó nhứt lịt pẹ cứ như cho cái test iq 1 3 2 6 7 5 4 làm sao biết index của từng số trong O(logn)
osCpCsi.png


toy bó tay ở bước 1
irGoYrZ.gif
Click to expand...
coi như biết thêm kiến thức mới. Mà sau gặp lại chắc cm gì đã nhớ. Mấy bài bit manipulation làm đi làm lại vẫn quên hết. Mạt vận vl :burn_joss_stick:
 
pikachu_1 said:
Cái luật 2 nó hơi điêu, đáng lẽ tách thành hẳn 3 luật
11-> 01 ok
111-> 011 not ok
110-> 010 ok
Click to expand...
quy luật 2 là được phép đảo bit ở những pattern thế lày: bit liền sau X là 1 và các bit liền sau 1 là 0 (hoặc ko có)
***X1000
****X100
*****X10
******X1
quy luật 1 là
*******X
cũng là trường hợp đặc biệt của quy luật 2 thoy
osCpCsi.png
 
1000 --> 1001 --> 1011 --> 1010 --> 1110 --> 1111 --> 1101 --> 1100 -->
0100 --> 0101 --> 0111 --> 0110 -->
0010 --> 0011 -->
0001 --> 0000

osCpCsi.png

(15 bước) 1000 --> 1001 --> 1011 --> 1010 --> 1110 --> 1111 --> 1101 --> 1100 --> 0100
(7 bước) 0100 --> 0101 --> 0111 --> 0110 --> 0010
(3 bước) 0010 --> 0011 --> 0001
(1 bước) 0001 --> 0000

vậy là suy ra n=2^k thì số bước là 2^(k+1) - 1 = 2n - 1 là xong cái khó thứ 2

cái khó thứ 3 là tìm ra quy luật những số khác 2^k
UKiCiKh.png


ví dụ
1001 là 14 bước = 15 bước của 1000 trừ 1
1011 là 13 bước = 15 bước của 1000 trừ 2
1010 là 12 bước = 15 bước của 1000 trừ 3
1110 là 11 bước = 15 bước của 1000 trừ 4
1111 là 10 bước = 15 bước của 1000 trừ 5
1101 là 9 bước = 15 bước của 1000 trừ 6
1100 là 8 bước = 15 bước của 1000 trừ 7

thế đéo nào chỉ dòm những bit 1, với giá trị của bit 1 đó là 2^(i+1) - 1:
1001 --> bit 1 ở index i = 3 và i = 0, có giá trị là 15 và 1 --> 14 = 15 - 1
1011 --> bit 1 ở index i = 3, 1, 0, có giá trị là 15, 3, 1 --> 13 = 15 - 3 + 1
1010 --> bit 1 ở index i = 3, 1, có giá trị là 15, 3 --> 12 = 15 - 3
1110 --> bit 1 ở index i = 3, 2, 1, có giá trị là 15, 7, 3 --> 11 = 15 - 7 + 3
1111 --> 10 = 15 - 7 + 3 - 1
1101 --> 9 = 15 - 7 + 1
1100 --> 8 = 15 - 7
vãi cả lol` thế đéo nào nhìn ra quy luật +-+-... như vậy được
kH9BFd2.gif


thấy ròi thì code chỉ 4 dòng thoy
sign = +1, -1, +1, -1, ...
v = 1, 3, 7, 15, ...
kệ mọe bit 1 đầu tiên ở đâu cứ lấy trị tuyệt của +-+-... là được
C++: 
class Solution {
public:
    int minimumOneBitOperations(int n) {
        // 100 --> 101 --> 111 --> 110 --> 10 --> 11 --> 1 --> 0: n=2^k --> 2n - 1 ops
        // 1000 --> 1001 --> 1011 --> 1010 --> 1110 --> 1111 --> 1101 --> 1100 --> 100
        //             -       -+       -       -+       -+-      - +      -
        //             1       31       3       73       731      7 1      7
        //            -1       -2       -3       -4       -5       -6       -7
        int res{};
        for (int v = 1, sign = 1; n; n >>= 1, v += v + 1)
            if (n % 2) res += exchange(sign, -sign) * v;
        return abs(res);
    }
};

bước 1 đọc hiểu đề bước 2 tìm ra công thức cho n=2^k có thể mò được, còn bước 3 tìm ra quy luật +-+- dới hạng DNA thế lol` nào nghĩ ra được
dzipaLk.gif
dzipaLk.gif
dzipaLk.gif
 
Last edited:
EzLink said:
Bài hnay là sao thế các bác
ví dụ 10 dịch ra bit là 1010 thì sẽ tốn 6 step để convert thành 0 chứ nhỉ, sao test case lại trả 12 :waaaht:chắc em đang hiểu sai mong các bác chỉ giáo
View attachment 2209992
Click to expand...
1010
1110 2nd op
1111 1st op
1101 2nd op
1100 1st op
0100 2nd op
0101 1st op
0111 2nd op
0110 1st op
0010 2nd op
0011 1st op
0001 2nd op
0000 1st op
Quy luật kiểu làm thế nào set được các leftmost bit về 0 thì cứ 1 bước 2 xong đến 1 bước 1 => tổng 12 bước
 

Similar threads

Masterchiefs
8 tờ báo Mỹ kiện OpenAI và Microsoft
Replies
9
Views
721
porpro84
porpro84
T
kiến thức Kèo play to earn miễn phí - Delabs Game
Replies
4
Views
107
Tranviethai98
T
T
kiến thức Kèo play to earn miễn phí - Delabs Games
Replies
4
Views
188
Tranviethai98
T
elementary
Ta thay đổi trước khi Google thay đổi
2 3
Replies
58
Views
4K
ProfessorX
ProfessorX
Masterchiefs
Núi lửa ở Nam Cực phun vàng thật mỗi ngày
2
Replies
24
Views
3K
xuccam2
xuccam2

Share this page

Back
Top