I Love short description :)

I'm just glad that there isn't any interactive problem.

as a human, i also love playing undertale

maybe the keyboards battery died after those lengthy problem statements so now we are left with this short description

Yeah higher the jump in between the problems higher is the difficulty change

1

hey can you give me tips how did you rise up so fast?

If you get a WA at B its over

As a tester, the contest is a friend.

which includes green stocks?
P.S: it is only a joke. I never bought any stocks.

the optimal indicies for the first operation are 1, 4, 10, 22, ....

a bit constructive first paint the cell 1 then check how much i can cover by painting ith cell that will satisfy l=1,r= ith cell ,then (i-1+1)/2

a pattern like 2*(curr+1) will be formed please write it on pen paper you will surely get it

my code : https://mirror.codeforces.com/contest/2040/submission/295579978

Authors: solve the same problem for multiple testcases. lol

Keep track of a value you will assign to the nodes, starting at 1. DFS and use precalculated sieve to determine when a parent-child value difference is prime, in which case increment the value by 1 until it is no longer prime. The number of increases is upper bounded by about n/2, which ensures the value never exceeds 2n.

Just fill everything in dfs with odd numbers starting from 1. When you fill children of some node u, skip odd number x + 2, where x is the parent's odd number. In the end you'll have at most one unfilled node, so just fill it with even number x + 1, where x is the parent's number. It works because the difference of two non-adjacent odd numbers is an even number greater than 2.

Another solution: solve in dfs order for subtrees first, then when combining add 1 to the whole first subtree and starting from the second subtree add double the size of all previously considered subtrees plus 2 to the whole now considered subtree. After the first dfs, the final answer will be obtained by going to the leaves from the root and adding all calculated values plus 1.

that's the first thing to do for permutation problems

Can you explain further? Did you do this on pen and paper (seems like a daunting task), and if you did this via code — did you calculate S(P) for all of them manually?

what was the pattern I sill didn't get it?

I started by thinking of maximising sum of intervals of each length. Realised you can't really get better than, say, for n = 5, for intervals of length 2 you can get at best 1 + 2 + 3 + 4. Then for length 3 you can get at best 1 + 2 + 3. And so on. And eventually realised that every piece besides the biggest one has to have as neighbors both a bigger and a smaller than it (considering the edges of the permutation to be 0). So essentially this is like going through the numbers in order and putting either smallest position still possible either biggest. So, like this, for example: n = 4

0  0
0 1    0
0 1   2 0
0 1   3 2 0
0 1 4 3 2 0 (this last one will always be the same, whether you try putting it on the left or right)

This can also be written then as either putting left or right. So for the given example it's L R R (you put 1 to the left, 2 and 3 to the right, 4 in what remains). And then finally when I started listing how all combinations of L and R would look I realised that this if you put the combinations in order, their results will literally be in the same order lexicographically, too (if you consider R bigger than L).

Same. I lost track with pen and paper at $$$n = 5$$$ so I just coded up a brute force construction method and then it's pattern seeking from there.

Lmao

As a pupil, I did solve C

Nah, it's just a find-a-pattern problem, not much knowledge is required to solve it.

Do a brute force to find the optimal value sum first and then see all the permutations that give the result for some small $$$n$$$ like $$$7$$$. Try to see the pattern.

I liked C but it might have been harder or just as hard as D, which is not very cool. Also someone said they found it somewhere on codeforces, so, it shouldn't have been in the contest.

same, couldnt figure out how to do it without computing 2^n

same bro despite of finding the pattern it is difficult to implement it Does anyone knows how to solve such type of problems please explain , it is much needed ?? Please

same :(

That would be quite weird to try to implement, so instead of using 4 as the smallest non-prime, use 1 and see where that gets you. That's how I did it.

tried implementing the same

The one that is closed on top ($$$\lceil x \rceil$$$) is ceil, the one with the closing under it ($$$\lfloor x \rfloor$$$) is floor.

$$$ceil(x) = \lceil{x}\rceil$$$

$$$floor(x) = \lfloor{x}\rfloor$$$

$$$round(x) = \lfloor{x}\rceil$$$

how did u assigned nodes

really thought so

i found it easier to solve, but much much harder to prove

can u tell why am i getting tle?

d

i found E < C < D

more like get the k-th unimodal permutation competitive googling