Educational Codeforces Round 65 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	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

Idea: Roms

Tutorial

Solution (Roms)

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    int tc;
    cin >> tc;
    for(int t = 0; t < tc; ++t){
        cin >> n >> s;
        int pos = n;
        for(int i = 0; i < n; ++i)
            if(s[i] == '8'){
                pos = i;
                break;
            }
            
        if(n - pos >= 11)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
	return 0;
}

1167B - Lost Numbers

Idea: vovuh

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

vector<int> p = {4, 8, 15, 16, 23, 42};
int ans[4];

int main()
{
	for(int i = 0; i < 4; i++)
	{
		cout << "? " << i + 1 << " " << i + 2 << endl;
		cout.flush();
		cin >> ans[i];
	}
	do
	{
		bool good = true;
		for(int i = 0; i < 4; i++)
			good &= (p[i] * p[i + 1] == ans[i]);
		if(good) break;
	}
	while(next_permutation(p.begin(), p.end()));
	cout << "!";
	for(int i = 0; i < 6; i++)
		cout << " " << p[i];
	cout << endl;
	cout.flush();
	return 0;
}

1167C - News Distribution

Idea: MikeMirzayanov

Tutorial

Solution (BledDest)

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

const int N = 1000043;
vector<int> g[N];

int color[N];
int siz[N];
int n, m;
int cc = 0;

int dfs(int x)
{
	if(color[x])
		return 0;
	color[x] = cc;
	int ans = (x < n ? 1 : 0);
	for(auto y : g[x])
		ans += dfs(y);
	return ans; 
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++)
	{
		int k;
		scanf("%d", &k);
		for(int j = 0; j < k; j++)
		{
			int x;
			scanf("%d", &x);
			--x;
			g[x].push_back(i + n);
			g[i + n].push_back(x);
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(!color[i])
		{
			cc++;
			siz[cc] = dfs(i);
		}
		printf("%d ", siz[color[i]]);
	}
}

Solution (PikMike)

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;

int n, m;
int rk[N], p[N];

int getP(int a){
	return (a == p[a] ? a : p[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);
	p[b] = a;
	rk[a] += rk[b];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n) p[i] = i, rk[i] = 1;
	
	forn(i, m){
		int k;
		scanf("%d", &k);
		int lst = -1;
		forn(j, k){
			int x;
			scanf("%d", &x);
			--x;
			if (lst != -1)
				unite(x, lst);
			lst = x;
		}
	}
	
	forn(i, n)
		printf("%d ", rk[getP(i)]);
	puts("");
}

1167D - Bicolored RBS

Idea: adedalic

Tutorial

Solution (adedalic)

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

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

int n;
string s;

inline bool read() {
	if(!(cin >> n))
		return false;
	cin >> s;
	return true;
}

inline void solve() {
	string t(n, '0');
	
	int bal = 0;
	fore(i, 0, n) {
		if(s[i] == ')')
			bal--;
		
		t[i] = char('0' + (bal & 1));
		
		if(s[i] == '(')
			bal++;
	}
	
	cout << t << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1167E - Range Deleting

Idea: Roms

Tutorial

Solution (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e6) + 99;
int n, x;
int a[N];
vector <int> pos[N];
int prefMax[N];

int main() {
	scanf("%d %d", &n, &x);
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		pos[a[i]].push_back(i);	
		prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i]));
	}
	
	int p = 1;
	int lst = n + 5;
	for(int i = x; i >= 1; --i){
		if(pos[i].empty()){
		    p = i;
		    continue;
		}
		if(pos[i].back() > lst) break;
		p = i;
		lst = pos[i][0];
	}	

	long long res = 0;
	lst = -1;
	for(int l = 1; l <= x; ++l){
		int r = max(l, p - 1);
		if(lst != -1) r = max(r, prefMax[lst]);
		res += x - r + 1;
		if(!pos[l].empty()){
    		if(pos[l][0] < lst) break;
    		lst = pos[l].back();
		}
	}	

	cout << res << endl;
	return 0;
}

1167F - Scalar Queries

Idea: adedalic

Tutorial

Solution (adedalic)

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

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

const int MOD = int(1e9) + 7;

int add(int a, int b) {
	a += b;
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}

int n;
vector<int> a;

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore(i, 0, n)
		cin >> a[i];
	return true;
}

vector<li> f;
void inc(int pos, int val) {
	for(; pos < sz(f); pos |= pos + 1)
		f[pos] += val;
}
li sum(int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[pos];
	return ans;
}

vector<int> S[2];

inline void solve() {
	fore(k, 0, 2) {
		S[k].assign(n, 0);
		f.assign(n, 0);
		
		vector<int> dx(a.begin(), a.end());
		sort(dx.begin(), dx.end());
		
		fore(i, 0, n) {
			int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin());
			S[k][i] = int(sum(pos) % MOD);
			inc(pos, i + 1);
		}
		reverse(a.begin(), a.end());
	}
	
	reverse(S[1].begin(), S[1].end());
	int ans = 0;
	fore(i, 0, n) 
		ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 1)))));
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1167G - Low Budget Inception

Idea: adedalic

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = 200 * 1000 + 555;
const int D = 7077;

int n, d, m;
int a[N], qs[N];

inline bool read() {
	if(scanf("%d%d", &n, &d) != 2)
		return false;
	fore(i, 0, n)
		scanf("%d", &a[i]);
	
	assert(scanf("%d", &m) == 1);
	fore(i, 0, m)
		scanf("%d", &qs[i]);
	return true;
}

bitset<D> L, R, cur;
int dist[N];
set<int> has;

void shiftL(int s, int t, int &uk) {
	L <<= t - s;
	for(; uk < n && a[uk] < t; uk++) {
		if(t - a[uk] - 1 < D)
			L[t - a[uk] - 1] = 1;
		if(t - a[uk] < D)
			L[t - a[uk]] = 1;
	}
}

void shiftR(int s, int t, int &uk) {
	R >>= t - s;
	if(!has.count(t))
		R[0] = 0;
	
	for(; uk < n && a[uk] < t + D; uk++) {
		if(a[uk] - t >= 0) {
			R[a[uk] - t] = 1;
			if(a[uk] - t + 1 >= 0)
				R[a[uk] - t + 1] = 1;
		}
	}
}

inline void solve() {
	fore(i, 0, m) {
		dist[i] = INF;
		int pos = int(lower_bound(a, a + n, qs[i]) - a);
		if(pos > 0)
			dist[i] = qs[i] - a[pos - 1] - 1;
		if(pos < n)
			dist[i] = min(dist[i], a[pos] - qs[i]);
	}
	has = set<int>(a, a + n);
	
	int uL = 0, uR = 0;
	L.reset();
	R.reset();
	fore(i, 0, m) {
		shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL);
		shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR);
		
		double ans = atan2(1, dist[i]);

		cur = L & R;
		int pos = (int)cur._Find_first();
		if(pos < D) {
			int ds = pos;
			ans = max(ans, 2 * atan2(1, ds));
		}
		printf("%.15f\n", ans);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Comments (37)

Show archived | Write comment?

DomiKo

5 years ago, # |

+32

Editorial of F is soooo goooooddd. thx man

→ Reply

farmersrice

← Rev. 5 →

+19

F is a little overcomplicated I think. Easier way to think about it is to see that every contribution of the lower-valued items on the left is that their contribution is just the number of spaces on the left of each of them plus one (if example $$$a_j < a_i$$$ and $$$j < i$$$, contribution is $$$j + 1$$$, since this is the number of intervals that the lower-valued item gets included in). Multiply this by the number of intervals on the right (n - index), since it contributes that many more times. Then easy done. Do this with the segment tree by updating the position index in fenwick tree with itself to get contribution over all of them fast (contribution from left side is query(index) * (n - index)). Then do same thing on the right side. (All values are zero indexed in this explanation)

UPD: Ok, someone has asked for a clearer explanation, so I have taken a little more time to write it out. It is very large, so I spoilered it.

better explanation

Each number contributes to the final sum a certain number of times (multiplier, or coefficient). So the end result is sum of all $$$a_i * mult_i$$$ where a is our array. We will explain this with zero indexing.

First, note that the total number of items to the left of index $$$i$$$, including $$$i$$$, is just $$$i + 1$$$, and the total number of items on the right, including $$$i$$$, is $$$n - i$$$.

Now we consider that the multiplier is contributed to by $$$(i + 1) * (n - i)$$$, because this is the total number of segments the number is included in.

Now consider the cases where contribution is increased by an element less than our current element at position $$$i$$$ in the array. Let's call this element as having position $$$j$$$.

Add to the multiplier the number of contributions from the left hand side: each number on the left hand side less than us contributes to the multiplier by the number of times it is seen. This is equal to the number of spaces on the left of the number, including that number. Then multiply this count by the number of items on the right, including the one at position $$$i$$$, because this is the number of segments in which $$$a_j$$$ is included. This contribution will be $$$(j + 1) * (n - i)$$$.

A similar thing happens with the right hand side, except on the right hand side the contribution to the coefficient is $$$(i + 1) * (n - j)$$$.

Now we have to compute these values for all $$$j$$$ in fast time. We can do this with a fenwick tree (also called BIT, binary indexed tree) or segment tree. Process the values from small to large and keep two fenwick trees. When you have finished processing index $$$i$$$, just update the fenwick tree representing the left nodes with $$$i + 1$$$ at index i, and update the right fenwick tree with $$$n - i$$$. Then, we can query really fast, because we only need the sum of the values given by each individual $$$a_j$$$ to find the final multiplier.

The final multiplier will be (i + 1) * (n - i) + leftTree.queryRange(0, i - 1) * (n - i) + rightTree.queryRange(i + 1, n - 1) * (i + 1), where queryRange is inclusive.

Jackie_Chen

5 years ago, # ^ |

wouldn't this solution overcount?

ohhhh nevermind this is genius thank you!

atsumumiya

just a minor correction in last line: (i + 1) * (n — i) + leftTree.queryRange(0, i) * (n — i) + rightTree.queryRange(i + 1, n) * (i + 1) . Thnx for the explanation.

Oh shoot, thanks!!!

(also there were some other typos in that last line i corrected)

Bug_Debug

Please explain problem C .The problem as well as input ,output is not clear to me. How become the output 4 4 1 4 4 2 2 for sample test case ?

nilesh8757

← Rev. 2 →

Use some pen & paper, you'll get eventually.

sea_26

Read the problem attentively, you'll understand input & output.

pasthec

Firstly you read the number of people and the number of groups, then for each group you read the which people belong to this group. In then end for each people $$$i$$$ you wish to find the number of people that are share a group with $$$i$$$.

motatoes

Can problem C be solved using DSU data structure ?

GustavoGuerra

← Rev. 3 →

Yes. Initially, you want to add everyone in a group of friends do the same component. Then, when someone is into another group, you connect the components.

This is exactly what the editorial says in the last line.

vagi

I think one person cannot be in more than one component as if he's in more than one component those components cannot be disjoint as he'll be friends with people from both components. I'm still not very clear about problem C. Can somebody explain the solution once.

Let's say there are two main groups on the input: group A consisting of p, q and r and group B with two other guys: u and v.

If the next line of the input says that there exists another group, C, consisting of r and u, that means there's an edge connecting them and, therefore, their groups. Now, there is a connection between p and q with r, from r to u (just became friends), and from u to v.

That means we need a fast way to unite those disjoint sets of friends.

In the end, we are required to say how many people will know about the news if person i starts spreading it. From the statement, we know that one guy tells the news to everyone in his groups of friends, so we only need to print the size of the component containing i-th person.

You can check my submission (54194939). It's pretty easy to read and there are lots of comments.

Thanks for the explanation! I get it now

time_to_dual

I'm really sad that this is the first time I did an interactive problem and the tutorial in the contest show fflush(stdout) to flush output in C++. I kept getting idleness error in the contest and couldn't figure out why (WA is much easier to deal with). After this editorial released, I changed fflush(stdout) to cout.flush() and I could debug my old code in a blink. You guys should update the tutorial for the interactive problem. It was frustrating.

tfg

No. It's your fault for using IO optimizations without understanding what they do minimally. https://codeforces.me/contest/1167/submission/54261003 fflush + commenting the optimizations.

My tip is always using endl instead of '\n' since code stays the same and endl flushes the output. Example: https://codeforces.me/contest/1167/submission/54205213

With this being said this is worth mentioning in that blog.

Thanks. Now I know. Good lesson tho.

Errichto

Use endl only in interactive problems! It's slow so you risk TLE.

I meant always using endl in interactive problems, my bad I was careless in the comment.

Rogue33

If you use cout and endl then you don't need an extra cout.flush() in C++.

GrandDaddy

The link to this blog has not yet been mentioned in the contest page. Should you not add it to the contest page as soon as the editorial is published? Just asking.

the_annoying_

For Lost Numbers I used almost the same trick.But struck with one problem.I was using GCD to get to know unique number but it turns out that it is not.let say the array is [a,b,c,d,e,f] and x=a*b and y=b*c .So GCD(x,y) should give me "b" but i was getting multiple of b.So is there a way to resolve this issue.Thanks is advance.

ehnryx

gcd(x,y) gives you b only if gcd(a,c)=1. Otherwise, it will give you gcd(a,c)*b, which is a multiple of b.

Pratibha._899

The explanation to the solution of problem C is not very clear. Can someone explain the approach in simpler words ?

Use a DSU to connect all of the groups. This can be done in O(group size) for each group by connecting the first person in each group to everyone else. Then find the size of the group each person is in to get the answer.

I managed to pass G with 2 pointers (breaking early helped a lot). I do prefer the editorial solution though. Thanks!

Tutis

Why is it enough to maintain 7000 positions to the left and right?

awoo

Oh, I totally forgot to mention this in editorial. Basically, positions further than that won't ever be needed. Check the angle you get for the closest collision between a building and a ray. It's less or equal to $$$arctan(\frac 1 {3500})$$$. Find the maximum $$$x$$$ such that $$$2 arctan (\frac 1 x) > arctan (\frac 1 {3500})$$$ so that two buildings collinding produce greater angle. That $$$x$$$ is 7000, thus further collisions will never affect the answer.

lsr10122018

Can someone explain the editorial of problem E (Range Deleting)?
Having a difficult time to understand it or is there any other approach which is simpler and easy to explain.

snehalgupta

Hello, I solved Problem C using DFS in Java. I saw one "Accepted" submission in GNU C++ with the same logic. I am getting time limit exceeded on test case 6. I have tried to speed up the code as much as possible. Is it possible that the same solution in Java gives a time limit but not in GNU C++?

imhemant

Whenever your program might go in deep recursion or dfs you might get RunTime Error. This is due to StackOverFlow Error. As stack size of Java is very low, hence, either you should avoid deep recursion and use iteration or increase stack size dynamically.

Source :

_Anas__

Problem F

Many people got WA on test 35 (me too) as we didn't mod while adding inside BIT

dreamplayDaddy

awoo adedalic
Can you please explain the editorial of problem E (Range Deleting)? Not able to get it

RaghavS

can anyone explain problem D properly?? here is my solution.. and it is getting wrong on test case 17Your text to link here...

SJMormo

54435380 In C, Why am I getting memory limit over and over again? Can anyone please help?

You are declaring a vector of size z inside you for loop — and you are doing it m times. Two global arrays of size 5*1e5 and m vectors with variable sizes (but sum equal to 1e5) are using too much memory.

You can declare the vector "vec" outside of the for loop and just reuse it — or don't use it at all.

kush_76

here is my submission of problem C News Distribution http://codeforces.me/problemset/submission/1167/55075296 please, can someone tell what's wrong in it its showing tle and I don't know why?

awoo's blog