gk orz

depends

ikr

Test case for BreakFree seems wrong. https://www.codechef.com/START93D/problems/REMOSET

number of palindromic numbers below 2e15 are 427

so precalculate all those number and iterate in array and see how we can form those numbers

Were you storing all the edges?

something like a multisource Dijkstra, idk what else to call it

BFS. Put every node x[i] in a p_queue acc to their d[i] and do bfs if d[i] become 1 for any node remove it from queue. Once your queue become empty check every node is visited or not

You take the initial k vertices put them into a heap kind of thing, sorted by their ranges, extract the vertex with the largest range, delete it from the heap, update the max range of every other vertex reachable from the extracted vertex, (val-1, if val is the range of the extracted vertex), also add into the heap new vertices which have not yet been deleted from the heap with their respective ranges, do it until the heap is not empty. Now, if every vertex has at least once been extracted, HURRAY!

sorry i am noob but why did you stop at 32823 but not continued from 32923 let suppose

Using DP.

Notice that the string can be split into maximal segments of consecutive characters. In each such segment, all characters must be equal to each other, but characters for all segments can be chosen independently of each other.

Now, consider some bracket sequence. Convert this into a sequence of integers: ( gets replaced by $$$1$$$, ) gets replaced by $$$-1$$$. Now, the bracket sequence is an RBS iff

• all prefix sums are non-negative, and
• the sum of all elements is zero.

Since all characters within a segment need to be equal, a segment of length $$$len$$$ will change the prefix sum by $$$+len$$$ or $$$-len$$$. $$$-len$$$ is not possible, if this would make the prefix sum negative.

Now, we create an array containing the lengths of all segmets of equal characters (in order). Now, we calculate all possible prefix sum values at the end of each segment using knapsack dp in $$$O(n\cdot \text{number of segments}) = O(n^2)$$$. If we can get a prefix sum equal to $$$0$$$ at the end, a solution exists. We can find this by doing backtracking on the dp array.

It is true that this contest was easier than some previous "Rated for All" Starters. But as mentioned here, we do expect it to be sometimes less challenging for the highest rated participants now. The range of "Rated for All" contests has increased, and so there will be some contests where IGMs solve all problems without too much sweat.

We just feel that there are enough users in the 7-star range as well, who find these challenging enough to have it be rated for all. For eg. in yesterday's contest, there were 25 7-star coders, and 8 of them solved all 7 problems. But 10 couldn't solve 1 problem and 7 couldn't AC 2 problems. Given that we definitely cannot have contests every month where the number of AKs is 1 or 2, we feel that having occasional easier Rated for All contests is a better compromise than having much fewer Rated for All contests.

Maybe from the next time, we'll also add something along the lines of "We expect it to challenge IGMs" or "We expect IGMs to AK the problem set" in the intro blog. Would that help?