Разбор Educational Codeforces Round 73

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

1221A - Игра 2048

Идея: Roms

Разбор

Решение (Roms)

for t in range(int(input())):
	n = input()
	l = filter(lambda x : x <= 2048,  map(int, input().split()) )
	print('YES' if sum(l) >= 2048 else 'NO')

1221B - Кони

Идея: BledDest

Разбор

Решение (PikMike)

n = int(input())
for i in range(n):
	print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))

1221C - Идеальная команда

Идея: Roms

Разбор

Решение 1 (BledDest)

t = int(input())
for i in range(t):
	c, m, x = map(int, input().split())
	d = max(c, m) - min(c, m)
	x += d
	if(c > m):
		c -= d
	else:
		m -= d
	ans = min(c, m, x)
	c -= ans
	m -= ans
	x -= ans
	ans += (c + m) // 3
	print(ans)

Решение 2 (PikMike)

#include <bits/stdc++.h>

using namespace std;

int main(){
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i){
		int c, m, x;
		cin >> c >> m >> x;
		int l = 0, r = min(c, m);
		int ans = 0;
		while (l <= r){
			int mid = (l + r) / 2;
			if (c + m + x - 2 * mid >= mid){
				l = mid + 1;
				ans = mid;
			}
			else{
				r = mid - 1;
			}
		}
		cout << ans << "\n";
	}
}

1221D - Сделаем забор великим снова

Идея: Roms

Разбор

Решение (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const long long INF64 = (long long)(1e18) + 100;

int t;
int n;
int a[N];
int b[N];
long long dp[3][N];

long long calc(int add, int pos){
	long long &res = dp[add][pos];
	if(res != -1) return res;

	res = INF64;
	if(pos == n) return res = 0;
	for(long long x = 0; x <= 2; ++x)
		if(pos == 0 || a[pos] + x != a[pos - 1] + add)
			res = min(res, calc(x, pos + 1) + x * b[pos]);
		
	return res;
}

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			scanf("%d", b + i);
		}

		for(int i = 0; i <= n; ++i) 
			dp[0][i] = dp[1][i] = dp[2][i] = -1;				
		printf("%lld\n", calc(0, 0));
	}
	return 0;
}

1221E - Игра со строкой

Идея: Roms

Разбор

Решение (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;

int t;
int a, b;
string s;

int main() {
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b >> s;
		vector <int> v;
		int l = 0;
		while(l < s.size()){
			if(s[l] == 'X'){
				++l;
				continue;
			}

			int r = l + 1;
			while(r < s.size() && s[r] == '.') ++r;
			v.push_back(r - l);
			l = r;
		}
		
		bool ok = true;
		int id = -1;
		int cnt = 0;
		for(int i = 0; i < v.size(); ++i){
			if(b <= v[i] && v[i] < a) ok = false;
			if(b + b <= v[i]){
				if(id == -1) id = i;
				else ok = false;
			}
			if(a <= v[i] && v[i] < b + b) ++cnt; 
		}

		if(!ok){
			cout << "NO" << endl;			
			continue;
		}

		if(id == -1){
			if(cnt & 1) cout << "YES" << endl;
			else cout << "NO" << endl;
			continue;
		}

		ok = false;
		int sz = v[id];
		assert(sz >= a);
		for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
			int rem2 = sz - a - rem1;
			int ncnt = cnt;
			if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
			if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;

			if(rem1 >= a) ++ncnt;
			if(rem2 >= a) ++ncnt;
			if(ncnt % 2 == 0) ok = true;
		}
		
		if(ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

1221F - Выбери квадрат

Идея: Neon

Разбор

Решение (Ne0n25)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef long long li;
typedef pair<int, int> pt;

const int N = 1000 * 1000 + 13;

int n;
pair<pt, int> a[N];
vector<int> vals;
vector<pt> ev[N];
pair<li, int> t[4 * N];
li add[4 * N];

void build(int v, int l, int r) {
	if (l == r) {
		t[v] = mp(-vals[l], l);
		add[v] = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2 + 1, l, m);
	build(v * 2 + 2, m + 1, r);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

void push(int v, int l, int r) {
	if (add[v] == 0) return;
	t[v].x += add[v];
	if (l != r) {
		add[v * 2 + 1] += add[v];
		add[v * 2 + 2] += add[v];
	}
	add[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int val) {
	push(v, l, r);
	if (L > R) return;
	if (l == L && r == R) {
		add[v] += val;
		push(v, l, r);
		return;
	}
	int m = (l + r) >> 1;
	upd(v * 2 + 1, l, m, L, min(m, R), val);
	upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

pair<li, int> get(int v, int l, int r, int L, int R) {
	push(v, l, r);
	if (L > R) return mp(-li(1e18), 0);
	if (l == L && r == R) return t[v];
	int m = (l + r) >> 1;
	auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
	auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
	return max(r1, r2);
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
	
	forn(i, n) {
		vals.pb(a[i].x.x);
		vals.pb(a[i].x.y);
	}
	
	vals.pb(0);
	sort(all(vals));
	vals.pb(vals.back() + 1);
	
	vals.resize(unique(all(vals)) - vals.begin());
	
	forn(i, n) {
		int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
		int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
		ev[min(x, y)].pb(mp(max(x, y), a[i].y));
	}
	
	n = sz(vals);
	
	build(0, 0, n - 1);
	
	li ans = -1;
	int ansl = -1, ansr = -1;
	
	for (int i = sz(vals) - 1; i >= 0; i--) {
		for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
		auto cur = get(0, 0, n - 1, i, n - 1);
		if (cur.x + vals[i] > ans) {
			ans = cur.x + vals[i];
			ansl = vals[i]; ansr = vals[cur.y]; 
		}
	}
	
	printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
	
}

1221G - Граф и числа

Идея: BledDest

Разбор

Решение (BledDest)

#include <bits/stdc++.h>

using namespace std;

const int N = 40;
const int M = 20;

long long incident_mask[N];
vector<int> g[N];
int n, m;
long long ans = 0;
long long cntmask[1 << M];

long long binpow(long long x, long long y)
{
	long long z = 1;
	while(y > 0)
	{
		if(y % 2 == 1) z *= x;
		x *= x;
		y /= 2;
	}
	return z;
}

int used[N];

void dfs(int x, int c)
{
	if(used[x])
		return;
	used[x] = c;
	for(auto y : g[x])
		dfs(y, 3 - c);
}

long long countIsolated()
{
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(g[i].empty())
			ans++;
	return ans;
}

long long countComponents()
{
	memset(used, 0, sizeof used);
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(!used[i])
		{
			ans++;
			dfs(i, 1);
		}
	return ans;
}

bool bipartite()
{
	memset(used, 0, sizeof used);
	for(int i = 0; i < n; i++)
		if(!used[i])
			dfs(i, 1);
	for(int i = 0; i < n; i++)
		for(auto j : g[i])
			if(used[i] == used[j])
				return false;
	return true;
}

long long countIndependentSets()
{
	int m1 = min(n, 20);
	int m2 = n - m1;
	//cerr << m1 << " " << m2 << endl;
	memset(cntmask, 0, sizeof cntmask);
	for(int i = 0; i < (1 << m1); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = 0; j < m1; j++)
		{
			if((i & (1 << j)) == 0)
				continue;
			if(curmask & (1 << j))
				good = false;
			curmask |= ((1 << j) | incident_mask[j]);
		}
		if(good)
		{
			cntmask[curmask >> m1]++;
		}
	}	
	for(int i = 0; i < m2; i++)
		for(int j = 0; j < (1 << m2); j++)
			if(j & (1 << i))
				cntmask[j] += cntmask[j ^ (1 << i)];
	long long ans = 0;
	for(int i = 0; i < (1 << m2); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = m1; j < n; j++)
		{
			if((i & (1 << (j - m1))) == 0)
				continue;
			if(curmask & (1ll << j))
				good = false;
			curmask |= (1ll << j) | incident_mask[j];
		}
		if(good)
		{
			//cerr << i << endl;
			ans += cntmask[(i ^ ((1 << m2) - 1))];
		}
	}
	return ans;
}

long long calc(int mask)
{
	if(mask == 0)
		return binpow(2, n);
	if(mask == 1 || mask == 4)
		return countIndependentSets();
	if(mask == 2)
		return binpow(2, countComponents());
	if(mask == 3 || mask == 6)
		return binpow(2, countIsolated());
	if(mask == 5)
		return (bipartite() ? binpow(2, countComponents()) : 0);
	if(mask == 7)
		return (m == 0 ? binpow(2, n) : 0);
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
		incident_mask[x] ^= (1ll << y);
		incident_mask[y] ^= (1ll << x);
	}
	for(int i = 0; i < 8; i++)
	{
		//cerr << i << " " << calc(i) << endl;
		if(__builtin_popcount(i) % 2 == 0)
			ans += calc(i);
		else
			ans -= calc(i);
	}
	cout << ans << endl;
    return 0;
}

#include<bits/stdc++.h> using namespace std; #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long int ll; int main(){ SPEED; ll t; cin>>t; while(t--){ ll n; cin>>n; ll a[n]; ll b[n]; for(ll i = 0; i< n; i++){ cin>>a[i]>>b[i]; } ll dp[3][n]; dp[0][0]=0; dp[1][0]=b[0]; dp[2][0]=b[0]*1ll*2; for(ll i = 1; i <= n-1; i++){ for(ll j = 0; j< 3; j++){ ll temp = LONG_MAX; for(ll k = 0; k < 3; k++){ if(a[i]+j!=a[i-1]+k){ temp = min(temp, dp[k][i-1]+b[i]*1ll*j); } } dp[j][i]=temp; } } cout<<min(dp[0][n-1], min(dp[1][n-1], dp[2][n-1]))<<endl; } }

Комментарии (63)

Показать архивные | Написать комментарий?

Swiftending

5 лет назад, # |

Very sorry gor noob question, but in G why is F(0.1) number of independent sets in graph?

→ Ответить

awoo

5 лет назад, # ^ |

$$$F(\{0, 1\})$$$ is such a coloring that no pair of vertices colored $$$1$$$ are connected by an edge. So the subtask is to count the number of ways to choose vertices to color them $$$1$$$ in such a way that no pair is connected by an edge. And that's the definition of an independent set.

Yeah, I figured it out by myself after some time... I think you should include this explanation in the editorial though, it's not immediately obvious.

← Rev. 2 →

+11

Meh, I think it's fine. Editorials are not supposed to be immediately obvious for everybody.

uzzal_rahman

I still don't understand Why it is not beneficial to increase the length of some board by three or more.... (Problem D) Can anyone help???

pulkit1411

because there is no need. even if u increase by 2 or 1 or 0 u can de different from ur neighbors

Hd7

+13

Assuming $$$a_i = a_{i-1}$$$. We can increase $$$a_i$$$ or $$$a_{i-1}$$$ by 1.
If we decide to increase $$$a_i$$$ by 1, it doesn't change anything before, so the Fence is still great up to now.
If we decide to increase $$$a_{i-1}$$$ by 1, it can equal to $$$a_{i-2}$$$ and break the Fence's greatness. In this situation, we can continuously increase $$$a_{i-1}$$$ by 1 (now, it increased 2 units) or increase $$$a_{i-2}$$$ by 1.
That's the reason why we should increase every $$$a_i$$$ at most $$$2$$$.

-VIBE

10 месяцев назад, # ^ |

what if increasing ai-2 by 1, ai-3 becomes equal to ai-2

towrist

4 года назад, # ^ |

3 case structure theorem

vatsalseth33

Can anyone tell me why am I getting a TLE for test case 16 even though I am doing the problem in O(N).85221066

saksham199

Using fast input with your code gets accepted. 85483073

can someone explain 5th question . I dont think explanation is correct , how can u convert fourth type segment into 2nd type segment and what about the cases in a>=2*b

kums_

Can someone give me the proof for problem B?

Let's play chess. :v BTW, all black cells $$$(i,j)$$$ in a chess board have the same parity of $$$i+j$$$ and different from all white cells.

prabalsingh24

I did it using a bfs. Similar to bipartite colouring

I do the same with dfs :))

lantrungseo

Hold on, what is OR-convolution mentioned in G? I couldn't google it.

Google sum over subsets DP, that's the thing you need.

Yah I solve G using that, just wondering what is OR convolution

I remember seeing it here and here but idk if it's really needed in the solution.

Thanks a lot. As I know curiosity always leads me to sth more to learn

rananjay23

In problem A , how to prove that if sum of numbers other than numbers greater than 2048 is greater or equal to 2048 then answer will be Yes ?

NoobCoder1998

Very weak test cases for A even my wrong code got accepted

Ebiarat

?your code is correct

k180231

can someone tell me what if (c + m + x - 2 * mid >= mid) means in problem C ?

If $$$mid$$$ teams are formed, then $$$mid$$$ coders are already taken and $$$mid$$$ mathematicians are also taken. That leaves us with $$$(c - mid) + (m - mid) + x$$$ people to fill the empty spot in each of the $$$mid$$$ teams. So if that condition if true, then there are enough people to form at least $$$mid$$$ teams.

BadBot

In Problem E, when we consider segments of type 4, where len >= 2*b, how can we say that Bob can always convert it into a segment of type 2? If (a+b) <= len < 3b, if Bob makes his move, the segment will become type 3

Mindjolt

When $$$len \geq 2*b$$$, Bob can always get a segment of type $$$2$$$ by saving the $$$b$$$ right most places and then choosing his segment. Eg. if $$$b=2$$$ and $$$len=8$$$, $$$\ ........ \rightarrow\ ....XX..\ $$$ Now he can use the right most place when Alice doesn't have a move left.

Guaguapi

← Rev. 4 →

Problem F ,if I submit my code with GNU C++17 ,I would Wrong answer on test 2, if I submit my code with GNU C++14,it was Accepted.Could someone tell me why? my code: 60964098 60962460. Sorry for my poor English.

dwight_shrute

In 5, how are we sure that 2b>=a when it is only mentioned that a>b?

forget

We don't. If a <= 2b then there is just no segment of the third type.

HeshamAli

need a proof for problem "A" solution please

mivael

There are accepted solutions (e.g. 60854023)
for Problem C (Perfect Teams) which are just
$$$min \{c, m, \left \lfloor{\frac{c+m+x}{3}}\right \rfloor\}$$$

Could someone please prove (or explain the idea behind) the formula?

ien49fh

By definition, each team consists of a coder, a mathematician, and exactly three people. The resource with minimal availability decides how many perfect teams you can build.

kushagrasri

i can understand how minimal availability of c & m decide the outcome but what does (c+m+x)/3 here signify?

can you please explain? _/\_

hduoc2003

haizz i am bad at implementation algorithm. That's why i rarely do well in the contest :< . Can someone give me advice on this matter, pls !! sorry for my poor english :D

akane_psycho

Read and understand good codes of the questions you are doing... try to remember loopholes and learn to make your code short and simple. Also each line of the code should be important that is your code shouldn't be redundant.

Chanandler_bong

Can E be solved like this? I am not sure! :3

First take segment length of dots, then sort them and obviously ignore the lengths smaller than b. Then we declare vector < pair > info which saves what happens if alice starts, if bob starts when there are first i lengths only.

Now in these sorted lengths, take the first one and save who wins if there is only that first segment and alice starts the move, if there is only that last segment and bob starts the move

Then we iterate i from 1 to size of segment lengths array. For i-th element, we decide who will win if alice starts, if bob starts the move when there are only first i segments. We decide considering the i-th length and the information from info[i-1]......and save it in info[i]......

**sorry for my explanation.....i suck at explaining :(

xiaoshizhan

problem A mathematical induction proof: (1) if the sum of the not larger than 1 elements is greater than 1, the numbers can merged into 1. obvious. (2)suppose the sum of not larger than 2^(k-1) elements is greater than 2^(k-1), the numbers can be merged into 2^k. Then if the sum smaller than 2^k elements of is larger than 2^k , the numbers can be merged into 2^k.

Jhin

in D what is the proof that time complexity of the recursion won't be large I did not get how the dp is exactly working

GaryZ005

because all boards will be increased by no more than two.

Yeah I know but there's a for loop with calc function with three possibilities x=0 x=1 x=2 so it's o(3^n) complexity isnt it ? Or if statement is making it o(n) but why

No it is 3*3*n

ag157

My recursive DP solution for problem D is timing out , It times out in the test case where answer is always 0 , the weird thing is that it times out even after I hardcode the case where number of elements are always 1! can someone please check and let me know where I can optimize ? Thanks ! https://codeforces.com/contest/1221/submission/61071469

doubleux

I hope your problem is already solved by now, but I'm writing it for other people!

Use fastio. I was having the same problem! Write this inside main(): ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

triedodin

Great Code!!!

rahul_ag

Can anyone please help me in problem D. I am getting wrong answer on teset case 2. I am using tabulation approach instead of memoization. Here is also Link to my submission. Thanks in advance