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

_Gia_Cat_Luong_

Senior Member
Ý tưởng y chang các thím trên, không có gì đặc biệt:

Python:
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        maxSize = 0
        def getSize(r, c):
            if grid[r][c] != 1:
                return 0
            
            grid[r][c] = 0
            size = 1
            if r > 0 and grid[r - 1][c] == 1:
                size += getSize(r - 1, c)
            if r < len(grid) - 1 and grid[r + 1][c] == 1:
                size += getSize(r + 1, c)
            if c > 0 and grid[r][c - 1] == 1:
                size += getSize(r, c - 1)
            if c < len(grid[0]) - 1 and grid[r][c + 1] == 1:
                size += getSize(r, c + 1)
                
            return size
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                maxSize = max(maxSize, getSize(r, c))
                    
        return maxSize
 

Violet_7

Senior Member
16/7/2022:
  • 1 câu medium khá hay nhưng hơi dài
  • nhìn vào đề bài lúc đầu khá bí ý tưởng, sau 1 lúc nghĩ thì nhận thấy quả bóng sẽ ra khỏi ma trận tại các điểm cạnh viền, và mỗi điểm cạnh viền đều có số cách ra khỏi ma trận
1657932677404.png

  • như tại điểm quả bóng chỉ có 1 cách ra khỏi ma trận, nhưng điểm dưới quả bóng sẽ có 2 cách ra khỏi ma trận
  • tạo mảng 2d numWaysOutGrid trong đó numWaysOutGrid[i.][j.] là số cách ra khỏi ma trận của điểm (i, j) -> tính numWaysOutGrid
  • duyệt lần lượt từ move 1 đến move thứ maxMove
  • tạo mảng 2d numWays trong đó numWays[i.][j.] là số cách đến điểm đó tại move đó
  • ở mỗi move, result += numWays[i.][j.] * numWaysOutGrid[i.][j.]
  • ở move đầu tiên, numWays chỉ có numWays[startRow][startColumn] = 1
  • để update numWays ở move tiếp theo, duyệt 4 điểm liền kề tại 1 điểm và update numWays tại 4 điểm đó
  • Ra đáp án
  • Time: O(max move * m * n)
  • Space O(m * n)
  • Code: https://leetcode.com/submissions/detail/748153441/
  • Nghĩ mất 15p, mà bài này dài quá nên code tiếp mất thêm 15p :beat_brick::beat_brick:
 
Last edited:

san1201

Junior Member
Một cách DP khác.
  • Đặt ret[j][move] là số cách di chuyển từ vị trí ban đầu đến điểm (i, j) với đúng move bước.
    [*]Dễ thấy ret[j][move] = ret[i - 1][j][move-1] + ret[i ][j - 1][move-1] + ret[i+1 ][j][move-1] + ret[i ][j+1][move-1].
  • Kết quả sẽ bằng tổng ret đi theo đường viền hình chữ nhật với move từ 0 -> maxMove - 1. (Chú ý vị trí góc cộng 2 lần).
  • Code: https://leetcode.com/problems/out-of-boundary-paths/submissions/
  • Time O(m*n*maxMove), Space O(m*n*maxMove). Space có thể optimize thành O(m*n) được mà ngại code quá
 

randomA

Junior Member
Một cách DP khác.
  • Đặt ret[j][move] là số cách di chuyển từ vị trí ban đầu đến điểm (i, j) với đúng move bước.
    [*]Dễ thấy ret[j][move] = ret[i - 1][j][move-1] + ret[i ][j - 1][move-1] + ret[i+1 ][j][move-1] + ret[i ][j+1][move-1].
  • Kết quả sẽ bằng tổng ret đi theo đường viền hình chữ nhật với move từ 0 -> maxMove - 1. (Chú ý vị trí góc cộng 2 lần).
  • Code: https://leetcode.com/problems/out-of-boundary-paths/submissions/
  • Time O(m*n*maxMove), Space O(m*n*maxMove). Space có thể optimize thành O(m*n) được mà ngại code quá
https://leetcode.com/submissions/detail/748318119/

Tui cũng dùng cách này. Faster than 92% và less memory hơn 88% (code Java) nên thôi khỏi optimize tiếp.

Cái cách của Violet ở trên có vẻ chậm hơn nhiều (faster than 16.82%) do cố save memory. (Không biết có phải code bằng C lắm cách tối ưu hơn không nên cách của @Violet_7 mới bị chậm như vậy khi so sánh hay không nữa)
 

Tuấn Mỏ

Senior Member
Đóng góp 1 cách giải DP và tối ưu hoá bằng SIMD

nhưng vẫn chỉ beat đc 79%
1657956596099.png


C++:
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse41,sse42,popcnt,abm,mmx,avx,avx2,svml,tune=native")

class Solution {
public:
    long long dp[52][52];
    long long dp_temp[52][52];
    long long mod = 1e9 + 7;
  
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iModOperation(__m256i& a, __m256i& b)
    {
        __m256i apd = _mm256_cvtepi64_pd(a);
        __m256i bpd = _mm256_cvtepi64_pd(b);
        __m256i div = _mm256_cvtpd_epi64(
            _mm256_mul_pd(
                 _mm256_floor_pd(
                    _mm256_div_pd(
                        apd,
                        bpd
                    )
                 ),
                 bpd
            )
        );     
      
        return _mm256_sub_epi64(a, div);
    }
  
    __attribute__((target("avx512vl"))) int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0)
            return 0;
      
        std::memset(dp, 0, sizeof(dp));
      
        for(int y = 1; y <= m; ++y)
        {
            dp[y][1] += 1;
            dp[y][n] += 1;
        }
      
        for(int x = 1; x <= n; ++x)
        {
            dp[1][x] += 1;
            dp[m][x] += 1;
        }
      
        __m256i vec2iMod = _mm256_set1_epi64x(mod);
      
        long long ret = dp[startRow + 1][startColumn + 1]; 
      
        for(int move = 2; move <= maxMove; ++move)
        {
            std::memset(dp_temp, 0, sizeof(dp_temp));
          
            for(int y = 1; y <= m; ++y)
            {
                long long* pRowDpTemp = &dp_temp[y][0];
                long long* pRowDp = &dp[y][0];
              
                int x = 1;
              
                // AVX
                for(; x <= n - 4; x += 4)
                {
                    long long* pCurDpTemp = pRowDpTemp + x;
                    long long* pCurDp = pRowDp + x;
                  
                    __m256i vec2iDpTemp = _mm256_loadu_si256((__m256i*)pCurDpTemp);
                  
                    __m256i vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                     
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                  
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                     
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                  
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                     
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);

                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                     
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                  
                    _mm256_storeu_si256((__m256i *)pCurDpTemp, vec2iDpTemp);
                }
              
                // NORMAL
                for(; x <= n; ++x)
                {
                    dp_temp[y][x] += dp[y - 1][x];
                    dp_temp[y][x] %= mod;
                  
                    dp_temp[y][x] += dp[y][x - 1];
                    dp_temp[y][x] %= mod;
                  
                    dp_temp[y][x] += dp[y + 1][x];
                    dp_temp[y][x] %= mod;

                    dp_temp[y][x] += dp[y][x + 1];
                    dp_temp[y][x] %= mod;
                }
            }
          
            std::memcpy(dp, dp_temp, sizeof(dp));
          
            ret += dp_temp[startRow + 1][startColumn + 1];
          
            ret %= mod;
        }

        return ret;
      
    }
};


P/S: Tối ưu hoá thêm bằng mảng 1 chiều

C++:
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse41,sse42,popcnt,abm,mmx,avx,avx2,svml,tune=native")

#define WIDTH 52
#define HEIGHT 52
class Solution {
public:
    long long dp[HEIGHT * WIDTH];
    long long dp_temp[HEIGHT * WIDTH];
    long long mod = 1e9 + 7;
    
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iModOperation(__m256i& a, __m256i& b)
    {
        __m256i apd = _mm256_cvtepi64_pd(a);
        __m256i bpd = _mm256_cvtepi64_pd(b);
        __m256i div = _mm256_cvtpd_epi64(
            _mm256_mul_pd(
                 _mm256_floor_pd(
                    _mm256_div_pd(
                        apd,
                        bpd
                    )
                 ),
                 bpd
            )
        );       
        
        return _mm256_sub_epi64(a, div);
    }
    
    __attribute__((target("avx512vl"))) int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0)
            return 0;
        
        std::memset(dp, 0, sizeof(dp));
        
        for(int y = 1; y <= m; ++y)
        {
            dp[y * WIDTH + 1] += 1;
            dp[y * WIDTH + n] += 1;
        }
        
        for(int x = 1; x <= n; ++x)
        {
            dp[1 * WIDTH + x] += 1;
            dp[m * WIDTH + x] += 1;
        }
        
        __m256i vec2iMod = _mm256_set1_epi64x(mod);
        
        long long ret = dp[(startRow + 1)  * WIDTH + startColumn + 1];   
        
        for(int move = 2; move <= maxMove; ++move)
        {
            std::memset(dp_temp, 0, sizeof(dp_temp));
            
            for(int y = 1; y <= m; ++y)
            {
                long long* pRowDpTemp = &dp_temp[y * WIDTH];
                long long* pRowDp = &dp[y * WIDTH];
                
                int x = 1;
                
                // AVX
                for(; x <= n - 4; x += 4)
                { 
                    long long* pCurDpTemp = pRowDpTemp + x;
                    long long* pCurDp = pRowDp + x;
                    
                    __m256i vec2iDpTemp = _mm256_loadu_si256((__m256i*)pCurDpTemp);
                    
                    __m256i vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);

                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    _mm256_storeu_si256((__m256i *)pCurDpTemp, vec2iDpTemp); 
                }
                
                // NORMAL
                for(; x <= n; ++x)
                {
                    dp_temp[y * WIDTH + x] += dp[(y - 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;
                    
                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x - 1];
                    dp_temp[y * WIDTH + x] %= mod;
                    
                    dp_temp[y * WIDTH + x] += dp[(y + 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;

                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x + 1];
                    dp_temp[y * WIDTH + x] %= mod;
                }
            } 
            
            std::memcpy(dp, dp_temp, sizeof(dp));
            
            ret += dp_temp[(startRow + 1) * WIDTH + startColumn + 1];
            
            ret %= mod;
        }

        return ret;
        
    }
};
 
Last edited:

randomA

Junior Member
Đóng góp 1 cách giải DP và tối ưu hoá bằng SIMD

nhưng vẫn chỉ beat đc 79%
View attachment 1268224

C++:
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse41,sse42,popcnt,abm,mmx,avx,avx2,svml,tune=native")

class Solution {
public:
    long long dp[52][52];
    long long dp_temp[52][52];
    long long mod = 1e9 + 7;
 
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iModOperation(__m256i& a, __m256i& b)
    {
        __m256i apd = _mm256_cvtepi64_pd(a);
        __m256i bpd = _mm256_cvtepi64_pd(b);
        __m256i div = _mm256_cvtpd_epi64(
            _mm256_mul_pd(
                 _mm256_floor_pd(
                    _mm256_div_pd(
                        apd,
                        bpd
                    )
                 ),
                 bpd
            )
        );    
     
        return _mm256_sub_epi64(a, div);
    }
 
    __attribute__((target("avx512vl"))) int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0)
            return 0;
     
        std::memset(dp, 0, sizeof(dp));
     
        for(int y = 1; y <= m; ++y)
        {
            dp[y][1] += 1;
            dp[y][n] += 1;
        }
     
        for(int x = 1; x <= n; ++x)
        {
            dp[1][x] += 1;
            dp[m][x] += 1;
        }
     
        __m256i vec2iMod = _mm256_set1_epi64x(mod);
     
        long long ret = dp[startRow + 1][startColumn + 1];
     
        for(int move = 2; move <= maxMove; ++move)
        {
            std::memset(dp_temp, 0, sizeof(dp_temp));
         
            for(int y = 1; y <= m; ++y)
            {
                long long* pRowDpTemp = &dp_temp[y][0];
                long long* pRowDp = &dp[y][0];
             
                int x = 1;
             
                // AVX
                for(; x <= n - 4; x += 4)
                {
                    long long* pCurDpTemp = pRowDpTemp + x;
                    long long* pCurDp = pRowDp + x;
                 
                    __m256i vec2iDpTemp = _mm256_loadu_si256((__m256i*)pCurDpTemp);
                 
                    __m256i vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                    
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                 
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                    
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                 
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                    
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);

                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                    
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                 
                    _mm256_storeu_si256((__m256i *)pCurDpTemp, vec2iDpTemp);
                }
             
                // NORMAL
                for(; x <= n; ++x)
                {
                    dp_temp[y][x] += dp[y - 1][x];
                    dp_temp[y][x] %= mod;
                 
                    dp_temp[y][x] += dp[y][x - 1];
                    dp_temp[y][x] %= mod;
                 
                    dp_temp[y][x] += dp[y + 1][x];
                    dp_temp[y][x] %= mod;

                    dp_temp[y][x] += dp[y][x + 1];
                    dp_temp[y][x] %= mod;
                }
            }
         
            std::memcpy(dp, dp_temp, sizeof(dp));
         
            ret += dp_temp[startRow + 1][startColumn + 1];
         
            ret %= mod;
        }

        return ret;
     
    }
};


P/S: Tối ưu hoá thêm bằng mảng 1 chiều

C++:
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse41,sse42,popcnt,abm,mmx,avx,avx2,svml,tune=native")

#define WIDTH 52
#define HEIGHT 52
class Solution {
public:
    long long dp[HEIGHT * WIDTH];
    long long dp_temp[HEIGHT * WIDTH];
    long long mod = 1e9 + 7;
   
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iModOperation(__m256i& a, __m256i& b)
    {
        __m256i apd = _mm256_cvtepi64_pd(a);
        __m256i bpd = _mm256_cvtepi64_pd(b);
        __m256i div = _mm256_cvtpd_epi64(
            _mm256_mul_pd(
                 _mm256_floor_pd(
                    _mm256_div_pd(
                        apd,
                        bpd
                    )
                 ),
                 bpd
            )
        );      
       
        return _mm256_sub_epi64(a, div);
    }
   
    __attribute__((target("avx512vl"))) int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0)
            return 0;
       
        std::memset(dp, 0, sizeof(dp));
       
        for(int y = 1; y <= m; ++y)
        {
            dp[y * WIDTH + 1] += 1;
            dp[y * WIDTH + n] += 1;
        }
       
        for(int x = 1; x <= n; ++x)
        {
            dp[1 * WIDTH + x] += 1;
            dp[m * WIDTH + x] += 1;
        }
       
        __m256i vec2iMod = _mm256_set1_epi64x(mod);
       
        long long ret = dp[(startRow + 1)  * WIDTH + startColumn + 1];  
       
        for(int move = 2; move <= maxMove; ++move)
        {
            std::memset(dp_temp, 0, sizeof(dp_temp));
           
            for(int y = 1; y <= m; ++y)
            {
                long long* pRowDpTemp = &dp_temp[y * WIDTH];
                long long* pRowDp = &dp[y * WIDTH];
               
                int x = 1;
               
                // AVX
                for(; x <= n - 4; x += 4)
                {
                    long long* pCurDpTemp = pRowDpTemp + x;
                    long long* pCurDp = pRowDp + x;
                   
                    __m256i vec2iDpTemp = _mm256_loadu_si256((__m256i*)pCurDpTemp);
                   
                    __m256i vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                      
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                   
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                      
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                   
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 52));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                      
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);

                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                      
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                   
                    _mm256_storeu_si256((__m256i *)pCurDpTemp, vec2iDpTemp);
                }
               
                // NORMAL
                for(; x <= n; ++x)
                {
                    dp_temp[y * WIDTH + x] += dp[(y - 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;
                   
                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x - 1];
                    dp_temp[y * WIDTH + x] %= mod;
                   
                    dp_temp[y * WIDTH + x] += dp[(y + 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;

                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x + 1];
                    dp_temp[y * WIDTH + x] %= mod;
                }
            }
           
            std::memcpy(dp, dp_temp, sizeof(dp));
           
            ret += dp_temp[(startRow + 1) * WIDTH + startColumn + 1];
           
            ret %= mod;
        }

        return ret;
       
    }
};
Ặc có gì sai sai. Cái này được tối ưu rồi mà sao chạy đến tận 11ms.
Cái của tui chạy Java chẳng optimize gì cả mà cũng chỉ 5ms.

Có ai biết tại sao không?
 

_Gia_Cat_Luong_

Senior Member
Ặc có gì sai sai. Cái này được tối ưu rồi mà sao chạy đến tận 11ms.
Cái của tui chạy Java chẳng optimize gì cả mà cũng chỉ 5ms.

Có ai biết tại sao không?
Vụ nỳa này trong group đã bàn rồi, thím có thể lội trang lại. Tóm tắt đơn giản thì trên LC java runtime nó chạy tối ưu hơn nên thường sẽ nhanh hơn C++.
 

bribnt

Đã tốn tiền
https://leetcode.com/submissions/detail/748318119/

Tui cũng dùng cách này. Faster than 92% và less memory hơn 88% (code Java) nên thôi khỏi optimize tiếp.

Cái cách của Violet ở trên có vẻ chậm hơn nhiều (faster than 16.82%) do cố save memory. (Không biết có phải code bằng C lắm cách tối ưu hơn không nên cách của @Violet_7 mới bị chậm như vậy khi so sánh hay không nữa)

Tại vì bài đó dùng vector of vector nên vừa tốn bộ nhớ vừa phân mảnh.

Mình dùng std::array cấp phát thừa 64x64 mà mem vẫn bé hơn 99%.
1657959082267.png


https://leetcode.com/submissions/detail/748374660/


C++:
class Solution {

#define M 1'000'000'007
    
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {

       // cấp phát thừa 2 đơn vị ở hai chiều m/n. Tính chỉ số bắt đầu từ 1 để làm sentinel
        std::array<std::uint32_t, 64 * 64> dp{};
        
        ++startRow, ++startColumn;
        dp[startRow<<6 | startColumn] = 1;
        
        std::uint32_t res = 0;
        int rb = startRow, re = startRow, cb = startColumn, ce = startColumn;
        
        for (int k = 1; k <= maxMove; ++k) {
            decltype(dp) tmp{};
            rb = max(1, rb-1), re = min(m, re+1), cb = max(1, cb-1), ce = min(n, ce+1);
            for (int i = rb; i <= re; ++i) {
                for (int j = cb; j <= ce; ++j) {
                    // a & -(cond) <=> a if cond else 0
                    int c0j = dp[i<<6 | j] & -(i == 1),
                        cmj = dp[i<<6 | j] & -(i == m),
                        ci0 = dp[i<<6 | j] & -(j == 1),
                        cin = dp[i<<6 | j] & -(j == n);
                    
                    res = (res + c0j + cmj + ci0 + cin) % M;
                    
                    tmp[i<<6 | j] = ((dp[i<<6|(j-1)] & -(j > 1)) + (dp[i<<6|(j+1)] & -(j < n)) +
                                     (dp[(i-1)<<6|j] & -(i > 1)) + (dp[(i+1)<<6|j] & -(i < m))) % M;
                }
            }
            dp = std::move(tmp);
        }
        
        return res;
    }
};

auto _ = [](){
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();
 

Violet_7

Senior Member
https://leetcode.com/submissions/detail/748318119/

Tui cũng dùng cách này. Faster than 92% và less memory hơn 88% (code Java) nên thôi khỏi optimize tiếp.

Cái cách của Violet ở trên có vẻ chậm hơn nhiều (faster than 16.82%) do cố save memory. (Không biết có phải code bằng C lắm cách tối ưu hơn không nên cách của @Violet_7 mới bị chậm như vậy khi so sánh hay không nữa)
Thực ra mình ko quan trọng cái đó lắm, miễn là time complexity ok là được, còn muốn nhanh thì chuyển về std::array như bác bribnt.
 

bribnt

Đã tốn tiền
C++:
                // NORMAL
                for(; x <= n; ++x)
                {
                    dp_temp[y * WIDTH + x] += dp[(y - 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;
                 
                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x - 1];
                    dp_temp[y * WIDTH + x] %= mod;
                 
                    dp_temp[y * WIDTH + x] += dp[(y + 1) * WIDTH + x];
                    dp_temp[y * WIDTH + x] %= mod;

                    dp_temp[y * WIDTH + x] += dp[y * WIDTH + x + 1];
                    dp_temp[y * WIDTH + x] %= mod;
                }
            }

Đoạn này nếu bác dùng kiểu std::uint32_t thì chỉ cần một phép mod là đủ. Vì giá trị M của đề bài nhỏ hơn 2^32 / 4.

Thực ra mình ko quan trọng cái đó lắm, miễn là time complexity ok là được, còn muốn nhanh thì chuyển về std::array như bác bribnt.
Trong bài này thực ra dùng std::array theo lý thuyết thì không hiệu quả lắm, vì đoạn swap ở mỗi bước với array là O(m*n), còn với vector là O(1). Nhưng không hiểu sao thử thay bằng vector 1 chiều thì lại chậm hơn.
 

Arik97

Senior Member
Implement kiểu DP top-down: gọi f(x,y,move) là số cách đi ra ngoài từ vị trí x,y, đang có k moves = tổng số cách đi từ vị trí đó và các vị trí liền kề, có k-1 moves:
Python:
class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        @lru_cache(None)
        def n_ways(x,y,moves):
            if moves==0:
                return 0
            count=0
            for (i,j) in [(-1,0),(0,1),(1,0),(0,-1)]:
                r,c=x+i,y+j
                if r<0 or r==m or c<0 or c==n:
                    count+=1
                else:
                    if moves>1:
                        count+=n_ways(r,c,moves-1)
            return count
        return n_ways(startRow,startColumn,maxMove)%(pow(10,9)+7)
 
Last edited:

Tuấn Mỏ

Senior Member
Đoạn này nếu bác dùng kiểu std::uint32_t thì chỉ cần một phép mod là đủ. Vì giá trị M của đề bài nhỏ hơn 2^32 / 4.

Nếu chỉ dùng kiểu dữ liệu 4byte thì lúc dùng simd để mod ko làm đc bác, mình phải cast nó về kiểu double thì mới tính modulo đc, _mm256_irem_epi32 chỉ support cho svml
 

Tuấn Mỏ

Senior Member
Ặc có gì sai sai. Cái này được tối ưu rồi mà sao chạy đến tận 11ms.
Cái của tui chạy Java chẳng optimize gì cả mà cũng chỉ 5ms.

Có ai biết tại sao không?

Mình tối ưu hoá 1 xí ở đoạn ko dùng SIMD thì xuống còn 4ms

1657967343501.png


C++:
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse41,sse42,popcnt,abm,mmx,avx,avx2,svml,tune=native")

#define WIDTH 52
#define HEIGHT 52
class Solution {
public:
    long long dp[HEIGHT * WIDTH];
    long long dp_temp[HEIGHT * WIDTH];
    long long mod = 1e9 + 7;
    
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iModOperation(__m256i& a, __m256i& b)
    {
        __m256i apd = _mm256_cvtepi64_pd(a);
        __m256i bpd = _mm256_cvtepi64_pd(b);
        __m256i div = _mm256_cvtpd_epi64(
            _mm256_mul_pd(
                 _mm256_floor_pd(
                    _mm256_div_pd(
                        apd,
                        bpd
                    )
                 ),
                 bpd
            )
        );       
        
        return _mm256_sub_epi64(a, div);
    }
    
    __attribute__((target("avx512vl"))) int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0)
            return 0;
        
        std::memset(dp, 0, sizeof(dp));
        
        for(int y = 1; y <= m; ++y)
        {
            dp[y * WIDTH + 1] += 1;
            dp[y * WIDTH + n] += 1;
        }
        
        for(int x = 1; x <= n; ++x)
        {
            dp[1 * WIDTH + x] += 1;
            dp[m * WIDTH + x] += 1;
        }
        
        __m256i vec2iMod = _mm256_set1_epi64x(mod);
        
        long long ret = dp[(startRow + 1)  * WIDTH + startColumn + 1];   
        
        for(int move = 2; move <= maxMove; ++move)
        {
            std::memset(dp_temp, 0, sizeof(dp_temp));
            
            for(int y = 1; y <= m; ++y)
            {
                long long* pRowDpTemp = &dp_temp[y * WIDTH];
                long long* pRowDp = &dp[y * WIDTH];
                
                int x = 1;
                
                // AVX
                for(; x <= n - 4; x += 4)
                { 
                    long long* pCurDpTemp = pRowDpTemp + x;
                    long long* pCurDp = pRowDp + x;
                    
                    __m256i vec2iDpTemp = _mm256_loadu_si256((__m256i*)pCurDpTemp);
                    
                    __m256i vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - WIDTH));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp - 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + WIDTH));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);

                    vec2iDp = _mm256_loadu_si256((__m256i*)(pCurDp + 1));
                    vec2iDpTemp = _mm256_add_epi64(vec2iDpTemp, vec2iDp);                       
                    vec2iDpTemp = vec2iModOperation(vec2iDpTemp, vec2iMod);
                    
                    _mm256_storeu_si256((__m256i *)pCurDpTemp, vec2iDpTemp);                     
                }               
                
                // NORMAL
                for(; x <= n; ++x)
                {
                    int idx = y * WIDTH + x;
                    dp_temp[idx] += dp[idx - WIDTH];
                    dp_temp[idx] %= mod;
                    
                    dp_temp[idx] += dp[idx - 1];
                    dp_temp[idx] %= mod;
                    
                    dp_temp[idx] += dp[idx + WIDTH];
                    dp_temp[idx] %= mod;

                    dp_temp[idx] += dp[idx + 1];
                    dp_temp[idx] %= mod;
                    
                    if(y == startRow + 1 && x == startColumn + 1 && move == maxMove)
                        break;                   
                }
            } 
            
            std::memcpy(dp, dp_temp, sizeof(dp));
            
            ret += dp_temp[(startRow + 1) * WIDTH + startColumn + 1];
            
            ret %= mod;
        }

        return ret;
        
    }
};
 

bribnt

Đã tốn tiền
Nếu chỉ dùng kiểu dữ liệu 4byte thì lúc dùng simd để mod ko làm đc bác, mình phải cast nó về kiểu double thì mới tính modulo đc, _mm256_irem_epi32 chỉ support cho svml

Chưa thử tìm nhưng bác coi có cách nào dùng trick để không phải tính mod với SIMD không.
Search trên trang của intel thì riêng _mm256_div_pd + _mm256_floor_pd latency khoảng 14 + 8 = 22 clock rồi.

Nếu dùng x - (M & -(x >= M)) thì mất 4 clock, nhân 4 lên thành 16 là vẫn ít hơn. Chưa kể nó còn tự parallel được nữa.

1657974668541.png


https://leetcode.com/problems/out-of-boundary-paths/submissions/

C++:
class Solution {

#define M 1'000'000'007
    static inline __attribute__((always_inline)) std::uint32_t modSum2(std::uint32_t a, std::uint32_t b)
    {
        std::uint32_t res = a + b;
        return res - (M & -(res >= M));
    }
    
    static inline __attribute__((always_inline)) std::uint32_t modSum(std::uint32_t a, std::uint32_t b, std::uint32_t c, std::uint32_t d)
    {
        return modSum2(modSum2(a, b), modSum2(c, d));
    }
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        
        if ((startRow + maxMove < m) & (startRow - maxMove >= 0) & (startColumn + maxMove < n) & (startColumn - maxMove >= 0))
            return 0;
        
        std::array<std::uint32_t, 64*64> dp1{}, dp2{};
        
        ++startRow, ++startColumn;
        dp1[startRow<<6 | startColumn] = 1;
        
        std::uint32_t res = 0;
        int rb = startRow, re = startRow, cb = startColumn, ce = startColumn;
        
        decltype(dp1)* curr = &dp1, *other = &dp2;
        
        for (int k = 1; k <= maxMove; ++k) {
            // other->clear();
            auto &dp = *curr, &tmp = *other;
            
            rb = max(1, rb-1), re = min(m, re+1), cb = max(1, cb-1), ce = min(n, ce+1);
            
            // i = 1
            res = std::accumulate(&dp[1<<6|cb], &dp[1<<6|(ce+1)], res, modSum2);
            
            for (int i = rb; i <= re; ++i) {
                
                res = modSum2(dp[i<<6|1], res);
                
                for (int j = cb; j <= ce; ++j) {
                    tmp[i<<6 | j] = modSum(
                                        dp[i<<6|(j-1)] & -(j > 1), 
                                        dp[i<<6|(j+1)] & -(j < n),
                                        dp[(i-1)<<6|j] & -(i > 1),
                                        dp[(i+1)<<6|j] & -(i < m));
                }
                
                res = modSum2(dp[i<<6|n], res);
            }
            
            // i = m
            res = std::accumulate(&dp[m<<6|cb], &dp[m<<6|(ce+1)], res, modSum2);
            std::swap(other, curr);
        }
        
        return res;
    }
};

auto _ = [](){
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    return 0;
}();
 

Tuấn Mỏ

Senior Member
Chưa thử tìm nhưng bác coi có cách nào dùng trick để không phải tính mod với SIMD không.
Search trên trang của intel thì riêng _mm256_div_pd + _mm256_floor_pd latency khoảng 14 + 8 = 22 clock rồi.

Nếu dùng x - (M & -(x >= M)) thì mất 4 clock, nhân 4 lên thành 16 là vẫn ít hơn. Chưa kể nó còn tự parallel được nữa.

View attachment 1268763

https://leetcode.com/problems/out-of-boundary-paths/submissions/

Theo ý tưởng của Bác thì e convert nó thành ntn, latency giảm xuống còn 8,
1657980977151.png


C++:
    __attribute__((target("avx512dq, avx512vl"))) __m256i vec2iSumMod(__m256i& a, __m256i& b, __m256i& M)
    {
        __m256i vec2iSum = _mm256_add_epi64(a, b);
      
        return _mm256_sub_epi64(
            vec2iSum,
            _mm256_andnot_si256(
                _mm256_cmpgt_epi64(M, vec2iSum),
                M
            )
        );
    }

Bác dùng bitwise đỉnh thật đấy,

Hàm sumMod2 của bác là trừ đi 1 phần Mod sau khi sum nếu sum >= Mod, e vẫn chưa hiểu lắm ý tưởng đằng sau hàm sumMod2 ấy, Bác có thể giải thích thêm đc ko nhỉ? thanks
 
Last edited:

bribnt

Đã tốn tiền
Hàm sumMod2 của bác là trừ đi 1 phần Mod sau khi sum nếu sum >= Mod, e vẫn chưa hiểu lắm ý tưởng đằng sau hàm sumMod2 ấy, Bác có thể giải thích thêm đc ko nhỉ? thanks

Hàm này giả định cả 0 <= a, b < M.
Cho nên a + b < 2M.
Nếu a + b >= M thì (a + b) % M === a + b - M
a + b < M thì (a + b) % M === a + b - 0

Cái đoạn res - (M & -(res >= M)):
  • Nếu (res >= M) ==> -(res >= M) = -1 = 0xffffffff toàn bit 1, khi and với số toàn bit 1 sẽ ra chính nó.
  • Nếu (res < M) ===> -(res >= M) = -0 = 0x0000000 toàn bit 0, khi and với 0 thì luôn bằng 0.
 

Violet_7

Senior Member
17/7/2022:
  • 1 Câu hard khá khoai
  • Nhìn vào đề bài lúc đầu, éo có ý tưởng gì, bí tầm 15p.
  • Lúc sau để ý 1 điều:
  • VD n = 4 có 2 cặp thỏa mãn đề bài thì sẽ có 1 mảng thỏa mãn [3, 1, 4, 2]
  • vậy nếu add số 5 vào mảng này thì số cặp sẽ tăng tùy vị trị của số 5
  • nếu [3, 1, 4, 2, 5] -> ko tăng cặp nào
  • nếu [3, 1, 4, 5, 2] -> tăng 1 cặp
  • nếu [3, 1, 5, 4 ,2] -> tăng 2 căp
  • ...
  • Như vậy áp dụng tính chất trên ta có thể xây dựng công thức quy hoạch động
  • tạo mảng 2d dp trong đó dp[i.][j.] là số lượng mảng có thể có nếu n == i và k == j
  • như vậy dp[i.][j.] = sum(dp[i - 1][0] -> dp[i - 1][j.]) (cái này hơi khó nói ở đây, mà cx dễ thôi :))
  • Nhưng sẽ gặp vấn đề nếu như j >= i thì sum(dp[i - 1][0] -> dp[i - 1][j - i]) sẽ ko đc cộng vào dp[i.][j.] (cái này cx khó nói nốt, :)) nên nhưng th như thế phải trừ cái sum đó
  • Vấn đề tiếp theo là phải cố gắng sử lí cái trường hợp số lớn cho hợp lí
  • ra đáp án
  • Time: O(n* k)
  • Space: O(n * k) (có thể rút gọn xuống space O(k) cx khá dễ thôi mà làm 45p nên hơi lười)
  • Code: https://leetcode.com/submissions/detail/748946855/
  • Câu này nghĩ mất 20 phút, mà code gặp nhiều vấn đề nên mất con mẹ 45p :beat_brick::beat_brick:
 

_Gia_Cat_Luong_

Senior Member
17/7/2022:
  • 1 Câu hard khá khoai
  • Nhìn vào đề bài lúc đầu, éo có ý tưởng gì, bí tầm 15p.
  • Lúc sau để ý 1 điều:
  • VD n = 4 có 2 cặp thỏa mãn đề bài thì sẽ có 1 mảng thỏa mãn [3, 1, 4, 2]
  • vậy nếu add số 5 vào mảng này thì số cặp sẽ tăng tùy vị trị của số 5
  • nếu [3, 1, 4, 2, 5] -> ko tăng cặp nào
  • nếu [3, 1, 4, 5, 2] -> tăng 1 cặp
  • nếu [3, 1, 5, 4 ,2] -> tăng 2 căp
  • ...
  • Như vậy áp dụng tính chất trên ta có thể xây dựng công thức quy hoạch động
  • tạo mảng 2d dp trong đó dp[i.][j.] là số lượng mảng có thể có nếu n == i và k == j
  • như vậy dp[i.][j.] = sum(dp[i - 1][0] -> dp[i - 1][j.]) (cái này hơi khó nói ở đây, mà cx dễ thôi :))
  • Nhưng sẽ gặp vấn đề nếu như j >= i thì sum(dp[i - 1][0] -> dp[i - 1][j - i]) sẽ ko đc cộng vào dp[i.][j.] (cái này cx khó nói nốt, :)) nên nhưng th như thế phải trừ cái sum đó
  • Vấn đề tiếp theo là phải cố gắng sử lí cái trường hợp số lớn cho hợp lí
  • ra đáp án
  • Time: O(n* k)
  • Space: O(n * k) (có thể rút gọn xuống space O(k) cx khá dễ thôi mà làm 45p nên hơi lười)
  • Code: https://leetcode.com/submissions/detail/748946855/
  • Câu này nghĩ mất 20 phút, mà code gặp nhiều vấn đề nên mất con mẹ 45p :beat_brick::beat_brick:
Công nhận bài hnay khó thật, trước từng làm qua rồi mà h làm lại vẫn thấy chua :ROFLMAO::ROFLMAO:
 
Top