shashiHIGS's blog

TLE on 287B
By shashiHIGS, 11 years ago, In English

Can anyone help me to improve the code.. Here is my solution:3406918.

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

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

you should use binary search

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Use scanf()/printf()

And also change this part for(long long i=K;i<N;i+=(K-T-1)) to long long i; for(i=K;i<N;i+=(K-T-1))

*** Brute force is the alternate solution of this problem ... But actually this problem should be done by binary search or mathematically

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

    And also change this part for(long long i=K;i<N;i+=(K-T-1)) to long long i; for(i=K;i<N;i+=(K-T-1)) ---> Why we must change this?Does it make our time less?

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

      No it doesn't make the time less. Your algorithm is still O(N) which is not fast enough. Binary Search (O(lgN)) does the work! The idea is that if you know that you need x splitters, the greedy way is to pick the x splitters that have the most outputs (the last splitter mightn't be in these top x splitters to have n outputs in total), so basically you bsearch to find x.

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

      Suhaylee, You can read comments of this entry... here you will see a comment just like this post... from that, I have made me known that, it makes our time less...

      this solution gives TLE, where as this is accepted ... difference is in just data type of 'i'... And you may know, 'long long' takes some more time than 'int'...

      → Reply