I Love short description :)

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

Hope for the best :o, :D , :)

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, ....

If the count of 1 in an array of length n is >= n / 2, then it can be made an array consisting of all ones using second operation. Now, to perform second operation, the endpoints of the subarray must be equal to 1. Hence, we can start constructing the answer from the smallest most optimal subarray, which is 1 0 0 1. Now, after applying second operation, it would become 1 1 1 1. Again, to fill next 0's, we can add another 1 after (k + 1) zeroes where k is the current subarray length which is all 1. The array will become 1 1 1 1 0 0 0 0 0 1, notice that count of 1 is still >= n / 2. This way, you can bruteforce your answer for any n.

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

This explains so many submissions on C, despite its difficulty being near 1800.

How did you find this problem?

Oh no, its the exact same task !! Authors please be careful from next time bcz many people might have known this so its a bit unfair for us.

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.

stfu

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

I couldnt implement C for 1 hour I feel like I am stupid.

It is cool but it appeared before.

pretty sure your code is copy pasted. A lot of newbies and pupils have the exact same code as you. Its an already existing question.

F is combinatorics, not constructive

Actually one of your homies loves constructive problems

haha loved that!

But can it be hacked?

Did you prove that there are no impossible inputs?

That's quite common as to not spoil the solution. Alternatively you have to guarantee that solution always exists, but that is not always obvious.

You did the same mistake to me at my first submission,notice that shift=n-2 and R-L+1=n,this mean your shift you decrease n-1 times when L==R,in other word when L==R,your shift will decrease n-1 times,initially shift=n-2 and n-2-(n-1)=n-2-n+1=-1,you right shift (k-1) by -1 ((k-1)>>-1) will happen unexpected operation

I totally agree with you. What are the testers doing? If it's a problem from another country's website then I can understand why they accidentally made the same problem. But another exact same problem from codeforces????? Insane. It is really unfair for ppl who didnt try this problem like me.

lmao auto and consts to try to avoid plagiarism

lol

You can think like this,initially we have no 1 in our array,if n=1,then we just need to add 1 to the array,and if n=2,also do the same thing add more 1 to the array then answer=2,but think about does n=3 we need to add 1 more? the answer is no,why?For example,you can add 1 in your second times like this ,[1,0,1,0,...0],the sum of interval [1,3] is 2 and the length of interval is (3-1)+1=3,ceil(3/2)=2,so for n=3,answer=2,and similary for n=4,answer=2,So according to this observation we need to make sure the 1 already been added into the array is completely use by us so for example if our array already become [1,1,1,1,1,0,0,0,.....0] assume that there is k times 1 in our array,then how much 1 i will get if i place my next 1 optimally?The answer is (k+1)*2,because you already have k times 1 and you add 1 more then you have k+1 times 1,and let s=(k+1)*2,obviously s/2=(k+1) which is satisfy the statement,so you can directly run a simulation to approach this and the time complextiy will be O(logn) and overall for all test case will be O(tlogn) which is under limit,below is my submission hope useful to you 295580740

at any vertex you have two choices(if the step is even)- either go down to one of the child vertex or go to the parent vertex... the probability of going to a parent vertex is 1/degree while going to a child node is (degree-1)/degree. let E denote the expected number of steps to reach parent vertex then E= 1/degree + ((degree-1)/degree)*(1/degree)+(((degree-1)/degree)^2)*(1/degree)+........ . Solving this you get the required value of 2*degree-1.

Yes, it was a typo, fixed now