Please read the new rule regarding the restriction on the use of AI tools. ×

Questionable constraint regarding a CSES problem.

Revision en1, by PeruvianCartel, 2023-12-06 04:16:53

Hi guys, in this problem: CSES: Maximum Building II, the constraint for $$$n$$$, $$$m$$$ was $$$1000$$$, which sounds fishy. Therefore, I tried the trivial $$$O(n^3)$$$ brute, and surprisingly it AC with the slowest testcase being 0.9s (I guess it's because the operations was so simple and predictable that the compiler and CPU just do some hocus pocus and speed it up like 10 times).
So... why did the author decide to set the constraint that low? You can solve that problem in $$$O(n^2)$$$, with good constant, so it's not like you have to be extremely generous when it comes to time limit to let these solutions pass, so what is the motive behind it? Was the $$$O(n^3)$$$ brute the intended algorithm? (which doesn't really make sense, since it's supposed to be a hard problem????)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English PeruvianCartel 2023-12-06 04:16:53 972 Initial revision (published)