Weekly Training Farm 22 — 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

Weekly Training Farm 22 is over. Congratulations to the winners :

W4yneb0t (perfect score in < 1 hour!)
aaaaajack (perfect score)
eddy1021

Here is the editorial :

Problem A

This problem can be solved by greedy. We list down the positive integers one by one. We keep a pointer that initially points to the first letter of s. Whenever the pointed character in the string s matches the corresponding digit of the integer, we move the pointer one step to the right and continue. Repeat this process until the pointer reaches the end.

However, we still need to know whether the answer can be large. The key is to note that the answer will never exceed 10⁶, because after writing down 10 consecutive numbers, at least one of them has last digit equals to the current digit, so the pointer will move to the right at least once when we write down 10 consecutive numbers. Thus, in the worse case, we'll only list down the numbers from 1 to 10⁶, which is definitely fast enough.

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<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;

vector<pair<char,int> > vec;
const int N = 100000;

void gen()
{
	for(int i = 1; i <= N*10; i++)
	{
		int x=i;
		string r;
		while(x)
		{
			r+=char('0'+x%10);
			x/=10;
		}
		for(int j = int(r.size())-1;j>=0;j--)
		{
			vec.pb(mp(r[j],i));
		}	
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	gen();
	string s; cin>>s;
	int ptr=0; int p2 = 0;
	while(p2<s.length()&&ptr<vec.size())
	{
		if(s[p2]==vec[ptr].fi) 
		{
			p2++;
			ptr++;
			continue;
		}
		ptr++;
	}
	ptr--; //remember this
	cout<<vec[ptr].se;
}

Problem B

This problem can be solved using dynamic programming. Firstly, observe that if we already determine which set of problems to solve, then it's best to solve the problem in increasing order of time needed to solve in order to minimize the time penalty. Thus, we can first sort the problems in increasing order of time needed, breaking ties arbitarily.

Let dp[i][j] denote the maximum number of problems solved and minimum time penalty acquired when doing so by using exactly j minutes and only solving problems among the first i ones. dp[0][0] = (0, 0) (the first integer denotes the number of problems solved and the second integer denotes the time penalty in order to do so). The transitions can be handled easily by simply considering whether to solve the i-th problem or not. The time complexity of this solution is O(nT) (T is the duration of the contest)

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<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 = 100011;
const int T = 301;
ii dp[N][T];
ii a[N];

ii maxi(ii a, ii b)
{
	if(a.fi!=b.fi)
	{
		if(a.fi>b.fi) return a;
		else return b;
	}
	else
	{
		if(a.se<b.se) return a;
		else return b;
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	int t = 300;
	for(int i = 1; i <= n; i++)
	{
		cin>>a[i].fi>>a[i].se;
	}
	sort(a+1,a+n+1);
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= t; j++)
		{
			dp[i][j]=mp(-1,-1);
		}
	}
	dp[0][0] = mp(0,0);
	ii maxans = mp(0,0);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= 300; j++)
		{
			dp[i][j] = dp[i-1][j];
			if(j-a[i].fi>=0&&dp[i-1][j-a[i].fi].fi!=-1)
			{
				dp[i][j] = maxi(dp[i][j], mp(dp[i-1][j-a[i].fi].fi+1, dp[i-1][j-a[i].fi].se+j+20LL*a[i].se));
			}
			if(i==n) maxans = maxi(maxans, dp[i][j]);
		}
	}
	cout<<maxans.fi<<' '<<maxans.se<<'\n';
}

Problem C

This is an ad hoc problem. Firstly, we can use two moves to determine what the value of the first bit is. (simply flipping it twice will tell you its value. Now, if the bit is 1, you don't need to flip it anymore. If it's 0, you'll need to flip it. In any case, we'll flip the second bit as well. (if the first bit needs to be flipped, we'll flip [1, 2] and flip [2, 2] otherwise) After flipping the second bit, we can determine whether it's a 1 or 0 by calculating from the total number of 1s of the string before the flip and after the flip. We can repeat this for every 2 consecutive bits until we arrive at the last two bits. At this point, we know what the second last bit is, and we also know the total number of 1 bits. So, we can easily deduce the value of the last bit from the information as well. Now, we just need to perform one last flip to make the last 2 bits become 1. The total number of moves made is n + 1.

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<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 flip(int l, int r)
{
	cout<<l<<' '<<r<<'\n';
	fflush(stdout);
	int cnt; 
	cin>>cnt;
	return cnt;
}

int main()
{
	int n; cin>>n;
	int c1 = flip(1,1);
	if(c1==n)
	{
		cout<<-1<<'\n'; fflush(stdout);
		return 0;
	}
	int c2 = flip(1,1);
	bool pre = 0; //does previous need a flip?
	if(c2<c1)
	{
		pre=1;
	}
	if(c2==n)
	{
		cout<<-1<<'\n'; fflush(stdout);
		return 0;
	}
	int cnt = c2;
	for(int i = 2; i <= n - 1; i++)
	{
		int prevcnt = cnt;
		int newcnt;
		if(pre)
		{
			newcnt = flip(i-1,i);
			if(newcnt==prevcnt)
			{
				pre=1;
			}
			else
			{
				pre=0;
			}
		}
		else
		{
			newcnt = flip(i,i);
			if(newcnt<prevcnt)
			{
				pre=1;
			}
			else
			{
				pre=0;
			}
		}
		cnt=newcnt;
		if(newcnt==n)
		{
			cout<<-1<<'\n'; fflush(stdout);
			return 0;
		}
	}
	if(cnt==n)
	{
		cout<<-1<<'\n'; fflush(stdout);
		return 0;
	}
	if(cnt==n-2)
	{
		flip(n-1,n);
		cout<<-1<<'\n'; fflush(stdout);
		return 0;
	}
	assert(cnt==n-1);
	if(pre)
	{
		flip(n-1,n-1);
		cout<<-1<<'\n'; fflush(stdout);
	}
	else 
	{
		flip(n,n);
		cout<<-1<<'\n'; fflush(stdout);
	}
}

Problem D1

First, we can use 18 moves to determine the value of a, by asking 2 to 19 in increasing order and the first yes answer will be the value of a. If there're no "yes" answers, then the value of a is 20.

Call a number good if it can be represented as the sum of nonnegative multiples of as and b. Note that if x is good, then x + a, x + b are both good.

Now that we have the value of a, let's think about what b is. Consider the numbers ka + 1, ka + 2, ..., ka + (a - 1) for a fixed k. If none of these numbers are good, we can immediately say that b is larger than (k + 1)a. Why? Suppose b = qa + r. Clearly, r ≠ 0 since a and b are coprime. Note that xa + r for all x ≥ q will be the good, since xa + r = (qa + r) + (x - q)a = b + (x - q)a. So, b cannot be less than any of the numbers ka + 1, ka + 2, ..., ka + (a - 1), or else one of these numbers would've been good, a contradiction. Note that this also means that if y is the smallest integer such that ya + 1, ya + 2, ..., ya + (a - 1) are not all bad, then there will be exactly one good number, which will be b. Also note that for all integers k > y, there will have at least one good number among ka + 1, ka + 2, ..., ka + (a - 1). Thus, we can now binary search for the value of y. In each iteration of the binary search, we need to ask at most a - 1 ≤ 19 questions, and there are at most $\text{[math]}$ iterations, so the maximum number of operations needed is 19·19 + 18 = 379 < 380.

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<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;

bool good(int n) //returns whether n can be represented as ax + by
{
	cout<<"? "<<n<<'\n';
	fflush(stdout);
	int x; cin>>x;
	return x;
}

const int N = 500000;
int main()
{
	int a, b;
	a=20;
	int t;
	cin>>t;
	while(t--)
	{
		a=20;
		for(int i = 2; i <= 19; i++)
		{
			if(good(i))
			{
				a=i;
				break;
			}
		}
		int lo = 1; int hi = N/a+2;
		while(lo<=hi)
		{
			int mid = (lo+hi)>>1;
			int pos = -1;
			for(int i = 1; i <= a - 1; i++)
			{
				if(good(mid*a+i))
				{
					pos=mid*a+i;
					break;
				}
			}
			if(pos==-1)
			{
				lo=mid+1;
			}
			else
			{
				b=pos;
				hi=mid-1;
			}
		}
		cout<<"! "<<a<<' '<<b<<'\n';
		fflush(stdout);
		//int x; cin>>x;
	}
}

Problem D2

This problem is the same as D1, but with higher constraints. Firstly, we find the value of a in 18 moves as in problem D. To proceed, we need to think about this problem from another angle. Suppose we know a number N that is good and not a multiple of a, and we can find the maximum number k such that N - ka is good, then what does this tell us? This means that N - ka is a multiple of b. Why? We know that N - ka = ax + by for some nonnegative integers x and y since N - ka is good. If x > 0, then N - (k + 1)a = a(x - 1) + by is also good, contradicting the maximality of k. Thus, x = 0 and so N - ka = by. Note that b > 0 since we choose N so that it's not a multiple of a.

To find a value of N such that N is good and not a multiple of a, it is sufficient to take 500000a - 1, since any number greater than ab - a - b is guaranteed to be good. (this is a well-known fact)

We can find the largest k such that N - ka is good via binary search, because if N - ma is not good then N - (m + 1)a can't be good. (or else if N - (m + 1)a = ax + by, then N - ma = a(x + 1) + by) This takes at most 19 questions.

What to do after finding a value which is a multiple of b? Let C = N - ka. We consider the prime factorization of C. The main claim is that if $\text{[math]}$ is good, then x must be a multiple of b. The reasoning is the same as what we did before. So, we can find the prime factorization of C, and divide the prime factors one by one. If the number becomes bad, we know that the prime factor cannot be removed, and proceed to the next prime factor. Since a number less than 10000000 can have at most 23 prime factors (maximum is 2²³), so this takes another 23 questions.

Thus, we only used at most 18 + 19 + 23 = 60 questions to find the values of a and b.

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<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;

bool good(int n) //returns whether n can be represented as ax + by
{
	cout<<"? "<<n<<'\n';
	fflush(stdout);
	int x; cin>>x;
	return x;
}

struct NumberTheory
{
	vector<ll> primes;
	vector<bool> prime;
	vector<ll> totient;
	vector<ll> sumdiv;
	vector<ll> bigdiv;
	void Sieve(ll n)
	{
		prime.assign(n+1, 1);
		prime[1] = false;
		for(ll i = 2; i <= n; i++)
		{
			if(prime[i])
			{
				primes.pb(i);
				for(ll j = i*2; j <= n; j += i)
				{
					prime[j] = false;
				}
			}
		}
	}
	
	ll phi(ll x)
	{
		map<ll,ll> pf;
		ll num = 1; ll num2 = x;
		for(ll i = 0; primes[i]*primes[i] <= x; i++)
		{
			if(x%primes[i]==0)
			{
				num2/=primes[i];
				num*=(primes[i]-1);
			}
			while(x%primes[i]==0)
			{
				x/=primes[i];
				pf[primes[i]]++;
			}
		}
		if(x>1)
		{
			pf[x]++; num2/=x; num*=(x-1);
		}
		x = 1;
		num*=num2;
		return num;
	}
	
	bool isprime(ll x)
	{
		if(x==1) return false;
		for(ll i = 0; primes[i]*primes[i] <= x; i++)
		{
			if(x%primes[i]==0) return false;
		}
		return true;
	}

	void SievePhi(ll n)
	{
		totient.resize(n+1);
		for (int i = 1; i <= n; ++i) totient[i] = i;
		for (int i = 2; i <= n; ++i)
		{
			if (totient[i] == i)
			{
				for (int j = i; j <= n; j += i)
				{
					totient[j] -= totient[j] / i;
				}
			}
		}
	}
	
	void SieveSumDiv(ll n)
	{
		sumdiv.resize(n+1);
		for(int i = 1; i <= n; ++i)
		{
			for(int j = i; j <= n; j += i)
			{
				sumdiv[j] += i;
			}
		}
	}
	
	ll getPhi(ll n)
	{
		return totient[n];
	}
	
	ll getSumDiv(ll n)
	{
		return sumdiv[n];
	}
	
	ll modpow(ll a, ll b, ll mod)
	{
		ll r = 1;
		if(b < 0) b += mod*100000LL;
		while(b)
		{
			if(b&1) r = (r*a)%mod;
			a = (a*a)%mod;
			b>>=1;
		}
		return r;
	}
	
	ll inv(ll a, ll mod)
	{
		return modpow(a, mod - 2, mod);
	}
	
	ll invgeneral(ll a, ll mod)
	{
		ll ph = phi(mod);
		ph--;
		return modpow(a, ph, mod);
	}
	
	void getpf(vector<ii>& pf, ll n)
	{
		for(ll i = 0; primes[i]*primes[i] <= n; i++)
		{
			int cnt = 0;
			while(n%primes[i]==0)
			{
				n/=primes[i]; cnt++;
			}
			pf.pb(ii(primes[i], cnt));
		}
		if(n>1)
		{
			pf.pb(ii(n, 1));
		}
	}

	//ll op;
	void getDiv(vector<ll>& div, vector<ii>& pf, ll n, int i)
	{
		//op++;
		ll x, k;
		if(i >= pf.size()) return ;
		x = n;
		for(k = 0; k <= pf[i].se; k++)
		{
			if(i==int(pf.size())-1) div.pb(x);
			getDiv(div, pf, x, i + 1);
			x *= pf[i].fi;
		}
	}
};

NumberTheory nt;

const int N = 500000;
int main()
{
	nt.Sieve(N+1);
	int a, b;
	a=20;
	int t; cin>>t;
	while(t--)
	{
		a=20;
		for(int i = 2; i <= 19; i++)
		{
			if(good(i))
			{
				a=i;
				break;
			}
		}
		int MX = N*a-1;
		int lo = 1; int hi = N-1;
		int ans = 0;
		while(lo<=hi)
		{
			int mid=(lo+hi)>>1;
			if(good(MX-mid*a))
			{
				ans=mid;
				lo=mid+1;
			}
			else
			{
				hi=mid-1;
			}
		}
		int big = MX - ans*a; //this thing is a multiple of b
		vector<ii> ppf;
		nt.getpf(ppf, big);
		for(int i = 0; i < ppf.size(); i++)
		{
			int p = ppf[i].fi;
			while(big%p==0)
			{
				if(!good(big/p)) break;
				big/=p;
			}
		}
		b=big;
		cout<<"! "<<a<<' '<<b<<'\n';
		fflush(stdout);
		//int x; cin>>x;
	}
}

Problem E

Firstly, note that a connected graph on n vertices with n edges contains exactly 1 cycle. Call the vertices on the cycle the cycle vertices. From each cycle vertex, there's a tree rooted at it. Thus, call the remaining vertices the tree vertices. Note that the number of useless edges is equal to the length of the cycle.

Now, we do some casework :

u is equal to a tree vertex

Note that this will not change the length of the cycle. Thus, we just have to count how many ways are there to change the value of a_u such that the graph remains connected. The observation is that for each tree node u, the only possible values of a_u are the nodes which are not in the subtree of u in the tree u belongs to. Thus, the number of possibilities can be calculated with a tree dp. For each tree, we calculate the subtree size of each node and add all these subtree sizes and subtract this from the total number of ways to choose a non-tree vertex u and choosing the value of a_u. This part can be done in O(n) time.

u is equal to a cycle vertex

For two cycle vertices u and v, let d(u, v) be the directed distance from u to v (We consider the distance from u to v in the functional graph $\text{[math]}$ for all 1 ≤ i ≤ n). Note that if we change a_u to x, and the root of the tree x is in is v (x = v is x is a cycle vertex), then the length of the cycle after the change will be d(v, u) + 1 + h[x], where h[x] is the height of x in its tree. The key is instead of fixing u and iterate through all other nodes x, we iterate through all endpoints x and see how it changes our answer. Note that if x is fixed, which also means that v is fixed, then we just have to add 1 to the answer for c = d(v, u) + 1 + h[x] for all cycle vertices u. However, note that d(v, u) ranges from 0 to C - 1 (where C denotes the length of the original cycle), so this is equivalent to adding 1 to the answer for c = h[x] + 1, h[x] + 2, ..., h[x] + C. Now, we can iterate through all vertices x and add 1 to the answer for c = h[x] + 1, h[x] + 2, ..., h[x] + C. To do this quickly, we can employ the "+1, -1" method. Whenever we want to add 1 to a range [l, r], we add 1 to ans_l and subtract 1 from ans_r + 1. Then, to find the actual values of the ans array, we just have to take the prefix sum of the ans array.

Finally, do not forget to subtract the cases where v = a_u from the answer. The total complexity is O(n).

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<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 = 1000011;

bool iscycle[N];
int visited[N];
ll ans[N];
int n;
vi adj[N];
int a[N];
vi cyc;
ll subsize[N];
vector<vector<ll> > vec; //nodes sorted by height
ll subsizesum;

void dfs2(int u)
{
	cyc.pb(u);
	iscycle[u]=1;
	visited[u] = 3;
	if(visited[a[u]] == 3) return ;
	dfs2(a[u]);
}

void findcyc(int u)
{
	visited[u] = 2;
	if(visited[a[u]] == 0)
	{
		findcyc(a[u]);
	}
	else if(visited[a[u]] == 1)
	{
		visited[u] = 1;
		return ;
	}
	else
	{
		dfs2(u);
	}
	visited[u] = 1;
}

void upd(int l, int r, ll s)
{
	ans[r+1]-=s;
	ans[l]+=s;
}

int ptr;
void dfs(int u, int d)
{
	if(vec[ptr].size()<=d) vec[ptr].pb(0);
	vec[ptr][d]++;
	subsize[u]=1;
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i];
		dfs(v,d+1);
		subsize[u]+=subsize[v];
	}
	if(d>0) subsizesum+=subsize[u];
}

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		//cin>>a[i];
		scanf("%d", a + i);
		a[i]--;
	}
	findcyc(0);
	memset(visited,0,sizeof(visited));
	for(int i = 0; i < n; i++)
	{
		if(!(iscycle[a[i]]&&iscycle[i]))
		{
			adj[a[i]].pb(i);
		}
	}
	vec.resize(int(cyc.size()));
	int c = cyc.size();
	for(int i = 0; i < cyc.size(); i++)
	{
		dfs(cyc[i],0);
		ptr++;
	}
	upd(c,c,ll(n-1)*ll(n-c) - subsizesum);
	for(int i = 0; i < c; i++)
	{
		for(int j = 0; j < vec[i].size(); j++)
		{
			//j is the height
			upd(j+1,j+c,vec[i][j]);
		}
	}
	upd(c,c,-c); //subtract original cycle edges
	ll cur=0;
	for(int i = 1; i <= n; i++)
	{
		cur+=ans[i];
		printf("%I64d ", cur);
	}
}

	Rev.	Lang.	By	When	Δ	Comment
	en2		zscoder	2017-01-20 16:44:50	33
	en1		zscoder	2017-01-20 16:33:43	21213	Initial revision (published)

Problem A

Problem B

Problem C

Problem D1

Problem D2

Problem E

History