Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// int tt = clock();
#endif
int T; cin >> T;
while(T--) {
int n, d;
cin >> n >> d;
int x, MAG = (int)sqrt(d) + 10;
for(x = 0; x < MAG; x++) {
if(x + (d + x) / (x + 1) <= n)
break;
}
cout << (x < MAG ? "YES" : "NO") << endl;
}
return 0;
}
```

1288B - Yet Another Meme Problem

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
a, b = map(int, input().split())
print(a * (len(str(b + 1)) - 1))
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
from math import factorial as fact
mod = 10**9 + 7
def C(n, k):
return fact(n) // (fact(k) * fact(n - k))
n, m = map(int, input().split())
print(C(n + 2*m - 1, 2*m) % mod)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int> > a;
int a1, a2;
bool can(int mid)
{
vector<int> msk(1 << m, -1);
for(int i = 0; i < n; i++)
{
int cur = 0;
for(int j = 0; j < m; j++)
if(a[i][j] >= mid)
cur ^= (1 << j);
msk[cur] = i;
}
if(msk[(1 << m) - 1] != -1)
{
a1 = a2 = msk[(1 << m) - 1];
return true;
}
for(int i = 0; i < (1 << m); i++)
for(int j = 0; j < (1 << m); j++)
if(msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1)
{
a1 = msk[i];
a2 = msk[j];
return true;
}
return false;
}
int main()
{
scanf("%d %d", &n, &m);
a.resize(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
int lf = 0;
int rg = int(1e9) + 43;
while(rg - lf > 1)
{
int m = (lf + rg) / 2;
if(can(m))
lf = m;
else
rg = m;
}
assert(can(lf));
printf("%d %d\n", a1 + 1, a2 + 1);
}
```

Idea: Ne0n25

**Tutorial**

Tutorial is loading...

**Solution 1 (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
const int N = 300 * 1000 + 13;
const int P = 550;
typedef pair<int, int> pt;
int n;
int a[N];
vector<int> pos[N];
pt ans[N];
int cnt[N];
int tot;
void add(int x){
++cnt[x];
if (cnt[x] == 1) ++tot;
}
void rem(int x){
if (cnt[x] == 1) --tot;
--cnt[x];
}
int f[N];
void upd(int x){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
++f[i];
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
forn(i, m){
pos[a[i]].push_back(i);
}
vector<pt> qr;
forn(i, n){
for (int j = 1; j < int(pos[i].size()); ++j)
qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
if (!pos[i].empty())
qr.push_back(make_pair(pos[i].back() + 1, m - 1));
}
sort(qr.begin(), qr.end(), [](const pt &a, const pt &b){
if (a.x / P != b.x / P)
return a.x < b.x;
if ((a.x / P) & 1)
return a.y < b.y;
return a.y > b.y;
});
forn(i, n) ans[i] = {i, i};
forn(i, m) ans[a[i]].x = 0;
int L = 0, R = -1;
forn(i, qr.size()){
int l = qr[i].x;
int r = qr[i].y;
if (r < l) continue;
int x = a[qr[i].x - 1];
while (L < l) rem(a[L++]);
while (L > l) add(a[--L]);
while (R > r) rem(a[R--]);
while (R < r) add(a[++R]);
ans[x].y = max(ans[x].y, tot);
}
forn(i, m){
if (i == pos[a[i]][0]){
ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
upd(a[i]);
}
}
forn(i, n) if (pos[i].empty()){
ans[i].y = max(ans[i].y, i + get(i));
}
forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
return 0;
}
```

**Solution 2 (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
const int N = 300 * 1000 + 13;
typedef pair<int, int> pt;
int n;
int a[N];
vector<int> pos[N];
pt ans[N];
int prv[N];
vector<int> t[4 * N];
void build(int v, int l, int r){
if (l == r - 1){
t[v].push_back(prv[l]);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v].resize(r - l);
merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), t[v].begin());
}
int get(int v, int l, int r, int L, int R, int val){
if (L >= R)
return 0;
if (l == L && r == R)
return lower_bound(t[v].begin(), t[v].end(), val) - t[v].begin();
int m = (l + r) / 2;
return get(v * 2, l, m, L, min(m, R), val) + get(v * 2 + 1, m, r, max(m, L), R, val);
}
int f[N];
void upd(int x){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
++f[i];
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
}
forn(i, m){
pos[a[i]].push_back(i);
}
vector<pt> qr;
forn(i, n){
for (int j = 1; j < int(pos[i].size()); ++j)
qr.push_back(make_pair(pos[i][j - 1] + 1, pos[i][j] - 1));
if (!pos[i].empty())
qr.push_back(make_pair(pos[i].back() + 1, m - 1));
}
forn(i, n) ans[i] = {i, i};
forn(i, m) ans[a[i]].x = 0;
forn(i, n){
int cur = -1;
for (auto it : pos[i]){
prv[it] = cur;
cur = it;
}
}
build(1, 0, m);
forn(i, qr.size()){
int l = qr[i].x;
int r = qr[i].y;
if (r < l) continue;
int x = a[qr[i].x - 1];
int cnt = get(1, 0, m, l, r + 1, l);
ans[x].y = max(ans[x].y, cnt);
}
forn(i, m){
if (i == pos[a[i]][0]){
ans[a[i]].y = max(ans[a[i]].y, a[i] + get(a[i]));
upd(a[i]);
}
}
forn(i, n) if (pos[i].empty()){
ans[i].y = max(ans[i].y, i + get(i));
}
forn(i, n) printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
return 0;
}
```

**Solution 3 (pikmike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 600 * 1000 + 13;
int f[N];
void upd(int x, int val){
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
f[i] += val;
}
int get(int x){
int res = 0;
for (int i = x; i < N; i |= i + 1)
res += f[i];
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> mn(n);
iota(mn.begin(), mn.end(), 0);
vector<int> mx = mn;
vector<int> a(m);
forn(i, m){
scanf("%d", &a[i]);
--a[i];
mn[a[i]] = 0;
}
vector<int> pos(n);
forn(i, n) pos[i] = n - i - 1;
forn(i, n) upd(i, 1);
forn(i, m){
mx[a[i]] = max(mx[a[i]], get(pos[a[i]] + 1));
upd(pos[a[i]], -1);
pos[a[i]] = i + n;
upd(pos[a[i]], 1);
}
forn(i, n){
mx[i] = max(mx[i], get(pos[i] + 1));
}
forn(i, n) printf("%d %d\n", mn[i] + 1, mx[i] + 1);
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 443;
int n1, n2, m, r, b;
string s1, s2;
int u[N];
int v[N];
struct edge
{
int y, c, f, cost;
edge() {};
edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};
int bal[N][N];
int s, t, oldS, oldT, V;
vector<int> g[N];
vector<edge> e;
void add(int x, int y, int c, int cost)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0, cost));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0, -cost));
}
int rem(int num)
{
return e[num].c - e[num].f;
}
void add_LR(int x, int y, int l, int r, int cost)
{
int c = r - l;
if(l > 0)
{
add(s, y, l, cost);
add(x, t, l, cost);
}
if(c > 0)
{
add(x, y, c, cost);
}
}
int p[N];
int d[N];
int pe[N];
int inq[N];
bool enlarge()
{
for(int i = 0; i < V; i++)
{
d[i] = int(1e9);
p[i] = -1;
pe[i] = -1;
inq[i] = 0;
}
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = 0;
for(auto z : g[k])
{
if(!rem(z)) continue;
if(d[e[z].y] > d[k] + e[z].cost)
{
p[e[z].y] = k;
pe[e[z].y] = z;
d[e[z].y] = d[k] + e[z].cost;
if(!inq[e[z].y])
{
q.push(e[z].y);
inq[e[z].y] = 1;
}
}
}
}
if(p[t] == -1)
return false;
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
return true;
}
void add_edge(int x, int y)
{
add(x, y + n1, 1, r);
add(y + n1, x, 1, b);
}
void impose_left(int x)
{
if(s1[x] == 'R')
{
add_LR(oldS, x, 1, m, 0);
}
else if(s1[x] == 'B')
{
add_LR(x, oldT, 1, m, 0);
}
else
{
add(oldS, x, m, 0);
add(x, oldT, m, 0);
}
}
void impose_right(int x)
{
if(s2[x] == 'R')
{
add_LR(x + n1, oldT, 1, m, 0);
}
else if(s2[x] == 'B')
{
add_LR(oldS, x + n1, 1, m, 0);
}
else
{
add(oldS, x + n1, m, 0);
add(x + n1, oldT, m, 0);
}
}
void construct_bal()
{
for(int i = 0; i < n1; i++)
{
for(auto z : g[i])
{
if(e[z].y >= n1 && e[z].y < n1 + n2)
bal[i][e[z].y - n1] += e[z].f;
}
}
}
void find_ans()
{
int res = 0;
string w = "";
for(auto x : g[s])
if(rem(x))
{
cout << -1 << endl;
return;
}
for(int i = 0; i < m; i++)
{
if(bal[u[i]][v[i]] > 0)
{
bal[u[i]][v[i]]--;
res += r;
w += "R";
}
else if(bal[u[i]][v[i]] < 0)
{
bal[u[i]][v[i]]++;
res += b;
w += "B";
}
else w += "U";
}
cout << res << endl << w << endl;
}
int main()
{
cin >> n1 >> n2 >> m >> r >> b;
cin >> s1;
cin >> s2;
for(int i = 0; i < m; i++)
{
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
}
oldS = n1 + n2;
oldT = oldS + 1;
s = oldT + 1;
t = s + 1;
V = t + 1;
for(int i = 0; i < n1; i++)
impose_left(i);
for(int i = 0; i < n2; i++)
impose_right(i);
for(int i = 0; i < m; i++)
add_edge(u[i], v[i]);
add(oldT, oldS, 100000, 0);
while(enlarge());
construct_bal();
find_ans();
}
```

Thanks for the nice editorial.

And , Actually am not able to understand how combinatorics is right to use and how it is applied for the Problem C . And also some have solved it using dp , i dont understand that approach either

So, can anyone please help me with my above stated problem.

Thanks in advance

combinatorics — if you have n identical object and r different object number of ways of arrangement is (n+r-1) C r-1 or n+r-1 C n

now in these question n=2*m and r=n and now total number of distribution is (n+2m-1)c(2m) and each distribution can be arranged in ascending order in one way (assuming all boxes identical for one movement and then which ever combination is there u have one way of arrange them in ascending order)

In your first two lines, for how many places you are arranging n identical objects and r distinct objects??

For combinatorics solution of C, we need to find number of non decreasing sequences of length $$$2m$$$ with values between $$$1$$$ and $$$n$$$.

We can convert this problem as follows ( since we want non decreasing values ).

Let $$$x_{i}$$$ denote number of times we take value $$$i$$$ in our sequence. Clearly $$$x_{i} >= 0$$$. Also,

$$$ x_1 + x_2 + x_3 + ... + x_{n-1} + x_{n} = 2m $$$.

The number of solutions to this is given by, $$$ \binom{n+2m-1}{n-1} = \dfrac{(n+2m-1)!}{(n-1)!(2m)!}$$$. You can read more about Stars and Bars.

Those who haven't understood after reading Stars and Bars what should they consider star and what should they consider bar they can just assume all the position of an array as balls (so we got 2*m ball, right? ) and list all the numbers from 1 to n (inclusive) and think every number as container or a box.

So when you are putting a ball in a box the ball will automatically get the number of the box on it. And you can put as many ball as you want in a box.

so every time we will use all balls and will get different combination from it. And obviously there will be a single permutation for a combination for which after collecting all the balls from the containers(or box!) we can sort them in non-descending order according to their number. :D

Pretty easy, huh? :3

problem i am facing is there might be two sequence whose sorted arrangement produce same result so how can we consider both the sequence as both are same only because we are interested in final sorted sequence. it would be very helpful if someone can explain me this

how can we directly use

x1+x2+x3+...+x(n−1)+xn=2mor Stars and bars Theorem here ? isnt there is a condition that the array must be non decreasing sequences ?The question given in $$$C$$$ is equivalent to "choosing non decreasing sequence of length $$$2m$$$ with values between $$$1$$$ and $$$n$$$".

Proof: If we obtain two sequences, $$$a,b$$$ that satisfy conditions given in question $$$C$$$, then we have $$$a_1 <= a_2 <= .... <= a_{m-1} <= a_{m} <= b_{m} <= b_{m-1} <= .... <= b_2 <= b_1$$$.

Conversely, if we have a sequence of $$$2m$$$ elements, $$$s_1 <= s_2 <= .... <= s_{2m-1} <= s_{2m}$$$, then we can make arrays $$$a,b$$$ as $$$a=(s_1, s_2, ..., s_{m})$$$ and $$$b=(s_{m+1}, s_{m+2}, ..., s_{2m-1}, s_{2m})$$$.

Yeah i understand that but my question was as my array must be non decreasing sequences how can i directly use Stars and bars theorm ? isnt that theorm is just randomly choosing repetedly element ?

Oh. Choosing a non decreasing sequence of length $$$L$$$ with elements taking $$$D$$$ distinct values can be modeled as follows.

Sort the $$$D$$$ distinct values. Number them from $$$1$$$ to $$$D$$$. Let $$$x_i$$$ denote number of occurrences of $$$ith$$$ element that we take in the sequence. Then we need $$$x_i >= 0$$$, and

$$$ x_1 + x_2 + .... + x_{D-1} + x_{D} = L $$$

Think of it like this, there are $$$L$$$ blank balls in a row, and you need to make $$$D-1$$$ vertical separators between them, and then in $$$ith$$$ segment write value of $$$ith$$$ number on all the balls, this gives a sequence that we require. Two separators can coincide too, so that means we don't take some element at all.

got it..thank you very much

awesome explaination

.

I can explain my approach, which involves combinatorics, hope you will find it helpful. In the problem it is stated that the first array is non decreasing, while second array is non increasing, so, for the first array, if you set any element at the rightmost index, then every element left of it will be less than or equal to that element. Similarly, in the case of second array, if you set any element at the rightmost index, every element left of it will be greater than equal to the rightmost one. Now, suppose

iis the rightmost element of first array, andjis the rightmost element of second array, we can set all values from 1 to n in this manner`for i=1 to n do:`

`for j=i to n do:`

Now, whatever will be the value of

i, all values left of it will be less than or equal to it so, we need to select the values from 1 to i, and after selecting them, put the in non decreasing order, so, you can imagine that as solving equation: x1 + x2 + ... + xi = m-1 for non negative integers.Same goes for

j, we need to solve for non negative integers, the equation xj + ... + xn = m-1. You can solve this using multinomial theorem, and will get the desired result.why you put x1 + x2 + ... + xi = m-1 ?? i think number of elements is m-1 not the sum of elements is m-1.

Because the values would be less than equal to i. Suppose i is 2 and m is 3, we can have the following combinations: 1 1 ( x1 = 2, x2 = 0) 1 2 ( x1 = 1, x2 = 1) 2 2 ( x1 = 0, x2 = 2)

Have a look here for Combination with Repitition: https://sites.math.northwestern.edu/~mlerma/courses/cs310-05s/notes/dm-gcomb.

Consider the non-descending sequence given in the editorial. It's a sequence of $$$2m$$$ elements, all between $$$1$$$ and $$$n$$$. The number of ways of building a sequence like that is the answer for our problem. We just need to figure a way of calculating it. So, basically, picking $$$r$$$ elements from a set of $$$n$$$ elements (with replacement, because we can select the same number more than once).

Imagine that, since you are replacing elements, you are "adding" new ones to the set. Each of the $$$r$$$ elements we pick is replaced, except for the last one. In total, $$$r - 1$$$ replacements. The formula is $$${n + r - 1 \choose r}$$$. In this case, $$$r = 2m$$$ (amount of elements to pick). Finally, $$${n + 2m - 1 \choose 2m}$$$.

Your approach of thinking for this problem of combination with replacement seems interesting. However I dont fully understand why that works. Or you can say I'm not able to get this intuition. Can you explain more?

I only know how to understand this using the stars and bars method.

The problems are equivalent! I picked $$$2m$$$ elements from a set of $$$n$$$, with repetitions, right? That's because I considered the sequence of length $$$2m$$$. What if I only considered the amount of times I picked an element, i.e their frequency?

Let's call $$$freq_i$$$ the amount of times I picked the $$$i$$$-th element. It's easy to see that $$$freq_1 + freq_2 + ... + freq_n = 2m$$$. Because $$$2m$$$ is the length of the first sequence.

Now, the question is: how many solutions does this equation have? Any solution can be arranged into two arrays that satisfy the original problem statement. The stars and bars problem will give us the answer: amount of ways to distribute $$$r$$$ identical objects among $$$n$$$ distinct containers. Here, $$$r = 2m$$$. Finally, the formula is (still) $$$n + 2m - 1 \choose{2m}$$$!

Take a look at this comment. The link he posted shows some other problems that are equivalent to stars and bars.

Thank you for the reply.

I am sorry I should have asked my question properly. I already understand how the stars and bars problem relates to solving the problem of combination with replacement.

What I am interested in understand is how you used the intuition of "adding new elements to the set" to consider replacement. i.e. your lines --

Imagine that, since you are replacing elements, you are "adding" new ones to the set. Each of the r elements we pick is replaced, except for the last one. In total, r-1 replacements.So how does this "adding to the set" thing works to fulfil the replacement issue?

This is just a trick to easily remember the formula. It isn't necessarily right. You can find more explanation here.

I can't understand the number n + 2m — 1, and I don't know r — 1 replacement.why except for the last one? why we can see selection as replacement? Can you explain more clear?Thank you very much.I see it so long but I can't understand.

The number of ways to pick $$$2m$$$ elements from a set on $$$n$$$ elements

with repetitions(also called replacement) is given by the closed formula I mentioned above. I recommend that you take a look in this Wikipedia page.Just explaining my view of it: Replacing an element is adding a new one to the set. We will replace every element we pick, with exception of the last one, because we will have finished the process then. This gives us $$$n + r - 1$$$ choose $$$r$$$. Substitute $$$r$$$ for $$$2m$$$ and you get the formula.

DP Approach:

Consider

2mplaces to be filled by numbers of range1tonand suppose we are at indexiand value at(i+1)thindex isxso the max value of all the indices less than/equal toiwill bex.Now, we have two cases

1) Assign value of

xtoith index and find answer fori-1places for values in range (1,x).2) Find answer for

iplaces for values in range (1,x-1).Base cases:

1) when

number of placesleft is1answer will ben(fill it with values from 1 to n).2) when

max value can be 1answer will be1(fill all places with 1).Recurrence relation num(x,m) = num(x,m-1) + num(x-1,m)Can you ai<=bi;

When we are reducing number of choices from x to x-1 we are eliminating the highest number thus filling remaining positions with smaller numbers.

Because the question is equivalent to finding a non-decreasing sequence of length 2m where each value lies in [1, n]. So, instead of thinking in terms of two arrays A and B, we now only think in term of a single array and this single array has to satisfy two conditions. i.e. it should be of length 2m and has every value in the range [1, n].

You can understand it in this way :- As the sequence is non decreasing we can say that sequence will be like there will be some 1's (greater than or equal to zero) then some 2's then 3's and so on.. upto n. So now we have to divide the whole sequence into n parts where size of each part can be greater than or equal to 1.Suppose parts are saparated by lines then there will be n-1 lines hence now we simply have to select n-1 positions from 2*m+n-1 places which is C(n+2*m-1,n-1).

Sorry for bad english.

I think i have a better solution for A

If not, please let me know

https://pastebin.com/SjQMG52P

How about this one ?

can you explain the approach behind it?

So nice solution. And here is the explanation.

How do you get rid of the ceil function?

`x + ceil(d/(x+1))`

can also be written as`ceil(x + (d/(x+1)))`

. For`ceil(x + (d/(x+1))) <=n`

,`x + (d/(x+1)) <=n`

holds.Very Nice solution.

I think it doesn't matter if it's ceil or floor as long as there's a solution for x. If there's a solution for x, both ceil and floor will work for this problem.

thanks

Persistent segtree in E is mle.

Unfortunate

I managed to fit persistent segment tree (PST) in ML

In my solution there are at most 6*10^5 update queries to PST. Moreover, every query creates O(log) new vertexes and one vertex need 3 integers (it's 12 byte). So, PTS requires 6*10^5*20*12 = 144 MB < 256 MB

I dynamically allocated memory hence each node had an integer and two pointers. But that exceeded memory. Probably i should statically allocate all memory next time.

How to solve D using graph?? (There is graph tag in question!!) if anyone could provide any submission link using graphs that would be very helpful for me,thanks in advance.

Create a graph where each node is a number from $$$0$$$ to $$$(2^m) - 1$$$. There is an edge between $$$u$$$ and $$$v$$$ ($$$u \leq v$$$) if and only if

`(u & v) == u`

. This way, you can go from one bitmask to every other comprehended inside it.When binary searching the answer, for each array on the input you should compute two bitmasks. Let's call them $$$G_{msk}$$$ and $$$L_{msk}$$$. If you are currently trying answer $$$x$$$, then mark elements greater than or equal to $$$x$$$ with a $$$1$$$ on $$$G_{msk}$$$, otherwise $$$0$$$. $$$L_{msk}$$$ is the complement of $$$G_{msk}$$$. That means

`L_msk = ~(G_msk)`

.Start a dfs from every $$$G_{msk}$$$ and check if any of it's neighbors is among the $$$L_{msk}$$$. If it is, then you found a pair for current $$$x$$$ as answer. Notice that it means you found two bitmasks such that bitwise or is

`(1<<m) - 1`

.adedalic why didn't you use ceil() function in problem A. I think I got WA on TC 22 because I used ceil(). My solution 1: link My soln 2 :using_binary_search Both give WA in TC 22.

I got AC by using binary search here is the link to my solution:- link

Use double instead of float

I am having slow rankups XD.

I'm much slower than you. But I don't want to give up ever.

Very nice solution for problem D (fast and compact one). Also very hard to find out such a nice solution like this. Thank for tough problem and its brilliant solution. This helps me learn more about bitmask which I didnt know too much before. Thanks again!

can some one explain editorial of E in simple words ? Thanks ...

Can someone explain dp approach in problem C

Consider the sequence given in the editorial. I'll call it a "good sequence".

The answer to the problem is the number of ways of building it. Memoize the amount of good sequences you can build from a position $$$pos$$$ given that the last number you used was $$$last$$$. These are gonna be the two states.

Now, we transition through the states: for every number from $$$last$$$ to $$$n$$$, try to use it as the $$$pos$$$-th element of the good sequence.

Submission: 68825881

Would you please tell us(people like me!) how you have created newline in your comment :D

I did (Shift + Enter), but double Enter might do the trick aswell.

OH!!

Thanks a lot ^_^

In your code..I have seen if pos==m then return 1..let say,if I have 8 in pos-1 then at the last position i have choices of (n-8) then why to return 1

First of all, I use recursive approaches for dynamic programming problems because it's more intuitive to me.

Ok, so you gotta understand that

`if(pos == m) return 1`

is a base case, where I need to stop making recursive calls.The meaning of it is: If the current position for which the function is called is equal to $$$m$$$ — the last position — it means that I was able to build a valid answer until this point. So I need to return $$$1$$$ to increment the answer count.

This is a very common approach for problems that ask you to compute the amount of ways to do something. I hope I was able to explain it clearly, but you should take a look at AtCoder Educational DP Contest.

I'm not a Sports Programming master, so you'll probably learn more by doing it!

not able to implement (n+2*m-1) C (2m)

please help me how to do it

i tried using tgamma function also as

tgamma(n)=n-1!

Hope this will be helpful. nCr with MOD

you can use nCr = n-1Cr-1 + n-1Cr and use memoization for this problem. you can see my submission for better understanding

E can be solved easily using policy based data structure indexed_set and inserting the elements as a pair of negative timestamp of insertion and the index of friend. Every time you remove a friend and insert it at the top, store the max position of current friend, which can be calculated using order_of_key function and adjust the time as -(n+i) where i denotes the ith message, after all the operations loop over all the friends and find the current positions of friends in the set and update max position and min position accordingly.

My Solution : 68882102

Although this is a good trick to know, consider using BIT's instead. They're faster.

your solution modified: 68888920

哈哈

Explained Solution Of Prob. A Using Ternary Search:

May someone please explain B?

By the looks, you know it's a math related problem. So get some paper and write down some equation and solve it. So what is the equation? a*b + a + b = conc(a,b). Now the conc() part is mathematically weird. So you change it into real math. conc(12,23) = 1223 = 1200 + 23. So you are just putting 0s at the end of a, how many? equal to the number of digits that b has that is the length of b, then you are just adding b. So conc(a,b) = a*10^len(b) + b. Now by simple math you have b = 10^len(b) — 1. What does that mean? You started from a*b + a + b = conc(a,b). So if that is true then you have b = 10^len(b)-1, that is b must be equal to some power of 10 minus 1. you know that "some power" is the length of b. and (some power of 10) — 1 is always 9,99,999 etc. You can pick b = 9, 99, 999 or any such number. Then for every a, a*b + a + b = conc(a,b) is true. So all we need to find is how many 9, 99, 999 or this type of number there is within the given range of 1 to b, and you know for each of this kind of number , every possible a is a valid answer. For example, for the input 4 11, you know between 1 to 11 only 9 is a valid b. and for that b every a from 1-4 is a valid answer. so your answer is 1*4 = 4.

nice explanation sami I just want to add that you can easily calculate the length of the number b by using 10 based logarithm as b will always be 9 or 99 or 999... so you can get |b| using log10(b+1)

I haven't understood this part of problem A tutorial -> "Since the ceiling function is monotonically increasing so we can assume that ⌈f(x)⌉≤⌈f(x+1)⌉ for all x>=sqrt(d)"

You first need to understand concavity. Try my explanation

f(x) = x + d / (x+1)^2, differentiate to get the rate of change, f'(x) = 1 — d / (x+1)^2 . When the rate of change is positive the function is increasing. Here, when x >= sqrt(d), d / (x+1)^2 is always < 1, thus 1 — d / (x+1)^2 is always positive. So the function increases without ever decreasing (monotonically increasing) and that means for any x >= sqrt(d), f(x) <= f(x+1).

f(x) = x+d/(x+1) => f'(x) = 1 — d/(x+1)^2. So as we are considered about positive slope then 1-d/(x+1)^2 >= 0 and form here we should get x >= sqrt(d) -1. so where is this -1 then?

x >= sqrt(d) — 1 is actually the absolute correct equation. But without math, just by looking (which of course saves time) we could say for x >= sqrt(d) function f starts to increase monotonically so if we just run a loop from 0 to sqrt(d) and check for each value if it satisfies the condition is enough. But if your upper bound is sqrt(d)-1 that is correct too.

This competition is great!

why does this 68940816 for prob A fail on test 50! I have used the values of x that would give minimum.

Use double instead of float.

yep...thanks,it worked

can some one explain the first approach in E and what does the following mean in the editorial

"You are just required to count the number of distinct values on some segments."Let's say you want to count the maximum place for friend 4. Consider the sequence

4 1 3 1 5 4

After the first 4, person 4 is in position 1. Then person 1 moves ahead of them, then 3 moves ahead of them. When 1 messages again, he doesn't move ahead of 4, because he's already ahead. Finally, person 5 moves ahead of 4. So because the segment between the 4's contains 3 distinct values moves, person 4 moves down 3 positions. Thus, for each friend, identify the segments between messages, count the number of unique values of a, and take the largest of them.

I had a solution that's a good deal simpler than persistent segment trees, by exploiting the offline nature of the queries. First, a sweep gives another array p such that p[i] is the previous time a[i] messaged (so a[p[i]] = a[i], or p[i] = -1). Each query now takes the form of "how many values of i (l <= i < r) satisfy p[i] < y". I sort these queries by y, and also sort the elements of p by y, then do a sweep that updates and queries a Fenwick tree.

Incidentally, one doesn't need to treat the initial state separately. Just prepend n, n-1, n-2, ..., 1 to the given sequence: the initial state is consistent with having received that sequence of messages.

Thanks bmerry , very nice explanation .

can we solve this using only segment tree (Not persistent segment tree) . We can make segment tree of size m and for each number store the position in array of m where it appears . query for each consecutive positions . Like suppose m is 4 1 3 1 5 4 . Make segment tree of this array and suppose for 4 , we can query (1,5) , (5,5) for finding number of distinct integers between them .

See this answer.

Why does problem A pass if we brute force from 1 to n ...very weak test set https://codeforces.com/contest/1288/submission/68953916 this is my submission that passed

edit:got it...it was my mistake...such an input is not possible that should give tleI wrote some brood for A, and found what: Let's have some val = n/2; So lets check if our condition with x = val is true; Is it okey, and if yes, why it works?) https://codeforces.com/contest/1288/submission/68785380

Sadly I did exactly the same thing at contest time. But not n/2. I did d/2. And got wa :)

I also just check with val = n/2 or n/2 +1 or n/2 -1... It passed!!! https://codeforces.com/contest/1288/submission/68792002 taking x+ ceil(d/(x+1)) to be x+ d/x we get x + d/x >= n so nx-x^2-d >= 0 and maxima of nx-x^2-d occurs at n/2.So we will check around n/2.

I really liked $$$C$$$. I collected the ideas from many folks and wrote an editorial myself for the $$$C$$$ here.

Here is my code to all the problems that I solved for this contest, if anybody wants to refer.

please explain D in Div 2.

Can someone explain the editorial of prob A? I am not able to understand it

In problem B understood why b will be of kind 999999...... but how is final answer a*(len(b+1)-1) Can someone explain

How can we count the number of distinct values on some segments using segment tree with vectors in node? (In editorial of problem E, "The constraints allow you to do whatever you want: segtree with vectors in nodes, Mo, persistent segtree (I hope ML is not too tight for that)." ) Can someone explain the segment-tree approach?

I think people typically refer to it as a merge sort tree (should be googlable). It's usually used to answer the queries of kind: given $$$L, R$$$ and $$$X$$$, find the number of values less than $$$X$$$ on a range $$$[L; R]$$$ of an array.

So let's rephrase our subtask to these terms. Build an array $$$prev$$$ such that $$$prev_i$$$ is the index of the previous occurrence of the value $$$a_i$$$ or $$$-1$$$ if there is none. Now $$$query(L, R, L)$$$ on an array $$$prev$$$ will count only the values which have their previous occurrence to the left of the query segment. So for each unique value only its first occurrence in the segment will be counted. Thus the result of the query is the number of distinct values on a segment.

My second solution is the example of the implementation.

I see, thank you very much! It seems that we can apply this way to online queries.

Can you please explain how to do the task if we have online queries ?

I think we can deal with online queries using the same approach pikmike referred, because in this approach we don't need to sort given queries.

How can we handle updates too ?

Do you mean updates of values in an array? I refer to only an array whose values are fixed. (Online query means we cannot get next queries before we answer a current query.)

Yes I mean if I update values in an array too. I got your explanation about online queries.

Anyone use BIT for counting number of different number in a given segment for dealing with E :)))?

Any approach for solving D other than bitmask?

You can also solve E in $$$O((n+m)+m\cdot logn)$$$ by using an ordered set.

SpoilerYou first initialize min and max values of a number to the position where they originally are, and keep a list of keys of the elements. When placing an element to the top, you look at its order in the set and take the maximum of that and its max value now. You change its min value to 1, and its key to something, that is smaller, than all other keys. You also check the maximum of max values and order of elements at the end of the procedure.

ordered set is $$$O(\log n)$$$ per query. That's literally my third solution but slowed down by using ordered set instead of BIT.

I might be wrong but I would say that ordered set is easier, because you don't have to get the idea of reversing the order of people.

Hi, I had a fairly basic(and probably a stupid doubt). But I tried to run a Brute Force for Problem D in the contest and it gave me a TLE. However, as per my calculation, the complexity of my algorithm is O(m*m*n). Since m<=8 and n<=3*10^5, it shouldn't do that(as in throw a TLE).

Can somebody explain what am I calculating incorrectly? Here's the submission link: https://codeforces.com/contest/1288/submission/68810165

In your program, you switched up the variables; m is what n is in the problem statement and n is what m is. So m is max $$$ 3\cdot 10^5 $$$ and n is max 8. This means, that your $$$ O(m^2) $$$ solution gets TLE. Also, it's not wise to declare arrays with variable sizes, it can cause errors depending on which C++ version and compiler you are using. You can look the details up online. I would recommend using vectors.

Oh alright!

It took me a while to get it. Thanks! Thank you for the suggestion for using vectors too! I usually do use them however, I get a little uncomfortable sometimes when declaring vectors of multiple dimensions. Thanks a lot for the suggestion. I'll practice more and get used to them.

"If we want to verify that the answer is not less than x, we have to choose two arrays such that bitwise OR of their masks is (2^m)−1". Can someone please explain this line to me given in editorial of problem D.

What we are doing is replacing every value in every array with 1 if it is at least x, and 0 otherwise. For example, if we had arrays {1,2,3,4,5} and {6,5,4,3,2}, and x=4 then these would become {0,0,0,1,1} and {1,1,1,0,0}. These are our "bitmasks." If we OR every pair of values at the same index for these two arrays, we get {1,1,1,1,1}. Interpreting this as a string of a binary number is where we get that this is one less than a power of two, in this case 2^5-1.

Guys in https://codeforces.com/problemset/problem/1288/B this problem can (8,9) or (7,9) be answers. 8 * 9 + 8 + 9 = 89 7 * 9 + 7 + 9 = 79 5 * 9 + 5 + 9 = 59 ???

It is asking how many solutions there are, it is not asking for you to provide a solution.

I'm not providing answers. I'm asking what if this happens. In the future just think before saying something.

Yes, according to the problem statement, of course.

I think I'm correctly implementing a Merge Sort Tree for E, giving me O((m+n)log(m+n)) complexity. Can anyone who understands Java help me understand why I'm getting TLE? Thanks!!

https://codeforces.com/contest/1288/submission/69596326

Never mind; not sure how to delete a message but got it up and running

D is a really beautiful question.

Beautiful combinatoric solution for C, I love it! I used dp with some kind of weird optimization (calculating prefix sum in the dp matrix). Then it goes to $$$O(n^2m)$$$ and got passed... 70214567

Not able to to understand the basic idea of 1288E-Message Simulator Help please

Thanks in Advance..

If you look at the array of the users sending messages you can see that when a user x sends a message and goes to the front the number of unique users that messaged after that until user x messages again or the end of messages is reached determines how much user x will be pushed to the right. This problem can be solved by using a merge sort tree which I suggest you read up on if you’re not familiar with it. What it provides us with is a means to get a sorted array of values mapped from the individual messages of a continuous interval in the array of messages. In the case of the solution from the editorial that mapping is the index of the previous occurrence of the person that sent the message in the array of messages, -1 by default. That way when we do a query for an interval from l to r we can binary search the array the merge sort tree provides us with for the value l and thus find the number of messages for which the user who sent them messaged for the first time in that interval.

Alternative dp solution for C:

Let's have dp[diff][index] where diff the possible B index — A index. Notice that because the value of the next index for A can never get smaller and the value of the next index for B can never get bigger, the difference will either stay the same or get smaller. For the transition loop from newDiff = 0, to newDiff <= diff. Notice that with the current diff, newDiff can occur (diff — newDiff + 1) times, so we have to multiply it -> dp[diff][index] += nextDp(newDiff, index+1) * (diff — newDiff + 1). So we just sum of these values for the current dp state. The answer will be the sum of dp[x][0], for 0 <= x < n (if you do it recursively).

Thanks a lot for nice editorial.

I actually got stuck when I have tried to prove why for x = sqrt(d) — 1 value is the minimum one for this function.

Thanks in advance :)

Problem E (2nd solution):

I have been hardly trying to understand that part:

" On the j-th message sent count the number of taken positions to the right of posa[j], set 0 in posa[j], update posa[j]:=j+n and set 1 in posa[j].

And don't forget to update each friend's maximum after all the messages are sent, that is the number of taken positions to the right of his final one as well. "

Any Help?

I had a hard time figuring it out, here is what I think it means : count the number of non zero items to the right of posa[j] in the BIT, then set 0 in the location posa[j] of the BIT, then now you change the value of posa[j] since it has moved to n+j, you set posa[j] = j+n, finally in the BIT, in the location posa[j](which means in the location n+j), set it to 1.

My code for D is significantly shorter and doesn't use binary search, running in $$$O(nm2^m)$$$ and barely squeaking past time limit.

Basically, for each subset of columns $$$S$$$, I find the maximum across all rows for the minimum element in that subset -- let's call that $$$MaxMin(S)$$$ -- and store whichever row ID gives us that maximum. Then, I loop over all the subsets of columns again. For each subset, I take the minimum of $$$MaxMin(S)$$$ and $$$MaxMin(S^c)$$$, and whichever subset maximizes that minimum is the correct one to take. I find whatever row ID gave us $$$MaxMin(S)$$$ and whatever one gave us $$$MaxMin(S^c)$$$ and print those two.

Maybe code can explain it better. My code is here.

Thanks, Such an elegant solution

I solved Problem C: Two Arrays ( 1288C - Two Arrays ) with O(n). Kindly have a look if anyone is interested. 75613441

How to solve D with Dp ? There is DP tag for this problem but I'm not sure how to approach.

The graph of the function in problem A is so odd.