solve A and B fast(miserable part is I saw 'how' in place of 'hope', then gave advice only to get downvotes lol)

get high rank, easy-peasy answer

i came down from 1321 to pick u up lets go to pupil together , ps: u wont believe me but rating graph wont lie

Why there is a huuuge phase of solution hacks for 12 hrs and after 3 hrs from its finish STILL no rating changes published? I'm not sure the whole process of calcing rating changes takes more than 3 hrs itself.

edit: 7 HOURS already passed from solution hacks phase finish and still nothing... why do we have to wait soo long

You'd have got upvotes if you weren't gray. :')

Yup,aiming for pupil rn but it might take a while.

I think that's only because educational round is extend-ICPC rule, which means it will have a 12 hours open hack.

This is a very regular thing in Codeforces. Means Codeforces have a daily maintain on its datebase.

++

++

You Will or You HOPE ?

me too)))))

it's almost it :d

I personally think the post should be upvoted/downvoted after the contest has ended depending on the quality of problems and/or any issues faced...

get hacked

Perform better than you did earlier.

Reverse psychology doesn't always work, you learnt it the hard way

ig, its the story of every contest nowadays

can u explain the problem to me...if all subarray is good for tst cs 1 then ans should 4C1+4C2+4C3+4C4 =15

that's not correct way of calculating total number of subarrays

total number of subarrays of a specific length let say k = n-k+1; for example subarrays of length 1 = n-1+1 = n; subarrays of length 2 = n-2+1=n-1; this way subarrays are calculated

This is so gay lol

at least you solved it

How you solved C?

how to calculate if the length is valid using masks only? my solution tle as I use the index & the masks which will of course tle :) (mle before tle) :D https://codeforces.net/contest/1550/submission/122504948

My idea for E, Firstly binary search the answer. Precalculate each mask having 1 bit,2 bit, 3 bit,4 bit set separately.

For each index precalculate up to how much it can be extended to the left for each alphabet. Now suppose we want to check whether $$$len$$$ is possible. We will find the answer for each mask in increasing order of a number of bit set (which we have precalculated earlier). $$$dp[mask]$$$ will store the lowest index from the left where all the set bit of this mask has a length of $$$len$$$. Now if we have mask where $$$kth$$$ bit is set, we want the $$$kth$$$ alphabet to be the last alphabet to have a contagious length $$$len$$$. we already know dp[mask^k] ,

if this is possible we can find the first index after dp[mask^k] where $$$len$$$ of alphabet $$$k$$$ is possible, this can be easily found using lower_bound with some precomputation of each alphabet, in this way $$$dp[mask]$$$ will be the minimum answer of all the bit set in mask. And finally if $$$dp[(1«k)-1]$$$ has a index then it is possible otherwise not. My complexity is $$$O(k*(2^{k})*log(n)*log(n))$$$ but passes in 1107 ms.

why ??

When you realised C was just about one DAMN observation — that you need to check only subarrays of size 3 and 4.

What if someone didn't make this particular observation and just implemented checking subarrays of size 3, 4, 5, 6, 7, 8 and so on in the most straightforward fashion? Their solution would always bail out on subarray of size 5 anyway (so sizes of 6, 7, 8 won't be tested) and thus avoid TLE. Submission 122458692 is a very good example of this.

When trying to hack various accepted solutions for problem C, I noticed that the opportunities to TLE them are very much limited. Moral of this story: don't give up even if you missed an important observation. Your "silly" bruteforce solution with multiple nested loops may actually have $$$O(N)$$$ time complexity, just because the observation that you failed to notice still benefits you nevertheless.

In your solution 122498108 can you explain why you only need R = 1 and not any larger value of R? I can see that for all examples of using those edges one can connect the whole graph but I can't find a proof or good explanation as to why. Thank you.

The solution for A can actually be calculated using arithmetic sequence and is simply

ans = sqrt(s-1)+1

I believe, that greedy works correctly, like dp. At least, my solution for A is greedy. You can check it 122453650

Main fact that i used for promlem C is that good array cant be larger than 4. So you can calc good subarrays of length 1,2,3,4 in O(N)

Well there are multiple steps, but the first crucial observation you have to make is that the final array will be in a form of a_i = i+k or i-k (k is a constant positive integer). So you have to figure out a way to loop through the possible k values. The next step is that you realize for most k, the number of ways of arranging an excellent array will be simply nC(n/2) for even numbers and for odd numbers, if we let x = (n+1)/2, and y = n — (n+1)/2, then it will nCx+nCy. So if you somehow reduce the range of k you have to calculate, then you can simply naively loop through the rest of the range, which will result in O(n) solution.

the hint of problem b is an observation about how the values a and b affect the final answer. Can we say that no matter how we slice the contribution of a in the answer will be same. Now try to think how the value of b affects the answer and what happens when it goes negative.

I think it's $$$\lceil \sqrt{N} \rceil$$$ as Dilworth's theorem gives a lower bound, and it can be easily constructed by grouping elements in an interval of $$$[i\sqrt{N},(i+1)\sqrt{N})$$$ in increasing order and then sort the groups in decreasing order.

If b>=0 , then just pick every element one at a time to maximize points.
Else if b<0 , then one-by-one pick continous substrings with ( value != starting value(str[0]) ) and then pick remaining substring in one move.
Reason for picking 2nd group for b<0 :- Because group of elements which is not equal to first element will always 1 less than or equal to other group. It can't be more than other group. So value of b which is (-)ive will be added less no. of times.
You can check this — 122468733

Check here

I have a solution for even numbers, so I didn't pass the tests, but I'm sure it's almost complete solution. Firstly notice that in order for the given formula to be correct, meaning $$$a_i + a_j = i + j$$$, integers $$$a_i$$$ and $$$a_j$$$ should be of form $$$i + k$$$ and $$$j - k$$$. So for example $$$a_5 + a_3 = 5 + 3$$$ holds for $$$a = 7$$$ and $$$b = 1$$$, which is the same as saying $$$a = 5 + 2$$$ and $$$b = 3 - 2$$$.

So we can notice that we can traverse every $$$i$$$ from 1 to infinity, but the constraints are a bit too large for this. However, we can also notice that we can add or subtract any number between 1 and $$$min(1 - l, r - n)$$$ to each of the numbers without leaving the bounds. We can clearly see that subtracting any of the value in these bounds won't exceed $$$l$$$ nor $$$r$$$.

So this means that there are exactly $$${{min(1 - l, r - n)}\choose{n/2}} + x$$$ ways where x represents the number of ways when we can't choose two options for every single integer. This however is easily solvable, because you can notice that if for some $$$p$$$, $$$a_k + p > r$$$, then we can guarantee that $$$a_k + (p + 1) > r$$$ and $$$a_k - 1 + (p + 1) > r$$$, meaning $$$a_{k-1} + (p + 1) > r$$$. Similar statement holds for $$$q$$$ for which $$$a_k - q < l$$$. So just find the border value between these two cases (select all and select only some). Once you find the edge value it's easy to notice that you can bruteforce every value $$$\geq p$$$ as there are at most $$$n$$$ such values. Hope this helps.

The problem I encountered is bruteforcing for odd $$$n$$$, so this solution fails on the last and first number of first test, but solves the second and third. I'd appreciate if somebody provides a workaround for this. Thanks.

EDIT: I see I made a mistake which made the explanation sound poor.

Is the k static or can be changed for every query?

That is really not required for the problem. If you notice no subarray of size greater than equal to 5 can be good, as there will always be at least 3 non-decreasing or 3 non-increasing elements. Sadly I realized it so late that I couldn't implement it during the contest.

k-th smallest statistic?

test 1 5 1 -1 10101

Correct answer is 2, your code gives 3. It's better to remove the zeroes and then you are left with 111, so you only need to apply the operation 3 times.

9 1 9 6

one more, who found but couldn't implement.

you can solve it without observing that but it is hard to implement

my_submission