Problem: http://www.spoj.com/problems/CRICKDP/

I tried doing it by finding the minimum removal cost for each score in and then using this to calculate the maximum total score by DP, but this is too slow. Any other ideas will be appreciated. Thanks.

# | User | Rating |
---|---|---|

1 | tourist | 3697 |

2 | Benq | 3583 |

3 | Petr | 3522 |

4 | ecnerwala | 3467 |

5 | Radewoosh | 3466 |

6 | maroonrk | 3369 |

7 | Um_nik | 3358 |

8 | jiangly | 3330 |

9 | Miracle03 | 3314 |

10 | scott_wu | 3313 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 213 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 179 |

7 | Ashishgup | 177 |

8 | maroonrk | 173 |

9 | vovuh | 172 |

9 | antontrygubO_o | 172 |

Problem: http://www.spoj.com/problems/CRICKDP/

I tried doing it by finding the minimum removal cost for each score in and then using this to calculate the maximum total score by DP, but this is too slow. Any other ideas will be appreciated. Thanks.

*k* characters can be used. The code is not yet complete as it's only calculating the minimum number of changes. The problem also requires the actual answer with minimum changes. So how to do this?

Problem: http://www.spoj.com/problems/PARTY/

Solution: http://ideone.com/XWCBcI

I am using the recurrence relation given here but as you can see it's not giving the correct output for the second case. Please help me find the error.

I am generating primes till `sqrt(10**9)`

using Sieve of Eratosthenes and then calculating divisors of numbers in the given range by dividing them by primes till `sqrt(number)`

but it's getting TLE.

**UPDATE:**I found my mistake. The sieve implementation is wrong.

**UPDATE2:**I corrected the Sieve but its still getting TLE. I am using the same algorithm as this New solution

`0`

so how is this algorithm correct? Or is my implementation wrong? Someone please help prove the correctness of this algorithm. Thanks.

I was reading about hashing from here and I am unable to understand the part about calculation of hash of a substring. I am calculating the hash of the entire input string in this way : `h (S) = S [0] + S [1] * P + S [2] * P ^ 2 + S [3] * P ^ 3 + ... + S [N] * P ^ N`

Suppose `P = 31`

and a = 1, b = 2, c = 3 and so on. Then for the input string `abcdab`

, h[0] = 1, h[1] = 32, h[2] = 2915, h[3] = 122079, h[4] = 1045600, h[5] = 58303902. Now from these values, how can I calculate `h[0..1]`

or `h[3..5]`

?

`ans = max(ans,j-i)`

?

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2021 19:24:10 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|