Блог пользователя Mastermind222

Doubt regarding Problem C: Codeforces Round #717 (Div. 2)

Автор Mastermind222, история, 4 года назад, По-английски

Problem C

My Accepted Solution

According to me, the time complexity of the above code is O(sum*n*n)(sum= sum of the array passed to the function) and hence should result in a TLE verdict(Correct me if I am wrong).Help me in clearing this doubt. Thanks in advance. :)

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

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

I think the time complexity is maxSum*n which would be 2000*100*100 =2*10^7 which will pass in the given time constraints.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    maxSm*n is the time complexity for the partition function and an additional *n for the iteration I guess.

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

Try this test

Spoiler
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes,recevied a TLE verdict.

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Can someone try to uphack my solution with this? I feel like Mastermind222's solution got hacked because he's passing the vector without reference and hence your sys tests time is 1.6 secs on the other hand, mine is 0.9 secs. I feel like mine will still pass with this testcase

    Here is the proof

    I think that is the case. I get 1.6 secs on my desktop with this test case.

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

Yes it should TLE. Weak test cases.A lot of people have done the same.

→ Ответить