ABC was too easy this contest.

I understood the editorial algorithm for C, but can someone help me with why the greedy algorithm is correct? I am unable to prove it. Thanks alot!

For problem C I kept on overthinking that the solution would involve DP, however I did notice that the constraints on $$$x$$$ was too big and that it would most probably lead to TLE. However, can anyone think if DP is feasible for problem C if $$$x$$$ was actually some small number?

My approach on C: If we consider a maximal block of same character sequence of size say $$$l$$$ then the number of ways we can pick an element to survive in that block is $$$l$$$ ways, after which there exists $$$(l-1)!$$$ arrangements to delete the remaining elements in the block. Hence there exists a total of $$$(l - 1)! \times l = l!$$$ ways within the block to perform the valid operation. And if there are $$$k$$$ such blocks then there exists a total of $$$\prod_{i}^{k}l_{i}!$$$ valid operations.

This approach fails however, not sure why. Any help/corrections appreciated!

Can someone help me with understanding my solution to B more clearly? I tried using binary search by answer here. I felt it was a plausible solution since if a radius (say r) is an answer then all radiis > r are also the answer. I tried implementing some solution, didnt work, maybe my impl on binary searching for real answers suck. Help/Correction appreciated!

// checks if point is inside circle
bool check(pair<float, float> circle, pair<float, float> point, float w){
    return ((circle.first - point.first) * (circle.first - point.first) + 
    (circle.second - point.second) * (circle.second - point.second)) <= w * w;
}

//checks if circles A and B are touching
bool istouch(pair<double, double> a, pair<double, double> b, double w){
    return w + w >= ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}


//checks if the radius is a valid answer
bool isok(pair<float, float> b, pair<float, float> p, pair<float, float> o, pair<float, float> a, float w){
    return (check(b,o,w) & check(b,p,w) | (check(a,o,w) & check(a,p,w))) | 
    (check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w));
}

double WORST = 3e3f;
double EPS = 1e-6f;

void solve(){
    pair<float, float> p, a, b, o;
    cin >> p.first >> p.second;
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;

    o = make_pair(0.0f, 0.0f);

    double l = 0.0f, r = WORST;
    double w = r;

    //binary searching the answer starts from here
    while(r - l > EPS){
        double mid = (l + r)/2;
        if(isok(b,p,o,a,w)){
            w = mid;
            r = mid;
        } else {
            l = mid;
        }
        // cout << l << " " << r << "\n";
    }

    cout << w << "\n";

}

Hi I was upsolving the C problem, can someone tell me why this wont pass the second test case? Thanks in advanced! my solution

This one passed the pretests (for now) and is not a dp solution but what i basically thought was that the palindrome of length 2 or 3 should not exist, so basically

s[i] != s[i+1] || s[i] != s[i+2]

If it does happen then I change the values of s[i+1] or s[i+2] to # sign. The reason being that im considering # to hold a value that is not equal to its i+2 or i+1. So if i ever encounter # sign i skip it knowing that if s[j] = # then theres no need to check s[j+1] || s[j+2] because it will not be ever equal. Hence the answer is just the number of # signs in the resulting string! Code (I used # here because the dollar sign was converting my text to latex)

Can someone explain why did this solution TLE's? My Solution

But the time limit for D is 2s, so shouldn't the cap be 10^10 approx?

Im pretty sure my code will pass all test cases if not due to TLE.

The time limit for D is 2s, so can O(N^2) solution work for D? My solution for D

Oh, thanks for your help!

Can someone explain why this wont pass third test case for problem B? 87097426

How does https://mirror.codeforces.com/contest/1358/submission/81520389 exceed time limit? since max of a is 2*10^5 or just O(2n) how does it exceed TL?? It passed the pretests during the contest, but i saw that after the contest i got it wrong :(