Блог пользователя invoker._

Time and memory complexity(Pls help!)
Автор invoker._, история, 3 года назад, По-английски

Problem link: 1654C - Alice and the Cake

I tried solving the problem with a different approach. It would be great if someone helps me analyze the time and space complexity of my submission, because I feel it should be within constraints and somehow it fails!

Thanks for your time reading :)

152639386

Problem solved: see ACGN reply

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You are getting a MLE because you are using std::map

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Your program probably ran into an infinite loop because your variables val and oddval overflowed int.

AC submission by replacing int with long long in your declaration of val and oddval: 152648929

By the way, std::maps do not cause MLE since std::map also has space complexity O(n). An infinite loop, on the other hand, creates a large call stack which leads to MLE.

→ Ответить