Mastermind222's blog

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

By Mastermind222, history, 4 years ago, In English

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. :)

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

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

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.

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

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

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

Try this test

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

    Yes,recevied a TLE verdict.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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.

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

      Passed in 1263ms on that test case.

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

        Yup I passed with 1.6 secs, I guess passing the vector without reference is the problem

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

          You are doing approx 2000*100*100*100 ≈ 10⁹ operations, which is on the edge.

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

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

→ Reply