Down_bad_4_haiender288's blog

new manmade horrors (barely within comprehension) just dropped
By Down_bad_4_haiender288, history, 3 hours ago, In English

Author's solution: O(N^4)

GPT's solution: O(N)

:skull:

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
40 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This $$$O(n^4) \rightarrow O(n)$$$ reduction looks genius, GPT just says:

// Deterministic O((q+1)*n) time and O(n) auxiliary space, where q is the
// number of distinct input x coordinates (including the source's x=0).
// The statement gives integer x in [-200,200], hence q<=401: linear here.

Ok. I have better solution! It's $$$O(1)$$$. We have $$$n \leq 50, k \leq 3000$$$ so it's $$$O(1)$$$.

→ Reply