Task G is almost identical to a task from the Polish Olympiad in Informatics called Parade. The only difference is in the POI task, you can not choose $$$a = b$$$.

evc = n / 2;
if (n & 1) evc++;

is the same as

evc = (n + 1) / 2 ; 

for C I'm getting different outputs on my system than the codeforces judge?

Where is the formal proof of correctness to the editorial solution of D?

I was hoping to see the cleanest solution and proof to the problem, now the editorial for this problem is very unhelpful.

I have a question about how to arrive at the correct conclusion for a problem, for example, Problem B. That is, how to reach that solution—what was the clue in the problem that led to solving it in that way? I find it difficult to arrive at such a conclusion.

What I mean is, how should I study to improve this? Is it just about practicing problems, or does it require a more mathematical way of thinking? If anyone reads this, I would appreciate it if they could recommend a book or any resource. :(

I am unable to understand the language of E and cant think of any approach i thought may be 3 loops as time is 2.5S but still dont understood minimum number of characters of C w.r.t to all strings we can make ? how can i know there can be many string can be formed. Anyone pls just point me in right direction. thanks

Who can help me why I had a WA2, problem E? https://codeforces.net/contest/2050/submission/295355937

For problem D, I used insert() and erase() functions to modify the string and it gave me TLE on testcase 7, later, I changed my solution to keep track of what characters from the original string are moved to their left using an array and kept adding such characters to an empty string. I think my current solution is O(n) but it got a TLE on testcase 8. Can someone tell why I got TLE? Submission link

Can I please get some help in G? Wrong answer on test 2 — 295368314

My approach:

Navigate all the possible paths from the root node (0) to all the leaf nodes using DFS. For each such path, store the values of their degrees in an array $$$a$$$. If we consider some subarray [L, R] of $$$a$$$ (basically, a path) and remove all the nodes in this subarray then the number of components = $$$(\sum_{i=L}^R a_i) - 2 \cdot (R - L)$$$

The above equation can be rewritten in terms of prefix sum as:

$$$p[r + 1] - p[l] - 2 \cdot (r - l)$$$
$$$p[r + 1] - p[l] - 2 \cdot (r + 1) + 2l + 2$$$
$$$(p[r + 1] - 2 \cdot (r + 1)) - (p[l] - 2l) + 2$$$

Compute the array p using the equation above. Iterate from the left, maintain a current minimum variable, compute the value for $$$R + 1 = i$$$ and update result. The final answer will be maximum of such results in all possible paths from root node to leaf node.

Note: I am computing the prefix sum array in a different way. To get the sum of subarray [L, R] I would have to query $$$p[R + 1] - p[L]$$$

For C, will not be time complexity O(x*x) in the worst-case scenario where x is the length of the number? When the count of both 2s and 3s becomes equal to x/2. How is it getting accepted for a constraint of 10^5 on number length?

Can anyone clarify?

Task G solution 295409653

Could you guys help me with question G? I got the wrong answer for test case 17. https://codeforces.net/contest/2050/submission/295318789

2050C — Uninteresting Number he said" We can choose how many of the available digits 2and 3we will transform. Transforming more than 8 twos and more than 8 threes is pointless because remainders modulo 9 their transformation adds to the sum will repeat." in fact Transforming more than 8 twos and more than 3 threes is pointless
because 3*3=9,than their transformation adds to the sum will repeat.

Can anyone please tell me the recursive approach of solving problem E, as directly telling the dp approach doesn't takes the intuition under consideration and writing correct recurrence relation makes it very easy to optimise from memoisation to space optimisation.

Below is my incorrect and complex solution with too much of if and else condition.

Idea: Take three pointers i,j,k pointing to a,b,c respectively, if a[i] matches c[k] then increment i and k, if b[i] matches with c[k] then increment j and k, if none of them matches with c[k] then check by incrementing i first then k and vice versa and then increment j and k and viceversa

int recur(string &a, string &b, string &c, int i,int j, int k) {
    if(k >= c.length()) return maxm(0,a.length()-i,b.length()-j);
    if(i >= a.length() && j >= b.length()) return c.length() - k;
    if (i < a.length() && a[i] == c[k]) {
        return recur(a,b,c,i+1,j,k+1);
    } else if (j < b.length() && b[j] == c[k]) {
        return recur(a,b,c,i,j+1,k+1);
    } else if(i < a.length() && j < b.length()) {
        return 1+min(recur(a,b,c,i+1,j,k+1), recur(a,b,c,i,j+1,k+1));
    } else if(i < a.length()) {
        return min(recur(a,b,c,i+1,j,k), 1+recur(a,b,c,i,j,k+1));
    } else if(j < b.length()) {
        return min(recur(a,b,c,i,j+1,k), 1+recur(a,b,c,i,j,k+1));
    } else return 0;
}
int main() {
	// your code goes here
    int t;
    cin>>t;
    while(t--) {
        string a, b, c;
        cin>>a>>b>>c;
        cout<<recur(a, b, c, 0, 0, 0)<<endl;
    }
}

Hi, I have a doubt in a different approach of problem G (may be wrong)

This approach involves getting the diameter, removing the vertices along the diameter and then calculating the number of component (nc)

The final answer will be nc+2.

I wan't to know if it is a right approach and if it is possible to implement it in the time limit.

Thanks

template contest.

In C, I am getting error in test case 3 in 401th case which is 9223372036854775807. It is showing that expected "NO" but got "YES" instead. But this number can be converted to 9's multiple if one of the 2 is changed. Can someone pls explain ?

nvm

Problem C: The only extra piece of proof that I wish should be added is that, after calculating the num2s and num3s in the string. We can loop at most 9 times for each of twos, threes. As anything after this would be rudimentary as it would be divisible by 9 directly, so the loop should run from i = [1 to min(num2, 10LL)), j = [1 to min(num3, 10LL)). As, someone might think why running loop (num2*num3) times per test case doesn't add up to TLE, this is cause we would be checking for atmost 81 different states, which is of constant time complexity, and breaking out after it.

can someone hack me please Problem G 296473359

I Solved It greedly by picking node lca(a,b) which called root which have max number of edges

After that I Picked greedly node a which the node that have max number of connected components with lca(a,b)

After that I pick node b which have max number of connected components with node b

can somebody explain why my code for C is not working?

Problem E solution with recursive approach:

int best(int i, int j, int k)
{
    if (k == c.sz)
    {
        return 0;
    }
    if (dp[i][j] != -1)
        return dp[i][j];
    int ch1 = -1, ch2 = -1;
 
    if (i < a.sz)
        ch1 = bool(a[i] == c[k]) + best(i + 1, j, k + 1);
    if (j < b.sz)
        ch2 = bool(b[j] == c[k]) + best(i, j + 1, k + 1);
    dp[i][j] = max(ch1, ch2);
    return dp[i][j];
}

in Problem E why i am getting TLE in tc 16?

https://codeforces.net/problemset/submission/2050/303333663

Editorial for G is too complicated. Dp on trees wasn't needed and was too advanced for this. Rather just root the tree at the node with max degree, reduce the degree of each node by 2 except for the root and find the max degree sum path for all the children of the root and add the top 2 max Paths.

My submission — 304341864

There also exists a greedy solution for C.

Let $$$sum$$$ denote sum of all digits, $$$cnt[i]$$$ denote the occurrences of $$$i$$$ in $$$n$$$. Let $$$x = sum \ \text{mod}\ 9$$$. While $$$x \neq 0$$$, we do the following,

1. If $$$x$$$ is a multiple of 3 and $$$cnt[3] > 0$$$, change a 3 to a 9 and update sum (Call this operation 1)
2. Else if $$$cnt[2] > 0$$$, change a 2 to a 4 and update sum (Call this operation 2)
3. If neither of the above is possible, break.

Proof: It is always better to use first operation than second whenever possible. For operation 1, $$$x$$$ is either $$$3$$$ or $$$6$$$. If it is $$$3$$$ then we get $$$3 + 6 \cong 0 \ \text{mod}\ 9$$$ in one change, whereas with operation 2, we would do $$$3 \rightarrow 5 \rightarrow 7 \rightarrow 9 \cong 0 \ \text{mod}\ 9$$$. Thus we now need 3 lesser occurrences of $$$2$$$.

Similarly, for $$$6 \ \text{mod}\ 9$$$, by applying the operation 1, we get $$$3\ \text{mod}\ 9$$$, which will take 3 occurrences of two as above compared to the 6 occurrences otherwise $$$(6\to 8\to 1 \to 3 \to 5 \to 7 \to 0)$$$. Since each time operation 1 is possible, we are reducing the total number of operation 2's needed by 3, it is no worse than an $$$\text{OPT}$$$ algorithm, hence optimal.