Probably both. It is really easy to detect — cheaters will often have something like if(n==123445): print([obviously wrong number])

because Vovuh loves us!

that means the testers will solve the problems of the round, and give feedback to authors if they found a bug or statement is unclear or something

It means that the 'Penalty' displayed in 'Standing' page is increased by 10.

Hint : With $$$x$$$ as your first number, you can construct array for all $$$n$$$ in range $$$(kx + k*(k - 1)/2, x(2^k - 1))$$$

In your code :- " auto bs =pam.lower_bound(n-a[i]); " It may point to pam.end();

Hacks in phase of hacks do not change anything

Yes, it is o(n*n).try a=200000*0 b=200000*199999 , will get a tle

case 1 and 2 are invalid input for C1 since there won't be duplicates

Case 1: Answer is 5. ( LLLLR ) or ( LLLLL )

Case 2: Answer is 5. ( RRRRL ) or ( RRRRR )

Case 3: Answer is 1. ( L ) or ( R )

The cases are valid for C1, because the first number is N, so there are no duplicates.

input 5 5 6 7 6 6 causes infinite loop, you don't handle well situation when A[left] = A[right]

Because in java String concatenation creates a new copy of the string so that the overall complexity is O(n^2). You should use StringBuffer and use append() method for the concatenation. It will work in O(K). K is the number of characters.

yep, vector erase() in O(n) and multiset erase in O(logn)!

erase in std::vector have the complexity linear to the size of the vector (it have to move the elements after the deleted element forward), while that in multiset is have the complexity log of the size of the vector.

Yes, multiset is implemented as a self-balancing binary tree, for which deletion is O(log n).

Vector deletion is O(n) in the worst case.

check this link

yes, I did the same but with using unordered map STL .

Here is my solution.

Hint:

4

4 1 2 3

See what your code does

This might be useful.

Take it for an example:

7

4 3 5 1 2 2 1

Instead of putting people of different heights randomly with keeping the difference between two adjacent heights one (e.g. 2 1 1 2 3), you can try to find a maximum height and a minimum height and form a cycle with other heights in between them. To do it, you have to find the longest possible contiguous non-decreasing sequence of numbers with difference between adjacent numbers 0 or 1 in the sorted array of heights. Notice that we need at least 2 elements of same value except for the maxima and minima in our output sequence, else we cant form the desired cycle.

For our example we go like this, if we take 1 as our minima and we can go upto 3 as our maxima. As we have only one 3 we can't accommodate 4 here. So we can form a sequence like this, 1 2 3 2 1. So we start from our minima, climb up to the maxima and again climb down to the minima. I hope you got the insight.

Try this case:

6

234567

1 1 4 4 6 7 8 1 1

Your code stops at the 3rd element (4), while it is more optimal to continue.

https://codeforces.me/blog/entry/20553 BTW someone just asked same question in this post

Thanks for your great idea!:)

Very nice! thank you

I had a different idea resulting in $$$O(nm)$$$ time complexity. But mine was very laborous to code. Submission: 53355339

Assume that the array is fixed. How do we check if it can be turned to only zeroes?

1. Either toggle the first row or not
2. Toggle every column with a one in the first row
3. Toggle every row with a one in the first column

Make an data structure that can maintain the state of this algorithm when we change bits in the original array, and make two instances of it, one with the first row flipped and one without. Then do the following:

1. check if either datastructure can be made all zeroes
2. If either could, output its current row- and column flips.
3. Otherwise, toggle the last bit that is not yet toggled in both. This essentially changes the solution we want to produce from all zeroes to zeroes in all but some suffix.
4. If there was no bit to toggle, output NO
5. Otherwise, update the two structures, and go back to step 1.

Why is this $$$O(nm)$$$?

When you toggle a bit that is not on the first row or on the first column, the structures do not need to be updated, so the change can be done in $$$O(1)$$$. There are $$$(n-1)(m-1)$$$ such bits.

When you toggle a bit that is on the first column but not on the first row, you have to toggle one row, which can be done in $$$O(m)$$$. There are $$$n$$$ such bits.

When you toggle a bit that is on the first row but not on the first column, you have to toggle one column, which can be done in $$$O(n)$$$. There are $$$m$$$ such bits.

When you toggle the bit both on the first row and column, you have to run the algorithm again in time $$$O(nm)$$$, but there is only one such bit.

So in total, we do $$$O(1) \cdot (n-1)(m-1) + O(m) \cdot n + O(n) \cdot m + O(nm) \cdot 1 = O(nm)$$$ work.

I will try to explain the idea of how i did.

Suppose an integer x can be used as a1.

Let the restritions:

1. sum of all ai for i from 1 to k should be n;
2. the condition ai<ai+1≤2*ai should be satisfied for each i from 1 to k−1.

The min possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by one.

The max possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by multiplying by 2.

Therefore, to respect the restriction 01, the inequality down needs to be true:

$$$x+(x+1)+(x+2)+(x+3)+ ... +(x+k-1) ≤ n ≤ x+x*2+x*2^{2}+x*2^{3}+ ... +x*2^{k-1}$$$

The left side is a sum of arithmetic progression and the right side is a sum of geometric progression, so:

$$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$

Thus, we can binary search the x:

• If $$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$, this x can be used;
• If $$$\dfrac{(x+x+k-1)*k}{2} > n $$$, we have to decrease x;
• If $$$ x*(2^{k}-1) < n$$$, we have to increase x.

After find a possible x to be a1, we can binary the others elements of array a at same way.

Complexity: O(k*log(N))

According to documentation: Complexity of std::multiset::lower_bound is: Logarithmic in the size of the container.
Complexity of std::lower_bound is: The number of comparisons performed is logarithmic in the distance between first and last (At most log_2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

std::multiset::iterator is a bidirectorial iterator, but it isn't random access, thus std::multiset::lower_bound will work faster ($$$O(log(N))$$$ vs $$$O(N)$$$). In general, if you have to choose between container's method and an algorithm from std, the first option is more preferable. (There are some exceptional cases, but they are not related to competitie programming)

you never initialized the vector cnts

you get n integers instead of 9 for the third line input in your solution.

6

5 6 3 4 2 1

you misunderstood the problem. take leftmost or rightmost elements and make a strictly increasing sequence with those.
5
4 2 3 1 5
the answer is 2
LR
take 4 (the leftmost elements) first and then 5 and make this sequence that is in increasing order{4,5}