Positive contribution unlocks from...

It's impossible to have fun writing educational...

good luck

Try to find corner case like me, if you r confident that your approach is correct, otherwise try to change the idea.. :|

I have my tool to download statements and test cases (no auth involved, just fetch the pages) and it started failing today too. I think it's not auth related, maybe some URLs changed.

It is because cf api wasn’t working during contest

Note that any x[i] that is between min(a[]) and max(a[]) can be placed somewhere for free, since there exist two a[i],a[i+1] where that x[i] fits in between.

So we are left with some x[i] like 1...min(a[])-1, and max(a[])+1,...,x

The smaller ones (if some exist) can be placed in front of the first element, after the last element, or between the two elements with value min(a[]).

Same goes for the greater ones.

notice that you need to find only min max from given array
then you need to handle ranges 1..(min-1) and (max+1)..x
so you can put them in the beginning, in the end or between some a[i]-a[i] pair if a[i] lies between given 1..x range

lgbt person detected

My solution is clean :D

During the contest, I observed that inserting v to an array is free if min(array) <= v <= max(array), but I didn't realize that we can just consider inserting 1 and x. Instead, I considered inserting all numbers in [1, x] and ended up having so many corner cases (discussing the relation between [1, x] and [min(array), max(array)]).

Hint – you can just add 1 and x to the given array, not all of the numbers

My approach

Observation Define initial score is the score you get for not putting any number

1. For any 2 adjacent elements, putting any numbers that lies between them won't affect the initial score

2. Based on 1., we can put as many number as possible that we haven't put that still within the range between two elements

3. Now if we observe carefully, all numbers within the min element and max element of the array will be put accordingly. So we're only left with $$$1 .. min-1$$$ and $$$max+1 .. x$$$ (just need to take care when $$$x$$$ is smaller than $$$max$$$)

The rest is implementation

When you put $$$x$$$ between $$$a$$$ and $$$b$$$ (assume $$$x \gt a \gt b$$$), the difference turns into $$$(x-a) + (x-b)$$$ where it used to be $$$a-b$$$. So the difference delta is $$$delta=(x-a)+(x-b)-(a-b)=2(x-a)$$$. Since when you put $$$x$$$ $$$(x \gt max)$$$ between any two elements the delta can only be greater or equal than $$$2(x-max)$$$ and you can actually achieve that equal, it is the optimal solution. Then just simply consider the case that you don't put it between any two (meaning that you put it at the beginning or at the end).

no more than once:

I thought it was clear? Idk

Its clearly written in the second paragraph bro : " For the i-th point, it can be either xi−1, xi or xi+1"

You are not swapping the subtrees in the first one.

I did with some wiered two pointer like aproach.

Note that we can never buy more sugar than on first day. So create prefix sums of the sorted prices, and binary search the number of shops we can visit on day 0.

Then we can buy the same amount of sugar maybe for some more days. Calculate this number as $$$(x-sum)/cnt$$$

So after that number of days, x is not enough to buy that number of sugars any more. So decrement the number of sugar until x is enough to pay that new number of sugars. Then the same repeats... until number of sugars is zero.

Answer this question : At what days range we can buy $$$k$$$ number of items? (For each $$$1 \le k \le n$$$)

To answer that question, we can use binary search. We can buy $$$k$$$ candies at day $$$d$$$ if $$$(a_1 + ... + a_k) + k \times d \le x$$$ (in other words, our money csn buy $$$k$$$ number of items)

We can use greedy to prioritize the cheapest item first and use prefix sum to count $$$a_1 + .. + a_k$$$

Sort the array from cheapest to most expensive. Go from left to right through the array to calculate a prefix sum up to this point. Also store in another array how many days you would be able to buy the with current configuration $$$(x-sum[i])/cnt[i] + 1$$$. Then go backwards through the array $$$i=n\dots 1$$$: you buy all packs you haven't already bought with the previous configuration: $$$(cnt[i+1] - cnt[i]) * i$$$

154535703

Answer is 2^x, where x = number of nodes such that it's left and right subtrees aren't isomorphic.

Isomorphic means that you can get the subtrees equal by using some sequence of swaps.

Sort each subtree for each node according to the preorder string, starting from the leaves. Lexicographically smaller subtree to the left, greater to the right. Then count the amount $$$K$$$ of nodes for which both subtrees form different preorder strings. Answer is $$$2^K$$$

check on each node if the string of left children is same as right children. if not, multiply the result by 2. construct string of each node with s[node] + min(child string) + max(child string) to avoid duplication.

Do you have former experience in math contests? If not, then I think it is normal to not solve any questions for the first few times due to various reasons like competition anxiety and newness. If it happens repeatedly and you do not find joy in doing it then it's not for you. I am still finding out myself...

CP is hard to start with but once you will do some questions, you will learn how to think and it will be a lot more fun. Just do questions close to your difficulty level. Maybe these problems were hard for you. You can try some div3 problems.

my confident ass, trying to count the number of As and Bs to determine if the string would be unique or not only to get to know, in first test case, that it won't be enough they still can be unique.

You have to sort the array, and then for each i, calculate the maximum number of days you can buy only from the first i shops in the sorted array. This can be done in this way: (x — pre[i])/i, where pre is the prefix sum till i

"STEV" in your code is so cool, how can you make it?

You are using Array.sort, in Java it runs on Quick Sort whose worst case Time Complexity is O(n2)