Codeforces Round #361 (Div. 2) Editorial

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Author:danilka.pro.

We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES".

C++ code

pair < int , int > s[55][55];
int v[55][55];
pair < int , int > where[55];
int main(void)
{
    for (int i = 1;i <= 10;++i)
        for (int j = 1;j <= 10;++j)
            v[i][j] = -1;
    v[1][1] = 1;
    v[1][2] = 2;
    v[1][3] = 3;
    v[2][1] = 4;
    v[2][2] = 5;
    v[2][3] = 6;
    v[3][1] = 7;
    v[3][2] = 8;
    v[3][3] = 9;
    v[4][2] = 0;
    for (int k = 0;k <= 9;++k)
        for (int i = 1;i <= 4;++i)
            for (int j = 1;j <= 4;++j)
                if (v[i][j] == k) where[k] = {i,j};
    for (int i = 0;i <= 9;++i)
        for (int j = 0;j <= 9;++j)
            s[i][j] = {where[i].x - where[j].x,where[i].y - where[j].y};
    string number;
    int len;
    fi>>len;
    fi>>number;
    vector < string > ans;
    for (int k = 0;k <= 9;++k)
        if (k != number[0] - '0')
        {
            string cnt = "";
            cnt += k + '0';
            auto pos = where[k];
            for (int i = 0;i < len - 1;++i)
            {
                pos.x += s[number[i+1] - '0'][number[i] - '0'].x;
                pos.y += s[number[i+1] - '0'][number[i] - '0'].y;
                if (1 <= pos.x && pos.x <= 4 && 1 <= pos.y && pos.y <= 3 && v[pos.x][pos.y] != -1)
                    cnt += v[pos.x][pos.y] + '0';
                else break;
            }
            if (cnt.length() == len) 
            {
                fo << "NO\n";
                return 0;
            }
        }
    puts("YES");
    return 0;
}

Another C++ code

pair<int, int> pos[10];
int n;
char a[100]; pair<int, int> v[100];
pair<int, int> operator - (pair<int, int> a, pair<int, int> b){
    return mp(a.first - b.first, a.second - b.second);
}
pair<int, int> operator + (pair<int, int> a, pair<int, int> b){
    return mp(a.first + b.first, a.second + b.second);
}
bool inside(pair<int, int> pos){
    return (pos.first <= 3 && 1 <= pos.first && pos.second <= 3 && pos.second >= 1) || pos == (mp(4, 2));
}
int main(){
    int cnt = 0;
    FOR(x, 1, 3){
        FOR(y, 1, 3){
            cnt++;
            pos[cnt] = mp(x, y);
        }
    }
    pos[0] = mp(4, 2);
    cin >> n;
    scanf("%s", a+1);
    FOR(i, 1, n-1){
        v[i] = pos[a[i+1] - '0'] - pos[a[i] - '0'];
    }
    if(n == 1) return cout << "NO", 0;
    int c = 0;
    FOR(i, 0, 9){
        bool ok = true;
        pair<int, int> curr_pos = pos[i];
        FOR(i, 1, n-1){
            curr_pos = curr_pos + v[i];
            if(!inside(curr_pos)) ok = false;
        }
        if(ok) c++;
    }
    if(c == 1) return cout << "YES", 0;
    cout << "NO";
}

Another C++ code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
bool mark[11];
bool flag1,flag2;
 
int main()
{
    ll n;
    string s;
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        mark[s[i]-'0']=true;
    }
    if((mark[1]||mark[2]||mark[3])&&(mark[7]||mark[9]))
        flag1=true;
    if((mark[1]||mark[4]||mark[7])&&(mark[3]||mark[6]||mark[9]))
        flag2=true;
    if((mark[1]||mark[2]||mark[3])&&mark[0]){
        cout<<"YES";
        return 0;
    }
    if(flag1&&flag2){
        cout<<"YES";
        return 0;
    }
    cout<<"NO";
return 0;
}

Python code

n = int(raw_input())
s = raw_input()
a = []
for i in range(10):
	a.append(True)
for i in range(n):
	c = int(s[i])
	a[c] = False
inc = 0
if a[1] and a[2] and a[3]:
	inc = -3
if a[7] and a[9] and a[0]:
	inc = +3
if a[1] and a[4] and a[7] and a[0]:
	inc = -1
if a[3] and a[6] and a[9] and a[0]:
	inc = +1
if inc == 0:
	print("YES")
else:
	print("NO")

B. Mike and Shortcuts

Author:danilka.pro,I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

We can build a complete graph where the cost of going from point i to point j if |i - j| if a_i! = j and 1 if a_i = j.The we can find the shortest path from point 1 to point i.One optimisation is using the fact that there is no need to go from point i to point j if j ≠ s[i],j ≠ i - 1,j ≠ i + 1 so we can add only edges (i, i + 1),(i, i - 1),(i, s[i]) with cost 1 and then run a bfs to find the shortest path for each point i.

You can also solve the problem by taking the best answer from left and from the right and because a_i ≤ a_i + 1 then we can just iterate for each i form 1 to n and get the best answer from left and maintain a deque with best answer from right.

Complexity is O(N).

C++ code with queue

int d[1 << 20];
int s[1 << 20];
queue < int > Q;
void go(int k,int val)
{
    if (d[k]) return;
    d[k] = val;
    Q.push(k);
}
int main(void)
{
    int n;
    scan(n);//scan integer
    for (int i = 1;i <= n;++i) scan(s[i]);
    go(1,1);
    while (!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        go(s[node],d[node] + 1);
        if (node > 1) go(node - 1,d[node] + 1);
        if (node < n) go(node + 1,d[node] + 1);
    }
    for (int i = 1;i <= n;++i) print(d[i] - 1);
    eol;
    return 0;
}

C++ code with deque

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

const int N = int(1e6) + 5;
int n, d[N], a[N], bd[N];

int main() {
	assert(cin >> n);
	for (int i = 0; i < n; ++i) {
		assert(scanf("%d", &a[i]) == 1);
		a[i]--;
		d[i] = i;
	}
	
	for (int i = 0; i < n; ++i)
		bd[i] = int(1e9);

	deque <int> st;

	for (int i = 0; i < n; ++i) {
		if (i)
			d[i] = min(d[i], d[i - 1] + 1);

		while (!st.empty() && st.front() < i)
			st.pop_front();

		if (!st.empty())
			d[i] = min(d[i], bd[st.front()] - i);

		d[a[i]] = min(d[a[i]], d[i] + 1);
		bd[a[i]] = a[i] + d[a[i]];

		while (!st.empty() && bd[a[i]] <= bd[st.back()])
			st.pop_back();


		st.push_back(a[i]);
	}

	for (int i = 0; i < n; ++i) {
		if (i)
			putchar(' ');
		printf("%d", d[i]);
	}
	return 0;
}

Python code

import Queue
n = int(raw_input())
a = raw_input().split(' ')
used = []
d = []
for i in range(0, n):
    used.append(False)
    d.append(-1)
q = Queue.Queue()
q.put(0)
d[0] = 0
while not(q.empty()):
    v = q.get()
    for dl in range(-1, +2):
        u = v + dl
        if 0 <= u and u < n and d[u] == -1:
            d[u] = d[v] + 1
            q.put(u)
    u = int(a[v]) - 1
    if d[u] == -1:
        d[u] = d[v] + 1
        q.put(u)
for i in range(0, n):
    print(d[i])

$\text{[math]}$ What if you have Q queries Q ≤ 2 × 10⁵ of type (x_i, y_i) and you have to answer the minimal distance from x_i to y_i.

C. Mike and Chocolate Thieves

Author:danilka.pro,I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

Suppose we want to find the number of ways for a fixed n.

Let a, b, c, d ( 0 < a < b < c < d ≤ n ) be the number of chocolates the thieves stole. By our condition, they have the form b = ak, c = ak², d = ak³,where k is a positive integer. We can notice that $\text{[math]}$ , so for each k we can count how many a satisfy the conditions 0 < a < ak < ak² < ak³ ≤ n, their number is $\text{[math]}$ . Considering this, the final answer is $\text{[math]}$ .

Notice that this expression is non-decreasing as n grows, so we can run a binary search for n.

Total complexity: Time ~ $\text{[math]}$ , Space: O(1).

C++ code


ll get(ll x)
{
    ll ans = 0;
    for (int i = 2;1ll * i * i * i <= x;++i)
        ans += x / (1ll * i * i * i);
    return ans;
}
int main(void)
{
    ll m;
    fi>>m;
    ll n = 0;
    for (ll k = 1ll << 60;k;k /= 2)
        if (n + k <= 1e16 && get(n+k) < m) n += k;
    ++n;
    if (get(n) == m) fo << n << '\n';
    else fo << "-1\n";
    return 0;
}

Another C++ code


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

long long get(long long n)
{
    long long ans = 0;
    for (long long i = 2; i * i * i <= n;++i)
        ans += n / (1ll*i * i * i);
    return ans;
}

int main()
{
    long long m,n=-1;
    cin>>m;
    
    long long l=0,r=5e15;
    while (l<r)
    {
        long long mid = (l+r)/2;
        if (get(mid)<m) l=mid+1;
        else r=mid;
    }
    
    if (get(l)==m) n=l;

    cout << n << '\n';
    return 0;
}

D. Friends and Subsequences

Author:I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

First of all it is easy to see that if we fix l then have $\text{[math]}$ . So we can just use binary search to find the smallest index r_min and biggest index r_max that satisfy the equality and add r_max - r_min + 1 to our answer. To find the min and max values on a segment [l, r] we can use Range-Minimum Query data structure.

The complexity is $\text{[math]}$ time and $\text{[math]}$ space.

C++ code O(N)


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

int n, a[200001], b[200001];
long long ans;
deque<int> mx, mn;
int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1, j = 1; i <= n; i++) {
        while(!mx.empty() and a[mx.back()] <= a[i]) mx.pop_back();
        while(!mn.empty() and b[mn.back()] >= b[i]) mn.pop_back();
        mx.push_back(i);
        mn.push_back(i);
        while(j <= i and a[mx.front()] - b[mn.front()] > 0) {
            j++;
            while(!mx.empty() and mx.front() < j) mx.pop_front();
            while(!mn.empty() and mn.front() < j) mn.pop_front();
        }
        if(!mx.empty() and !mn.empty() and a[mx.front()] == b[mn.front()]) ans += min(mx.front(), mn.front()) - j + 1;
    }
    printf("%lld", ans);
}

C++ code O(N log N)


# include <bits/stdc++.h>
# define scan(x) scanf("%d",&x)
using namespace std;
# define fi cin
# define fo cout
int dx[20][1 << 20];
int dy[20][1 << 20];
int lg[1 << 20];
int mx(int l,int r)
{
    int p = lg[r - l + 1];
    return max(dx[p][l],dx[p][r - (1 << p) + 1]);
}
int mn(int l,int r)
{
    int p = lg[r - l + 1];
    return min(dy[p][l],dy[p][r - (1 << p) + 1]);
}
int main(void)
{
    int n;
    scan(n);
    for (int i = 1;i <= n;++i) scan(dx[0][i]);
    for (int i = 1;i <= n;++i) scan(dy[0][i]);
    for (int p = 1;(1 << p) <= n;++p)
        for (int i = 1;i + (1 << p) - 1 <= n;++i)
            dx[p][i] = max(dx[p-1][i],dx[p-1][i + (1 << (p-1))]),
            dy[p][i] = min(dy[p-1][i],dy[p-1][i + (1 << (p-1))]);
    for (int i = 2;i <= n;++i)
        lg[i] = lg[i >> 1] + 1;
    long long ans = 0;
    for (int i = 1;i <= n;++i)
    if (mx(i,i) <= mn(i,i))
    {
        int l = i-1,r = i;
        for (int p = 1 << lg[n - i + 1];p;p >>= 1)
            {
                if (p + l <= n && mx(i,l+p) < mn(i,l+p)) l += p;
                if (p + r <= n && mx(i,r+p) <= mn(i,r+p)) r += p;
            }
        ans += r - l;
    }
    fo << ans << '\n';
}

C++ code O(N log ^ 2 N)


int a[1 << 20];
int b[1 << 20];
int Sa[1 << 20];
int Sb[1 << 20];
int n;
int lg[1 << 20];
void updA(int i,int val)
{
    for (;i <= n;i += i&(-i)) Sa[i] = max(Sa[i],val);
}
int quA(int i)
{
    int ans = -(1e9+1);
    for (;i;i -= i&(-i)) ans = max(ans,Sa[i]);
    return ans;
}
void updB(int i,int val)
{
    for (;i <= n;i += i&(-i)) Sb[i] = min(Sb[i],val);
}
int quB(int i)
{
    int ans = (1e9+1);
    for (;i;i -= i&(-i)) ans = min(ans,Sb[i]);
    return ans;
}
int mx(int T)
{
    return quA(T);
}
int mn(int T)
{
    return quB(T);
}
int main(void)
{
    for (int i = 2;i <= 1e6;++i) lg[i] = lg[i/2] + 1;
    scan(n);
    for (int i = 1;i <= n;++i) scan(a[i]),Sa[i] =-(1e9+1);
    for (int i = 1;i <= n;++i) scan(b[i]),Sb[i] = (1e9+1);
    ll ans = 0;
    for (int i = n;i;--i)
    {
        updA(i,a[i]);
        updB(i,b[i]);
        if (mx(i) > mn(i)) continue;
        int l = i-1,r = i;
        for (int p = 1 << lg[n - i + 1];p;p >>= 1)
            {
                if (p + l <= n && mx(l+p) < mn(l+p)) l += p;
                if (p + r <= n && mx(r+p) <= mn(r+p)) r += p;
            }
        ans += r - l;
    }
    fo << ans << '\n';
    return 0;
}

Another C++ code


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

const int N = int(1e6) + 5;
int a[N], b[N], n;
int lfa[N], rga[N], lfb[N], rgb[N], nxt[N];

void calc_max(int *a, int *lf, int *rg) {
	stack <int> st;
	a[n] = int(1e9) + 1;

	for (int i = 0; i <= n; ++i) {
		while (!st.empty() && a[st.top()] < a[i]) {
			rg[st.top()] = i;
			st.pop();
		}

		lf[i] = st.empty() ? -1 : st.top();
		st.push(i);
	}
}

int naive() {
	int res = 0;
	for (int i = 0; i < n; ++i)
		for (int j = i; j < n; ++j)
			if (*max_element(a + i, a + j + 1) == *min_element(b + i, b + j + 1))
				res++;
	return res;
}

bool read() {

	if (!(cin >> n))
		return false;

	for (int i = 0; i < n; ++i)
		assert(scanf("%d", &a[i]) == 1);
	for (int i = 0; i < n; ++i)
		assert(scanf("%d", &b[i]) == 1);
}

void solve() {
	calc_max(a, lfa, rga);

	for (int i = 0; i < n; ++i)
		b[i] = -b[i];
	calc_max(b, lfb, rgb);

	map <int, int> pos, last;

	for (int i = 0; i < n; ++i) {
		b[i] = -b[i];
		nxt[i] = n;

		if (!pos.count(b[i]))
			pos[b[i]] = i;
		else
			nxt[last[b[i]]] = i;
		last[b[i]] = i;
	}

	long long res = 0;
	
	for (int i = 0; i < n; ++i) {
		if (!pos.count(a[i]))
			continue;

		int pb = pos[a[i]];

		while (nxt[pb] <= i) {
			pb = nxt[pb];
			if (lfb[pb] != -1 && b[lfb[pb]] == b[pb])
				lfb[pb] = lfb[lfb[pb]];
		}
		pos[a[i]] = pb;

		for (int t = 0; t < 2 && pb < n; ++t, pb = nxt[pb]) {
			int lf = max(lfa[i], lfb[pb]);
			int rg = min(rga[i], rgb[pb]);

			if (lf < min(i, pb) && max(i, pb) < rg)
				res += (min(i, pb) - lf) * 1ll * (rg - max(i, pb));
		}
	}

	cout << res << endl;
}

int main() {
	while (read())
		solve();
	return 0;
}

$\text{[math]}$ What if you need to count (l₁, r₁, l₂, r₂), 1 ≤ l₁ ≤ r₁ ≤ n, 1 ≤ l₂ ≤ r₂ ≤ n and $\text{[math]}$ .

Hint:Take idea from this problem.

C++ code for Bonus


const int mod = 1e9 + 7;
int a[1 << 20];
int b[1 << 20];
int st[1 << 20];
int dr[1 << 20];
map < int , ll > A,B;
int main(void)
{
    int n;
    IOS;
    fi>>n;
    for (int i = 1;i <= n;++i) fi>>a[i];
    for (int i = 1;i <= n;++i) fi>>b[i];
    deque < int > d;
    for (int i = 1;i <= n;++i)
    {
        while (!d.empty() && a[d.back()] < a[i]) d.pop_back();
        if (d.empty()) st[i] = 0;
        else st[i] = d.back();
        d.push_back(i);
    }
    d.clear();
    for (int i = n;i;--i)
    {
        while (!d.empty() && a[d.back()] <= a[i]) d.pop_back();
        if (d.empty()) dr[i] = n+1;
        else dr[i] = d.back();
        d.push_back(i);
    }
    for (int i = 1;i <= n;++i)
        A[a[i]] += 1ll * (i - st[i]) * (dr[i] - i);
    while (!d.empty()) d.pop_back();
    for (int i = 1;i <= n;++i)
    {
        while (!d.empty() && b[d.back()] > b[i]) d.pop_back();
        if (d.empty()) st[i] = 0;
        else st[i] = d.back();
        d.push_back(i);
    }
    d.clear();
    for (int i = n;i;--i)
    {
        while (!d.empty() && b[d.back()] >= b[i]) d.pop_back();
        if (d.empty()) dr[i] = n+1;
        else dr[i] = d.back();
        d.push_back(i);
    }
    for (int i = 1;i <= n;++i)
        B[b[i]] += 1ll * (i - st[i]) * (dr[i] - i);
    for (auto &it : A) it.y %= mod;
    for (auto &it : B) it.y %= mod;
    int ans = 0;
    for (auto it : A)
        ans = (ans + 1ll * it.y * B[it.x]) % mod;
    fo << ans << '\n';
    return 0;
}

E. Mike and Geometry Problem

Author:I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

Let define the following propriety:if the point i is intersected by p segments then in our sum it will be counted $\text{[math]}$ times,so our task reduce to calculate how many points is intersected by i intervals 1 ≤ i ≤ n.Let dp[i] be the number of points intersected by i intervals.Then our answer will be $\text{[math]}$ . We can easily calculate array dp using a map and partial sum trick,here you can find about it.

The complexity and memory is $\text{[math]}$ and O(n).

C++ code


# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
const int nmax = 2e5 + 5;
const int mod = 1e9 + 7;
int pow(int a,int b,int mod)
{
    int ans = 1;
    while (b)
    {
        if (b&1) ans = (1ll * ans * a) % mod;
        a = (1ll * a * a) % mod;
        b /= 2;
    }
    return ans;
}
int f[nmax];//factorial
int c[nmax];//inverse of factorial
map < int , int > s;
int C(int n,int k) // combination
{
    int ans = (1ll * f[n] * c[k]) % mod;
    return (1ll * ans * c[n - k]) % mod;
}
main(void)
{
    int n,k;
    int ans = 0;
    ios_base :: sync_with_stdio(0);
    fi>>n>>k;assert(1 <= k && k <= n && n <= 2e5);
    f[0] = c[0] = 1;
    for (int i = 1;i <= n;++i) f[i] = (1ll * f[i-1] * i) % mod,c[i] = pow(f[i],mod-2,mod);
    for (int i = 1;i <= n;++i)
    {
        int a,b;
        fi>>a>>b;
        assert(-1e9 <= a && a <= b && b <= 1e9);
        ++s[a];--s[b+1];
    }
    int l = s.begin()->x;
    int sum = 0;
    for (auto it : s)
    {
        int dist = it.x - l;
        if (sum >= k) ans += (1ll * C(sum,k) * dist) % mod;
        ans = (ans >= mod ? ans - mod : ans);
        sum += it.y;
        l = it.x;
    }
    return fo << ans << '\n',0;
}

Another C++ solution

#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

const int mod = 1e9+7;

ll pp(ll x, int y)
{
	if (!y) return 1;
	ll t = pp(x,y/2);
	t = 1ll*t*t;
	t%=mod;
	if (y%2) t*=1ll*x;
	t%=mod;
	return t;
}

int n,k;

struct s
{
	int x;
	int y;
};

s a[2*200000];

ll c[200001];

void gen()
{
	ll b = 1;
	
	c[k] = 1;
	for (int i=k+1; i<=n; i++)
		b*=	i,b%=mod,b*=pp(i-k,mod-2),b%=mod,c[i]=b;
}


ll ans = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

	cin>>n>>k;
	
	gen();
	
	for (int i=0; i<n; i++)
		cin>>a[2*i].x>>a[2*i+1].x,a[2*i].y = 1,a[2*i+1].y=-1,a[2*i+1].x++;
		
	sort(a,a+2*n, [] (s x, s y) { if (x.x!=y.x) return (x.x<y.x); return (x.y>y.y);});
	
	int last = a[0].x;
	int now = 0;
	
	for (int i=0; i<2*n;)
	{
		int d = a[i].x;
		ans += 1ll * c[now] * (d-last);
		ans%=mod;
		while (a[i].x==d)
			now+=a[i].y,i++;
		last = d;
	}
	
	cout<<ans;
		
    return 0;
}

$\text{[math]}$ what if $\text{[math]}$ where l, r are given in input.

I'm really sorry that problem A was harder than ussually.

Rev.	Кто	Когда	Δ	Комментарий
en13	I_Love_Tina	2016-08-29 20:22:51	343	Reverted to en11
en12	I_Love_Tina	2016-08-29 20:20:18	343
en11	I_Love_Tina	2016-07-16 17:57:54	27	Tiny change: 'e can use a simple Segment Tree or a Range-Min' -> 'e can use Range-Min'
en10	I_Love_Tina	2016-07-09 14:40:24	1612
en9	I_Love_Tina	2016-07-08 12:27:35	936
en8	I_Love_Tina	2016-07-07 10:51:20	2	Tiny change: '[Mike and C' -> '[A.Mike and C'
en7	I_Love_Tina	2016-07-07 10:50:58	12
en6	I_Love_Tina	2016-07-06 23:38:47	3421
en5	I_Love_Tina	2016-07-06 23:29:51	672
en4	I_Love_Tina	2016-07-06 23:09:25	1174
en3	I_Love_Tina	2016-07-06 22:51:58	158	Tiny change: ' sum trick [here you ' -> ' sum trick,[here you '
en2	I_Love_Tina	2016-07-06 22:39:45	18
en1	I_Love_Tina	2016-07-06 22:30:52	12785	Initial revision (published)

История