As you wish

a ni pro

Yea I hate long statements usually problem setters try to make the problem in to a story and just extend it by 2 paragraphs which is annoying

Happy birthday, brother. I hope this round is memorable in your life.

Happy birthday!!!

Happy Birthday!!

Happy Birthday! The first time I became blue was on my Birthday — 23rd Sept. I hope You have an amazing contest today.

Happy Birthday!!!

Happy Birthday

Happy Birthday!

happy birthday :) Ramtin510

Inshaallah

Fixed, sorry for waiting!

Nice !!!

i guess because of too much traffic the site was not loading

Me too, Good luck to us ;)

Hoping to get nearby ratings

please don't refresh any more

panicking nothing else

How to solve it ?

yeah i stuck at this problem for entire contest :(

any idea for this problem?

If you're sure that your binsearch is correct, then probably you haven't looked through all cases on how 2 slices can be related to each other(I found 6 separate cases)

1 10 0 17 7 9 8 14 14 19 5 8 2 14 11 14 2 16 2 2 7 9

Doesn't work on your code

Solution for n is the product of no of solutions for each digit of n. (So you only need to solve from 0 to 9)

Yes

how did u find this, like how do u find the same problem in general?

This ARC B is much easier than current one because all numbers are distinct and also it is guaranteed that operation exist.

235953756 Can't find the bug for code in C :(

try to observe a pattern in the given test cases. There is simple formula hidden

me to just for a second.

Relax, I've solved the EFGA problems :)

don't worry, I took at least 15min to mind-solve it and even then it was just trying random approaches until I found one that worked (then I proved it, of course). And I'm a master...

nope ig , you are having delta +105

I could not think of E yet, still trying lol

can u pls explain ur solution, I am new to using hashing for strings in cp

Nice idea!

[x,y] means interval from (inclusive) x to (inclusive) y.

We have to jump into these intervals: [0,0] -> [1,5] -> [3,4] -> [5,6] -> [8,10] -> [0,1]

We can check if this works if we fix k=3:

[0,0] -> [-3,3] //we can jump anywhere here

[-3,3] & [1,5] = [1,3] //this is the overlap. We can be anywhere here

[1,3] -> [-2,6] //we can jump anywhere here

[-2,6] & [3,4] = [3,4] //we can be anywhere here

[3,4] -> [0,7] //we can jump anywhere here

[-0,7] & [8,10] = [ERROR] //we have no overlap and nowhere to jump. K=3 does not work!

Code:

bool good(int k, vector<pii> &segs){
    pair<int, int> current = make_pair(0,0);
    for (int i = 0; i < segs.size(); i++){
        current = make_pair(current.first-k, current.second+k); //we can jump anywhere here
        if(segs[i].first > current.second) return false; //no overlap
        if(segs[i].second < current.first) return false; //no overlap
        current = make_pair(max(current.first, segs[i].first), min(current.second, segs[i].second)); //we can be anywhere here
    }
    
    return true;
}

Construct the graph $$$i \rightarrow A[i]$$$, this type of graph is well known (Functional Graph). An important property is that it consist of several cycles and nodes that following the directed edges reach some cycle. So obviously if there is a 1 on a leaf you have to change it and switch the next node. In the end you will only have cycles left, some nodes will have 0 others 1. If the number of 1's in a cycle is odd, then it's impossible. Otherwise let $$$A_1, A_2, \ldots , A_{2k}$$$ the nodes that have 1, then you have two ways to convert them to 0. Grouping $$$(A_1, A_2), (A_3, A_4), \ldots , (A_{2k-1}, A_{2k})$$$ or $$$(A_2, A_3), (A_4, A_5), \ldots, (A_{2k}, A_1)$$$. Choose the one that minimize the changes.

Another way of doing it is by considering an undirected graph with edges $$$i \leftrightarrow a_{i}$$$. Now solve for each connected component individually. Notice that each connected component is a tree with one extra edge because there are $$$m$$$ nodes and $$$m$$$ edges, where $$$m$$$ is the size of the component. Try both using the extra edge or ignoring it. Now the problem becomes turning off all the lights in the tree, which we can just do using dfs.

Submission

I found it on easier side than usual, no dynamic programming problem was there also generally there's a question of tree data structure which wasn't.

Question E is the simplest

I just saw that if we want to remove the letter with the highest count then pairing it with 2nd highest letter will be beneficial.... that's why I use set to maintain the order of letters on the basis of their count ... I pick the last and second last and delete them and the update them and reinsert it and this will cost log(n) and do this till the size of the set is greater then 1. we will do this for n/2 element so, TC will be nlogn. 235912384 there is math solution also but I come up with this one during contest

I have noticed that you can transform the string in a compression of it, example: "aaabbc" is converted to 3 2 1,then the new problem is given an array you can rest 1 to an adjacent pair of numbers any number of times and if a number become 0 remove it and refill the space and this new problem look easier for me to solve.

А possible logical chain:

1) In final string you can't make any operation, since it's the shortest possible achievable string.

2) => In final string $$$s_1 = s_2, s_2 = s_3, \ldots, s_{k-1} = s_k$$$. I.e all symbols are equal in final string.

3) Quite intuitive thing to do is try to bruteforce that "final symbol".

4) Then you can see than until there is at least two different letters and at least one "final symbol", than there is an adjacent pair of symbols, one of which is "final symbol" and one of which is not. It's like a simple application of that classic obvious lemma: if there is a binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10".

From now it's more or less obvious what's next to do (I believe)

Steps 1, 2, 3 seems very logical to me. Maybe step 4 can be seen like an "observation", but this "lemma" about "binary string with at least one "0" and at least one "1", than there is an substring "01" or substring "10"" is way too classical, and it is an easily recognizable pattern after you seen this some number of times. So it all comes down to "solve more problems to be able to quickly recognize such patterns", who could have guessed

FWIW, I'd like to point out that the DP approach for C does work, although it's not efficient (time complexity $$$O(n^3))$$$. But solving it using DP in $$$O(n^3)$$$ is still a good learning exercise, as you might find transitions difficult if you are accustomed to thinking about DP problems in a certain manner, owing to the fact that the neighbors are joined together after deletion of inner elements. I suggest people comfortable with DP to try this out.

For example, you might define $$$dp[i][j]$$$ as the minimum number of characters remaining at the end when we are only dealing with $$$str[i...j]$$$. Then, you might try collapsing the first pair, say starting at index $$$x$$$. However, there's no way to proceed now because $$$dp[i][x - 1]$$$ and $$$dp[x + 1][j]$$$ cannot be combined.

Submission