Imbue take home exam

时间线

• 第 1 天：投递。
• 第 2 天：收到拒信，理由是 background/skillset 和他们的需求不够匹配。拒信里同时给了一个可选的 take-home：通过的话直接进面试流程，并且跳过第一轮 coding。填一个 Typeform（名字和邮箱），一天之内 MarioHR 发来测评链接。

形式

• 平台是 MarioHR，用 GitHub 登录，全程录屏。
• 限时，官方说预留 1–2 小时，难度很高，"不指望做完"，主要看解题思路和代码能力。
• 语言随意，可以查文档和库 禁止 AI。
• 题目是 repo 的形式，代码放在
  1. solution/

  复制代码
  目录，附带
  1. test_cases.md

  复制代码
  。

题目（应该是 TopCoder 上的 RowGame，大意）

• 您好！
  本帖隐藏的内容需要积分高于 200 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 200 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
  
  
  思路
  带 cache 的 DFS 如果把 score 放进键里，状态数会爆炸；如果 score 不放进键里，结果就是错的。正确做法是把 score 当成 DP 的值：dp[步数][位置] = 到达这里时的最高分。因为分数越高，能走的步只会越多（高分支配低分），所以每个状态只保留最高分就够了。
  方向完全由步数的奇偶决定，状态里可以不放方向。开局只有一个合法状态。
  k 最大 4 亿，O(k·N²) 跑不完。后期的走法会变成在某个区间来回刷分，DP 数组每两步整体加一个固定的增量。检测到增量稳定后，算出最早什么时候会出现变化（某一步变合法或变不合法、最优来源被反超、新格子能到达），直接跳到那个时候，再接着模拟。
  注意溢出：最高分能到 8e18 左右，int64 刚好装得下.
  后续：take-home 挂了。DP 只差一个初始化 bug，可惜时间不够。需要先想清楚 DP 状态和初始状态，再动手写。