Разбор Educational Codeforces Round 146

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

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

Разбор

Решение (awoo)

for _ in range(int(input())):
	n, k = map(int, input().split())
	for x in range(2):
		if n - x * k >= 0 and (n - x * k) % 2 == 0:
			print("YES")
			break
	else:
		print("NO")

1814B - Длинные ноги

Идея: BledDest

Разбор

Решение (awoo)

for _ in range(int(input())):
	a, b = map(int, input().split())
	ans = a + b
	for m in range(1, 100000):
		ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1))
	print(ans)

1814C - Параллельный поиск

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		int n;
		scanf("%d", &n);
		vector<int> s(2);
		for(int j = 0; j < 2; j++)
			scanf("%d", &s[j]);
		vector<pair<int, int>> a(n);
		for(int j = 0; j < n; j++)
		{
			scanf("%d", &a[j].first);
			a[j].second = j + 1;
		}
		sort(a.begin(), a.end());
		reverse(a.begin(), a.end());
		vector<vector<int>> lists(2);
		for(int j = 0; j < n; j++)
		{
			int cost1 = s[0] * (lists[0].size() + 1);
			int cost2 = s[1] * (lists[1].size() + 1);
			if(cost1 < cost2)
				lists[0].push_back(a[j].second);
			else
				lists[1].push_back(a[j].second);
		}
		for(int j = 0; j < 2; j++)
		{
		    cout << lists[j].size();
		    for(auto x : lists[j]) cout << " " << x;
		    cout << endl;
		}
	}
}

1814D - Балансировка пушек

Идея: adedalic

Разбор

Решение (adedalic)

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toInt() }
        val f = readln().split(' ').map { it.toLong() }
        val d = readln().split(' ').map { it.toLong() }

        fun checkAround(pos : Long) : Int {
            val qs = Array(2 * k + 1) { MutableList(0) { 0 } }

            fun inside(x : Long, pos: Long) = (pos - k <= x) && (x <= pos + k)
            for (i in f.indices) {
                var newD = maxOf(1L, pos / f[i])
                if (newD != d[i] && newD + 1 != d[i] && inside(d[i] * f[i], pos)) {
                    val id = (i + 1)
                    qs[(d[i] * f[i] - pos + k).toInt()].add(id)
                }
                repeat(2) {
                    if (inside(newD * f[i], pos)) {
                        val id = if (newD == d[i]) (i + 1) else -(i + 1)
                        qs[(newD * f[i] - pos + k).toInt()].add(id)
                    }
                    newD++
                }
                
            }

            val cntPerId = IntArray(n) { 0 }
            var cntDistinct = 0
            var cntGood = 0

            fun addToSeg(cid : Int) {
                val id = -1 + if (cid > 0) cid else -cid
                val c = if (cid > 0) 1 else 0

                if (cntPerId[id] == 0)
                    cntDistinct++
                cntPerId[id]++

                cntGood += c
            }
            fun eraseFromSeg(cid : Int) {
                val id = -1 + if (cid > 0) cid else -cid
                val c = if (cid > 0) 1 else 0

                cntPerId[id]--
                if (cntPerId[id] == 0)
                    cntDistinct--

                cntGood -= c
            }
            var ans = 0
            for (p in 0 until k)
                qs[p].forEach { addToSeg(it) }
            for (p in 0..k) {
                qs[p + k].forEach { addToSeg(it) }
                if (cntDistinct == n)
                    ans = maxOf(ans, cntGood)
                qs[p].forEach { eraseFromSeg(it) }
            }
            return n - ans
        }

        var ans = n
        for (i in f.indices) {
            ans = minOf(ans, checkAround(d[i] * f[i]))
        }
        println(ans)
    }
}

1814E - Фишки на цепочке

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const li INF = (li)(1e18);
const int N = 200043;

struct data
{
	array<array<long long, 2>, 2> d;
	data() {
	    for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
	};
	data(li x)
	{
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
		d[0][0] = 0;
		d[1][1] = x;
	};
	data(data l, data r)
	{
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					for(int x = 0; x < 2; x++)
					{
						if(j == 0 && k == 0) continue;
						d[i][x] = min(d[i][x], l.d[i][j] + r.d[k][x]);
					}
	};
};

data T[4 * N];
li a[N];

void recalc(int v)
{
	T[v] = data(T[v * 2 + 1], T[v * 2 + 2]);
}

void build(int v, int l, int r)
{
	if(l == r - 1) T[v] = data(a[l]);
	else
	{
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m, r);
		recalc(v);
	}
}

void upd(int v, int l, int r, int pos, li val)
{
	if(l == r - 1)
	{
		a[l] = val;
		T[v] = data(a[l]);
	}
	else
	{
		int m = (l + r) / 2;
		if(pos < m)
			upd(v * 2 + 1, l, m, pos, val);
		else
			upd(v * 2 + 2, m, r, pos, val);
		recalc(v);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++)
	{
		scanf("%lld", &a[i]);
	}
	build(0, 0, n - 1);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		int x;
		li k;
		scanf("%d %lld", &x, &k);
		upd(0, 0, n - 1, x - 1, k);
		printf("%lld\n", T[0].d[1][1] * 2);
	}
}

1814F - Вышки связи

Идея: Neon

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

const int N = 200002;
const int V = 50 * N;

using pt = pair<int, int>;

int n, m;
pt a[N];
vector<pt> t[4 * N];
int p[N], rk[N], vs[N];
int cntV;
pt g[V];
bool ans[V];

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

int k;
int* ptr[V];
int val[V];

void upd(int &a, int b) {
  ptr[k] = &a;
  val[k] = a;
  k += 1;
  a = b;
}

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

void unite(int v, int u) {
  v = getp(v), u = getp(u);
  if (v == u) return;
  if (rk[v] > rk[u]) swap(v, u);
  upd(p[v], u);
  g[cntV] = {vs[v], vs[u]};
  upd(vs[u], cntV++);
  if (rk[v] == rk[u])
    upd(rk[u], rk[u] + 1);
}

void solve(int v, int l, int r) {
  int cur = k;
  for (auto& [v, u] : t[v]) 
    unite(v, u);
  if (l + 1 == r) {
    ans[vs[getp(0)]] = 1;
  } else {
    int m = (l + r) / 2;
    solve(v * 2 + 1, l, m);
    solve(v * 2 + 2, m, r);
  }
  while (k > cur) {
    k -= 1;
    (*ptr[k]) = val[k];
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> a[i].first >> a[i].second;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    int L = max(a[x].first, a[y].first);
    int R = min(a[x].second, a[y].second);
    upd(0, 0, N, L, R + 1, {x, y});
  }
  
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    rk[i] = 1;
    vs[i] = i;
    g[i] = {-1, -1};
  }
  
  cntV = n;
  solve(0, 0, N);
  
  queue<int> q;
  for (int i = 0; i < cntV; ++i) if (ans[i]) 
    q.push(i);
  
  while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : {g[v].first, g[v].second}) {
      if (u != -1 && !ans[u]) {
        ans[u] = true;
        q.push(u);
      }
    }
  }
  
  for (int i = 0; i < n; ++i) if (ans[i])
    cout << i + 1 << ' ';
}

#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() void solve(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while (t--) { solve(); } } void solve() { long long n, s1, s2; cin >> n >> s1 >> s2; long long r[n]; vector<pair<long long, long long>> v; for (int i = 0; i < n; i++) { cin >> r[i]; v.push_back({r[i], (i + 1)}); } // for (auto &it : v) // cout << it.first << " " << it.second << endl; sort(all(v)); long long tc1 = 0; long long tc2 = 0; vector<long long> lista; vector<long long> listb; for (int i = n - 1; i >= 0; i--) { long long cost1 = v[i].first * s1; long long cost2 = v[i].first * s2; tc1 += cost1; tc2 += cost2; // cout << tc1 << " " << tc2 << endl; if (tc1 > tc2) { listb.push_back(v[i].second); tc1 -= cost1; } else { lista.push_back(v[i].second); tc2 -= cost2; } } // cout << endl; cout << lista.size() << " "; for (auto &it : lista) { cout << it << " "; } cout << endl; cout << listb.size() << " "; for (auto &it : listb) cout << it << " "; cout << endl; }

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

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

Abito

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

I know it isn't an "issue", but in problem B the variable names are a,b while here they are n,m

→ Ответить

Bnahmad15

In problem B, My thought was ternary search since the values tend to decrease at first and then increase but the problem I faced is that around the middle of the curve, the values don't necessarily keep changing in the same way (X-axis for max K length and Y-axis for cost)

As you notice some irregularities, can this be handled using only ternary search or by iterating over a much smaller range of K's?

The5threich

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

I tried a weaker 1-D case (go from 0 to n)
there $$$\sqrt{n}$$$ seems to be the best leg size. (floor or ceil I don't remember)
(somewhat related to the fact that $$$x + a/x$$$ minimizes at $$$x = \sqrt{a}$$$ and
similar is the case with $$$x-1 + \lceil n/x \rceil$$$)
But ofc the problem is going up a notch to the 2-D case.
(new to code-forces and I don't know how to write in laTex etc, pardon me for that).

OMG_wc

+18

problem EF video solution for Chinese：

BiliBili

LiuZhaocheng

why the rating result are not visible now?

wanghai673

because it's an unrated round

the_coder_8297

Can anyone please elaborate on the solution of Problem D, please?

parasguglani1

A can be solved by just checking parity of n and k

if (n % 2 == 0 || k % 2)
     yes
    else no

VON_Remember_Me

Can you please give an explanation of this? Also, what is meant by parity check?

← Rev. 2 →

parity means it's odd or even.

if n is even, it can be made with 2 coins.

if n is odd then k must be odd as well otherwise it is not possible.

example

For a more formal proof

proof

AshishLikePanner

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

nice solution. It takes me some time to understand your solution. How can I improve my problem solving skills?

RISHI_2003

can anyone please explain me why this code will not work for problem B?

induk_v_tsiane

The cost is different depending on where you put it. Say that the current number of elemnts in list_a is k1, and in list_b is k2, then the cost of adding an element S is S * (k1 + 1) * S1 in the first case, and S * (k2 + 1) * S2 in the second case.

__Martian

Can anyone tell me why we need to fix the value of K in B.

parveen1981

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

Let's say we are calculating answer for $$$b$$$ only (you can extend this to $$$a$$$ also).

Now, let's say you are using 2 values of $$$k$$$ i.e. $$$k_1 < k_2$$$. So your answer would be kind of $$$b/k_1 + b/k_2$$$, here if you just replace $$$b/k_1$$$ with $$$1$$$ you would get better answer and we can always do this since we will always increase value of $$$k$$$ from 1 to $$$k_2$$$ and $$$k_1$$$ is working on just the remainder of $$$b/k_2$$$.

atharva_sarage

E Has a nice observation, we would never take 3 consecutive edges. Any elegant solution using this observation.

(Take , NotTake, Take) is better than (Take, Take, Take) and both achieve our goal. f(i) = min(2*e(i,i+1) + f(i+2) , 2*[e(i,i+1)+e(i+1,i+2)] + f(i+3))

SriniV

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

Sorry for necroposting, but could you expand on how we can utilize this to quickly answer update queries? Does it still require the "classical" segment tree sol mentioned in edi?

vantaablackk

Solution to problem B seems pretty complicated. Can someone please explain a simpler approach?

lllei

It's not difficult. You should just know the answer is $$$\lceil\frac{a}{k}\rceil + \lceil\frac{b}{k}\rceil + (k - 1)$$$ when you add your feet to k long. Then if you remove the ceil, you can get $$$\frac{a + b}{k} + k - 1$$$, it's just an inequality $$$a + b \ge 2 \times \sqrt{a \times b}$$$ when $$$a = b$$$ the equality is achieved. Therefore, for this function, it's $$$\frac{a + b}{k} = k$$$, .i.e $$$k^2 = a + b$$$. So $$$k = \sqrt{a + b}$$$, you can get the smallest value. However, you remove the ceil, so there maybe 2 off the correct answer. You should check around. Anyway, 1e5 is enough.

At_Atharva

How did you come to the conclusion that

(A+b)/k)=k ?

Because the inequality I wrote abode. $$$\frac{a + b}{k} + k \ge 2 \times \sqrt{a + b}$$$, and when $$$\frac{a + b}{k} = k$$$ the equality takes.

the_Incharge

can someone recommend more problems similar to E

B_Consistent

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

If the Editorial has atleast transistion states you could even try to reduce to matrix form The editorial is as good as problem statement. It's one of the kind we call it Skind S means not "shit".It means Super

Misuki

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

Sorry for necroposting, but I want to share my solution of F without using KRT.

Consider doing lazy tag on rollback DSU, when we visit to a certain time, add a tag with time stamp on the representative of vertex $$$1$$$, and when we rollback(assume this edge point to $$$boss$$$), if this edge is added before the tag on $$$boss$$$ is added, then push down the tag. At the end just check whether each vertex have tag on it.

I found it is quite amazing that we can do lazy tag on DSU, maybe there also have some potential application of it?

vaal

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

Can anyone please tell me why my submission TLEs on test 5 for Problem D? It uses the same solution as editorial. Submission: 239734235

What is the recurrence relation used in Problem E ? what Dp transistions should one speed up ? It would be better to add equations and how they were transformed into matrix form. IMO this is the only step which is key in the matrix expo problems and Editorial is missing them

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