Hello everybody,
I need your help! Given a string S (|S| <= 10^5) consisting of uppercase letters and an integer K (K <= |S|). Consider a set consisting of all uppercase letters. We are to choose some letters from that set and replace their occurences in S with a star ('*'). Our goal is to make at least one star appear in each substring of length K and we need to do this choosing minimum number of different letters from the set. Output the minimum number of letters and the letters in different lines. If multiple solutions exist, we can print any of them. For example, if S="ABA" and K=2, then we can choose either 'A' or 'B' and receive "*B*" and "A*A" respectively.
Thanks in advance! :)
OK, it was overkill
does O(26 * 2 ^ 26) solution become accept ?
I always take 108 computations per second as a standard worst case for a solution to pass in online judges. So if time limit per test is > 2 seconds it will
Shouldn't it be 10^6 in 1 sec? (Although I've seen 10^7 in 1 sec solution pass at times)
Ref: Competitive Programming 1 [Competitive Programming]
I think you are deducing that by looking at size of array like arr[100000] in code. That is not correct method
Nope I didn't mean that. Competitive Programming 1 states that 'CPU can do 1M operations in 1s' [See pg 18 of the pdf]. I suppose they were trying to be extra careful. Correct me if I'm wrong.
Computers have improved a lot after that book is written.
Normal computers can do about 3 * 109 bit operations which means something like 108 summations.
Ok. Thanks!
For each K sized subsequences(there are N — K + 1 of them) find the mask of the letters that does not occur in that subsequence. Lets call them bad subsets.
Afterwards you need to eliminate all the subsets which is subset of one of the above bad subsets. We can do this by somekind of top bottom dp approach which leads to O((2^26 + N)26) complexity. It might be possible to eliminate factor 26. I did not think about it enoubh yet.