In 159D - Palindrome pairs, if you know a method to find all the subpalindromes fast, you can get a better than O(L^2) solution:

1. Make two Segment Trees for counting the starts and the ends of palindromes.

2. If a palindrome(for example, odd) has center at position K and maximum length 2 * D + 1, then: 1 palindrome starts in K and ends in K, 1 starts in K — 1 and ends in K + 1, ..., last starts in K — D and ends in K + D. So, for adding their ends and starts in O(log L), we use segment updating.

3. What is the answer on the task? It's just a sum: for all K = 1, 2.., L — 1 we multiply the number of palindromes, that ended in K(exactly), and the number of palindromes starting later, i.e. st[K + 1] + st[K + 2] + ... + st[L]. Each number we can get in O(log L), using ST.

I am quite new to sport programming so I have never implemented a segment tree. I heard about it, though, but thought it was complicated. Anyway, I think my solution to 159C - String Manipulation 1.0 is quite neat :)

In short: binary search in a Fenwick tree.

Slightly longer: we start out with 26 arrays, all filled with 1's and having a length of k*repeats[c], where repeats is an array containing the number of occurrences of each character in the initial string. Then, we build a Fenwick tree on top of each of these arrays. After that, we start processing the request. For each request p_i, c_i, we perform a binary search in the corresponding Fenwick tree in order to find the leftmost position with p_i 1's before it. Then, we replace the 1 in that position with a 0. Each search takes O(log(k*repeats[c_i])) queries to the Fenwick tree, each being of O(log(k*repeats[c_i])) complexity, which yields O(log^2(k*repeats[c_i])) per each request. The entire complexity of the algorithm is O(n*log^2(k*|s|)).

After processing all requests, we extract the result by merely moving through the input string k times, each time either printing the corresponding character (if there's a 1 in its array) or omitting it.

I was trying a tree solution for C, but was getting wrong answers and eventually decided to make a solution that supposedly took advantage of the fact that the string is cyclic. Yet in reality, I think it can easily become a solution that needs O(sqrt(|ss|)) time to process each command. (Where ss is s repeated k times) (Currently it is O(|s| + k ).

There are initially k fragments of the ss string what you could do is for each of the k fragments, ad each letter, know the number of times the letter appears in the fragment and the positions of those appearances.

Now, in order to delete the P-th instance of a letter in the overall string (ss), you can first do a O(|k|) loop to find the fragment that has the p-th instance (Use the sums for each fragment instead of going through the letters in the fragment manually). After you find the fragment, you can use a O(|s|) loop to naively remove the [p — (sum of the letter counts of previous fragments) ]-th instance of the letter in the fragment.

This only looks like abusing the format of the string, because you can adapt it to work in O(sqrt(|s|)) time for any string (not just cyclic). So, let's say that ss has |ss| elements, you can always split it into O(sqrt|ss|) fragments of O(sqrt|ss|) letters each. The overall complexity would become O(sqrt|ss|) per step. The constraints make this good enough.

I am trying understand the 158E Phone calls solution but it seems a little complicated for me. In my little experience with dp I haven't found a problem like this. Could you explain the solution in more detail? Please!

This is not tutorial of VK 2015, can some body remove the tag?

Thanks for all!

B taxi. wrong answer on 67. can't even see inputs!

http://ideone.com/cTEsEx

I solved problem D using Manacher's Algo and prefix sums. 95691489

// This is a easiest way to solve this problem.
// Time complexity: O(N)
// Space complexity: O(N)

include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, ans = 0;
    cin >> n >>k; int arr[n];// without arr array time and space complexity O(1)
    for(int i = 0; i < n; i++) cin >> arr[i];// Time and Space complexity O(N)
    for(int i = 0; i < n; i++)// Time complexity O(N)
    {
        if(arr[i] > 0 && arr[i] >= arr[k - 1])ans ++;//if arr(ith index) >0 and arr(ith index) >= arr(k - 1 th index) ans will be increase by 1
    }
    cout<<ans;
    // Total time complexity  + Space complexity of this program is O(N)[always calculate from worse case]
    return 0;

On test case 37 the answer's shown as 3 . If n=3 and the numbers of students in each group are about 3 3 2 then it should need 2 cars .why the answer is 3????????? maximum students in a group are 4;

https://codeforces.com/problemset/submission/158/236650503

i have made all the cases ,why its giving wrong output..please check