thx very much i'm actually stupid for all this time i tought i was iterating over n not over k on the contest i brainlagged too much

why am i creating these entries shouldn t the dictonary create only (n) entries?

the map should have worked in space O(2 * n + some factors) right?

bruh i was one of those who wrote their solution with UM but i got MLE instead, can someone explain to me why i got MLE this is my code i also wrote a version in c++ and had failed again with MLE, after a while i had used the vectors with a space of O(n) and a complex of O(n*log(n))

this is my submission 333342133

There is a playlist of Shayan

https://youtube.com/playlist?list=PLzDmwrrgE-UVKGwxoYao36BVTvBozwLoG&si=YFCKfC59NI-LMqX7

u are not using dp properly u are updating the matrix only when u find a valid combinations of operations, try to think at ur tree of calls

input : 33 every fork is a possible path and u are updating ur matrix to 1 only when u find a valid sum that is divisible by 9

                   | - 3
          | - 3  - |
          |        | - 9
dp[0][0]- |
          |        | - 3
          | - 9    |
                   | - 9

in a bigger picture what u wrote is:

1) i try a path

if the sum of the digits on the path is not 0 mod 9 i'm going back and i m not updating the matrix [wrong]

if the sum of the digits on the path is 0 mod 9 i have found a solution

this is an exponential solution

try to use a 3th value {-1 : idk,1:found,0: ehi bro i have already try everything from this postion is usless that we are searching there}

sorry for bad english + it's 00:15 in my country + i'm sleeping

infact bro i challenge u to spot the difference between ur code and my version 295135560

btw a gigachad solution to this problems is:

the only 2 numbers that ^2 are less than 10 are 2 and 3 and change these digits is equal to adding 2 or 6 respectevely knowing that gcd(9,6) != 0 and gcd(9,2) == 1 u can exploit some properties of modular magic and bruteforce only a small set of value cuz without going deep in the modular math world:

from 0 if u add 6

0 — 6 — 12 % 9 == 3 — 9 % 9 == 0 and that's it [0,6,3,0] is usless adding more than 2 six instead for the 2

2 — 4 — 6 — 8 — 1 — 3 — 5 — 7 — 0 it's usless adding more than 8 two

u can bruteforce every possible combinations of six and two and u have ur answer :D

recursion is computationally heavy

iterative:

295133603