Fixed, thank you

I think I am,too.

me too

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.net/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.net/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

Odd, stable worked just fine for me

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.net/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.

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.

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

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.

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

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

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

no

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

if x is 0 you need to make it equal to k

I don't know where the mistake really is, but I found some hack cases.

In:

4
0 1 0 1

Out:

3 (should be 2)

In:

6
0 1 0 1 0 1

Out:

4 (should be 3)

The hack cases also works with n=8,10...

1
7 2
0010101
1 1
2 7

This test case gives different outputs for your submissions. Notice how 2 7 still gives you a different sort, but the indices are both outside of the first 1 and last 0, which are 3 and 6

When you are posting such a long piece of code, you need Spoiler and Block, which you can easily find up the textbox where you write your comments. It looks like:

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 2e5 + 10;

int pre0[MAXN];
int next1[MAXN];
int cnt[MAXN];

struct ans {
  int x, y;
};

bool operator<(ans a, ans b) { 
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}

void solve() {
  int n, m;
  cin >> n >> m;
  string a;
  cin >> a;
  int pre = -1;
  for (int i = 0; i < n; i++) {
    if (a[i] == '0') pre = i;
    pre0[i] = pre;
  }
  int next = n;
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] == '1') next = i;
    next1[i] = next;
  }
  set<ans> st;
  int x, y;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    if (x > y) swap(x, y);
    if (next1[x - 1] < pre0[y - 1])
      st.insert({next1[x - 1], pre0[y - 1]});
    else
      st.insert({0, 0});
  }
  cout << st.size() << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr),cout.tie(nullptr);
  int n;
  cin >> n;
  while (n--) {
    solve();
  }
  return 0;
}

this is my solution for problem C btw.
In my opinion, you may fix your formatting first, otherwise it will be difficult for anyone to understand your code. Hope this helps.

Look at this comment.

so long :<

Spoiler: You can solve it using diramida to find first / last element which is more/less then x. Another spoiler: iterate the minimum from 1 to n

First , for each element you can find the right most position that is more than a[i] using stack;(and find the right most position that is less than a[i]) Now lets define dp[l] = is position of max more than position of min in [l,r] for a fixed r: Now lets check how does dp[i] change after we increase r by 1; for all i such that a[r] is max in [i,r] , dp[i] will be changed to 1 , and in the same way for all i such that a[r] is min in [i,r] , dp[i] will be changed to 0;and the other dps will remain the same(because a[r] is not the max nor the min of that array so it will not affect dps condition); So sum of dp[i] for a fixed r will be the number of segments that we should count that the segment ends at r So for solving this problem we can increase r 1 by 1 and update dps using sum data structures like segment tree and we can solve this problem in O(n*log(n));

Imagine two stacks: one for increasing elements, the other for decreasing elements. If you draw it, you get a diagram of points consisting of two lines (one for increasing, one for decreasing). Then, for each point in the decreasing line, connect it to the first point smaller or equal to itself. The answer for a single index $$$i$$$ is the sum of the lengths of such segments. In order to maintain it while going left-to-right, use two sets with two stacks.

Code: https://codeforces.net/contest/1849/submission/216019848.