Đời Cơ Bản Là Buồn
Junior Member
Solution anti recursion cua? bo^?n to.a
https://leetcode.com/submissions/detail/734346169/
https://leetcode.com/submissions/detail/734346169/
https://leetcode.com/submissions/detail/748318119/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á
#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;
}
};
#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.Đó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; } };
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++.Ặ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?
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)
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;
}();
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.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)
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; } }
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.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.
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)
Đ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.
Ặ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?
#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;
}
};
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
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.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;
}();
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ùngx - (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/
__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
)
);
}
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
res - (M & -(res >= M))
: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 chua17/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