gautam94's blog

By gautam94, history, 5 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By gautam94, 6 years ago, In English

I have written this code http://ideone.com/11kNYs for solving this problem http://codeforces.com/problemset/problem/219/C It asks for the minimum number of changes in a string such that no two adjacent characters are same and also only the first 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?

Read more »

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

By gautam94, 6 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By gautam94, 6 years ago, In English

Problem link

My solution

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By gautam94, 7 years ago, In English

I am having trouble understanding the nlogn algorithm for solving the LIS problem. I have implemented the algorithm given here on page number 6. Link to CPP implementation. I think it's only checking the subsequence starting at index 0 so how is this algorithm correct? Or is my implementation wrong? Someone please help prove the correctness of this algorithm. Thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By gautam94, 7 years ago, In English

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

Read more »

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

By gautam94, 7 years ago, In English

386B - Fly, freebies, fly! Please help me understand this solution. 5711342 Is this the two pointers method. Why is the final answer ans = max(ans,j-i) ?

Read more »

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