invoker._'s blog

Time and memory complexity(Pls help!)
By invoker._, history, 2 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that's why #define int long long is useful

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what do you think about #define int short as suggested by Sparky Master

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        i think you can

        #define short long long
#define int short
        → Reply