Разбор Educational Codeforces Round 116

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	atcoder_official	162
2	maomao90	162
2	Um_nik	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

Разбор

Решение (adedalic)

fun main() {
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        println(s.last() + s.substring(1))
    }
}

1606B - Файлы обновлений

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    li n, k;
    cin >> n >> k;
    li ans = 0, cur = 1;
    while (cur < k) {
      cur *= 2;
      ++ans;
    }
    if (cur < n) ans += (n - cur + k - 1) / k;
    cout << ans << '\n';
  }
}

1606C - Банкноты

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    k += 1;
    vector<int> a(n);
    for (int& x : a) {
      cin >> x;
      int cur = 1;
      while (x--) cur *= 10;
      x = cur;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
      int cnt = k;
      if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1);
      res += a[i] * 1LL * cnt;
      k -= cnt;
    }
    cout << res << '\n';
  }
}

1606D - Красно-синяя матрица

Идея: BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<vector<int>> a(n, vector<int>(m));
		forn(i, n) forn(j, m) scanf("%d", &a[i][j]);
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){ return a[x][0] > a[y][0]; });
		vector<vector<int>> mxl(n, vector<int>(m, -INF));
		vector<vector<int>> mnr(n, vector<int>(m, INF));
		for (int i = n - 1; i >= 0; --i) forn(j, m){
			mxl[i][j] = a[ord[i]][j];
			if (i < n - 1) mxl[i][j] = max(mxl[i][j], mxl[i + 1][j]);
			if (j > 0) mxl[i][j] = max(mxl[i][j], mxl[i][j - 1]);
		}
		for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j){
			mnr[i][j] = a[ord[i]][j];
			if (i < n - 1) mnr[i][j] = min(mnr[i][j], mnr[i + 1][j]);
			if (j < m - 1) mnr[i][j] = min(mnr[i][j], mnr[i][j + 1]);
		}
		vector<int> mnl(m, INF), mxr(m, -INF);
		pair<int, int> ans(-1, -1);
		forn(i, n - 1){
			forn(j, m){
				mnl[j] = min(mnl[j], a[ord[i]][j]);
				if (j > 0) mnl[j] = min(mnl[j], mnl[j - 1]);
			}
			for (int j = m - 1; j >= 0; --j){
				mxr[j] = max(mxr[j], a[ord[i]][j]);
				if (j < m - 1) mxr[j] = max(mxr[j], mxr[j + 1]);
			}
			forn(j, m - 1) if (mnl[j] > mxl[i + 1][j] && mxr[j + 1] < mnr[i + 1][j + 1]){
				ans = {i, j};
			}
		}
		if (ans.first == -1){
			puts("NO");
			continue;
		}
		puts("YES");
		string res(n, '.');
		forn(i, n) res[ord[i]] = i <= ans.first ? 'R' : 'B';
		printf("%s %d\n", res.c_str(), ans.second + 1);
	}
	return 0;
}

1606E - Арена

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const int MOD = 998244353;

int n, x;
int c[N][N], dp[N][N];

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int mul(int x, int y) {
  return x * 1ll * y % MOD;
}

int main() {
  cin >> n >> x;
  for (int i = 0; i <= n; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) 
      c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
  }
  dp[n][0] = 1;
  for (int i = n; i > 1; i--) {
    for (int j = 0; j < x; ++j) {
      if (!dp[i][j]) continue;
      int pw = 1, nj = min(x, j + i - 1);
      for (int k = i; k >= 0; k--) {
        dp[k][nj] = add(dp[k][nj], mul(dp[i][j], mul(c[i][k], pw)));
        pw = mul(pw, nj - j);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= x; ++i)
    ans = add(ans, dp[0][i]);
  cout << ans << endl;
}

1606F - Древесные запросы

Идея: BledDest

Разбор

Решение (BledDest)

#include <bits/stdc++.h>     

using namespace std;

struct Vertex
{
 	int cost;
 	int depth;
 	int idx;
 	Vertex() {};
 	Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {};
};

bool operator <(const Vertex& a, const Vertex& b)
{
 	if(a.cost != b.cost)
 		return a.cost > b.cost;
 	if(a.depth != b.depth)
 		return a.depth > b.depth;
 	return a.idx < b.idx;
}

struct DSU
{
	int n;
 	vector<int> p;
 	vector<int> top;

 	int get(int x)
 	{
 		if(p[x] == x)
 			return x;
 		return p[x] = get(p[x]); 	
 	}

 	int get_top(int x)
 	{
 	 	return top[get(x)];
 	}

 	void merge(int x, int par)
 	{
 	 	p[x] = par;
 	}

 	DSU(int k = 0)
 	{
 	 	n = k;
 	 	p.resize(n);
 	 	iota(p.begin(), p.end(), 0);
 	 	top = p;
 	};
};

const int N = 200043;

int n;
vector<int> g[N];
int p[N], d[N], tin[N], tout[N];
int qv[N];
int qk[N];
int T = 0;

void dfs(int v = 0, int par = -1)
{
 	tin[v] = T++;
 	p[v] = par;
 	if(par == -1)
 		d[v] = 0;
 	else
 		d[v] = d[par] + 1;
 	for(auto x : g[v])
 		if(x != par)
 			dfs(x, v);
 	tout[v] = T;
}

pair<long long, long long> tree[4 * N];

pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
 	return make_pair(a.first + b.first, a.second + b.second);
}

pair<long long, long long> get(int v, int l, int r, int L, int R)
{
 	if(L >= R) return {0, 0};
 	if(l == L && r == R) return tree[v];
 	int m = (l + r) / 2;
 	return get(v * 2 + 1, l, m, L, min(R, m)) + get(v * 2 + 2, m, r, max(m, L), R);
}

void add(int v, int l, int r, int pos, pair<long long, long long> val)
{
 	if(l == r - 1)
 		tree[v] = tree[v] + val;
 	else
 	{
 	 	int m = (l + r) / 2;
 	 	if(pos < m) add(v * 2 + 1, l, m, pos, val);
 	 	else add(v * 2 + 2, m, r, pos, val);
 	 	tree[v] = tree[v] + val;
 	}                                                                  
}

pair<long long, long long> get_vertex_value(int v)
{
 	return get(0, 0, n, tin[v], tout[v]);
}

void add_on_path(int x, int y, pair<long long, long long> val)
{
 	// x is a descendant of y
 	add(0, 0, n, tin[x], val);
 	if(p[y] != -1)
 		add(0, 0, n, tin[p[y]], make_pair(-val.first, -val.second));
}

int calculate_cost(int v, int correction)
{
	//cerr << v << " " << correction << endl;
 	pair<long long, long long> res = get_vertex_value(v);
 	// first - (second + 1) * k <= 0
 	long long k = (res.first + res.second) / (res.second + 1) - 1;
 	if(correction < k) return correction;
 	return k;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; i++)
	{
	 	int x, y;
	 	scanf("%d %d", &x, &y);
	 	--x;
	 	--y;
	 	g[x].push_back(y);
	 	g[y].push_back(x);
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	scanf("%d %d", &qv[i], &qk[i]);
	 	--qv[i];
	}                   

	dfs();
	DSU dsu(n);
                        
	vector<long long> ans(q);
	set<Vertex> pq;
	vector<Vertex> curv(n);
	for(int i = 0; i < n; i++)
	{                     
	 	int count_children = g[i].size();
	 	if(i != 0) count_children--;               
	 	add_on_path(i, i, make_pair((long long)(count_children), 0ll)); 
	 	if(i != 0)
	 	{
	 		curv[i] = Vertex(calculate_cost(i, 200000), d[i], i);
			pq.insert(curv[i]);                                   
	 	}
                          
	}
                        
	for(int i = 0; i < q; i++)
		pq.insert(Vertex(qk[i], -1, i));

	while(!pq.empty())
	{
		Vertex z = *pq.begin();
		pq.erase(pq.begin());
		if(z.depth == -1)
		{
		 	auto res = get_vertex_value(qv[z.idx]);
		 	ans[z.idx] = res.first - res.second * z.cost;
	    }
	    else
	    {
	     	int v = z.idx;
	     	int pv = p[v];
	     	int newtop = dsu.get_top(pv);
	     	pair<long long, long long> val = get_vertex_value(v);
	     	val.second++;
	     	val.first--;
	     	if(newtop != 0)
	     		pq.erase(curv[newtop]);
	     	add_on_path(pv, newtop, val);
	     	if(newtop != 0)
	     		curv[newtop].cost = calculate_cost(newtop, z.cost);
	     	if(newtop != 0)
	     		pq.insert(curv[newtop]);
	     	dsu.merge(v, pv);
	    }
	}	

	for(int i = 0; i < q; i++)
		printf("%lld\n", ans[i]);
}

for (auto t : adj[now]) { if (t == fa) continue; dfs2(t, now); for (int i = 0; i <= sz[now] && i <= B; i++) { for (int j = 0; j <= sz[t] && j + i <= B; j++) { g[i + j] = max(g[i + j], f[now][i] + 1); g[i + j + 1] = max(g[i + j + 1], f[now][i] + f[t][j]); } } sz[now] += sz[t]; for (int i = 0; i <= sz[now] && i <= B; i++) { f[now][i] = g[i]; g[i] = -0x3f3f3f3f; } }

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

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

cometplaytetris

3 года назад, # |

← Rev. 2 →

+17

I didn't sort the array in problem D, but the rest matches with the editorial. No. No. No. NOOOOOOOOOOOOO my ratings :'(

→ Ответить

ducati

I hope the next Educational Round's editorial will be faster.

umanggupta1975

For problem E Total permutations possible are x^n. To get a winner I set one maximum value(suppose a) and set rest values less than a so they have a-1 options. So its total permutations will be n.(a-1)^(n-1). Now minimum value of a can be n otherwise all players will be eleminated in the first round. So I get the formula x^n — n.( (n-1)^(n-1) + (n)^(n-1) + (n+1)^(n-1) + ..... + (x-1)^(n-1)) Can anyone tell me what is wrong in this approach it is failing on sample 4.

geckods

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

It isn't always the case that the losing players can have any health that's less than the winning player's health. Take the case n=3, health values are 4,3,3.

+16

Thanks, Got it now.

toniskrijelj

In editorial of problem E it should be <2 or <=1, when talking about fights which ended.

Anonymous_Guy

Hi in Problem B, if k is larger than n/2 we can use ceil(log2(n)) to get the answer as at each step we can go up by power of ^2 so I am pretty confident in my solution.

But it fails at test case: 576460752303423489 576460752303423489 (https://codeforces.net/contest/1606/submission/133708639) I just want to know if this is because the precision points are too small to consider? and this is a language issue? but mathematically it is correct. Can you please help me?

SolidStateUMR

Precision error, definitely. In this case 57646075230342348 9 (as long long int) is implicitly converted to 57646075230342348 8 .0000 (as double)

Codeforces (along with most computers/compilers) uses 64-bit long long int and 64-bit IEEE-754 double. However, IEEE-754 double has only 53-bit significand precision, according to Wikipedia.

dreamsofcode

I have used a similar approach 133723445
The constraints of n and k are probably too big for log2() function, Therefore I've used log2l() for extra precision. You can read the documentation about these functions here https://www.cplusplus.com/reference/cmath/log2/

I used the log2l() version and it worked, also there is a similar version for the pow() function powl(). to use the long double. Thanks for the help :)

robinz62

My solution to D was much longer and more complicated, but here is at least a neat-ish observation that it used:

Just looking at the first column, we can be sure that if a solution exists, the row with the max element is red and the row with the min element is blue. This is enough to uniquely identify where the cut should be: going left to right, it is whenever we switch from red > blue to blue > red. Now that we know where the split is, we can simplify the matrix by only keeping the min and max element for each row, on each side of the matrix.

My solution did this, then treated each row as an interval [min, max]. On the left side, any overlapping/touching intervals need to be merged, and in the end we have a list of disjoint ranges, after which, in similar spirit to the editorial solution, we sort then brute force on the number of blue ranges. I then used BSTs on the right side to keep track of whether blue > red, which are quick to update since I've condensed each row into only 2 values.

kalashj93

UPDATING FILES :- doubt if (cur < n) ans += (n — cur +k-1) / k; can anyone explain why k-1 is being added . It seems to be confusing . Pls explain

bekzhan29

(a+b-1)/b is the same as ceil(a/b) if b is positive

ChenKaifeng

+58

Another solution for F with liangjiawen2007.

Considering the value of $$$k$$$, obviously we do at most $$$\frac n k$$$ operations. Thus, we can have a $$$O(n\sqrt n)$$$ solution based on the observation.

When $$$k\le \sqrt n$$$, there are at most $$$\sqrt n$$$ different values of $$$k$$$. We can have such dp as follow: $$$f_{i,j}$$$ for the maximum value you can get for $$$k=j$$$. Transforming is easy, $$$f_{u,i}=\sum \max(1, f_{v,i}-i)$$$ and we can do it in $$$O(n)$$$ for every $$$j$$$.

When $$$k>\sqrt n$$$, we do at most $$$\sqrt n$$$ operations, we can have dp as follow: $$$g_{i,j}$$$ for the maximum sons you can get when you do $$$j$$$ operations. When we merge subtree $$$u$$$ and $$$v$$$, we get $$$g_{u,i+j+1}\leftarrow g_{u,i}+g_{v,j}$$$.

This is a knapsack problem on tree, as $$$j \le \sqrt n$$$, we can use the trick that we only do $$$i\le \min(k,siz_u)$$$ and $$$j\le \min(k,siz_v)$$$ while transforming, then the time complexity will be $$$O(nk)$$$ while $$$k=\sqrt n$$$

The total time and space complexity is $$$O(n\sqrt n)$$$

Here is the submission 134047234

PoIar_

Could you elaborate on why the complexity is $$$ O(n \sqrt{n}) $$$? I find it a bit intuitive but I couldn't prove it

Byobe

Let me try to explain what I've got from the source code:

Two nested loops inside the DFS is what seems to be dangerous here. Let B = sqrt(n).

There are up to B subtrees for which sz[x] > B, so even if sz[t] and sz[now] are greater than B there are up to B such occasions. So if sz[t] > B then we spend up to $$$O(B) * O(B * B)$$$ for such cases.

On the other hand, there could be up to n "small subtrees" for which sz[t] < B. For such a subtree one can check that the complexity of the whole run $$$Dfs(t)$$$ is indeed $$$O(size^2)$$$. Let us denote by $$$n_b$$$ the number of subtrees of size $$$b < B$$$. Then $$$\sum_{b = 1}^{B} n_b b \leq n$$$ so $$$O(\sum_{b = 1}^{B} n_b b^2) = O(B \sum_{b = 1}^{B} n_b b) = O(Bn)$$$.

OLIN_ONE

can someone explain the output for n = 3 and x = 3 of problem E ?

surajmamgai

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

The different ways are: {1, 3, 3}, {3, 3, 1}, {3, 1, 3}, {2, 3, 3}, {3, 3, 2}, {3, 2, 3}, {1, 2, 2}, {2, 2, 1}, {2, 1, 2}, {1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {1, 1, 2}, {1, 2, 1}, and {2, 1, 1}.

T0p_

UPDATE It's my fault, I misunderstand that it will compare only the column. Please give me an apologize.

In problem D, I found that there is a test case ~~~~~ 1 3 3 7 9 8 4 8 14 15 9 13 ~~~~~

The solution gives the answer as NO.

But I think it is possible for YES by painting to be RBR with k = 2.

Please correct me if I'm wrong. Thank you :)

ivan100sic

+18

F has a much simpler solution based on the fact that we don't need to store DP values for many different pairs of $$$(x, k)$$$, for at most $$$O(n \log n)$$$ of them it will be greater than $$$|children(x)|$$$, leading to simple $$$O(n \log n)$$$ DP.

CarolinaMoura

Could you elaborate on that? I can't understand two things:

why it is the case that only $$$O(n \log n)$$$ vertices will have more than $$$|children(x)|$$$
let $$$v_{1}, v_{2}, ... , v_{n \log n}$$$ be those vertices. Why can you iterate through $$$\sum dp[v_{i}].size() $$$ without exceding the time limit?

hat

← Rev. 4 →

There are just $$$n$$$ vertices, not $$$n \log n$$$. Let $$$dp[u][k]$$$ be the answer of query $$$(u, k)$$$, there are only $$$O(n \log n)$$$ pairs of $$$(u, k)$$$ that $$$dp[u][k] \gt |children(u)|$$$.

To prove it, for a fixed $$$k$$$, let's construct a tree that maximize the number of $$$u$$$.

For a certain tree, let the lowest vertice that statisfies the condition above be $$$v$$$. $$$v$$$ must have at least one child $$$w$$$ that $$$|children(w)| \gt k + 1$$$. To maximize the number of $$$u$$$, there should be only one $$$w$$$. (If there are more than one child meet the requirement(call them $$$w_i$$$), we can leave only one child $$$w_1$$$, add other $$$w_i$$$ and $$$children(w_i)$$$ to $$$children(w_1)$$$. After that $$$dp[v][k]$$$ will only increase, which leads to number of $$$u$$$ increase.) Also, obviously all the children $$$w$$$ have should be leaves.

Then we consider $$$p$$$, the parent of $$$v$$$. We can also take all the children of $$$p$$$ except $$$v$$$, insert them to $$$children(w)$$$. It will not decrease the result. Repeat this process, we can see this tree is a chain with all leaves linked to one end.

For this tree, we can easily caculate that $$$dp[v][k] = |leaves|-k$$$, $$$dp[parent(v)][k] = |leaves|-2k, ...$$$ So the number of $$$u$$$ that $$$dp[u][k] \gt |children(u)| = 1$$$ will not exceed $$$\frac{n}{k}$$$. Use the sum of harmonic series we can prove there are only $$$O(n \log n)$$$ pairs.

I was able to understand now. Thank you very much!

dunjen_master

← Rev. 3 →

can someone explain problem E ? For n = 3 and x = 3 I can only think of 12 cases and not 15 -

1 1 1
2 2 1
2 1 2
1 2 2
2 2 2
3 3 1
3 3 2
3 1 3
3 2 3
1 3 3
2 3 3
3 3 3

KanishkGoel

2 1 1

1 2 1

1 1 2

In these scenarios, everyone dies after first the round.

VincentBoy

In problem E, why dp[n][0] = 1 ? can anyone explain for me :'(

Hogwarts.dropout

Can anyone please tell what's the intuition behind taking such states in E-Arena.

Spoiler

editorialist

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

In the solution for E-Arena given in the editorial, I didn't understand why dp[n][0] = 1;

which is that case where all n heroes are alive and each of them has dealt 0 damage?

binomanjesh

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

dp[i][j] actually stores the number of ways to choose the initial health and positions of the n-i heroes who have died by now.

Why is dp[n][0] = 1? before the first round, there are n heroes alive, 0 damage has been dealt and there are 0 heroes dead. Number of ways to chose the health and positions of 0 dead heroes is 1.

Блог пользователя awoo