Ask AI
Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.
Open Claude Desktopdynamic-programming · data-structures · prefix-sums
The organizer’s problem statement is available at the official source link.
sample trace
Cow Hopscotch: per-color Fenwick trees
For each cell, sum path counts from strictly upper-left cells of a different color. The Gold solution accelerates this sum with per-color Fenwick trees and a total count.
colors
| 1 | 1 | 1 | 1 |
| 1 | 3 | 2 | 1 |
| 1 | 2 | 4 | 1 |
| 1 | 1 | 1 | 1 |
path Counts
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 2 | 2 |
| 0 | 0 | 2 | 5 |
start
11
goal
44
answer
5- 1
Define a state
dp[r][c] counts valid paths that end at cell (r,c). The top-left cell starts with 1. - 2
Filter predecessors
Only cells in earlier rows and columns with a different color can transition into the current cell. - 3
Accelerate the sum
Gold keeps column-prefix counts in a Fenwick tree per color plus a total; subtract the current color?s count to get different-color predecessors. - 4
Read the destination
The destination state is 5, matching the sample output.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 charsRun output
Run your code to see output.