Today, while working on 1932E, I came up with a construction method that might be correct. However, this approach times out at the 13th test point. I believe finding a valid path is the bottleneck of my algorithm.↵
↵
Now, I have simplified the approach to finding a valid path in 1932E and want to ask if there is a method with a time complexity of $O(n^3)$ or better.↵
↵
Given an $n\times n$ matrix and an integer $k$, you need to start from $(1,1)$ and move to $(n,n)$, where you can only move one step down or one step to the right each time. The task is to find a valid path such that the sum of all numbers on the path equals $k$.↵
↵
- $2\le n\le 25,1\le k\le 10^{13}$.↵
↵
- Ensure that the **data is generated randomly**.↵
↵
↵
↵
Here are the Chinese description.↵
↵
给定一个 $n\times n$ 的矩阵和一个整数 $k$，你需要从 $(1,1)$ 出发走到 $(n,n)$，每次可以向下或向右走一步。请求出一种合法的路径使得路径上所有数的和为 $k$。保证数据随机生成。↵
↵
是否有一种 $O(n^3)$ 或更好的做法。
↵
Now, I have simplified the approach to finding a valid path in 1932E and want to ask if there is a method with a time complexity of $O(n^3)$ or better.↵
↵
Given an $n\times n$ matrix and an integer $k$, you need to start from $(1,1)$ and move to $(n,n)$, where you can only move one step down or one step to the right each time. The task is to find a valid path such that the sum of all numbers on the path equals $k$.↵
↵
- $2\le n\le 25,1\le k\le 10^{13}$.↵
↵
- Ensure that the **data is generated randomly**.↵
↵
↵
↵
Here are the Chinese description.↵
↵
给定一个 $n\times n$ 的矩阵和一个整数 $k$，你需要从 $(1,1)$ 出发走到 $(n,n)$，每次可以向下或向右走一步。请求出一种合法的路径使得路径上所有数的和为 $k$。保证数据随机生成。↵
↵
是否有一种 $O(n^3)$ 或更好的做法。
