#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

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

We hope everyone enjoyed the problems. Here is the editorial for the problems. I tried to make it more detailed but there might be some parts that might not be explained clearly.

Div. 2 A — Crazy Computer

Prerequisites : None

This is a straightforward implementation problem. Iterate through the times in order, keeping track of when is the last time a word is typed, keeping a counter for the number of words appearing on the screen. Increment the counter by 1 whenever you process a new time. Whenever the difference between the time for two consecutive words is greater than c, reset the counter to 0. After that, increment it by 1.

Time Complexity : O(n), since the times are already sorted.

Code (O(n))

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 1e5 + 3;
ll a[N];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, c; cin >> n >> c;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	//sort(a, a + n);
	int cnt = 0;
	for(int i = 0; i < n; i++)
	{
		if(i == 0) cnt++;
		else
		{
			if(a[i] - a[i - 1] <= c) cnt++;
			else cnt = 1;
		}
	}
	cout << cnt;
	return 0;
}

Div. 2 B — Complete The Word

Prerequisites : None

Firstly, if the length of the string is less than 26, output - 1 immediately.

We want to make a substring of length 26 have all the letters of the alphabet. Thus, the simplest way is to iterate through all substrings of length 26 (there are O(n) such substrings), then for each substring count the number of occurrences of each alphabet, ignoring the question marks. After that, if there exist a letter that occurs twice or more, this substring cannot contain all letters of the alphabet, and we process the next substring. Otherwise, we can fill in the question marks with the letters that have not appeared in the substring and obtain a substring of length 26 which contains all letters of the alphabet. After iterating through all substrings, either there is no solution, or we already created a nice substring. If the former case appears, output - 1. Otherwise, fill in the remaining question marks with random letters and output the string.

Note that one can optimize the solution above by noting that we don't need to iterate through all 26 letters of each substring we consider, but we can iterate through the substrings from left to right and when we move to the next substring, remove the front letter of the current substring and add the last letter of the next substring. This optimization is not required to pass.

We can still optimize it further and make the complexity purely O(|s|). We use the same trick as above, when we move to the next substring, we remove the previous letter and add the new letter. We store a frequency array counting how many times each letter appear in the current substring. Additionally, store a counter which we will use to detect whether the current substring can contain all the letters of the alphabet in O(1). When a letter first appear in the frequency array, increment the counter by 1. If a letter disappears (is removed) in the frequency array, decrement the counter by 1. When we add a new question mark, increment the counter by 1. When we remove a question mark, decrement the counter by 1. To check whether a substring can work, we just have to check whether the counter is equal to 26. This solution works in O(|s|).

Time Complexity : O(|s|·26²), O(|s|·26) or O(|s|)

Code (O(26^2*|s|)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 10000;
int cnt[27];
string s; int n;

bool valid()
{
	for(int i = 0; i < 26; i++)
	{
		if(cnt[i] >= 2) return false;
	}
	return true;
}

void fillall()
{
	for(int i = 0; i < n; i++)
	{
		if(s[i] == '?') s[i] = 'A';
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;
	n = s.length();
	if(n < 26) {cout << -1; return 0;}
	for(int i = 25; i < n; i++)
	{
		memset(cnt, 0, sizeof(cnt));
		for(int j = i; j >= i - 25; j--)
		{
			cnt[s[j]-'A']++;
		}
		if(valid())
		{
			//cout << "GG " << i << '\n';
			int cur = 0;
			while(cnt[cur]>0) cur++;
			for(int j = i - 25; j <= i; j++)
			{
				if(s[j] == '?')
				{
					s[j] = cur + 'A';
					cur++;
					while(cnt[cur]>0) cur++;
				}
			}
			fillall();
			cout << s;
			return 0;
		}
	}
	cout << -1;
	return 0;
}

Code (O(26*|s|)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 10000;
int cnt[27];
string s; int n;

bool valid()
{
	for(int i = 0; i < 26; i++)
	{
		if(cnt[i] >= 2) return false;
	}
	return true;
}

void fillall()
{
	for(int i = 0; i < n; i++)
	{
		if(s[i] == '?') s[i] = 'A';
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;
	n = s.length();
	if(n < 26) {cout << -1; return 0;}
	for(int i = 0; i < 26; i++) cnt[s[i]-'A']++;
	if(valid())
	{
		int cur = 0;
		while(cnt[cur]>0) cur++;
		for(int i = 0; i < 26; i++)
		{
			if(s[i] == '?')
			{
				s[i] = cur + 'A';
				cur++;
				while(cnt[cur]>0) cur++;
			}
		}
		fillall();
		cout << s;
		return 0;
	}
	for(int i = 26; i < n; i++)
	{
		cnt[s[i]-'A']++; cnt[s[i-26]-'A']--;
		if(valid())
		{
			//cout << "GG " << i << '\n';
			int cur = 0;
			while(cnt[cur]>0) cur++;
			for(int j = i - 25; j <= i; j++)
			{
				if(s[j] == '?')
				{
					s[j] = cur + 'A';
					cur++;
					while(cnt[cur]>0) cur++;
				}
			}
			fillall();
			cout << s;
			return 0;
		}
	}
	cout << -1;
	return 0;
}

Code (O(|s|)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 50000;
int cnt[27];
string s; int n;
int counter;

bool valid()
{
    //cout << counter << endl;
	return (counter == 26);
}

void fillall()
{
	for(int i = 0; i < n; i++)
	{
		if(s[i] == '?') s[i] = 'A';
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s;
	n = s.length();
	if(n < 26) {cout << -1; return 0;}
	counter = 0;
	for(int i = 0; i < 26; i++)
	{
		if(s[i] == '?')
		{
			counter++; continue;
		}
		cnt[s[i]-'A']++;
		if(cnt[s[i]-'A'] == 1) counter++;
	}
	if(valid())
	{
		int cur = 0;
		while(cnt[cur]>0) cur++;
		for(int i = 0; i < 26; i++)
		{
			if(s[i] == '?')
			{
				s[i] = cur + 'A';
				cur++;
				while(cnt[cur]>0) cur++;
			}
		}
		fillall();
		cout << s;
		return 0;
	}
	for(int i = 26; i < n; i++)
	{
		if(s[i] != '?') {cnt[s[i]-'A']++; if(cnt[s[i]-'A']==1) counter++;}
		if(s[i-26] != '?') {cnt[s[i-26]-'A']--; if(cnt[s[i-26]-'A']==0) counter--;}
		if(s[i-26] == '?') counter--;
		if(s[i] == '?') counter++;
		if(valid())
		{
			int cur = 0;
			while(cnt[cur]>0) cur++;
			for(int j = i - 25; j <= i; j++)
			{
				if(s[j] == '?')
				{
					s[j] = cur + 'A';
					cur++;
					while(cnt[cur]>0) cur++;
				}
			}
			fillall();
			cout << s;
			return 0;
		}
	}
	cout << -1;
	return 0;
}

Div. 2 C/Div. 1 A — Plus and Square Root

Prerequisites : None

Firstly, let a_i(1 ≤ i ≤ n) be the number on the screen before we level up from level i to i + 1. Thus, we require all the a_is to be perfect square and additionally to reach the next a_i via pressing the plus button, we require $\text{[math]}$ and $\text{[math]}$ for all 1 ≤ i < n. Additionally, we also require a_i to be a multiple of i. Thus, we just need to construct a sequence of such integers so that the output numbers does not exceed the limit 10¹⁸.

There are many ways to do this. The third sample actually gave a large hint on my approach. If you were to find the values of a_i from the second sample, you'll realize that it is equal to 4, 36, 144, 400. You can try to find the pattern from here. My approach is to use a_i = [i(i + 1)]². Clearly, it is a perfect square for all 1 ≤ i ≤ n and when n = 100000, the output values can be checked to be less than 10¹⁸

Unable to parse markup [type=CF_TEX]

which is a multiple of i + 1, and $\text{[math]}$ is also a multiple of i + 1.

The constraints a_i must be a multiple of i was added to make the problem easier for Div. 1 A.

Time Complexity : O(n)

Code (O(n))

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n; cin >> n;
	for(ll i = 1; i <= n; i++)
	{
		if(i == 1) cout << 2 << '\n';
		else cout << i*(i+1)*(i+1)-(i-1) << '\n';
	}
	return 0;
}

Div. 2 D/Div. 1 B — Complete The Graph

Prerequisites : Dijkstra's Algorithm

This problem is actually quite simple if you rule out the impossible conditions. Call the edges that does not have fixed weight variable edges. First, we'll determine when a solution exists.

Firstly, we ignore the variable edges. Now, find the length of the shortest path from s to e. If this length is < L, there is no solution, since even if we replace the 0 weights with any positive weight the shortest path will never exceed this shortest path. Thus, if the length of this shortest path is < L, there is no solution. (If no path exists we treat the length as ∞.)

Next, we replace the edges with 0 weight with weight 1. Clearly, among all the possible graphs you can generate by replacing the weights, this graph will give the minimum possible shortest path from s to e, since increasing any weight will not decrease the length of the shortest path. Thus, if the shortest path of this graph is > L, there is no solution, since the shortest path will always be > L. If no path exists we treat the length as ∞.

Other than these two conditions, there will always be a way to assign the weights so that the shortest path from s to e is exactly L! How do we prove this? First, consider all paths from s to e that has at least one 0 weight edge, as changing weights won't affect the other paths. Now, we repeat this algorithm. Initially, assign all the weights as 1. Then, sort the paths in increasing order of length. If the length of the shortest path is equal to L, we're done. Otherwise, increase the weight of one of the variable edges on the shortest path by 1. Note that this will increase the lengths of some of the paths by 1. It is not hard to see that by repeating these operations the shortest path will eventually have length L, so an assignment indeed exists.

Now, we still have to find a valid assignment of weights. We can use a similar algorithm as our proof above. Assign 1 to all variable edges first. Next, we first find and keep track of the shortest path from s to e. Note that if this path has no variable edges it must have length exactly L or strictly more than L, so either we're already done or the shortest path contains variable edges and the length is strictly less than L. (otherwise we're done)

From now on, whenever we assign weight to a variable edge (after assigning 1 to every variable edge), we call the edge assigned.

Now, mark all variable edges not on the shortest path we found as ∞ weight. (we can choose any number greater than L as ∞) Next, we will find the shortest path from s to e, and replace the weight of an unassigned variable edge such that the length of the path becomes equal to L. Now, we don't touch the assigned edges again. While the shortest path from s to e is still strictly less than L, we repeat the process and replace a variable edge that is not assigned such that the path length is equal to L. Note that this is always possible, since otherwise this would've been the shortest path in one of the previous steps. Eventually, the shortest path from s to e will have length exactly L. It is easy to see that we can repeat this process at most n times because we are only replacing the edges which are on the initial shortest path we found and there are less than n edges to replace (we only touch each edge at most once). Thus, we can find a solution after less than n iterations. So, the complexity becomes $\text{[math]}$ . This is sufficient to pass all tests.

What if the constraints were n, m ≤ 10⁵? Can we do better?

Yes! Thanks to HellKitsune who found this solution during testing. First, we rule out the impossible conditions like we did above. Then, we assign all the variable edges with ∞ weight. We enumerate the variable edges arbitarily. Now, we binary search to find the minimal value p such that if we make all the variable edges numbered from 1 to p have weight 1 and the rest ∞, then the shortest path from s to e has length ≤ L. Now, note that if we change the weight of p to ∞ the length of shortest path will be more than L. (if p equals the number of variable edges, the length of the shortest path is still more than L or it will contradict the impossible conditions) If the weight is 1, the length of the shortest path is ≤ L. So, if we increase the weight of edge p by 1 repeatedly, the length of the shortest path from s to e will eventually reach L, since this length can increase by at most 1 in each move. So, since the length of shortest path is non-decreasing when we increase the weight of this edge, we can binary search for the correct weight. This gives an $\text{[math]}$ solution.

Time Complexity : $\text{[math]}$ or $\text{[math]}$

Code (O(mnlogn))

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 1001;
const int M = 10001;
const ll INF = ll(1e18);

vector<ii> adj[N];
vector<int> adj2[N];
int L[M]; int R[M];
ll d1[N];
ll d2[N];
int par[N];
ll dist[N][N];

int n, m, l, s, e;

void dijkstra()
{
	d1[s] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, s));
	int cnt = 0;
	while(!pq.empty())
	{
		cnt++;
		int u = pq.top().se; ll d = pq.top().fi; pq.pop();
		for(int i = 0; i < adj[u].size(); i++)
		{
			int v = adj[u][i].fi; ll w = adj[u][i].se;
			if(d + w < d1[v])
			{
				d1[v] = d + w;
				pq.push(ii(d1[v], v));
			}
		}
	}
	cerr << "DIJKSTRA OPERATIONS : " << cnt << '\n';
}

bool dijkstra2()
{
	d2[s] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, s));
	while(!pq.empty())
	{
		int u = pq.top().se; ll d = pq.top().fi; pq.pop();
		for(int i = 0; i < adj2[u].size(); i++)
		{
			int v = adj2[u][i]; ll w = dist[u][v];
			if(d + abs(w) < d2[v])
			{
				d2[v] = d + abs(w);
				par[v] = u;
				pq.push(ii(d2[v], v));
			}
		}
	}
	if(d2[e] > l) return false;
	int cur = e;
	while(cur != s)
	{
		int p = par[cur];
		if(dist[p][cur] < 0)
		{
			dist[p][cur] = -2; dist[cur][p] = -2;
		}
		cur = par[cur];
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(dist[i][j] == -1)
			{
				dist[i][j] = INF;
			}
		}
	}
	cur = e;
	while(cur != s)
	{
		int p = par[cur];
		if(dist[p][cur] < 0)
		{
			dist[p][cur] = -1; dist[cur][p] = -1;
		}
		cur = par[cur];
	}
	return true;
}

void print()
{
	cout << "YES\n";
	for(int i = 0; i < m; i++)
	{
		int u = L[i]; int v = R[i];
		ll d = dist[u][v];
		if(d < 0) d = -d;
		cout << u << ' ' << v << ' ' << d << '\n';
	}
}

bool relax()
{
	for(int i = 0; i < n; i++) d2[i] = INF;
	memset(par, -1, sizeof(par)); //shouldn't be neccesary
	d2[s] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, s));
	while(!pq.empty())
	{
		int u = pq.top().se; ll d = pq.top().fi; pq.pop();
		for(int i = 0; i < adj2[u].size(); i++)
		{
			int v = adj2[u][i]; ll w = dist[u][v];
			if(d + abs(w) < d2[v])
			{
				d2[v] = d + abs(w);
				par[v] = u;
				pq.push(ii(d2[v], v));
			}
		}
	}
	//cerr << d2[e] << '\n';
	if(d2[e] == l) return true;
	int cur = e; bool meet = false;
	while(cur != s)
	{
		int p = par[cur];
		if(!meet && dist[p][cur] < 0)
		{
			ll d = abs(dist[p][cur]);
			dist[p][cur] = d + l - d2[e];
			dist[cur][p] = d + l - d2[e];
			//cerr << d << endl;
			meet = true;
		}
		if(meet) break;
		cur = par[cur];
	}
	return false;
}

int dist1[N][N];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> l >> s >> e;
	memset(dist1, -1, sizeof(dist1));
	for(int i = 0; i < m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		if(w > 0) 
		{
			adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
			adj2[u].pb(v); adj2[v].pb(u);
			dist1[u][v] = w; dist1[v][u] = w;
			dist[u][v] = w; dist[v][u] = w;
		}
		else
		{
			adj2[u].pb(v); adj2[v].pb(u);
			dist[u][v] = -1; dist[v][u] = -1;
		}
		L[i] = u; R[i] = v;
	}	
	for(int i = 0; i < n; i++)
	{
		d1[i] = INF; d2[i] = INF;
	}
	dijkstra(); //cerr << d1[e] << '\n';
	if(d1[e] < l)
	{
		cout << "NO\n";
		return 0;
	}
	if(d1[e] == l)
	{
		cout << "YES\n";
		for(int i = 0; i < m; i++)
		{
			int u = L[i]; int v = R[i];
			ll d = dist1[u][v];
			if(d <= 0) d = INF;
			cout << u << ' ' << v << ' ' << d << '\n';
		}
		return 0;
	}
	bool tmp = dijkstra2();
	if(!tmp)
	{
		cout << "NO\n";
		return 0;
	}
	//cerr << d2[e] << '\n';
	int cnt = 0;
	while(!relax()) 
	{
		relax(); cnt++;
	}
	cerr << "RELAXATIONS DONE : " << cnt << '\n';
	print();
}

Code (O(mlogn(logm+logL))

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 1001;
const int M = 10001;
const ll INF = ll(1e18);

int n, m, l, s, e;

struct edge
{
	int to; ll w; int label;
	edge(int _to, int _w, int _label){to = _to, w = _w, label = _label;}
};

int edgecnt = -1;
vector<edge> adj[N];
ll dist[N];
set<ii> used;

ll dijk(int p, ll val)
{
	for(int i = 0; i < n; i++) dist[i] = INF;
	dist[s] = 0;
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	pq.push(ii(0, s));
	while(!pq.empty())
	{
		int u = pq.top().se; ll d = pq.top().fi; pq.pop();
		for(int i = 0; i < adj[u].size(); i++)
		{
			edge tmp = adj[u][i];
			int v = tmp.to; ll w = tmp.w; int lab = tmp.label;
			if(lab >= 0)
			{
				if(lab < p) w = 1;
				else if(lab == p) w = val;
				else w = ll(1e14);
			}
			if(d + w < dist[v])
			{
				dist[v] = d + w;
				pq.push(ii(dist[v], v));
			}
		}
	}
	return dist[e];
}

void setw(int p, ll val)
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < adj[i].size(); j++)
		{
			int lab = adj[i][j].label;
			if(lab >= 0)
			{
				if(lab < p)
				{
					adj[i][j].w = 1;
				}
				else if(lab == p)
				{
					adj[i][j].w = val;
				}
				else
				{
					adj[i][j].w = INF;
				}
			}
		}
	}
}

void print()
{
	cout << "YES\n";
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < adj[i].size(); j++)
		{
			edge tmp = adj[i][j];
			int v = tmp.to; ll w = tmp.w; 
			if(used.find(ii(i, v)) == used.end())
			{
				cout << i << ' ' << v << ' ' << w << '\n';
				used.insert(ii(i, v)); used.insert(ii(v, i));
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> l >> s >> e;
	for(int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		int lab = -1;
		if(w == 0) 
		{
			lab = ++edgecnt;
		}
		adj[u].pb(edge(v, w, lab));
		adj[v].pb(edge(u, w, lab));
	}
	ll x = dijk(edgecnt, 1); ll y = dijk(-1, 1);
	if(!(x <= l && l <= y))
	{
		cout << "NO\n";
		return 0;
	}
	ll lo = -1; ll hi = edgecnt;
	ll mid, ans;
	while(lo <= hi)
	{
		mid = (lo+hi)/2;
		if(dijk(mid, 1) <= l)
		{
			ans = mid;
			hi = mid - 1;
		}
		else
		{
			lo = mid + 1;
		}
	}
	//now [0..ans] as 1 will give <= L whereas [0..ans - 1] as 1 will give > L
	if(ans == -1)
	{
		setw(-1, 0);
		print();
		return 0;
	}
	lo = 1; hi = INF;
	int ans2 = 0;
	while(lo <= hi)
	{
		mid = (lo+hi)>>1;
		if(dijk(ans, mid) <= l)
		{
			ans2 = mid;
			lo = mid + 1;
		}
		else
		{
			hi = mid - 1;
		}
	}
	//cerr << ans << ' ' << ans2 << '\n';
	setw(ans, ans2);
	print();
}

Div. 2 E/Div. 1 C — Digit Tree

Prerequisites : Tree DP, Centroid Decomposition, Math

Compared to the other problems, this one is more standard. The trick is to first solve the problem if we have a fixed vertex r as root and we want to find the number of paths passing through r that works. This can be done with a simple tree dp. For each node u, compute the number obtained when going from r down to u and the number obtained when going from u up to r, where each number is taken modulo M. This can be done with a simple dfs. To calculate the down value, just multiply the value of the parent node by 10 and add the value on the edge to it. To calculate the up value, we also need to calculate the height of the node. (i.e. the distance from u to r) Then, if we let h be the height of u, d be the digit on the edge connecting u to its parent and val be the up value of the parent of u, then the up value for u is equal to 10^h - 1·d + val. Thus, we can calculate the up and down value for each node with a single dfs.

Next, we have to figure out how to combine the up values and down values to find the number of paths passing through r that are divisible by M. For this, note that each path is the concatenation of a path from u to r and r to v, where u and v are pairs of vertices from different subtrees, and the paths that start from r and end at r. For the paths that start and end at r the answer can be easily calculated with the up and down values (just iterate through all nodes as the other endpoint). For the other paths, we iterate through all possible v, and find the number of vertices u such that going from u to v will give a multiple of M. Since v is fixed, we know its height and down value, which we denote as h and d respectively. So, if the up value of u is equal to up, then up·10^h + d must be a multiple of M. So, we can solve for up to be - d·10^- h modulo M. Note that in this case the multiplicative inverse of 10 modulo M is well-defined, as we have the condition $\text{[math]}$ . To find the multiplicative inverse of 10, we can find φ(M) and since by Euler's Formula we have x^φ(M) ≡ 1(modM) if $\text{[math]}$ , we have x^{φ(M) - 1} ≡ x^- 1(modM), which is the multiplicative inverse of x (in this case we have x = 10) modulo M. After that, finding the up value can be done by binary exponentiation.

Thus, we can find the unique value of up such that the path from u to v is a multiple of M. This means that we can just use a map to store the up values of all nodes and also the up values for each subtree. Then, to find the number of viable nodes u, find the required value of up and subtract the number of suitable nodes that are in the same subtree as v from the total number of suitable nodes. Thus, for each node v, we can find the number of suitable nodes u in $\text{[math]}$ time.

Now, we have to generalize this for the whole tree. We can use centroid decomposition. We pick the centroid as the root r and find the number of paths passing through r as above. Then, the other paths won't pass through r, so we can remove r and split the tree into more subtrees, and recursively solve for each subtree as well. Since each subtree is at most half the size of the original tree, and the time taken to solve the problem where the path must pass through the root for a single tree takes time proportional to the size of the tree, this solution works in $\text{[math]}$ time, where the other $\text{[math]}$ comes from using maps.

Time Complexity : $\text{[math]}$

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 1e5 + 1;
const int MAX = 1e9;
int MOD, n;

bool isprime[100001];
vector<ll> primes;
vector<ii> adj[N];
int subsize[N];
bool visited[N];
int treesize;
vi clrlist;
ll up[N];
ll down[N];
int h[N];
int PHI;
int dppart[N];

ll mult(ll a, ll b)
{
	return (a*b)%MOD;
}

ll add(ll a, ll b)
{
	return (a+b+MOD)%MOD;
}

ll modpow(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1) r=(r*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return r;
}

void Sieve(int n)
{
	memset(isprime, 1, sizeof(isprime));
	isprime[1] = false;
	for(int i = 2; i <= n; i++)
	{
		if(isprime[i])
		{
			primes.pb(i);
			for(int j = 2*i; j <= n; j += i)
			{
				isprime[j] = false;
			}
		}
	}
}

int phi(int n)
{
	ll num = 1; ll num2 = n;
	for(ll i = 0; primes[i]*primes[i] <= n; i++)
	{
		if(n%primes[i]==0)
		{
			num2/=primes[i];
			num*=(primes[i]-1);
		}
		while(n%primes[i]==0)
		{
			n/=primes[i];
		}
	}
	if(n>1)
	{
		num2/=n; num*=(n-1);
	}
	n = 1;
	num*=num2;
	return num;
}

ll inv(ll a)
{
	return modpow(a, PHI-1);
}

void dfs(int u, int par)
{
	if(par == -1) clrlist.clear();
	subsize[u] = 1; clrlist.pb(u);
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i].fi;
		if(visited[v]) continue;
		if(v == par) continue;
		dfs(v, u);
		subsize[u] += subsize[v];
	}	
	if(par == -1) treesize = subsize[u];
}

int centroid(int u, int par)
{
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i].fi;
		if(visited[v]) continue;
		if(v == par) continue;
		if(subsize[v]*2 > treesize) return centroid(v, u);
	}
	return u;
}

int parts = 0;
void fill(int u, int p, int cent)
{
	if(p == cent)
	{
		dppart[u] = parts;
		parts++;
	}
	else if(p != -1)
	{
		dppart[u] = dppart[p];
	}
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i].fi; int w = adj[u][i].se;
		if(v == p || visited[v]) continue;
		down[v] = add(mult(down[u], 10), w);
		up[v] = add(up[u], mult(modpow(10, h[u]), w));
		h[v] = h[u] + 1;
		fill(v, u, cent);
		//cout << v << ' ' << u << ' ' << up[v] << ' ' << up[u] << '\n';
	}
}

ll solve(int cent)
{
	for(int i = 0; i < clrlist.size(); i++)
	{
		up[clrlist[i]] = 0; down[clrlist[i]] = 0; h[clrlist[i]] = 0;
	}
	parts = 0;
	fill(cent, -1, cent); parts--;
	dppart[cent] = -1; 
	map<ll,ll> tot; //only count up
	vector<map<ll,ll> > vec; //only count up, but in specific subtree
	vec.resize(parts+1);
	tot[0]++;
	for(int i = 0; i < clrlist.size(); i++)
	{
		int u = clrlist[i];
		//cout << u << ' ' << up[u] << ' ' << down[u] << '\n';
		if(u == cent) continue;
		tot[up[u]]++;
		vec[dppart[u]][up[u]]++;
	}
	ll ans = 0;
	for(int i = 0; i < clrlist.size(); i++)
	{
		int u = clrlist[i];
		int ht = h[u];
		int pt = dppart[u];
		if(u == cent)
		{
			ans += (tot[0] - 1); //exclude cent as the vertex
		}
		else
		{
			ll val = ((-down[u])%MOD+MOD)%MOD;
			val = mult(val, inv(modpow(10, ht)));
			ans += (tot[val] - vec[pt][val]);
		}
	}
	return ans;
}

ll compsolve(int u)
{
	dfs(u, -1);
	int cent = centroid(u, -1);
	ll ans = solve(cent);
	//cout << u << ' ' << cent << ' ' << ans << '\n';
	visited[cent] = true;
	for(int i = 0; i < adj[cent].size(); i++)
	{
		int v = adj[cent][i].fi;
		if(!visited[v]) ans += compsolve(v);
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> MOD;
	if(MOD == 1)
	{
		cout << ll(n)*ll(n - 1);
		return 0;
	}
	Sieve(100000); PHI = phi(MOD);
	for(int i = 0; i < n - 1; i++) //tree is 0-indexed
	{
		int u, v, w; cin >> u >> v >> w;
		adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
	}
	cout << compsolve(0) << '\n';
	return 0;
}

Div. 1 D — Create a Maze

Prerequisites : None

The solution to this problem is quite simple, if you get the idea. Thanks to danilka.pro for improving the solution to the current constraints which is much harder than my original proposal.

Note that to calculate the difficulty of a given maze, we can just use dp. We write on each square (room) the number of ways to get from the starting square to it, and the number written on (i, j) will be the sum of the numbers written on (i - 1, j) and (i, j - 1), and the edge between (i - 1, j) and (i, j) is blocked, we don't add the number written on (i - 1, j) and similarly for (i, j - 1). We'll call the rooms squares and the doors as edges. We'll call locking doors as edge deletions.

First, we look at several attempts that do not work.

Write t in its binary representation. To solve the problem, we just need to know how to construct a maze with difficulty 2x and x + 1 from a given maze with difficulty x. The most direct way to get from x to 2x is to increase both dimensions of the maze by 1. Let's say the bottom right square of the grid was (n, n) and increased to (n + 1, n + 1). So, the number x is written at (n, n). Then, we can block off the edge to the left of (n + 1, n) and above (n, n + 1). This will make the numbers in these two squares equal to x, so the number in square (n + 1, n + 1) would be 2x, as desired. To create x + 1 from x, we can increase both dimensions by 1, remove edges such that (n + 1, n) contains x while (n, n + 1) contains 1 (this requires deleting most of the edges joining the n-th column and (n + 1)-th column. Thus, the number in (n, n) would be x + 1. This would've used way too many edge deletions and the size of the grid would be too large. This was the original proposal.

There's another way to do it with binary representation. We construct a grid with difficulty 2x and 2x + 1 from a grid with difficulty x. The key idea is to make use of surrounding 1s and maintaining it with some walls so that 2x + 1 can be easily constructed. This method is shown in the picture below. This method would've used around 120 × 120 grid and 480 edge deletions, which is too large to pass.

Now, what follows is the AC solution. Since it's quite easy once you get the idea, I recommend you to try again after reading the hint. To read the full solution, click on the spoiler tag.

Hint : Binary can't work since there can be up to 60 binary digits for t and our grid size can be at most 50. In our binary solution we used a 2 × 2 grid to multiply the number of ways by 2. What about using other grid sizes instead?

Full Solution

Of course, this might not be the only way to solve this problem. Can you come up with other ways of solving this or reducing the constraints even further? (Open Question)

Time Complexity : $\text{[math]}$

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

typedef pair<ii,ii> move;

set<move> ans;
int curx, cury;

bool isvalid(move x)
{
	if(x.fi.fi > 0 && x.se.fi > 0 && x.fi.se > 0 && x.se.se > 0 && x.fi.fi <= curx && x.fi.se <= cury && x.se.fi <= curx && x.se.se <= cury) return true;
	return false;
}

void edge(int x1, int y1, int x2, int y2)
{
	ans.insert(mp(mp(x1, y1), mp(x2, y2)));
}

void add(int bit)
{
	int x = curx;
	edge(x,x+2,x,x+3);
	edge(x+1,x+2,x+1,x+3);
	edge(x+2,x,x+3,x);
	edge(x+2,x+1,x+3,x+1);
	edge(x-2,x+3,x-1,x+3);
	edge(x,x+4,x+1,x+4);
	edge(x+3,x-2,x+3,x-1);
	edge(x+4,x,x+4,x+1);
	edge(x-1,x+1,x,x+1);
	if(bit%3==0) edge(x-1,x+2,x,x+2);
	if(bit%3!=2) edge(x+2,x-1,x+2,x);
	if(bit<3) edge(x+1,x-1,x+1,x);
	curx += 2; cury += 2;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll t; cin >> t;
	vector<int> digits;
	while(t)
	{
		digits.pb(t%6);
		t/=6;
	}
	reverse(digits.begin(), digits.end());
	edge(1, 2, 2, 2);
	edge(2, 1, 2, 2);
	curx = 2; cury = 2;
	for(int i = 0; i < digits.size(); i++)
	{
		add(digits[i]);
	}
	cout << curx << ' ' << cury << '\n';
	vector<move> clr;
	for(set<move>::iterator it = ans.begin(); it != ans.end(); it++)
	{
		if(!isvalid(*it))
		{
			clr.pb(*it);
		}
	}
	for(int i = 0; i < clr.size(); i++)
	{
		ans.erase(clr[i]);
	}
	cout << ans.size() << '\n';
	for(set<move>::iterator it = ans.begin(); it != ans.end(); it++)
	{
		move tmp = (*it);
		cout << tmp.fi.fi << ' ' << tmp.fi.se << ' ' << tmp.se.fi << ' ' << tmp.se.se << '\n';
	}
}

Div. 1 E — Complete The Permutations

Prerequisites : Math, Graph Theory, DP, Any fast multiplication algorithm

We'll slowly unwind the problem and reduce it to something easier to count. First, we need to determine a way to tell when the distance between p and q is exactly k. This is a classic problem but I'll include it here for completeness.

Let f denote the inverse permutation of q. So, the minimum number of swaps to transform p into q is the minimum number of swaps to transform p_{f_i} into the identity permutation. Construct the graph where the edges are $\text{[math]}$ for all 1 ≤ i ≤ n. Now, note that the graph is equivalent to $\text{[math]}$ and is composed of disjoint cycles after q_i and p_i are filled completely. Note that the direction of the edges doesn't matter so we consider the edges to be $\text{[math]}$ for all 1 ≤ i ≤ n. Note that if the number of cycles of the graph is t, then the minimum number of swaps needed to transform p into q would be n - t. (Each swap can break one cycle into two) This means we just need to find the number of ways to fill in the empty spaces such that the number of cycles is exactly i for all 1 ≤ i ≤ n.

Now, some of the values p_i and q_i are known. The edges can be classified into four types :

A-type : The edges of the form $\text{[math]}$ , i.e. p_i is known, q_i isn't.

B-type : The edges of the form $\text{[math]}$ , i.e. q_i is known, p_i isn't.

C-type : The edges of the form $\text{[math]}$ , i.e. both p_i and q_i are known.

D-type : The edges of the form $\text{[math]}$ , i.e. both p_i and q_i are unknown.

Now, the problem reduces to finding the number of ways to assign values to the question marks such that the number of cycles of the graph is exactly i for all 1 ≤ i ≤ n. First, we'll simplify the graph slightly. While there exists a number x appears twice (clearly it can't appear more than twice) among the edges, we will combine the edges with x together to simplify the graph. If there's an edge $\text{[math]}$ , then we increment the total number of cycles by 1 and remove this edge from the graph. If there is an edge $\text{[math]}$ and $\text{[math]}$ , where a and b might be some given numbers or question marks, then we can merge them together to form the edge $\text{[math]}$ . Clearly, these are the only cases for x to appear twice. Hence, after doing all the reductions, we're reduced to edges where each known number appears at most once, i.e. all the known numbers are distinct. We'll do this step in O(n²). For each number x, store the position i such that p_i = x and also the position j such that q_j = x, if it has already been given and - 1 otherwise. So, we need to remove a number when the i and j stored are both positive. We iterate through the numbers from 1 to n. If we need to remove a number, we go to the two positions where it occur and replace the two edges with the new merged one. Then, recompute the positions for all numbers (takes O(n) time). So, for each number, we used O(n) time. (to remove naively and update positions) Thus, the whole complexity for this part is O(n²). (It is possible to do it in O(n) with a simple dfs as well. Basically almost any correct way of doing this part that is at most O(n³) works, since the constraints for n is low)

Now, suppose there are m edges left and p known numbers remain. Note that in the end when we form the graph we might join edges of the form $\text{[math]}$ and $\text{[math]}$ (where a and b are either fixed numbers or question marks) together. So, the choice for the ? can be any of the m - p remaining unused numbers. Note that there will be always m - p such pairs so we need to multiply our answer by (m - p)! in the end. Also, note that the ? are distinguishable, and order is important when filling in the blanks.

So, we can actually reduce the problem to the following : Given integers a, b, c, d denoting the number of A-type, B-type, C-type, D-type edges respectively. Find the number of ways to create k cycles using them, for all 1 ≤ k ≤ n. Note that the answer is only dependent on the values of a, b, c, d as the numbers are all distinct after the reduction.

First, we'll look at how to solve the problem for k = 1. We need to fit all the edges in a single cycle. First, we investigate what happens when d = 0. Note that we cannot have a B-type and C-type edge before an A-type or C-type edge, since all numbers are distinct so these edges can't be joined together. Similarly, an A or C-type edge cannot be directly after a B or C-type edge. Thus, with these restrictions, it is easy to see that the cycle must contain either all A-type edges or B-type edges. So, the answer can be easily calculated. It is also important to note that if we ignore the cyclic property then a contiguous string of edges without D must be of the form AA...BB.. or AA...CBB..., where there is only one C, and zero or more As and Bs.

Now, if d ≥ 1, we can fix one of the D-type edges as the front of the cycle. This helps a lot because now we can ignore the cyclic properties. (we can place anything at the end of the cycle because D-type edges can connect with any type of edges) So, we just need to find the number of ways to make a length n - 1 string with a As, b Bs, c Cs and d - 1 Ds. In fact, we can ignore the fact that the A-type edges, B-type edges, C-type edges and D-type edges are distinguishable and after that multiply the answer by a!b!c!(d - 1)!.

We can easily find the number of valid strings we can make. First, place all the Ds. Now, we're trying to insert the As, Bs and Cs into the d empty spaces between, after and before the Ds. The key is that by our observation above, we only care about how many As, Bs and Cs we insert in each space since after that the way to put that in is uniquely determined. So, to place the As and Bs, we can use the balls in urns formula to find that the number of ways to place the As is $\text{[math]}$ and the number of ways to place the Bs is $\text{[math]}$ . The number of ways to place the Cs is $\text{[math]}$ , since we choose where the Cs should go.

Thus, it turns out that we can find the answer in O(1) (with precomputing binomial coefficients and factorials) when k = 1. We'll use this to find the answer for all k. In the general case, there might be cycles that consists entirely of As and entirely of Bs, and those that contains at least one D. We call them the A-cycle, B-cycle and D-cycles respectively.

Now, we precompute f(n, k), the number of ways to form k cycles using n distinguishable As. This can be done with a simple dp in O(n³). We iterate through the number of As we're using for the first cycle. Then, suppose we use m As. The number of ways to choose which of the m As to use is $\text{[math]}$ and we can permute them in (m - 1)! ways inside the cycle. (not m! because we have to account for all the cyclic permutations) Also, after summing this for all m, we have to divide the answer by k, to account for overcounting the candidates for the first cycle (the order of the k cycles are not important)

Thus, f(n, k) can be computed in O(n³). First, we see how to compute the answer for a single k. Fix x, y, e, f, the number of A-cycles, B-cycles, number of As in total among the A-cycles and number of Bs in total among the B-cycles. Then, since k is fixed, we know that the number of D-cycles is k - x - y. Now, we can find the answer in O(1). First, we can use the values of f(e, x), f(f, y), f(d, k - x - y) to determine the number of ways to place the Ds, and the As, Bs that are in the A-cycles and B-cycles. Then, to place the remaining As, Bs and Cs, we can use the same method as we did for k = 1 in O(1), since the number of spaces to place them is still the same. (You can think of it as each D leaves an empty space to place As, Bs and Cs to the right of it) After that, we multiply the answer by $\text{[math]}$ to account for the choice of the set of As and Bs used in the A-only and B-only cycles. Thus, the complexity of this method is O(n⁴) for each k and O(n⁵) in total, which is clearly too slow.

We can improve this by iterating through all x + y, e, f instead. So, for this to work we need to precompute f(e, 0)f(f, x + y) + f(e, 1)f(f, x + y - 1) + ... + f(e, x + y)f(f, 0), which we can write as g(x + y, e, f). Naively doing this precomputation gives O(n⁴). Then, we can calculate the answer by iterating through all x + y, e, f and thus getting O(n³) per query and O(n⁴) for all k. This is still too slow to pass n = 250.

We should take a closer look of what we're actually calculating. Note that for a fixed pair e, f, the values of g(x + y, e, f) can be calculated for all possible x + y in $\text{[math]}$ or O(n^1.58) by using Number Theoretic Transform or Karatsuba's Algorithm respectively. (note that the modulus has been chosen for NFT to work) This is because if we fix e, f, then we're precisely finding the coefficients of the polynomial (f(e, 0)x⁰ + f(e, 1)x¹ + ... + f(e, n)xⁿ)(f(f, 0)x⁰ + f(f, 1)x¹ + ... + f(f, n)xⁿ), so this can be handled with NFT/Karatsuba.

Thus, the precomputation of g(x + y, e, f) can be done in $\text{[math]}$ or O(n^3.58).

Next, suppose we fixed e and f. We will calculate the answer for all possible k in $\text{[math]}$ similar to how we calculated g(x + y, e, f). This time, we're multiplying the following two polynomials : f(d, 0)x⁰ + f(d, 1)x¹ + ... + f(d, n)xⁿ and g(0, e, f)x⁰ + g(1, e, f)x¹ + ... + g(n, e, f)xⁿ. Again, we can calculate this using any fast multiplication method, so the entire solution takes $\text{[math]}$ or O(n^3.58), depending on which algorithm is used to multiply polynomials.

Note that if you're using NFT/FFT, there is a small trick that can save some time. When we precompute the values of g(x + y, e, f), we don't need to do inverse FFT on the result and leave it in the FFTed form. After that, when we want to find the convolution of f(d, i) and g(i, e, f), we just need to apply FFT to the first polynomial and multiply them. This reduces the number of FFTs and it reduced my solution runtime by half.

Time Complexity : $\text{[math]}$ or O(n^3.58), depending on whether NFT or Karatsuba is used.

Code (NFT)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 251;
const int MOD = 998244353;
ll inv2;
ll prt;
ll iprt;

ll dpncr[N][N];
ll fact[N];
ll inverse[N];
ll g[N][N];
ll sumg[N][N][N];

vector<ii> perm;
int A, B, C, D;

ll modpow(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1) r = (r*a)%MOD;
		a = (a*a)%MOD;
		b>>=1;
	}
	return r;
}

ll inv(ll a)
{
	return modpow(a, MOD - 2);
}

ll choose(int n, int m)
{
	if(m < 0) return 0;
	if(n < m) return 0;
	if(m == 0) return 1;
	if(n == m) return 1;
	if(dpncr[n][m] != -1) return dpncr[n][m];
	dpncr[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
	dpncr[n][m] += MOD; dpncr[n][m] %= MOD;
	return dpncr[n][m];
}

void computefact()
{
	fact[0] = 1;
	for(ll i = 1; i < N; i++)
	{
		fact[i] = (fact[i - 1]*i)%MOD;
	}
	for(ll i = 1; i < N; i++)
	{
		inverse[i] = modpow(i, MOD - 2);
	}
}

void print(vector<ii>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i].fi << ' ' << vec[i].se << endl;
	}
	cout << "------------------------------------------------" << endl;
}

void printans(vector<ll>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << ' ';
	}
	cout << endl;
}

void printansi(vector<int>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << ' ';
	}
	cout << endl;
}

void calcpos(vector<ii>& pos)
{
	pos.resize(perm.size());
	for(int i = 0; i < perm.size(); i++)
	{
		pos[i] = ii(-1, -1);
	}
	for(int i = 1; i < perm.size(); i++)
	{
		if(perm[i].fi > 0)
		{
			pos[perm[i].fi].fi = i;
		}
		if(perm[i].se > 0)
		{
			pos[perm[i].se].se = i;
		}
	}
}

int reduce()
{
	int n = perm.size() - 1;
	vector<ii> pos;
	int cnt = 0;
	for(int i = 1; i <= n; i++) //Do a reduction
	{
		calcpos(pos);
		//print(pos);
		if(pos[i].fi > 0 && pos[i].se > 0)
		{
			if(pos[i].fi == pos[i].se) 
			{
				cnt++;
				ii tmp1 = perm[pos[i].fi];
				for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
				{
					if((*it) == tmp1)
					{
						perm.erase(it); break;
					}
				}
				continue;
			}
			int p1 = pos[i].se; int l = perm[p1].fi; ii tmp1 = perm[p1];
			int p2 = pos[i].fi; int r = perm[p2].se; ii tmp2 = perm[p2];
			for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
			{
				if((*it) == tmp1)
				{
					perm.erase(it); break;
				}
			}
			for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
			{
				if((*it) == tmp2)
				{
					perm.erase(it); break;
				}
			}
			perm.pb(ii(l, r));
		}
	}
	//count A, B, C, D
	for(int i = 1; i < perm.size(); i++)
	{
		if(perm[i].fi > 0 && perm[i].se > 0)
		{
			assert(perm[i].fi != perm[i].se);
			C++;
		}
		else if(perm[i].fi > 0)
		{
			A++;
		}
		else if(perm[i].se > 0)
		{
			B++;
		}
		else
		{
			D++;
		}
	}
	return cnt;
}

ll mult(ll a, ll b)
{
	ll r = (a*b)%MOD;
	r = (r+MOD)%MOD;
	return r;
}

ll add(ll a, ll b)
{
	ll r = ((a+b)%MOD+MOD)%MOD;
	return r;
}

ll F(ll a, ll b, ll c, ll d)
{
	ll ans = 1;
	if(d == 0)
	{
		if(a == 0 && b == 0 && c == 0) return 1;
		else return 0;
	}
	ans = mult(ans, fact[a]);
	ans = mult(ans, fact[b]);
	ans = mult(ans, fact[c]);
	ans = mult(ans, choose(a+d-1, d-1));
	ans = mult(ans, choose(b+d-1, d-1));
	ans = mult(ans, choose(d, C));
	return ans;
}

const int LG = 9;
const int root_pw = (1<<LG);
void fft (vector<int> & a, bool invert) 
{
	int n = (int) a.size();
 
	for (int i=1, j=0; i<n; ++i) {
		int bit = n >> 1;
		for (; j>=bit; bit>>=1)
			j -= bit;
		j += bit;
		if (i < j)
			swap (a[i], a[j]);
	}
 
	for (int len=2; len<=n; len<<=1) {
		int wlen = invert ? iprt : prt;
		for (int i=len; i<root_pw; i<<=1)
			wlen = int((wlen*1LL*wlen)%MOD);
		for (int i=0; i<n; i+=len) {
			int w = 1;
			for (int j=0; j<len/2; ++j) {
				int u = a[i+j]; int v = int((a[i+j+len/2]*1LL*w)%MOD);
				a[i+j] = u+v < MOD ? u+v : u+v-MOD;
				a[i+j+len/2] = u-v >= 0 ? u-v : u-v+MOD;
				w = int (w * 1LL * wlen % MOD);
			}
		}
	}
	if (invert) {
		ll nrev = inv(n);
		for (int i=0; i<n; ++i)
			a[i] = int((a[i]*1LL*nrev)%MOD);
	}
}

void multiply(vector<int>& a, vector<int>& b, vector<int>& res)
{
	vector<int> fa(a.begin(), a.end()), fb(b.begin(), b.end());
	int n = 1;
	while(n < max(a.size(), b.size())) n <<= 1;
	fa.resize(n); fb.resize(n);
	//cerr << "A : "; printansi(fa); cerr << "B : "; printansi(fb);
	fft(fa, 0); fft(fb, 0);
	//cerr << "INVERT ONCE : ";
	//printans(fa); printans(fb);
	//fft(fa, 1); fft(fb, 1); cerr << "INVERT BACK A: "; printans(fa); cerr << "INVERT BACK B: "; printans(fb);
	res.resize(n);
	for(int i = 0; i < n; i++) res[i] = int((fa[i]*1LL*fb[i])%MOD);
	//printans(fa);
	fft(res, 1);
	//cerr << "CONVOLUTION : "; printansi(res);
	
}

void computeg(int n)
{
	g[0][0] = 1;
	g[1][1] = 1;
	for(int i = 2; i <= n; i++)
	{
		for(int j = 1; j <= i; j++)
		{
			for(int k = 1; k <= i; k++)
			{
				g[i][j] = add(g[i][j], mult(g[i-k][j-1], mult(choose(i, k), fact[k-1])));
			}
			//cerr << g[i][j] << '\n';
			g[i][j] = mult(g[i][j], inverse[j]);
			//cerr << "G : " << i << ' ' << j << ' ' << g[i][j] << '\n';
		}
	}
	for(int i = 0; i <= A; i++)
	{
		for(int j = 0; j <= B; j++)
		{
			vector<int> gi; vector<int> gj;
			gi.resize(n+1); gj.resize(n+1);
			for(int k = 0; k <= n; k++)
			{
				gi[k] = int(g[i][k]);
				gj[k] = int(g[j][k]);
				//cerr << gi[k] << ' ' << gj[k] << '\n';
			}
			vector<int> res;
			multiply(gi, gj, res);
			for(int k = 0; k <= n; k++)
			{
				sumg[i][j][k] = res[k];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; perm.resize(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> perm[i].fi;
	}
	for(int i = 1; i <= n; i++)
	{
		cin >> perm[i].se;
	}
	ll tmpmult = 7*17;
	tmpmult = mult(tmpmult, modpow(2, 23 - LG)); 
	prt = modpow(3, tmpmult);
	inv2 = inv(2);
	iprt = inv(prt);
	A = 0; B = 0; C = 0; D = 0;
	memset(dpncr, -1, sizeof(dpncr));
	memset(sumg, 0, sizeof(sumg));
	memset(g, 0, sizeof(g));
	memset(fact, 0, sizeof(fact));
	memset(inverse, 0, sizeof(inverse));
	int cycles = reduce();
	computefact(); 
	computeg(n);
	//cerr << h(1, 0, 0) << endl;
	
	vector<ll> ans; ans.assign(n+1, 0);
	
	if(D - C < 0)
	{
		for(int i = 0; i < n; i++)
		{
			cout << ans[i] << ' ';
		}
		cout << endl;
		return 0;
	}

	for(int i = 0; i <= A; i++)
	{
		for(int j = 0; j <= B; j++)
		{
			ll coef = 1;
			coef = mult(coef, F(A-i,B-j,C,D));
			if(A > 0) coef = mult(coef, choose(A, i));
			if(B > 0) coef = mult(coef, choose(B, j));
			vector<int> gi; vector<int> gj;
			gi.resize(n+1); gj.resize(n+1);
			for(int k = 0; k <= n - cycles; k++)
			{
				gi[k] = int(g[D][k]);
				gj[k] = int(sumg[i][j][k]);
			}
			vector<int> res;
			multiply(gi, gj, res);
			//cout << gi.size() << ' ' << gj.size() << ' ' << res.size() << ' ' << ans.size() << ' ' << n << ' ' << cycles << '\n';
			for(int k = 0; k <= n - cycles; k++)
			{
				int moves = n - (k + cycles);
				ans[moves] = add(ans[moves], mult(res[k], coef));
			}
		}
	}
	
	for(int i = 0; i < ans.size(); i++)
	{
		ans[i] = mult(ans[i], fact[D-C]);
	}
	
	for(int i = 0; i < n; i++)
	{
		cout << ans[i] << ' ';
	}
	cout << endl;
	
	return 0;
}

Code (Karatsuba)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 251;
const int MOD = 998244353;
ll inv2;
ll prt;
ll iprt;

ll dpncr[N][N];
ll fact[N];
ll inverse[N];
ll g[N][N];
ll sumg[N][N][N];

vector<ii> perm;
int A, B, C, D;

ll modpow(ll a, ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1) r = (r*a)%MOD;
		a = (a*a)%MOD;
		b>>=1;
	}
	return r;
}

ll inv(ll a)
{
	return modpow(a, MOD - 2);
}

ll choose(int n, int m)
{
	if(m < 0) return 0;
	if(n < m) return 0;
	if(m == 0) return 1;
	if(n == m) return 1;
	if(dpncr[n][m] != -1) return dpncr[n][m];
	dpncr[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
	dpncr[n][m] += MOD; dpncr[n][m] %= MOD;
	return dpncr[n][m];
}

void computefact()
{
	fact[0] = 1;
	for(ll i = 1; i < N; i++)
	{
		fact[i] = (fact[i - 1]*i)%MOD;
	}
	for(ll i = 1; i < N; i++)
	{
		inverse[i] = modpow(i, MOD - 2);
	}
}

void print(vector<ii>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i].fi << ' ' << vec[i].se << endl;
	}
	cout << "------------------------------------------------" << endl;
}

void printans(vector<ll>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << ' ';
	}
	cout << endl;
}

void printansi(vector<int>& vec)
{
	for(int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << ' ';
	}
	cout << endl;
}

void calcpos(vector<ii>& pos)
{
	pos.resize(perm.size());
	for(int i = 0; i < perm.size(); i++)
	{
		pos[i] = ii(-1, -1);
	}
	for(int i = 1; i < perm.size(); i++)
	{
		if(perm[i].fi > 0)
		{
			pos[perm[i].fi].fi = i;
		}
		if(perm[i].se > 0)
		{
			pos[perm[i].se].se = i;
		}
	}
}

int reduce()
{
	int n = perm.size() - 1;
	vector<ii> pos;
	int cnt = 0;
	for(int i = 1; i <= n; i++) //Do a reduction
	{
		calcpos(pos);
		//print(pos);
		if(pos[i].fi > 0 && pos[i].se > 0)
		{
			if(pos[i].fi == pos[i].se) 
			{
				cnt++;
				ii tmp1 = perm[pos[i].fi];
				for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
				{
					if((*it) == tmp1)
					{
						perm.erase(it); break;
					}
				}
				continue;
			}
			int p1 = pos[i].se; int l = perm[p1].fi; ii tmp1 = perm[p1];
			int p2 = pos[i].fi; int r = perm[p2].se; ii tmp2 = perm[p2];
			for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
			{
				if((*it) == tmp1)
				{
					perm.erase(it); break;
				}
			}
			for(vector<ii>::iterator it = perm.begin(); it != perm.end(); it++)
			{
				if((*it) == tmp2)
				{
					perm.erase(it); break;
				}
			}
			perm.pb(ii(l, r));
		}
	}
	//count A, B, C, D
	for(int i = 1; i < perm.size(); i++)
	{
		if(perm[i].fi > 0 && perm[i].se > 0)
		{
			assert(perm[i].fi != perm[i].se);
			C++;
		}
		else if(perm[i].fi > 0)
		{
			A++;
		}
		else if(perm[i].se > 0)
		{
			B++;
		}
		else
		{
			D++;
		}
	}
	return cnt;
}

ll mult(ll a, ll b)
{
	ll r = (a*b)%MOD;
	r = (r+MOD)%MOD;
	return r;
}

ll add(ll a, ll b)
{
	ll r = ((a+b)%MOD+MOD)%MOD;
	return r;
}

ll F(ll a, ll b, ll c, ll d)
{
	ll ans = 1;
	if(d == 0)
	{
		if(a == 0 && b == 0 && c == 0) return 1;
		else return 0;
	}
	ans = mult(ans, fact[a]);
	ans = mult(ans, fact[b]);
	ans = mult(ans, fact[c]);
	ans = mult(ans, choose(a+d-1, d-1));
	ans = mult(ans, choose(b+d-1, d-1));
	ans = mult(ans, choose(d, C));
	return ans;
}

ll buffer[20001], bufferpos, siz = 1024;
const int LG = 4;

void multiply(int size, ll a[], ll b[], ll r[])
{
	if(size <= (1<<LG))
	{
		for(int i = 0; i < size*2; i++) r[i] = 0;
		for(int i = 0; i < size; i++)
		{
			if(a[i])
			{
				for(int j = 0; j < size; j++)
				{
					r[i+j] += a[i]*b[j];
					r[i+j] %= MOD;
				}
			}
		}
		for(int i = 0; i < size*2; i++)
		{
			r[i] %= MOD;
		}
		return ;
	}
	int s = size/2;
	multiply(s, a, b, r);
	multiply(s, a+s, b+s, r+size);
	ll *a2 = buffer+bufferpos; bufferpos += s;
	ll *b2 = buffer+bufferpos; bufferpos += s;
	ll *r2 = buffer+bufferpos; bufferpos += size;
	for(int i = 0; i < s; i++)
	{
		a2[i] = a[i] + a[i+s];
		if(a2[i]>=MOD) a2[i]-=MOD;
	}
	for(int i = 0; i < s; i++)
	{
		b2[i] = b[i] + b[i+s];
		if(b2[i]>=MOD) b2[i]-=MOD;
	}
	multiply(s, a2, b2, r2);
	for(int i = 0; i < size; i++)
	{
		r2[i] -= (r[i] + r[i+size]);
	}
	for(int i = 0; i < size; i++)
	{
		r[i+s] += r2[i];
		r[i+s]%=MOD;
		if(r[i+s]<0) r[i+s]+=MOD;
	}
	bufferpos -= (s+s+size);
}
ll gi[N+5]; ll gj[N+5];

void computeg(int n)
{
	g[0][0] = 1;
	g[1][1] = 1;
	for(int i = 2; i <= n; i++)
	{
		for(int j = 1; j <= i; j++)
		{
			for(int k = 1; k <= i; k++)
			{
				g[i][j] = add(g[i][j], mult(g[i-k][j-1], mult(choose(i, k), fact[k-1])));
			}
			g[i][j] = mult(g[i][j], inverse[j]);
		}
	}
	for(int i = 0; i <= A; i++)
	{
		for(int j = 0; j <= B; j++)
		{
			siz = 512;
			while(siz/2 >= n+1) siz>>=1;
			for(int k = 0; k < siz; k++)
			{
				if(k <= n)
				{
					gi[k] = g[i][k];
					gj[k] = g[j][k];
				}
				else
				{
					gi[k] = gj[k] = 0;
				}
			}
			ll *res = buffer+bufferpos;
			bufferpos+=2*siz;
			multiply(siz,gi,gj,res);
			for(int k = 0; k <= n; k++)
			{
				sumg[i][j][k] = res[k];
			}
			bufferpos-=2*siz;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; perm.resize(n+1);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> perm[i].fi;
	}
	for(int i = 1; i <= n; i++)
	{
		cin >> perm[i].se;
	}
	
	A = 0; B = 0; C = 0; D = 0;
	memset(dpncr, -1, sizeof(dpncr));
	memset(sumg, 0, sizeof(sumg));
	memset(g, 0, sizeof(g));
	memset(fact, 0, sizeof(fact));
	memset(inverse, 0, sizeof(inverse));
	int cycles = reduce();
	computefact(); computeg(n);
	vector<ll> ans; ans.assign(n+1, 0);
	
	if(D - C < 0)
	{
		for(int i = 0; i < n; i++)
		{
			cout << ans[i] << ' ';
		}
		cout << endl;
		return 0;
	}
	
	for(int i = 0; i <= A; i++)
	{
		for(int j = 0; j <= B; j++)
		{
			ll coef = 1;
			coef = mult(coef, F(A-i,B-j,C,D));
			if(A > 0) coef = mult(coef, choose(A, i));
			if(B > 0) coef = mult(coef, choose(B, j));
			siz = 512;
			while(siz/2 >= n-cycles+1) siz>>=1;
			for(int k = 0; k < siz; k++)
			{
				if(k <= n-cycles)
				{
					gi[k] = g[D][k];
					gj[k] = sumg[i][j][k];
				}
				else
				{
					gi[k] = gj[k] = 0;
				}
			}
			ll *res = buffer+bufferpos;
			bufferpos+=2*siz;
			multiply(siz,gi,gj,res);
			for(int k = 0; k <= n - cycles; k++)
			{
				int moves = n - (k + cycles);
				ans[moves] = add(ans[moves], mult(res[k], coef));
			}
			bufferpos-=2*siz;
		}
	}
	
	for(int i = 0; i < ans.size(); i++)
	{
		ans[i] = mult(ans[i], fact[D-C]);
	}
	
	for(int i = 0; i < n; i++)
	{
		cout << ans[i] << ' ';
	}
	cout << endl;
}

Comments (80)

Show archived | Write comment?

giorgosgiapis

8 years ago, # |

+23

Very nice problem set. Hope to see you prepare more rounds in the future!

→ Reply

zscoder

8 years ago, # ^ |

+29

Ya, I hope so. Currently this is the last of my problems for now but maybe there'll be more in the future.

code_fille

← Rev. 2 →

-9

Hey, the O(mnlogn) approach gave TLE on case 127 during contest, replacing cin/cout by scanf printf passed all test cases. Why are such cases kept? :/

20710181

Tosic

6 years ago, # ^ |

Because you should know that cin/cout is much slower unless "desynced": adding

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

speeds cin/cout up to be roughly as fast as scanf/printf.

Infused

+26

Really fast editorial. This is how all editorials should be written :)

Dabagh

Sorry. I was wrong. nice editorial :)

chaotic_iak

+11

My idea for Div1 D (which unfortunately didn't pass because I miscounted something crucial) was to use base 70.

Each digit is constructed with a hard-coded solution. The rest of the walls are shown above.

You might notice that each digit is a 6x5 area and not 5x5. Turns out that with 5x5, there is no grid giving exactly 67 paths. Had 5x5 worked, my idea would have also worked... almost. It needed 301 walls.

EDIT: You might notice that I did make a submission implementing this idea. When I first counted it, I forgot to account the last x70 block, so I thought I only needed 296 walls.

gengkev

This is not very important, but for the first sample solution for 716B - Complete the Word, should the time complexity be O(26 * 2 * |s|) and not O(26² * |s|) ? Anyway, thank you for writing a detailed editorial and providing solution code as well!

pjag

"Now, we binary search to find the maximal value p such that if we make all the variable edges numbered from 1 to p have weight 1 and the rest ∞, then the shortest path from s to e has length ≤ L. "

This should be minimal, right? It confused me for a while while reading the editorial.

You're right, I'll correct it.

Burunduk1

+39

Did authors expect "random walking" as solution in D? (start with empty grid, add some walls, while answer is enough big... start again).

If yes, what is running time of author's implementation?

My "random walking" has got TL 161 during the contest.

After optimization in 1.5 times, it gets OK in 1.3 sec =(

danilka.pro

+13

Nope, we were not expected that. Honestly, we should have set the TL to 0.5s to avoid this, but we just had not realized that such kind of solutions will do fine.

We'll be patient next time ;)

LLI_E_P_JI_O_K

My "not-random walking", i.e. on every step take the wall which will maximally reduce number of ways from (1,1) to (n,m), but still be >= T, pass in 0.187 secs:

Submission

I could AC it during contest, but forgot how to recalculate answer in O(1) when we add one wall to current field and done it using N*M recalculation.

WuHongxun

Amazing it works...

CSGO_is_life

Am I the only one stuck finding a relation in Div2C ? :(

ironsoul

Here is a my method of solving Div2 C: I just wrote a really slow solution. I wrote it down on paper and tried to found consistent pattern. To be honest, I do not know why my solution works but it got "ACCEPTED".

int n;
	cin >> n;
	BigInt dp[n + 1], st, e, s;
	dp[1].read("2");
	dp[2].read("17");
	st.read("14");
	e.read("8");
	s.read("6");
	for (int i = 3; i <= n; i++) {
		BigInt d = dp[i - 1] - dp[i - 2];
		d += st;
		dp[i] = dp[i - 1] + d;
		if (i == 3) {
			st += e;
		} else {
			st += s;
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[i].print();
		cout << '\n';
	}

GreenGrape

So was I during the contest, so I tried to brute it in a slightly optimised way :) That's an alternative to O(n). Although it's incredibly slow. http://codeforces.net/contest/716/submission/20703268

MahmoudAli

← Rev. 5 →

i made it as a picture so it can be more readable since some how the comment don't deal with my enters :D

Time Complexity : O(nlogn(logn + logMOD))

My cenroid decomposition is exactly O(nlogn), gets OK in 0.343 sec.

Use hash map
Inverse? Precalculate all negative powers of 10.

Ya you're right. Indeed these optimizations will make it $\text{[math]}$ .

sengxian

Can anybody explain why

I got TLE using unordered_map http://codeforces.net/contest/715/submission/20724049

But got AC using map http://codeforces.net/contest/716/submission/20703268

Isn't unordered_map faster than map? Maybe the clear operations slows down the unordered_map?

TLE

unordered_map can be hacked. See this: https://ipsc.ksp.sk/2014/real/problems/h.html

Thanks!

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

M.Mahdi

I have a faster (and easier to code!) solution for Div1B. It's $\text{[math]}$ . I described it in this comment!

kdh9949

+112

I have a cool Div1D Solution!

I used power of 3. with this structure, we only need to calculate the digit values of T in base of 3. if a digit is "0", we close all the blue and green "doors" for that digit. if a digit is "1", we open one "door". if a digit is "2", we open both doors. it gives a 41 * 41 size board (since ceil(log3(10^18)) == 38 and we need some more outlines) and max 299 walls. but we can remove some more walls at the outside.

Source : here

tantanvi

nice problemset and well_written editorial hope to see your next round

Um_nik

+53

You was not expected O(n⁴) solution to pass (in E)? 20714654 Really?

I'm confident that for n < 250 O(n²) multiplication is faster than FFT.

Yep, you're right that we were not expected O(n⁴) to pass. Actually we had one solution in O(n⁴) that appears to be written in very unoptimal way.

Anyway, great job getting the solution accepted!, we hoped you'll get an AC during the contest.

Thanks for the great problem, I enjoyed it a lot. Also thanks for ~~nasty~~ not to my taste problem C which forced me to solve E :) (no offence just don't like this kind of problems)

Swistakk

+10

We can find inverse of 10 mod m in O(10) :P. We need a, b, so that a * 10 + b * m = 1. We iterate through b and check if bm mod 10 is 1 and if yes then we get a :P. Either way, I used exgcd during contest xD.

Mohammad_Yasser

+57

Problem B div1: Complete The Graph, can be solved simply in O(n + m * log(m)).

First, let all the erased edges be weighted 1.

Then, run dijkstra from t, and save for each node its shortest distance from t.

Then, run dijkstra from s, and if the current edge is erased, then let its weight be = max( 1, L — current distance — shortest distance from the other end of the edge to t).

If at the end the shortest path from s to t was L, then there's an answer, which was formed during the second dijkstra. So the solution is simply running dijkstra twice.

Proof:-

Edge weights can be at least 1. They can only be increased than that.
In second dijkstra, when you set a weight to an erased edge that way:-

-- If it's currently not a shortest path edge, you do nothing.

-- If it's but the shortest path is < L, you modify this edge to make the path through it = L. By modifying the current edge you are sure that you're modifying a path distance to be = L, and no other edge weight in this path will modified in the future, unless there'll be another path distance = L. And you never let a path distance < L unless it has no erased edges. In that case it's impossible anyway, else you end up with at least one path distance = L, and the shortest distance >= L, so the shortest distance = L.

Code: 20710911

Sandip_Jana

Thanks for the logic. I solved Div2D finally after so many wa's. All thanks to U.

Also learnt that Priority Queue is slow in Java . So rather Use TreeSet

http://codeforces.net/contest/716/submission/20731857 I got TLE IN TESTCASE 117 . Next i replaced PriorityQueue in JAva and used TreeSet http://codeforces.net/contest/716/submission/20732812

Bamm and its Accepted. It was fun.

iliekcomputers

This is an awesome solution! Thanks.

abhishekvtangod

4 years ago, # ^ |

Edit: How will it handle the cases if the edges are repeating? Like, if there is a corner vertice with only one edge to main part of the graph, so if dijkstraS changes that edge value, it won't reflect in distT, hence the same edge gets different values.

This is Awesome!! Thank You :)

kkamesh

Hello, I got WA in systests of Div 2 B. Could somebody kindly point out the mistake?

http://codeforces.net/contest/716/submission/20692380

q..

About problem "Complete The Graph ": In my country, 0 is considered positive by some people. Even the math teachers have different opinions because we also use the term "strictly positive" for numbers > 0. Does "positive" always mean ">0" in English?

Yeah, it always does. Maybe you're confused because 0 is sometimes considered a natural number? It surely is not positive though.

bernett

In Div2-D/Div1-B, is there a way to solve the problem by modelling it as a minCost-maxFlow problem? I was trying this approach throughout the contest but couldn't find a way to do it.

Also, naming the starting as "s" and ending as "t" made me think of it as "source" and the "sink" since thats the commonly used variables for them. Even though I thought about a solution with Dijkstra, this made me continue to look at it as flow problem!

yelghareeb

In problem DIV2-D/DIV1-B, I solved it by excluding invalid cases as described in the editorial, then I run Dijkstra to find the shortest path from s to t (with replacing missing edges with ones).

After that I increase only ONE variable edge on the shortest path to a value that makes that shortest path equals to L. I assign infinity to all other variable edges.

I'm still getting wrong answer with this solution :( Is there anything wrong with this approach?

http://codeforces.net/contest/716/submission/20718122

NewNick

Maybe now there is other shorter path then your edge. Sometimes you cannot set this value.

5 5 4 0 4

0 1 0

1 2 1

1 3 1

3 4 0

2 4 1

it's clearly wrong in this input if you just assign 2 to the fourth edge , and 1 to the first one.

tik-tok

in the explanation of the problem C-div2 it is written that:

"we also require ai to be a multiple of i", why ?

ffao

+25

Not sure I'm a fan of extremely tight constraints for a constructive problem such as D. The intended solution itself needs exactly 50x50 space (and nearly exactly 300 walls), so you're leaving very few room for creativity in solutions.

Though my own case wasn't a problem with creativity; I saw the base 6 idea during the contest, but didn't eliminate the exterior walls, so I spent 320 walls instead of 300. Commenting two lines of the solution makes it pass :(

Can't agree more. I wanted to write exactly same comment after solving it today. Fortunately I didn't encounter problems with that, but I imagined how mad I would be if it had turned out I use 310 walls or something.

I_love_Captain_America

Editorial for Div2 D says

Firstly, we ignore the variable edges. Now, find the length of the shortest path from s to e. If this length is < L, there is no solution

I don't understand why there's no solution, as all paths from s to e can contain some of the variable edges, making it possible. What did I not understand?

meeeep

We want the shortest path to have length L. Since the shortest path in this case does not pass through any variable edges and is already shorter than L, there is nothing we can do to increase its length. Hence we can never set the shortest path to L and there is no solution.

I understand now.

gongy

In what cases should I expect unordered_map to be slower than normal map? I am quite confused as I haven't encountered this before, I always assumed unordered_map would be OK.

unordered_map TLE: 20721642 map AC: 20722164

I would really appreciate any insight on this! Thanks in advance.

rpk74m

maybe rehash

a.nabil

[D. Complete The Graph] why don't we assign all unknown edge with value=0, then find the shortest path, and if the shortest path was under value = p, then it is impossible to find solution, else we check the shortest path and assign the unkown edge to make the path length = p, and set the rest of the unknown edges to infinity ?????????????

← Rev. 3 →

take this case : 5 5 4 0 4

it's clearly wrong in this input either if you just assign 2 to the fourth edge and 1 to the first one,or if you assign 2 to the fourth edge and oo to the first one

microtony

+48

Div 1 D:

My solution 20712414 uses 50 rows and 36 columns

Block 1: 31 rows x 35 columns (1620288010530347424)

Block 2: 15 rows x 35 columns (482320623240)

Block 3: 4 rows x 35 columns (7770)

As you can see if there are only red walls we have 64C34 + 48C34 + 37C34 = 1620288010530347424 + 482320623240 + 7770 ways.

Now the walls on the blue lines can be deleted independently to reduce the answer. After sorting the values are like this: 1, 1, 1, 3, 6, 10, 14, 15, 21, 28, ..., 191724747789809255, 218169540588403635, 409894288378212890, 409894288378212890. This (multi)set of numbers is able to produce any subset sum between 1 and 10^18.

Max number of walls is 261 when input = 3.

King_George

Wondering how you find to divide the room like this? Did you write another code to find it?

bmerry

+20

I had an alternative solution for Div 1 C, also either O(n log n) or O(n log n log n) depending on whether you use a hash table or balanced binary tree. I couldn't make it work during the contest (today I discovered that multiset::count can take O(log n + count(k)) time, not just O(log n)), but I made it work afterwards.

Consider the tree to be rooted. For each subtree, we will compute the following, recursively:

A list of all numbers formed by starting somewhere in the subtree and walking up to the root (mod M).
A list of desired prefixes to match the suffixes formed by starting from the root and walking down to each node (mod M).
The number of interesting paths passing through the root.

This can be done by tree DP: for a particular subtree root, merge in the children one at a time. The problem is that done naively, this can be O(n^2) for a very deep tree. There are two tricks necessary to make this O(n log n):

Each list is stored as a set of values plus a linear transformation on those values (mod M). This allows addition of an extra edge to be done in constant time (e.g. up edges are transformed by x -> 10x+d, and linear transformations can be composed).
When counting, iterate over the smaller list and search in the larger list. Similarly, when merging, merge the smaller list in the larger one.

The second condition means that each time a value is used in iteration, it goes into a list that is at least twice the size. Thus, it is iterated only O(log n) times.

aaaaajack

← Rev. 4 →

I used this approach at first but I found that I didn't know how to add an extra down edge. How do you do that? Edit: Another problem I met is I don't know how to count the suffixes which match a given prefix.

Edit: Sorry, I didn't notice that you store something different in your second list. Now I understand :P

yolob2112

wrong answer on test 5(also where can i find the test cases?) for Div2 C

20728168

Could someone please tell what is wrong with the code.

haleyk100198

It's the overflow bug.

temp=(int)Math.pow(level*(level+1),2);

I am no expert with Java, but (int) should hold only about 2e9, while the power of pow could be 1e16.

rachitiitr

Integer Overflow.

gzz

Could you tell me what is the trick in Div.2 E's test 119?

http://codeforces.net/contest/716/submission/20732311

Thanks so much !!!

(I'm new here and it's a pity to see WA 119 while there're 120 test cases.

dear zscoder:in CF716B_Complete the Word,your Code O(26^2*|s|) is O(26*|s|)actually.

ivan.popelyshev

phi(M) is not required to find inverse of 10. Just check M+1, 2M+1, ... 9M+1 one of these can be divided by 10.

Hi everyone in the editorial of div2/d div1/b ,I didn't understand why this is true: "It is easy to see that we can repeat this process at most n times because we are only replacing the edges which are on the initial shortest path we found and there are less than n edges to replace ". I mean why there are at most n edges to replace in the shortest paths graph. could anyone explain that in details. thanks in advance;

sanket407

same doubt

Diplomate

There are n vertices in a graph and the shortest way doesn't visit any vertex twice. So at most the algorithm visits n vertices and n-1 edges.

voxel

in Div2 D: what is wrong with this approach:

replace all erased edges with cost 1, then find the shortest path (let us call it 'len'), then go through every edge in the shortest path, change the cost of the first erased edge you find to be L-len+1, then go to the erased edges that is not on the shortest path and set there cost to infinity, then add the changes to the original graph, then find the shortest path again, if the length of the path is not L, print 'NO', otherwise print the solution.

the source code: 20740319

take this case :

in this case : if the fourth edge is the first one u meet in ur dijkstra , u will assign 2 to it and assign 1 to the first one , then ur ans will be NO , because there still a path shorter than L;

LaercioJr

To solve your problem, find the shortest path s to t, and instead of setting the value of the first variable edge equals to the L-len+1, you can do a binary search(lower bound) on the new value of the variable edges, and if the path is less than L, adds in the value of the first variable edge of the shortest path, the amount needed for the shortest path be equal to L. Then check if the length of the path is L.

My approach: 20754984

fofao_funk

ignore

piewpiew

Is there a simpler solution to the Div2 D/Div1 B?

+68

Here's a O(n²) solution for 715E - Complete the Permutations.

Consider p_i as an edge from (i, 1) to (p_i, 0), q_i as an edge from (i, 0) to (q_i, 1).

There exists four kinds of chains : 01, 10, 11, 00, (e.g. 01 means (x,0)->....->(y,1))

We need to calculate the number of ways to link them into circle.(we can link 0->1 1->0)

Ways to form n circles with m 01-chains (let's define it as f_m, n) equals to Stirling numbers of the first kind. So we consider forming 01-chains with 00 + (10)* + 11 first, then consider forming circles with 01-chains.

Circles which consists with 10 chains only is not able to divide into 01-chains, so let's call them 10-circle and calculate them separately.

Suppose there are (cnt[10] - k) 10-chains which form t 10-circles. Then l = cnt[00] = cnt[11] 01-chains will be formed with k 10-chains. Define g_k = l! * k! * C(k + l - 1, l - 1), which equals to the ways to form them.

$\text{[math]}$

Define $\text{[math]}$

Time Complexity : O(n²)

Here's my code: 20756117

Orz syc1999 who got AC with O(n²) solution just after the contest ended.//It seems his solution based on DP is different from mine...

ANYONE PASSED DIV 2 D IN JAVA WITH 3 DIJIKSTRAS AND PRIORITYQUEUE ?? Getting TLE on case 129 http://codeforces.net/contest/716/submission/20757614

shubham1100

For Div2D, I have a solution similar to the editorial. It was timing out in the contest, but I just realized that was only in the test cases when s and t were not connected. Taking care of this case resulted in AC. My accepted solution.

I am not clear on the complexity of the solution (I think it's O(m*m*logn)). I thought someone might be able to help. My solution is as follows: Initialize all variable edges with weight 1.

In a loop

Find any shortest path. If its length is equal to L we are done. If its length is > L we are done , and the answer is NO.
Otherwise, the length is < L. While calculating the shortest path, we also keep track of the first variable edge in it(starting from s). If there is no such edge, then it means there is a path of length < L, with no variable edge in it. Hence the answer is NO.
Otherwise, increase the length of the variable edge so that the length of the path is L.

My intuition about the time complexity is similar to the editorial. It would be great if someone can help me on this :D.

luismo

5 years ago, # ^ |

My idea is similar, I just take the last variable edge in the shortest path found, WA16, here is my solution:

https://codeforces.net/problemset/submission/715/55517344

In div 2 D complete the graph code why the last 2 loops in dij2() are required ?? where the edges are set to -2 and then to infinity

architkarandikar

7 years ago, # |

There is another constructive solution for Div1B which has better complexity than the problem setter's solution.

Here is an O(n^2) solution which can be converted to O(m log n) using dijkstra-with-heaps/red-black-trees. The idea is to first do a dijkstra from t and then do a dijkstra from s, assigning weights on the fly. Assign weight (dist(s,t)-dist(nb,t))-dist(s,vt) to edge vt<->nb if this quantity is positive otherwise assign weight 1.

Link to O(n^2) implementation from virtual participation: 28398556

pk842

nicely explained DIV2 : D thanks!

iSikai

5 years ago, # |

Div 2.E Digit Tree can be solved without exclusive but with proper scheduling, just update answer assuming u both as the beginning and the end when you encounter it, using MapDown&MapUp, which record previous nodes . The only thing to keep in mind is to Update MapDown&MapUp only after coming back from a son of a centroid ,to guarantee nodes in the same son not combine with each other.

nmnsharma007

4 years ago, # |

Can anyone who reads this comment please point out the mistake in my Code for Complete the Graph? I am calculating minimum distance of every vertex from t first. Then I calculate distance from s and update the edge weights to get L as shortest path. What am I missing? Please help