Educational Codeforces Round 129 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))
    
    print('Alice' if max(a) >= max(b) else 'Bob')
    print('Alice' if max(a) > max(b) else 'Bob')

1681B - Card Trick

Idea: BledDest

Tutorial

Solution (awoo)

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = int(input())
	print(a[sum(map(int, input().split())) % n])

1681C - Double Sort

Idea: BledDest

Tutorial

Solution (awoo)

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	tmp = [i for i in range(n)]
	tmp.sort(key=lambda i: [a[i], b[i]])
	for i in range(n - 1):
		if a[tmp[i]] > a[tmp[i + 1]] or b[tmp[i]] > b[tmp[i + 1]]:
			print("-1")
			break
	else:
		ans = []
		for i in range(n - 1):
			for j in range(n - 1):
				if a[j] > a[j + 1] or b[j] > b[j + 1]:
					a[j], a[j + 1] = a[j + 1], a[j]
					b[j], b[j + 1] = b[j + 1], b[j]
					ans.append([j + 1, j + 2])
		print(len(ans))
		for it in ans:
			print(*it)

1681D - Required Length

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

int main()
{   
    int n;
    cin >> n;
    long long v;
    cin >> v;
    queue<long long> q;
    map<long long, int> dist;
    dist[v] = 0;
    q.push(v);
    while(!q.empty())
    {
        long long k = q.front();
        q.pop();
        string s = to_string(k);
        if(s.size() == n)
        {
            cout << dist[k] << endl;
            return 0;
        }
        for(auto x : s)
        {
            if(x == '0') continue;
            long long w = k * int(x - '0');
            if(!dist.count(w))
            {
                dist[w] = dist[k] + 1;
                q.push(w);
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

1681E - Labyrinth Adventures

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF64 = 1e18;

typedef pair<int, int> pt;
#define x first
#define y second

int main() {
	int n;
	scanf("%d", &n);
	vector<vector<pt>> d(n - 1, vector<pt>(2));
	forn(i, n - 1) forn(j, 2){
		scanf("%d%d", &d[i][j].x, &d[i][j].y);
		--d[i][j].x, --d[i][j].y;
	}
	int lg = 1;
	while ((1 << lg) < n - 1) ++lg;
	vector<vector<vector<vector<long long>>>> dp(n - 2, vector<vector<vector<long long>>>(lg, vector<vector<long long>>(2, vector<long long>(2, INF64))));
	forn(i, n - 2) forn(k, 2){
		dp[i][0][0][k] = abs(d[i][0].x + 1 - d[i + 1][k].x) + abs(d[i][0].y - d[i + 1][k].y) + 1;
		dp[i][0][1][k] = abs(d[i][1].x - d[i + 1][k].x) + abs(d[i][1].y + 1 - d[i + 1][k].y) + 1;
	}
	for (int l = 1; l < lg; ++l) forn(i, n - 2) forn(j, 2) forn(k, 2) forn(t, 2) if (i + (1 << (l - 1)) < n - 2){
		dp[i][l][j][k] = min(dp[i][l][j][k], dp[i][l - 1][j][t] + dp[i + (1 << (l - 1))][l - 1][t][k]);
	}
	int m;
	scanf("%d", &m);
	forn(_, m){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		--x1, --y1, --x2, --y2;
		int l1 = max(x1, y1), l2 = max(x2, y2);
		if (l1 > l2){
			swap(l1, l2);
			swap(x1, x2);
			swap(y1, y2);
		}
		if (l1 == l2){
			printf("%d\n", abs(x1 - x2) + abs(y1 - y2));
			continue;
		}
		vector<long long> ndp(2);
		ndp[0] = abs(x1 - d[l1][0].x) + abs(y1 - d[l1][0].y);
		ndp[1] = abs(x1 - d[l1][1].x) + abs(y1 - d[l1][1].y);
		for (int i = lg - 1; i >= 0; --i) if (l1 + (1 << i) < l2){
			vector<long long> tmp(2, INF64);
			forn(j, 2) forn(k, 2)
				tmp[k] = min(tmp[k], ndp[j] + dp[l1][i][j][k]);
			ndp = tmp;
			l1 += (1 << i);
		}
		long long ans = INF64;
		ans = min(ans, ndp[0] + abs(d[l1][0].x + 1 - x2) + abs(d[l1][0].y - y2) + 1);
		ans = min(ans, ndp[1] + abs(d[l1][1].x - x2) + abs(d[l1][1].y + 1 - y2) + 1);
		printf("%lld\n", ans);
	}
	return 0;
}

1681F - Unique Occurrences

Idea: BledDest

Tutorial

Solution 1 (awoo)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct edge{
	int u, w;
};

int n;
vector<vector<edge>> g;
vector<vector<int>> ng;
vector<int> tin, tout, siz, ord;
int T;

vector<int> pw;

void init(int v, int p = -1){
	tin[v] = T++;
	ord.push_back(v);
	siz[v] = 1;
	for (const auto &it : g[v]){
		int u = it.u, w = it.w;
		if (u == p) continue;
		pw[u] = w;
		init(u, v);
		siz[v] += siz[u];
	}
	tout[v] = T;
}

int isp(int v, int u){
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

vector<int> nsiz;
vector<vector<int>> dp;

long long dfs(int v, int x){
	long long res = 0;
	for (int u : ng[v])
		res += dfs(u, x);
	dp[v][0] = siz[v];
	dp[v][1] = 0;
	for (int u : ng[v]) dp[v][0] -= siz[u];
	for (int u : ng[v]){
		if (pw[u] == x){
			res += dp[u][0] * 1ll * dp[v][0];
			dp[v][1] += dp[u][0];
		}
		else{
			res += dp[u][0] * 1ll * dp[v][1];
			res += dp[u][1] * 1ll * dp[v][0];
			dp[v][0] += dp[u][0];
			dp[v][1] += dp[u][1];
		}
	}
	return res;
}

int main() {
	scanf("%d", &n);
	
	g.resize(n);
	forn(i, n - 1){
		int v, u, w;
		scanf("%d%d%d", &v, &u, &w);
		--v, --u, --w;
		g[v].push_back({u, w});
		g[u].push_back({v, w});
	}
	
	T = 0;
	tin.resize(n);
	tout.resize(n);
	siz.resize(n);
	pw.resize(n, -1);
	init(0);
	
	vector<vector<int>> sv(n, vector<int>(1, 0));
	for (int v : ord) for (auto it : g[v])
		sv[it.w].push_back(v);
	
	ng.resize(n);
	nsiz.resize(n);
	dp.resize(n, vector<int>(2));
	long long ans = 0;
	forn(i, n) if (!sv[i].empty()){
		sv[i].resize(unique(sv[i].begin(), sv[i].end()) - sv[i].begin());
		vector<int> st;
		for (int v : sv[i]){
			while (!st.empty() && !isp(st.back(), v))
				st.pop_back();
			if (!st.empty())
				ng[st.back()].push_back(v);
			st.push_back(v);
		}
		ans += dfs(0, i);
		
		for (int v : sv[i]) ng[v].clear();
	}
	
	printf("%lld\n", ans);
	return 0;
}

Solution 2 (awoo)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct edge{
	int v, u, w;
};

vector<vector<edge>> t;

void add(int v, int l, int r, int L, int R, const edge &e){
	if (L >= R)
		return;
	if (l == L && r == R){
		t[v].push_back(e);
		return;
	}
	int m = (l + r) / 2;
	add(v * 2, l, m, L, min(m, R), e);
	add(v * 2 + 1, m, r, max(m, L), R, e);
}

vector<int> rk, p;
vector<int*> where;
vector<int> val;

int getp(int a){
	return a == p[a] ? a : getp(p[a]);
}

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	where.push_back(&rk[a]);
	val.push_back(rk[a]);
	rk[a] += rk[b];
	where.push_back(&p[b]);
	val.push_back(p[b]);
	p[b] = a;
}

void rollback(){
	*where.back() = val.back();
	where.pop_back();
	val.pop_back();
}

long long trav(int v, int l, int r){
	int sv = where.size();
	for (auto it : t[v]) if (it.w == 0)
		unite(it.v, it.u);
	long long res = 0;
	if (l == r - 1){
		for (auto it : t[v]) if (it.w == 1)
			res += rk[getp(it.v)] * 1ll * rk[getp(it.u)];
	}
	else{
		int m = (l + r) / 2;
		res += trav(v * 2, l, m);
		res += trav(v * 2 + 1, m, r);
	}
	while (int(where.size()) > sv) rollback();
	return res;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<edge> e(n - 1);
	forn(i, n - 1){
		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
		--e[i].v, --e[i].u, --e[i].w;
	}
	sort(e.begin(), e.end(), [](const edge &a, const edge &b){
		return a.w < b.w;
	});
	t.resize(4 * n);
	forn(i, n - 1){
		int pos = lower_bound(e.begin(), e.end(), e[i], [](const edge &a, const edge &b){
			return a.w < b.w;
		}) - e.begin();
		add(1, 0, n, 0, pos, {e[i].v, e[i].u, 0});
		add(1, 0, n, pos, pos + 1, {e[i].v, e[i].u, 1});
		add(1, 0, n, pos + 1, n, {e[i].v, e[i].u, 0});
	}
	rk.resize(n, 1);
	p.resize(n);
	iota(p.begin(), p.end(), 0);
	printf("%lld\n", trav(1, 0, n));
	return 0;
}

bool compare_first(const std::pair<int, int> &a, const std::pair<int, int> &b) { if(a.first == b.first) { return a.second < b.second; } return a.first < b.first } //---------- bool compare_second(const std::pair<int, int> &a, const std::pair<int, int> &b) { if(a.second == b.second) { return a.first < b.first; } return a.second < b.second }

function Cut(int CurL, int CurR, int &CurE): for CurE in [CurL, CurR]: cur_real_size -= size[v] append value of Cut(L[v], R[v], CurE) to real_subtree_size for val in real_subtree_size: answer += val * cur_real_size return cur_real_size // edges are sorted in dfs order, so an edge have a dfs order, you can judge whether the edge is in the subtree or not. // CurE means the index of the edge you are visiting

#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <complex> #include <queue> #include <set> #include <unordered_set> #include <list> #include <chrono> #include <random> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <map> #include <unordered_map> #include <stack> #include <iomanip> #include <fstream> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> p32; typedef pair<ll,ll> p64; typedef pair<double,double> pdd; typedef vector<ll> v64; typedef vector<int> v32; typedef vector<vector<int> > vv32; typedef vector<vector<ll> > vv64; typedef vector<vector<p64> > vvp64; typedef vector<p64> vp64; typedef vector<p32> vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "<<x<<ln #define umap unordered_map #define uset unordered_set #define mp make_pair #define pb push_back #define ppb pop_back #define fi first #define se second #define INF 2e18 #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend #define sz(x) ((ll)(x).size()) #define max3(a,b,c) max(max((a),(b)),(c)) #define max4(a,b,c,d) max(max((a),(b)),max((c),(d))) #define min3(a,b,c) min(min((a),(b)),(c)) #define min4(a,b,c,d) min(min((a),(b)),min((c),(d))) template<class T> void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ ll n,x; cin>>n>>x; map<ll,ll> dist; queue<ll> q; q.push(x); dist[x]=0; while(!q.empty()){ ll t = q.front(); q.pop(); string s = to_string(t); if(s.size()==n){ cout<<dist[t]<<"\n"; return; } for(auto c:s){ if(c=='0') continue; ll z = t*((long long)(c-'0')); if(!dist[z]){ dist[z]=dist[t]+1; q.push(z); } } } cout<<-1<<"\n"; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif fast_cin(); // ll t; // cin >> t; // for(int it=1;it<=t;it++) { solve(); // } return 0; }

#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <complex> #include <queue> #include <set> #include <unordered_set> #include <list> #include <chrono> #include <random> #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <map> #include <unordered_map> #include <stack> #include <iomanip> #include <fstream> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> p32; typedef pair<ll,ll> p64; typedef pair<double,double> pdd; typedef vector<ll> v64; typedef vector<int> v32; typedef vector<vector<int> > vv32; typedef vector<vector<ll> > vv64; typedef vector<vector<p64> > vvp64; typedef vector<p64> vp64; typedef vector<p32> vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "<<x<<ln #define umap unordered_map #define uset unordered_set #define mp make_pair #define pb push_back #define ppb pop_back #define fi first #define se second #define INF 2e18 #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend #define sz(x) ((ll)(x).size()) #define max3(a,b,c) max(max((a),(b)),(c)) #define max4(a,b,c,d) max(max((a),(b)),max((c),(d))) #define min3(a,b,c) min(min((a),(b)),(c)) #define min4(a,b,c,d) min(min((a),(b)),min((c),(d))) template<class T> void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ ll n,x; cin>>n>>x; map<ll,ll> dist; queue<ll> q; q.push(x); dist[x]=0; while(!q.empty()){ ll t = q.front(); q.pop(); string s = to_string(t); if(s.size()==n){ cout<<dist[t]<<"\n"; return; } for(auto c:s){ if(c=='0') continue; ll z = t*((long long)(c-'0')); if(!dist.count(z)){ dist[z]=dist[t]+1; q.push(z); } } } cout<<-1<<"\n"; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif fast_cin(); // ll t; // cin >> t; // for(int it=1;it<=t;it++) { solve(); // } return 0; }

Comments (64)

Show archived | Write comment?

ahanshankar

2 years ago, # |

Why does my submission(158304624) for C give WA ("Arrays are not sorted")? My approach is to store each pair of $$$a_i$$$ and $$$b_i$$$ for both sorted and original arrays and compare all pairs, since pairs can't change, and then use a simple bubble sort to print swaps. I tried testing it on cfstress but it didnt give me any counterexamples(link).

→ Reply

beethoven97

2 years ago, # ^ |

← Rev. 3 →

here is your accepted code

you must do swaps in both arrays as the problem say but you did swaps in only one array. you can compare your previous code with this new code to see the few changes.

ah I see, thanks :)

itish

Through many hacks and further FST's on problem D, my rating is now 1899 :))

ClimateX

can any body tell me why this happened? these submissions are shared the same code 158313258: GUN C++ 17 158313168: GUN C++ 14 158313129: GUN C++ 20 (!! TLE !!)

happy_new_year_2022

The C++20 GUN is NA-45 while the C++17 one is AK-47

robostac

https://codeforces.net/blog/entry/62393

Because every value you insert is a multiple of the input it's possible to make a test case that blows up unordered_map. I'm just surprised that no-one found a way to hack the older implementation (possibly the primes required have higher digits and don't insert enough values to hit the time limit).

shadow9236

Don't use unordered map

https://codeforces.net/contest/1681/submission/158319237

Read this https://codeforces.net/blog/entry/62393

Guess.Who

I've seen something like that before.

Check Here.

Niket_Bahety

Finally I became a cyan !!

riadspartanbd

For problem C the name "Double Sort" gives the hint to use Bubble Sort

rick3300

Exactly!!! I used Selection Sort in this problem during the contest and unfortunately I got WA in both the submissions, but now when I implemented the exact same logic in Bubble Sort, it got accepted. This indicates that implementation with selection sort has some complications which bubble sort doesn't have.

Juanm1

i did selection sort

mxrthx

It's easy to see that any comparison based sorting algorithm is entirely valid for this problem. If you're getting WA that means you didn't implement it correctly.

WitchOfTruth

Not sure about that. What we need is not comparison-base but stability. Any stable sort should do

BledDest

If you sort the values as pairs $$$(a_i, b_i)$$$, you don't need stability.

A comparison based sort on both array values doesn't need stability, as all entities in question will already be considered by the comparator.

something like this works just fine:

Just make two passes as follows (and track the inversions):

any_sort(arr.begin(), arr.end(), compare_first);
any_sort(arr.begin(), arr.end(), compare_second);

I got it from Bleddest's response.

It's just that my solution relied on stability

Then again, there is no need for it to be comparison-based, you can implement this with any sorting

Divyanshu1593

+10

Something really unfair happened to me in this contest... I got accused of cheating in this round ... But this is not true. I guess this happened to me because I use Python and problem A and B where really straight forward , for example in problem B , most of the line of the code is for taking input and the actual solution is only of 1 line , which can be easily be similar to someone else. (158180193 my solution of B). This kind of things should be avoided at all cost , because it demotivates the falsely accused person!

ronin07

Can someone explain how we are getting min operations with BFS in problem D. Shouldn't we sort the string before multiplying?

llll.aditya.llll

← Rev. 2 →

Basically, we are using BFS because we don't know the future digits coming into our number after multiplication. Hence we can't pick any particular path before reaching the destination(i.e number of n digits) so we will visit the all the possible numbers(the numbers that we get after multiplying the current number with all distinct digits present in the current number) if we haven't visited them yet. As we are looking for all the possibilities sorting the string won't help.

Can anyone explain to me F better? What are the transitions, mentioned in the editorial?

dkg7888

I think it is basically building Splay tree and then normal DP . So , if you don't know splay tree just go through it once . You will find a blog and video on it in CF and also on CC .

lingfunny

If you like, I can give another solution to you.

But it solves the problem from an aspect differ from the tutorial.

ap_2089

Yeh Sure, lingfunny !

Sorry for the late reply and my poor English.

Let's try to calculate the answer from the different weights.

For every kind of weight of an edge, try to figure out the value that this kind of edge contributes to the answer.

For example, in the following illustration, the contribution of edges weigh $$$2$$$ is $$$3\times1+3\times3=10$$$.

illustration_1

Why?

If we cut the every edge weighs $$$2$$$(red edges), we will get $$$3$$$ new trees.

For the edge $$$(6, 7)$$$, the new trees it connected are $$$4,5,6$$$ and $$$7$$$, so answer will add $$$1\times3$$$. Because for the paths from $$$u$$$ to $$$v$$$, where $$$u=4,5,6$$$ and $$$v=7$$$, the value $$$2$$$ will definitly appear exactly once.

For the same reason, edge $$$(4, 1)$$$ will contribute $$$3\times 3$$$ to the answer.

Obviously, the edges with different values can't influence each other, so You can calculate the different values of edges partly.

Here is how to calculate the answer of edges with same value.

Firstly, get the 'bracket order' of the tree. Let $$$L[u]$$$ and $$$R[u]$$$ be the begining and ending indices of $$$u$$$ in the 'bracket order'.

It's another kind of Euler Tour of Tree. Instead of output the number as soon as you visit a node, you will output the number only when you first visit the node or finish visiting the node.

I don't know how to translate 'bracket order' to English since I'm Chinese and my English is poor. For example, the 'bracket order' of the tree in the illustration is $$$\texttt{4 5 5 6 7 7 6 1 2 2 3 3 1 4}$$$, hope you can understand what I want to express from the example. Or maybe you can see my code in the end.

Then, for a tree, cut the edges in dfs order and split the subtrees out, and cut the edges in a subtree recursively.

When you cut the subtree recursively and update CurE, CurE is increasing and always less than $$$O(n)$$$. So the time complexity is $$$O(n)$$$.

You can see my submission to have a better understanding, I think it's quite short: 158222894

Actually I don't know whether it's violation of rules for me to type the solution in the comment. If it is, please tell me and I will delete my comment at once.

Apologise again for my poor English.

weissle

May below code can explain what is bracket order.

def bracket_order(node):  
    print(node.val)  
    for child in node.children:  
        bracket_order(child)  
    print(node.val)

Yeah, thank you, very clear.

Edlue

What is the solution to the dynamic connectivity problem mentioned in F? Is there a good tutorial or video about it?

Bungmint

Codeforces EDU DSU section last lesson where the guy talks about DSU Mo's, offline dynamic connectivity using rollback DSUs. Go check that out.

adityagamer

Where is this section?

+20

Damn I either overestimated the average people’s ability to navigate codeforces or codeforces is not as user-friendly as I thought for people whose English is not their first language, based on this comment. It’s under codeforces EDU DSU step 3 theory. link

wakaranai

-13

Apparently C++14 log10 doesn't work properly for counting digits of numbers like: $$$10^{k} - 1, (k>=15)$$$ :(

Anyone know why?

Precision issue? Doubles and long doubles have limited precision, so the rounding could be off when the value is very close to a power of 10 for large numbers. It’s better to not use doubles/long doubles if possible. Just stick with integers manipulation

keyurchd_11

If someone solved F using HLD, could you please share your approach? Here's the submission SSRS_ made using HLD: 158189118

variety-jones

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

A: Game with Cards
B: Card Trick
C: Double Sort
D: Required Length
E: Labyrinth Adventures: Under maintenance
F: Unique Occurrences

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

BERNARD

Can someone explain the solution for problem E that uses segment tree, please?

ScarletS

Newtech66

+11

The idea is to maintain a structure in each node (let's say this node represents layers $$$[i,j]$$$), that contains the following information:

shortest distance starting in front of top door of $$$i$$$-th layer and ending in front of top door leading to $$$(j+1)$$$-th layer
...3 other similar values for other combinations of top/bottom doors.

It is possible to merge the structures for ranges $$$[i,j]$$$ and $$$[j+1,k]$$$ easily (maybe not, but my code was quite sloppy).

To answer queries, if the cells are in the same layer, it will just be the distance between them. Otherwise, we can find the answer for going from $$$[\text{starting layer},\text{ending layer})$$$ and then find the time taken to get to top/bottom doors for each layer. Then the answer is just the minimum of the possibilities $$$+1$$$ (to take care of crossing the door to the $$$j$$$-th layer).

By the way, the identity element for the structures (or answer for $$$[i,i]$$$) is not all zeroes, it must be $$$\infty$$$ for top->bottom or bottom->top to maintain consistency. And some other stuff, implementation requires care I guess...

Submission: 158239579

Interesting solution, thank you for sharing!

After some time thinking about it, I realized that it's just a waste of time to implement this :(

CCPSDCGK

+19

In problem F,if you use link cut tree to maintain the size of subtrees to solve this problem,it will be much easier.(

https://codeforces.net/contest/1681/submission/158267779

winging

In problem D,you can use IDA* and you don't need to think about the problem.And it's also can solve the problem.

+32

Wow,it's fantastic,but why not show your code to let us see?

Sure.(

https://codeforces.net/contest/1681/submission/158343031

black_trees

I wonder why this submission is for problem D. :)

And anyway, I don't think you passed problem F.

because there's no submission for problem F in your submissions until now (May/26 08:14 UTC+8).

If I'm wrong, plz point it out:)

Sorry,I'm wrong.

uttaran_das

Can someone explain the O(n^2) solution of F in a more detailed way? What is i in dp(v,i)? How does the transition work? What does the phrase when you consider gluing up paths from different children mean?

And also, why are the Tutorials on the challenging problems not elaborative enough? Those are written in a way that is tough to follow for Pupils or Specialists.

awoo

+49

I think that Pupils or Specialists just won't gain anything from upsolving the problem. You won't develop the intuition for similar problems by retyping the transitions in dp from the editorial. It's probably better to go solve easier tree dp problems first, learn different ways of counting the paths in trees, and then tackle this problem.

+14

Thank you for the reply. As a modest suggestion, I think it would be a good thing to keep some prerequisite sections in the tutorials (or link to a blog[in case of common techniques/Algo/DS] or the same kind of easier problem) to understand the concepts behind the main problems better.

Once again, thank you for writing these problems, it's always good to learn new things through solving problems.

swarup_312

Problem C:

Can Someone Explain me ! Why My Code Failed

Wrong Answer on test 2 (test case 65) 158363800

lavish315

It is usually beneficial if you can find a smaller test case where your code fails, and then try to figure out where your code is wrong.

Edit — Test case:

1
6
5 4 5 5 4 5
3 2 2 5 2 3

rahulc29

Hi, I would really appreciate it if somebody could tell me why my code doesn't work for C.

Let me explain my approach.

Bubble sort $$$a$$$ and for every $$$i$$$, $$$j$$$ that is swapped in $$$a$$$, swap it in $$$b$$$ as well. Store all pairs $$$(i,j)$$$.
After this bubble sort, $$$a$$$ is guaranteed to be sorted
If $$$b$$$ is also sorted then we are done and dump out the swapping indices stored in step 1
If $$$b$$$ is not sorted, we can still sort it if all the swaps necessary to make $$$b$$$ sorted, have the property that $$$a_i = a_j$$$.
Run bubble sort again on $$$b$$$ and check if a swap has been made for which $$$a_i \neq a_j$$$, if so, report $$$-1$$$, else continue with the sort
If our algorithm has still not terminated it is guaranteed that $$$b$$$ is sorted and $$$a$$$ is also sorted, so it is possible and we dump out all the indices we had stored.

The judge says my algorithm produces a case in which $$$b$$$ is apparently not correct. My code is here.

If you're able to come up with a counter-example, I'd really appreciate it if you can tell me what motivated it, I'm still improving my ability to think of counter-examples.

The following approach usually helps me in finding out a counter example:

First of all, try to go through the approach and at each step, ask if what you are doing is correct. Is there some case where your assumption is failing? Is there some case where your expected result will not hold.

Once you are confident that your approach is correct (on paper), try to go through the code and check if each block is behaving exactly how you want it to behave. You can usually check by taking some small examples.

The above process usually helps me finding out the blocks where my approach might be wrong, and gradually helps in getting a counter case.

Try with the above approach once for some time. If you are not able to find some counter case after enough efforts, this test case generated by CF Stress might help.

rurixx

I have solved the problem with exactly the same logic: 158188911

So, algorithm is ok, check your code.

In editorial of D: I don't understand that is sufficient to say time limit won't exceed. We have 1.5 million states in total. But they can be called multiple times.

Can somebody explain its time complexity please?

mac

Each 1.5 million states can have at most 9 outgoing edges because you could multiply that state with 1,2,3,...9

So number of edges in the graph is upper bounded by 1.5*9

dutin

It seems that tourist solved F — Unique Occurences with rollback DSU (submission). Can somebody explain this method?

As a side note, it seems that all top participants did not use the intended solution for F.

Dakto

+26

I've got a significantly shorter $$$O(n)$$$ solution for F.

I'm really bad at explaining, but let me try. The basic idea is similar to the second solution in the editorial. If we split the graph by each edge weight at a time, the answer is the sum of products of sizes of each pair of components that were formerly connected by an edge (neighbour components from now on).

This can be calculated in a single DFS. Now, when we are processing vertex $$$u$$$, which is connected with it's parent with an edge of type $$$x$$$, we're gonna calculate the answer for the pairs of components (the component that contains $$$u$$$, it's "son" components aka all components it neighbours except the one that contains its parent) when split by edges of type $$$x$$$. This value can be calculated pretty simply — the size of the component with $$$u$$$ is the size of $$$u$$$'s subtree — the sum of sizes of subtrees of descendants of $$$u$$$ whose parent edges are of type $$$x$$$. The neighbour components are similar, just shifted by one more level.

In the end we need to explicitly handle the root as if it had all types of edges going upwards.

Hopefully reading the code should clear it up: 158219114

NafisAlam

Can anyone give me a hint on how can we minimize the number of swaps on Problem C? thanks

KalbiatAman

If you use bubble sort you will do at most n*(n-1)/2 swaps. If you construct your algorithm by using bubble sort twice, at most it will do n*(n-1) swaps. For n=100 and a threshold of 10^4, it's more than enough.

In code for problem D. Why we are not updating the dist[w] with dist[k] + 1 when w exists in the map?

Phoenix76

As we only need the shortest distances, if we have already visited a node, we won't visit it again.

Hi! For the Problem D, could anyone tell why the first one gives WA, but not the second? The first uses a !map[x], while second uses !map.count(x). Why do these behave differently?

awoo's blog