Down_bad_4_haiender288's blog

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

Author's solution: O(N^4)

GPT's solution: O(N)

:skull:

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

»
7 weeks ago, hide # |
 
Vote: I like it +61 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
»
7 weeks ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

Are the $$$O(n^3) \to O(n^\omega)$$$ reductions literally just the problem allowing simulating matrix multiplication?

→ Reply
  • »
    »
    7 weeks ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    I’m willing to bet many of the other ones also hinge on algorithms that are either too obscure or long to put in a competitive programming contest or just straight garbage like tbank pointed out

    → Reply