Safrout's blog

SPOJ CT16E — Fish TLE with Java
By Safrout, 10 years ago, In English

I am getting TLE with this problem in java.

Here is the link to the problem http://www.spoj.com/problems/CT16E/

Here is my code http://ideone.com/bxG58H

Can I do more optimization to get it passed with java or I need to change the state representation or even the approach ??!!

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

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

y not try it out here on codeforces ? 16E - Fish

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

    I did now and it's accepted in codeforces.

    But I actually want to pass it on SPOJ with java :D .

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

Without having a closer look on the problem and just looking at the code, these are the optimizations I can suggest.

  • Optimize I/O, e.g. use PrintWriter for output. In this case you don't output a massive amount of numbers, so this should only make a small difference (but maybe a necessary one?).
  • Move out the if((mask&1<<i)!=0) part of the if-statement in the DP a loop level.
  • Divisions are expensive so move out the /pairs part from both loops in the DP, i.e. change to dp[mask] /= pairs.
  • I guess some time is spent in the BitCount function, especially considering it contains a modulo operation, eliminate the need and use of this function by simply keeping track of the number of ones as you move along.
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Main optimization for getting AC on SPOJ — change recursion with memoization to calculating dp with for-loop.

And it need to move out clause if((mask&(1 << i)) != 0) on "i" loop level, as Klein mentioned.

This code got AC on SPOJ: link to Ideone

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

Thank you so much Klein and Slamur .

→ Reply