Fixed, thank you

I think I am,too.

me too

good luck

What do u do bro? Ur 2nd id?

monster

The blog is not short anymore :D

It's just like a man Kneel in worship of someone

Why do you think it should be TLE? Is there any particular reason?

Because constraints are low

and speedforces

Solution

The main observation is that if $$$x<y<z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$. Proof: Define $$$f_i(n)$$$ to be the $$$i$$$-th bit of $$$n$$$. Let $$$i$$$ be the most significant bit of $$$x\oplus z$$$, then every bit higher than the $$$i$$$-th bit of $$$x,y,z$$$ must be equal, and $$$f_i(x)=0$$$, $$$f_i(z)=1$$$. If $$$f_i(y)=0$$$ then $$$x\oplus y<x\oplus z$$$, otherwise $$$y\oplus z<x\oplus z$$$.

Using this idea, we can prove that if $$$b_1<b_2<b_3<b_4<b_5$$$, then the edge between $$$b_1$$$ and $$$b_5$$$ are useless, because if we have this edge, we already have a triangle ($$$b_1,b_2,b_3$$$ or $$$b_3,b_4,b_5$$$). So there are only $$$O(n)$$$ useful edges.

I tried using a bit trie to do the binary search. Suppose you want >= m, then you can build the graph implicitly by doing the following bfs. You take a current node u, and then use your bittrie to take all values arr[x] such that arr[u]&arr[x] < m, then remove those x you used and add them to your queue. In this way you will prevent n^2 edges and get an implicit forest. Now that you have 2 different partitions, and check your check both of them to make sure their minxor >= m. At first, I tried using a bitTrie to do the checking as well but that TLEs, turns out the approach of sorting and checking adjacent elements as pointed out above will make it fast enough to pass. Also, I had to do alot of constant optimisation to make it work (recursive calls are too slow and pointer based bit trie is also too slow)

Submission: https://codeforces.com/contest/1849/submission/215997707

This is what I did.

First observation $$$x < y < z$$$, then $$$min(x\oplus y,y\oplus z)<x\oplus z$$$

Let's binary search on the maximum possible value.
So the problem reduces to checking whether a possible partition exists with the cost of both sets $$$\ge M$$$?

Iterate nos in sorted order. $$$dp[i][j]$$$ is true if it is possible to partition $$$a[1....i]$$$ (where $$$j<i$$$) such that the largest element in one set is at index $$$i$$$ and the largest element in other set is at index $$$j$$$, and false otherwise.

We can remove one dimension from this dp, letting $$$dp2[i]$$$ denote the smallest possible $$$j$$$, such that $$$dp[i][j]$$$ is true.

Once we know $$$dp2[i]$$$. $$$dp2[i+1]$$$ is either equal to $$$i$$$ or $$$dp2[i]$$$. So I first checked if it is possible to assign $$$dp2[i+1] = dp2[i]$$$, then I checked if $$$dp2[i+1]=i$$$, otherwise returned it is impossible to create such a partition.

The generalized version of this problem: https://codeforces.com/group/Uo1lq8ZyWf/contest/369641/problem/C

My solution does not construct a graph, but I guess it's one of the easiest for this problem.

Let's try to check if the 29-th bit is "on" in the answer. One can see that this can hold only if $$$n$$$ is not greater than 4. If $$$n$$$ is greater than 4, then it means that there're atleast 3 numbers whose 29-th bit is on/off, but number of groups is only 2 => their xor will be smaller than $$$2^{29}$$$.

If $$$n$$$ is not greater than 4, you can easily write a brute force and choose the best option. Otherwise, the answer is smaller than $$$2^{29}$$$. Let's notice that if 29-th bit is "on" in $$$x$$$ and isn't in $$$y$$$, then $$$x \oplus y$$$ is not smaller than $$$2^{29}$$$.

After this obsevation you can easily come up with the full solution: if $$$n$$$ is not greater than 4, then write a brute force. Otherwise, solve recursievly for number's whose (29, 28, 27..)-th bit is on/off.

void solve(vector<int> ord, int h) {
    int s = size(ord);
    if (s < 2) {
        return;
    }
    if (s <= 4) {
        // brute force
        return;
    }
    vector<int> nxt[2];
    for (int i : ord) {
        nxt[bool(a[i] & h)].push_back(i);
    }
    solve(nxt[0], h / 2), solve(nxt[1], h / 2);
}

solve({0, 1, ..., n - 1}, 1 << 29});

Had to wait a few minutes after each submission just to see WA on test 2.

Yeah. Submission

Just use two hashes. "If hash isn't working, it's because you haven't done enough of them"

I only now realized there is a 12 hour hacking phase. Well, feel free to hack this :(

just notice that if you have a pair {l,r}, this gives same as {l, r+1} if s[r+1] = 1, and this gives same as {l-1,r} if s[l-1] = 0.

so you just take each pair, remove all the extra ones on right side and zeros on left side and put in set, and output set.size(). you also have to add 1 if there is a pair that doesn't change s.

it is clear that this is sufficient, because if two pairs {l,r} are different after having removed the extra 1s and 0s, they will create different strings when sort.

you have to use a set.upper_bound or something to quickly remove extra 1s and zeros otherwise it will TLE because n*m = 10^11

See here for a relatively simple D&C solution. It can also be optimized to $$$O(n)$$$.

Agree. Had to optimize binary lifting up to linear memory

Can you write your approach also? That will be of great help.

Odd, stable worked just fine for me

How you stored suffix?

i guess u need rolling hash to counter MLE

Is my approach correct?

You should not insert the original string at the beginning. You can only count it if some copy is same as the original string after the sorting operation. Anyway, you are sorting the range for each copy and there could be 2*10^5 of them. So, in worst case the complexity would be O(n*m) ~ 10^10. That means, even if you fix the issue, you will likely get TLE.

https://www.youtube.com/watch?v=WbQDdWsK6UA

I too used DP. Here's my accepted solution : https://codeforces.com/contest/1849/submission/215947065

It's because you forgot to cache some of the states.

else{
  ll aa=sol(a,i+1,0,a[i]-1);
  ll bb=1+sol(a,i+1,1,a[i]-1);
  return dp[i][red][d] = min(aa,bb);
}

for me also

From last few contests I am getting stuck on A or B

https://www.youtube.com/watch?v=WbQDdWsK6UA

reduce everything to equal or less than k, then use sorting or heap.

Take a look at Ticket 17010 from CF Stress for a counter example.

Hashing

It was already explained by few folks in the comment section. However, I would like to share my approach. Let's say you have a range [l,r]. Let's consider a function S(l,r) which returns a string after sorting the range [l, r] on a copy of the original string s. S(l,r+1) = S(l, r) only if s[r+1] = 1. Similarly, S(l-1, r) = S(l, r) only if s[l-1] = 0. We can extend it further to S(l-a, r+b) = S(l, r) only if s[l-a...l-1] = 0 and s[r+1...r+b] = 1. Now, for each range, find the pair (a, b) where S(l, r) = S(l-a, r+b), a is minimised, and b is maximised. Then insert the pair into a set. The output would be the size of the set. However, you need to handle the cases where S(l,r) returns the original string. I guess if you understand the above approach, you would be able to figure that out easily.

C wasn't really greedy (it was precomputation using datastructures e.g. an array so that you could answer each query in O(1)). I don't see how C involved the use of a greedy idea. And D could have been solved using DP, although the greedy D solution is more intuitive.

IMO, A is just simple math. I don't see how it fits to be a Greedy problem.

I also wasted my entire contest on B revolving around customized sorting of priority queue and ending up in TLE.

It is not DP, it is purely Greedy.

First, we group all the continuous 1 and 2, and replace them with max.

For example, If the array is

[0, 1, 2, 1, 2, 1, 1, 1, 0, 1, 1, 1, 1]

We can replace it with

[0, 2, 0, 1]

It is purely Greedy now, we take a covered array. We spend a coin for 2, and mark its adjacent as covered, then we check for 1.

215975523

Basically dp[i] is the minimum cost to color the first i elements, with three cases:

• index i was colored by index i+1

• index i is able to color index i+1 (i.e. a[i] > 0)

• none of the above

Then you have to write 20 different transitions and hope that you haven't missed an edge case.

Check my code I think it really is clear

I agree.

The open hack phase does not give a rating, so its only kinda necessary to report him

Imagine we have to sort substring [L, R]. Let P be the length of longest prefix, consisting of 0, and S be the length of longest suffix, consisting of 1. Then, we actually have to sort only substring [L + P, R — S] (notice, if L + P > R — S, then substring is already sorted). In other words, L + P and R — S are the leftmost and the rightmost positions, which will have opposite bit after sorting. So, we have to count the number of distinct segments [L + P, R — S].

P.S. Sorry, if my English hurts you

If you like please upvote.

think about case where k = 1 and all health of monsters are 1e9, then it is O(n * logn * 1e9) that's pretty slow

array elements are upto 10^9 so if k = 1 then your solution takes upto n * 10^9 operations for single test, in other words TLE.

In case k = 1 and some a[i] = 1e9 then it's easy for your solution to get TLE.

Notice that you can subtract every a[i]the same multiple of k until one the a[i] reaches 0. Observe that the final array b where b[i] <= 0 for all i is given by b[i] = a[i]%k — bool(a[i]%k > 0)*k. By sorting b in decreasing fashion, you obtain the order of elimination (you can use a custom sort with a vector of pairs to keep track of the index).

Priority queue indeed works in $$$\mathcal{O} (\log n)$$$ per operation. But you are not doing $$$\mathcal{O}(n)$$$ operations because of this line: else pq.push({e-k,f});

Suppose all $$$a_i = 10^9$$$ and $$$k=1$$$.

No. If you use priority queue the complexity will be O(n * log(n) * 10^9) so it is too slow

You can think about getting remainder

same approach but my submission was accepted, i used heap in python

Small step k can brick your solution.

Found the problem, thank you for SpaceJellyfish hacking me. The problem lies in n, 1, n-1,2, n-2,3 Very smart

My approach:
Let's iterate through string S and remember indexes of 0's and 1's.
Now for every l and r binary search index of the first 1 and the last 0 in that range.
If the 0 index is lower than 1 index then there was no 'movement'.
Now insert pair {idx1, idx0} to the set.
The answer is set.size() + 1 if the string stayed the same.
Code

Here is my comment to similar question.

256127907 Can u please tell me what is wrong with this? It would be a great help!

i got it too, tho now i understood that suppose a[i] is of order 1e9 and k=1 (in simpler words a[i]>>k) , then to make a[i] to zero and then finally popping it out from priority queue will take time of a[i]-k which will be approx to 1e9 operations and yeah for popping and pushing consider logn as well so net complexity will be O(n*logn*(a[i]-k))

Can you explain your approach?

no