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

SPOJ CT16E — Fish TLE with Java
Автор Safrout, 10 лет назад, По-английски

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 ??!!

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

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

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

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

    I did now and it's accepted in codeforces.

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

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

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.
→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Thank you so much Klein and Slamur .

→ Ответить