ممكن تفتح الرسائل ؟؟

Damn, what a nice explanation. Thanks!

how did you come to this idea?

Thx for the hint, that helped me to finally come up with the solution :-) I think if I was somehow able to convince myself that greedy won't work I would change my approach but I don't know how to do that (how to write such proof).

But that's a really neat idea nonetheless. Kudos!!

no TLE!? I thought test cases were too big and discarded that kind of approaches:(

Idk, I looked through 6 cases just to be sure. It doesn't take much time tho. But you're kinda right

Since the sum of number and sum of digits is same. Let's say you change sum of digits on ith place by 1 then change in sum of numbers is 10^i. If you compensate this change in sum of digits at other place j then change would be -10^j. Net sum would be 0 iff i = j

For a general change in sum of digits you can view changes as numbers in base 10.

if sum of three didgits of the same rank >= 10, then the sum of digits of a, b, c > sum of digits of n, since n can contain only 8 digits

There is a bijection between the partitions of each digit of n into a sum of 3 numbers and the solution to the given problem. For Example n=26, the corresponding partitions are [[{0,1,1},{2,0,0}(and their permutations)],[{1,5,0},{2,3,1},{6,0,0},{2,4,0},{1,4,1},{2,2,2}(and their permutations)]]. Combining say {0,1,1} and {1,4,1} corresponds to a=01,b=14,c=11 and the tuple (01,14,11) for the solution.

Basically, the intuition is that we need a+b+c=n to hold in each decimal position as well for the digital sum property to hold. As a consequence, there must be no "carry-overs" while performing the addition a+b+c

The idea is basically from finding 2-majority element of a array without hashing,

I am basically first storing the count of each charater occurance in hash array.

After that, we lets define a process to reach minimum length which will be :-

(We will take the current majority character x in string and we will remove any pair x adjacent to non-x in string.)

if there is 2-majority element in array(if a element occured >= n/2 times), It will remain 2-majority after any no. of processes.

else if there is not any 2- mojority element in array. After some no. or processes, if string length is odd than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that. if string length is even than a element can reach maximum count of n + 1/2 elements and will remain 2-majority after that.

So, execute the process we defined on string and you will reach the answer after some analysis.(the solution I mentioned may seem tough to understand but it is simple when you will understand)

Thanks a lot! its a blunder

First assume that n is even. Then I claim that the answer is 0 if no character occurs more than n/2 times, and maxcnt-(n-maxcnt) = 2 * maxcnt — n otherwise where maxcnt is maximum number of occurrences of any character.

In the second case, we can see that the last remaining character is necessarily the one that occurs the most times, since it's impossible to remove all of them. (you can remove at most one per operation, and at most n/2 operations are performed so there's no way to remove all of them. The number of operations performed is bounded by the number of characters not equal to this most common character, which is n-maxcnt implying that at most 2*n-2*maxcnt characters can be removed. So the length is at least n-(2*n-2*maxcnt)=2*maxcnt — n. I claim that this can be achieved. Method: always try to remove exactly one non-most-common character per operation. This can always be done by choosing an occurrence of the most common character and one non-most-common character — it will always exist until all characters are made equal, at which point the length is 2*maxcnt-n.

We can show the first case by induction.

• Base case: n=2 then s1!=s2, then we can make the length 0.
• Inductive step: suppose it's true for n-2, now prove for n: we claim it is possible to remove characters so that no character occurs more than (n-2)/2 times in the remaining string. Take the most common character and remove it with any other character. In this way we can see that the condition is satisfied with the remaining string and we can continue until the string is empty.

When n is odd, the reasoning is similar, but since the parity of the length is constant, replace "0" by "1" in the above.

You can always remove a pair which contains the most frequent letter, as long as all the letters are not the same...

Delta is a word used in physics to describe small changes. In CP it is used to describe rating changes. Delta +105 therefore means your rating increased by 105

use This extension

thanks!

We iterate over all the nodes. If $$$vis_{i}$$$ is true, we already processed the component containing node $$$i$$$. The first dfs call flips all the necessary nodes from the bottom of the tree upwards, and also finds the extra edge. Before the second call, we use the extra edge, flipping the two lights associated with it, then run dfs again to see if using the extra edge requires less flips.