Codeforces Round #439 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Hi, all!

This is not Tommyr7, but the impostor behind the round :P. The statements are written by me. The characters in the round feature, again, the Monogatari anime series, and to be more specific, Nisemonogatari: Fake Tale. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!

On a side note, special kudos to the best impostors of the round (except me, lol)!

Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!

Here are hints for all problems and detailed tutorials for most of them. Stay tuned, more are coming!

Hints

Problem A

Problem B

Problem C

Problem D

Problem E

Tutorials

869A - The Artful Expedient

Author Tommyr7, cyand1317 / Preparation Tommyr7, cyand1317 / Tutorial cyand1317

Tutorial

Solution 1 (Tommyr7)

#include <bits/stdc++.h>
using namespace std;
#define Maxn 4000007
bool vis[Maxn];
int a[4007],b[4007],n;
int main()
{
	scanf("%d",&n);
	memset(vis,false,sizeof(vis));
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]=true;
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		vis[b[i]]=true;
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (vis[a[i]^b[j]]) ++ans;
	if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");
	return 0;
}

Solution 2 (cyand1317)

#include <stdio.h>

int main()
{
    puts("Karen");
    return 0;
}

869B - The Eternal Immortality

Author Tommyr7 / Preparation Tommyr7 / Tutorial cyand1317

Tutorial

Model solution (Tommyr7)

#include <bits/stdc++.h>
using namespace std;
long long L,R;
int ans;
int main()
{
	scanf("%lld%lld",&L,&R);
	if (R-L>=10) printf("%d\n",0);
	else
	{
		ans=1;
		for (long long i=L+1;i<=R;i++)
			ans=(1LL*ans*(i%10))%10;
		printf("%d\n",ans);
	}
	return 0;
}

869C - The Intriguing Obsession

Author Tommyr7 / Preparation Tommyr7 / Tutorial Tommyr7

Tutorial

Model solution (Tommyr7)

#include <bits/stdc++.h>
#define Maxn 5007
#define modp 998244353
int p[Maxn][Maxn];
int pre[Maxn];
int a,b,c;
int solve(int x,int y)
{
	int res=0;
	for (int k=0;k<=x&&k<=y;k++)
	{
		int del=pre[k];
		del=(1LL*del*p[x][k])%modp;
		del=(1LL*del*p[y][k])%modp;
		res=(res+del)%modp;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	memset(p,0,sizeof(p));
	p[0][0]=1;
	for (int i=1;i<=5000;i++)
	{
		p[i][0]=1;
		for (int j=1;j<=i;j++)
			p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;
	}
	memset(pre,0,sizeof(pre));
	pre[0]=1;
	for (int i=1;i<=5000;i++)
		pre[i]=(1LL*pre[i-1]*i)%modp;
	int ans=1;
	ans=(1LL*ans*solve(a,b))%modp;
	ans=(1LL*ans*solve(b,c))%modp;
	ans=(1LL*ans*solve(a,c))%modp;
	printf("%d\n",ans);
	return 0;
}

869D - The Overdosing Ubiquity

Author quailty / Preparation quailty / Tutorial quailty

Tutorial

Model solution (quailty)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

const int MAXN=255;

const int Mod=1000000007;
inline void add_mod(int &x,int y)
{
    x=(x+y<Mod ? x+y : x+y-Mod);
}

int u[MAXN],v[MAXN];

map<int,int> mp;
inline int get_id(int x)
{
    if(!mp[x])mp[x]=(int)mp.size();
    return mp[x];
}

vector<int> e[MAXN];
void add_edge(int u,int v)
{
    e[u].push_back(v);
    e[v].push_back(u);
}

inline int cal_size(int u,int n,int d)
{
    int t=u,c=0,res;
    while(t)c++,t>>=1;
    res=(1<<(d-c+1))-1,t=c;
    while(t<d)t++,u=u<<1|1;
    return res-max(min(u-n,1<<(d-c)),0);
}

int num[MAXN];
void pre_dp(int u,int f)
{
    for(auto &v:e[u])
    {
        if(v==f)continue;
        num[u]-=num[v];
        pre_dp(v,u);
    }
}

int vis[MAXN];
void dfs(int u,int &tot)
{
    add_mod(tot,num[u]);
    vis[u]=1;
    for(auto &v:e[u])
        if(!vis[v])dfs(v,tot);
    vis[u]=0;
}

int main()
{
    int n,m,d=0;
    scanf("%d%d",&n,&m);
    while((1<<d)<=n)d++;
    get_id(1);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        int t=u[i];
        while(t)get_id(t),t>>=1;
        t=v[i];
        while(t)get_id(t),t>>=1;
    }
    for(auto &t:mp)
    {
        int u=t.first,id=t.second;
        if(u>1)add_edge(get_id(u),get_id(u>>1));
        num[id]=cal_size(u,n,d);
    }
    pre_dp(1,0);
    for(int i=0;i<m;i++)
        add_edge(get_id(u[i]),get_id(v[i]));
    int res=0;
    for(int i=1;i<=(int)mp.size();i++)
    {
        int tot=0;
        dfs(i,tot);
        add_mod(res,1LL*tot*num[i]%Mod);
    }
    printf("%d\n",res);
    return 0;
}

869E - The Untended Antiquity

Author Tommyr7 / Preparation Tommyr7,cyand1317,visitWorld / Tutorial cyand1317

Tutorial

Solution 1 (visitWorld)

#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define bin(x) (1<<(x))
//#define LX_JUDGE

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }
template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }

template<typename T> inline void read(T &x) {
	char c;
	while ((c = getchar()) < '0' or c > '9');
	for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');
}

const int inf = 0x3f3f3f3f;
const int MAX_N = 2500;

struct Data {
	int u, d, id;
	Data() {}
	Data(int u, int d, int id) : u(u), d(d), id(id) {}
};

class SegmentTree {
	map<pii, int> G;
	int n, pcnt;
	vector<Data> H[MAX_N * 4 + 255];
#define ls (o << 1)
#define rs (o << 1 | 1)

	int _l, _r, _u, _d, _id;

	void ins(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			//printf("%d %d %d %d\n", l, r, _u, _d);
			H[o].pb(Data(_u, _d, _id));
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) ins(ls, l, m);
		if (m < _r) ins(rs, m + 1, r);
	}
	void del(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {
				if (it->id == _id) {
					H[o].erase(it);
					break ;
				}
			}
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) del(ls, l, m);
		if (m < _r) del(rs, m + 1, r);
	}
	inline int _ask(const vector<Data> &q, int h) {
		int best = inf, ans = -1;
		for (auto to : q) {
			if (to.u <= h and h <= to.d and to.d - to.u < best) {
				best = to.d - to.u;
				ans = to.id;
			}
		}
		return ans;
	}
	int ask(int o, int l, int r) {
		if (l == r) return _ask(H[o], _u);
		int m = (l + r) / 2;
		int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);
		return ans < 0 ? _ask(H[o], _u) : ans;
	}
#undef ls
#undef rs
public :
	void init(int n) {
		this->n = n;
		pcnt = 1;
	}
	void ins(int l, int u, int r, int d) {
		G[mp(l, u)] = _id = pcnt++;
		_l = l, _r = r, _u = u, _d = d;
		ins(1, 1, n);
	}
	void del(int l, int u, int r, int d) {
		_id = G[mp(l, u)];
		G.erase(mp(l, u));
		_l = l, _r = r;
		del(1, 1, n);
	}
	int ask(int x, int y) {
		_l = x, _u = y;
		return ask(1, 1, n);
	}
} my;

int main() {
	int n, m, Q;
	read(n), read(m), read(Q);
	my.init(2500); // FIX ME
	int opt, r1, c1, r2, c2;
	while (Q--) {
		read(opt), read(r1), read(c1), read(r2), read(c2);
		if (opt == 3) {
			//int a = my.ask(r1, c1), b = my.ask(r2, c2);
			//printf("%d %d\n", a, b);
			puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");
		} else if (opt == 1) {
			my.ins(r1, c1, r2, c2);
		} else {
			my.del(r1, c1, r2, c2);
		}
	}
	return 0;
}

Solution 2 (Tommyr7)

#include <bits/stdc++.h>
#define Maxn 2507
using namespace std;
int n,m,q;
map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;
pair<unsigned long long,unsigned long long> s[Maxn][Maxn];
void add(int x,int y,pair<unsigned long long,unsigned long long> del)
{
	for (int kx=x;kx<=2503;kx+=kx&(-kx))
		for (int ky=y;ky<=2503;ky+=ky&(-ky))
		{
			s[kx][ky].first+=del.first;
			s[kx][ky].second+=del.second;
		}
}
pair<unsigned long long,unsigned long long> query(int x,int y)
{
	pair<unsigned long long,unsigned long long> res=make_pair(0,0);
	for (int kx=x;kx;kx-=kx&(-kx))
		for (int ky=y;ky;ky-=ky&(-ky))
		{
			res.first+=s[kx][ky].first;
			res.second+=s[kx][ky].second;
		}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	memset(s,0,sizeof(s));
	srand(20001206);
	mp.clear();
	for (int i=1;i<=q;i++)
	{
		int t,r1,c1,r2,c2;
		scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);
		pair<unsigned long long,unsigned long long> del,udel;
		if (t==1)
		{
			del.first=rand();
			del.second=rand();
			udel=make_pair(-del.first,-del.second);
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;
			add(r1,c1,del);
			add(r1,c2+1,udel);
			add(r2+1,c1,udel);
			add(r2+1,c2+1,del);
		} else if (t==2)
		{
			del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);
			udel=make_pair(-del.first,-del.second);
			add(r1,c1,udel);
			add(r1,c2+1,del);
			add(r2+1,c1,del);
			add(r2+1,c2+1,udel);
		}
		else
		{
			del=query(r1,c1);
			udel=query(r2,c2);
			if (del==udel) printf("Yes\n"); else printf("No\n");
		}
	}
	return 0;
}

???: Impostor behind the round :P, guess who I am?

Tommyr7: I do hope you all enjoyed yourselves during the contest. See you next time!

Rev.	By	When	Δ	Comment
en7	Tommyr7	2017-10-07 16:12:04	46
en6	Tommyr7	2017-10-07 09:30:48	2
en5	Tommyr7	2017-10-07 09:29:23	72
en4	Tommyr7	2017-10-07 09:26:04	15	Tiny change: 'rials for the first two. Stay tun' -> 'rials for most of them. Stay tun'
en3	Tommyr7	2017-10-07 09:24:00	7202	Tiny change: '017-10-06]/ Tutori' -> '017-10-06] / Tutori'
en2	Tommyr7	2017-10-07 07:05:14	1052
en1	Tommyr7	2017-10-06 19:01:22	3281	Initial revision (published)

Hints

Tutorials

869A - The Artful Expedient

869B - The Eternal Immortality

869C - The Intriguing Obsession

869D - The Overdosing Ubiquity

869E - The Untended Antiquity

History