Fixed.

its not just you buddy, these are just speed forces rounds lately. People solve till ABC and There is huge difficulty gap in C and D. Good luck :D

ya dalala

i agree

poor how are you going to solve the problems of 1300 implementation((( i hope you wont die while you write 20 lines of code

Congrats ^_^

Of course, you will be rated after you participate in the competition

wish not granted

That's not a bug. It's feature.

+++1+++0---0

rly? I solved C in 15mins but 45 on D :) but maybe its just my skill in cp being poor ...

I solved B, D and E using DP :)

I didn't solve E, but I think it maybe smth like $$$dp[i][len][count]$$$, where $$$i$$$ is a length of prefix, $$$len$$$ is the maximum suffix, where all numbers are distinct and $$$count$$$ is the number of obtained correct sequences of length $$$k$$$. The number of states is not more than $$$N * K * N / K = N^2$$$, so it maybe correct if all transition is made no longer than $$$O(1)$$$. But unfortunately I got confused in the transitions :(.

You can make some prefix negative and rest all positive.

Same to me for problem C. Long way to go on the revenge journey.

I solved by finding, "in how many arrays does some subarray contribute?"

For this, I use a dp state where dp[i] gives number of arrays of length i, such that the subarray ending at the last index is used.

Now for calculating dp[i], we can first see that elements from i-k+1 to i should form a permutation of k, and for the rest, we can give any element from 1 to k. So we initially set dp[i] to be k! * exp(k,i-k).

Now we need to subtract those arrays from dp[i] which have their last used subarray ending at some index in the range [i-k+1, i), because it will intersect with our subarray ending at i. Suppose we have an array ending at j, which lies in [i-k+1, i). So number of arrays such that last used index is j, and [i-k+1,i] still forms a permutation is dp[j] * (i-j)!. We subtract this value from dp[i] for all j in [i-k+1, i).

Now our answer is the sum of contributions of all subarrays, so we can simply sum up dp[i] * exp(k,n-i), because for all elements after i, we can place anything we want.

Divide the array into two halves, make first half negative ascending and second half positive ascending. Pick the best answer among all possible half partitions (you can also make all positive and all negative).

If you only multiply by positive number then the answer would be number of elementsi such that a[i]>=a[i+1]. Instead what we can do is for some i turn the prefix before it to a negative increasing array. If the prefix contains k strictly decreasing segments then the number of operations needed to convert the whole prefix to an strictly increasing prefix such that all it's elements are negative is k. So we can just check it for each index i and calculate the minimum

You just need to maintain 3 variables: current_number_of_element, sorted_till(default = 0) and unsorted_from(default = inf) and do casework.

I created a tree and checked for validity using dfs.

I used a lazy segment tree for C

I kept track of L = current length of the array, A = the maximum possible number of sorted elements, B = minimum possible number of sorted elements. If B == L, then 0 is impossible. if A < L, 1 is impossible.

Let's make a stack which maintain values where 0=unsorted from here, 1=sorted until here, 2=unknown.
When processing query=='+', if stk.top()==0 then stk.push(0) (to propagate info) because array is unsorted obviously, else stk.push(2).
When processing query=='-', if stk.top()==1 then do{stk.pop();stk.top()=1;} (to propagate info) because array is sorted obviously, else just stk.pop().
my submission: 221294647

I used a stack: 221370839

Maintain a stack of states : 1 if sorted, 0 if not, -1 if both possible. When you add an element it's either 0 if the array is already not sorted, or -1 (since the last element can be decreasing too). For the queries : if last state is -1 and array is sorted erase all the minus ones and replace them with ones.

My 3 variable solution: 221315344

(same as described by adityagamer)

Pure implementation... Just playing around with booleans an conditions, but it's a bit complex

If a prefix of an array is not sorted, the arrays to which the prefix belongs is also not sorted. If array is sorted, all its prefixes are also sorted. Just simulate operations from left to right and keep track of the state of the prefix (whether it's sorted, not sorted, or no idea), if you find a contradiction, answer is no otherwise yes.

I fully agree, every edu looks like this for some reason.

can you explain your solution?

it can be solved without using any data structures

Your editorial for E is extremely hard to understand, please consider adding some explanations. Thanks.

Spoiler: ^this man solved one problem

+1

+1

btw, I upsolved problem D using DP. I noticed that most contestants solve it with some observations. If anyone's approach is similar to mine(not a good "observer" haha) and is stuck in WA, I hope my submission will help!

SleepingThread

I did, it got hacked for TLE here.

me

Can you explain your solution please?

Did you participate in this EDU? I couldn't find you in the standings.

Try this test:

1
+++1++--0

Since the beginning. It only doesn't give penalty if you fail test case 1 in order to avoid cases of "I accidentally submitted the wrong code". But if you fail test 3 and it's in the samples it's still going to give penalty.

What exactly do you mean by that?

1. Fast is subjective, fast for a Red coder is a smaller than fast for a specialist or a pupil.
2. Fast for a new joiner is bigger than fast for a veteran.

These two statements say 1. Don't compare yourself to others who have greater inherent skills than you, 2. You have to compare yourself to your past self.

My suggestions: 1. Watch this video: https://www.youtube.com/watch?v=tsNv9F3DGpQ. 2. Train your speed skills, maybe by making contests with x easy question for a duration of y minutes (Codeforces has this feature), and try to solve as much as you can during these contests. You then track your performance change (If any).

This what came to my mind.

Practice Cs, a and b will seem easier and you could get them faster.

List of numbers inserted in order: 1,2,4,3,5,6.

The first 4 elements are not sorted so the 0 and after inserting remaining 2 elements you remove the last 3 elements which leaves us with1,2,4 which is sorted so the 1.

It's possible to be like this:

1. ++++ -> 1231.
2. Not sorted
3. ++ -> 123111
4. --- -> 123
5. Sorted

1. arr = {1}
2. arr = {1, 2}
3. arr = {1, 2, 3}
4. arr = {1, 2, 3, 2}
5. arr = {1, 2, 3, 2} => 0
6. arr = {1, 2, 3, 2, 3}
7. arr = {1, 2, 3, 2, 3, 3}
8. arr = {1, 2, 3, 2, 3}
9. arr = {1, 2, 3, 2}
10. arr = {1, 2, 3}
11. arr = {1, 2, 3} => 1

Thanks everyone, I misunderstood that 0 is sorted in descending order :((

until the array size reach 4 you don't know weather it's sorted or not when the array size becomes 4 0 appears which means array is not sorted and it can be due to 4th element or any of the first 3 elements after that 2 elements added last 3 elements removed we are left with first elements and we don't know weather it's sorted or not so it can be sorted sorted and the sequence is correct for eg:- add 1, add 2, add 4, add 3 -> unsorted add 5, add 6, remove 6, remove 5, remove 3 array becomes 1, 2, 4 -> sorted

for each + sign append the following number

2,3,4,3

after this it is 0 so the array formed is unsorted again for each + append following number

2,3,4,3, 5,6

now remove three number from last as we have — then we get 2,3,4 after this it is 1 and also the array is sorted so it is true.

If for any index i we have A[i] == '0' and A[i+1] = '1' we can select that index to make the string 00...00 upto index i and 11...11 from index i+1 to n-1. So we try to find such index which can help us create such string and is possible for both the given strings.

same for me bro, I have -12 at C and I'm gonna lose my specialist :(

.

Could you explain the solution ?

you may try this testcase: 1 ++0++0++0--1 expected: NO your solution output : YES