Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### tbdsh's blog

By tbdsh, history, 5 weeks ago,

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.

Unable to parse markup [type=CF_MATHJAX]

(1,1)$出发走到$(n,n)$，每次可以向下或向右走一步。请求出一种合法的路径使得路径上所有数的和为$k\$。保证数据随机生成。

• +1

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by tbdsh (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by tbdsh (previous revision, new revision, compare).