XXII Open Cup, Grand Prix of BSUIR

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

DP Bitmask - Topic Stream

Shayan

До начала 09:09:01

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

XXII Open Cup, Grand Prix of BSUIR

Автор Qingyu, история, 3 года назад, По-английски

Let's discuss the tasks here.

How to solve problem B?

Qingyu
3 года назад
26

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

Написать комментарий?

errorgorn

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

+13

Was bitset intended for I? My $$$O(\frac{n^3}{w})$$$ solution runs in only 350ms.

→ Ответить

wilcot

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

← Rev. 3 →

No. There is simple $$$O(n^2)$$$ greedy solution.

Note that $$$1$$$ is always in the answer. Then we should greedily add vertices $$$2$$$, $$$3$$$, ...

For example, we want to add $$$i$$$ to the answer. We should also add all vertices from $$$i$$$ to $$$1$$$ and for each we should check that there are no bad vertices added. We can note that check for each vertex need $$$O(n)$$$ time, and if we check all vertices once, we will achieve $$$O(n^2)$$$.

→ Ответить

errorgorn

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

← Rev. 2 →

if we check all vertices once

How can we accomplish this? Can you elaborate more? Other than that, my solution is same, except using bitsets to speedup the check to $$$O(\frac{n}{w})$$$.

→ Ответить

YaoBIG

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

← Rev. 3 →

+25

Suppose we are trying to add vertex $$$v$$$ to the current set $$$S$$$ and we find a path from $$$v$$$ to $$$S$$$: $$$v = p_1, p_2,...,p_l$$$ ($$$p_l \in S$$$). Then we just iteratively check if $$$p_i$$$ is consistent with $$$S \cup $$${$$$p_{i+1},...,p_{l-1}$$$}. If we find that some vertex $$$p_j$$$ is a not consistent and we stop at vertex $$$p_j$$$, we simply mark all vertices in {$$$p_1,...,p_j$$$} bad and do not need to re-calculate the consistency of them anymore. On the other hand, if no bad vertices are found, then we just add $$$p_1,...,p_{l-1}$$$ to set $$$S$$$. From this you can see that for each pair $$$(u,v)$$$ we check at most once if the path from $$$u$$$ to $$$v$$$ is a palindrome of length greater than $$$k$$$.

→ Ответить

Um_nik

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

+49

B: "Set of edges without cycles" is a matroid. "Set of edges after which deletion graph is still connected" is also a matroid. You need to find the largest element in the intersection of these two and check that the remaining edges form a tree.

How to solve F (in 10 minutes)? Is it well known in Japan? We had a solution, which we didn't even try to implement because we thought we need at least 1,5 hours to do so.

→ Ответить

errorgorn

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

+18

https://oj.uz/problem/view/JOI20_hamburg I copied from here :P

→ Ответить

Qingyu

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

+23

Seems it appeared in JOISC 2020 Day 1...

→ Ответить

wasa855

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

B: Firstly, divide the whole graph into a tree and a forest, then 1+3 is the tree and 2 is the forest. Division plan can be found by matroid intersection.

By the way, how to solve C?

→ Ответить

Um_nik

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

C: For a fixed $$$k$$$ we need to choose $$$g = gcd(a, b)$$$, then $$$a' = a/g$$$ and $$$b' = b/g$$$ are coprime divisors of k, and $$$g$$$ should be a divisor of $$$k/a'b'(a'+b')$$$, so you can calculate the number of solution by trying all the possibilities for $$$a'$$$ and $$$b'$$$ and then calculating the number of divisors. So, to have a lot of solutions $$$k$$$ should have a lot of divisors, so let's generate some reasonable set of candidates (something like highly composite numbers but a bit looser) and check only them. With some very loose criteria (use only primes up to 40, each prime exponent starting from 5 is at most 1 greater than the previous one) works a couple of minutes on my laptop. I would not be surprised if it is possible to choose some tighter criteria so the solution can run on server and fit in TL.

→ Ответить

awoo

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

How to solve J? We guessed the answer by coding a naive solution with infinity being 500, but honestly to me it even sounds weird that the answer isn't always 1 (given $$$p \neq 1$$$).

→ Ответить

SendThemToHell

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

+23

There is a well known problem about two players playing a game with probability of winning equal to p for the first player (see https://en.m.wikipedia.org/wiki/Gambler%27s_ruin). You just need to tend the amount of money for one of the players to infinity

→ Ответить

awoo

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

I see, thanks

→ Ответить

wilcot

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

← Rev. 5 →

I have some different solution:

Let's solve the problem for one dimension (for many dimensions we should multiply probabilities for separate dimension).

Consider we are at position 1. Let's see all possible ways to get 0. We can count this ways using correct bracket sequences. For +1 we will use "(" and for -1 we will use ")". So, probability to get 0 we can calculate using this simple formula:

$$$P = C_0 \cdot q + C_1 \cdot p \cdot q^2 + ... = (\sum_0^{\infty} C_i \cdot (p \cdot q)^i) \cdot q$$$.

So we can use generating function of Catalan numbers: $$$G(z) = \frac{1 - \sqrt{1 - 4 \cdot z}}{2 \cdot z}$$$. We should calculate $$$G(p \cdot q) \cdot q$$$.

Then we should understand, that if we was at position x, then answer is $$$(G(p \cdot q) \cdot q)^x$$$.

Another solution:

Let's $$$w$$$ — probability to get $$$-1$$$ after some movements. Then $$$w = p + q \cdot w^2$$$

→ Ответить

Sorting

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

Is the opencup website not available outside of contests? I haven't been able to load it in quite some time.

→ Ответить

wilcot

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

← Rev. 4 →

+23

Editorial for D:

Note that the rotation operation in a binary tree does not change the order of numbers during forward traversal.

Also pay attention to selection sort — it sorts the array using the least number of swap operations.

Thus, the minimum answer will be equal to the minimum answer for sorting the array, obtained by direct tree traversal.

Let's learn how to do $$$swap(i, j)$$$ for a tree. To do this, we can use the following algorithm:

Raise vertex $$$i$$$ to the root.
Raise vertex $$$j$$$ to the root.
Make swap.

Thus, we can solve the problem using the minimum number of swap operations.

Unfortunately, this solution will not work, since the total number of operations will be exceeded (we can have $$$O(n^2)$$$ of them. One of two approaches can be used to solve this problem:

Use the splay operation to raise vertices to the root. In splay trees, this operation is amortized for $$$O(\log n)$$$.
Balance the tree. Next, we can implement the simplest lifting to the root of the tree, now it will work for $$$O(\log n)$$$. After raising, we perform the rotate operations in reverse order to restore balance to the tree.

In total, we obtain a solution in $$$O(n \log n)$$$.

→ Ответить

TeaTime

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

+13

Can anybody explain solution to problem F please?

→ Ответить

ecnerwala

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

+13

Consider the "tightest" constraint in each direction: the leftmost right edge, the rightmost left edge, the topmost bottom edge, and the bottommost top edge. Clearly, we should never place points further outside than these edges. If the leftmost right edge and the rightmost left edge cross, then all rectangles must share a common x-range, so 1D greedy; likewise with the other two. Otherwise, in order to cover all rectangles, there must be at least one point on each of these 4 edges.

For $$$m <= 3$$$, this means at least one point must cover two of these edges, so we can pick one of the 4 corners and recurse on the remaining rectangles with $$$m-1$$$. This takes $$$O(4^m n)$$$ time.

For $$$m = 4$$$, either one point covers two edges (in which case we pick a corner and recurse on $$$m = 3$$$) or there is exactly one point on each edge. Let's visualize the 4 edges as a rectangle, where we pick one point on each side. In this case, each shelter rectangle imposes one of a few types of constraints:

If the shelter fully contained, then $$$m = 4$$$ is impossible.
If the shelter fully covers one side, then it is always satisfied.
If the shelter covers a corner, then it imposes an OR constraint on the two adjacent sides.
If the shelter intersects two opposite sides, then it imposes an OR constraint on the two opposite sides.

Now, let's pick/sweep over all possible locations of the point on the left edge. If this is fixed, then we should greedily pick the points on the top and bottom to be as far right as possible. In particular, casework on either the top point or bottom point to be further left, and choose it as far right as possible to avoid breaking OR constraints with the left side and top/bottom OR constraints. Then, choose the other top/bottom point as far right as possible. Finally, check if there is a valid choice of the right point.

To implement this, we just need to be able to query, for a particular choice of one point, which range constraints does it impose on the others. This can be done with several range-update point-query-min/max seg trees, approximately one on each pair of sides. This leads to an $$$O(n \log(n))$$$ time solution.

Interestingly, this paper claims to also give an $$$O(n \log(n))$$$ solution for $$$m = 5$$$: https://www.cs.bgu.ac.il/~segal/pierce.pdf.

Code

#include <bits/stdc++.h>

template <typename T> void setmax(T &a, T b) { if (b > a) a = b; }
template <typename T> void setmin(T &a, T b) { if (b < a) a = b; }

namespace seg_tree {

// Floor of log_2(a); index of highest 1-bit
inline int log_2(int a) {
	return a ? (8 * sizeof(a)) - 1 - __builtin_clz(a) : -1;
}

inline int next_pow_2(int a) {
	assert(a > 0);
	return 1 << log_2(2*a-1);
}

struct point {
	int a;
	point() : a(0) {}
	explicit point(int a_) : a(a_) { assert(a >= -1); }

	explicit operator bool () { return bool(a); }

	// This is useful so you can directly do array indices
	/* implicit */ operator int() const { return a; }

	point c(bool z) const {
		return point((a<<1)|z);
	}

	point operator [] (bool z) const {
		return c(z);
	}

	point p() const {
		return point(a>>1);
	}

	friend std::ostream& operator << (std::ostream& o, const point& p) { return o << int(p); }

	template <typename F> void for_each(F f) const {
		for (int v = a; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	template <typename F> void for_parents_down(F f) const {
		// strictly greater than 0
		for (int L = log_2(a); L > 0; L--) {
			f(point(a >> L));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		for (int v = a >> 1; v > 0; v >>= 1) {
			f(point(v));
		}
	}

	point& operator ++ () { ++a; return *this; }
	point operator ++ (int) { return point(a++); }
	point& operator -- () { --a; return *this; }
	point operator -- (int) { return point(a--); }
};

struct range {
	int a, b;
	range() : a(1), b(1) {}
	range(int a_, int b_) : a(a_), b(b_) {
		assert(1 <= a && a <= b && b <= 2 * a);
	}
	explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}

	explicit operator std::array<int, 2>() const {
		return {a,b};
	}

	const int& operator[] (bool z) const {
		return z ? b : a;
	}

	friend std::ostream& operator << (std::ostream& o, const range& r) { return o << "[" << r.a << ".." << r.b << ")"; }

	// Iterate over the range from outside-in.
	//   Calls f(point a)
	template <typename F> void for_each(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++));
			if (y & 1) f(point(--y));
		}
	}

	// Iterate over the range from outside-in.
	//   Calls f(point a, bool is_right)
	template <typename F> void for_each_with_side(F f) const {
		for (int x = a, y = b; x < y; x >>= 1, y >>= 1) {
			if (x & 1) f(point(x++), false);
			if (y & 1) f(point(--y), true);
		}
	}

	// Iterate over the range from left to right.
	//    Calls f(point)
	template <typename F> void for_each_l_to_r(F f) const {
		int anc_depth = log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = (-a) & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point(((a-1) >> i) + 1));
		}
		for (int v = b & anc_msk; v; ) {
			int i = log_2(v);
			f(point((b >> i) - 1));
			v ^= (1 << i);
		}
	}

	// Iterate over the range from right to left.
	//    Calls f(point)
	template <typename F> void for_each_r_to_l(F f) const {
		int anc_depth = log_2((a-1) ^ b);
		int anc_msk = (1 << anc_depth) - 1;
		for (int v = b & anc_msk; v; v &= v-1) {
			int i = __builtin_ctz(v);
			f(point((b >> i) - 1));
		}
		for (int v = (-a) & anc_msk; v; ) {
			int i = log_2(v);
			f(point(((a-1) >> i) + 1));
			v ^= (1 << i);
		}
	}

	template <typename F> void for_parents_down(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = log_2((x-1) ^ y);
		for (int i = log_2(x); i > dx; i--) {
			f(point(x >> i));
		}
		for (int i = anc_depth; i > dy; i--) {
			f(point(y >> i));
		}
	}

	template <typename F> void for_parents_up(F f) const {
		int x = a, y = b;
		if ((x ^ y) > x) { x <<= 1, std::swap(x, y); }
		int dx = __builtin_ctz(x);
		int dy = __builtin_ctz(y);
		int anc_depth = log_2((x-1) ^ y);
		for (int i = dx+1; i <= anc_depth; i++) {
			f(point(x >> i));
		}
		for (int v = y >> (dy+1); v; v >>= 1) {
			f(point(v));
		}
	}
};

struct in_order_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N, S;
	in_order_layout() : N(0), S(0) {}
	in_order_layout(int N_) : N(N_), S(N ? next_pow_2(N) : 0) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		a += S;
		return point(a >= 2 * N ? a - N : a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		a += S, b += S;
		return range((a >= 2 * N ? 2*(a-N) : a), (b >= 2 * N ? 2*(b-N) : b));
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return (a < S ? a + N : a) - S;
	}

	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? (x>>1) + N : x) - S, (y >= 2 * N ? (y>>1) + N : y) - S};
	}

	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		int l = __builtin_clz(2*a+1) - __builtin_clz(2*N-1);
		int x = (2*a+1) << l;
		assert(S <= x && x < 2*S);
		return (x >= 2 * N ? (x>>1) + N : x) - S;
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		return bounds[1] - bounds[0];
	}
};

struct circular_layout {
	// Alias them in for convenience
	using point = seg_tree::point;
	using range = seg_tree::range;

	int N;
	circular_layout() : N(0) {}
	circular_layout(int N_) : N(N_) {}

	point get_point(int a) const {
		assert(0 <= a && a < N);
		return point(N + a);
	}

	range get_range(int a, int b) const {
		assert(0 <= a && a <= b && b <= N);
		if (N == 0) return range();
		return range(N + a, N + b);
	}

	range get_range(std::array<int, 2> p) const {
		return get_range(p[0], p[1]);
	}

	int get_leaf_index(point pt) const {
		int a = int(pt);
		assert(N <= a && a < 2 * N);
		return a - N;
	}

	// Returns {x,y} so that 0 <= x < N and 1 <= y <= N
	// If the point is non-wrapping, then 0 <= x < y <= N
	std::array<int, 2> get_node_bounds(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < 2 * N);
		int l = __builtin_clz(a) - __builtin_clz(2*N-1);
		int S = next_pow_2(N);
		int x = a << l, y = (a+1) << l;
		assert(S <= x && x < y && y <= 2*S);
		return {(x >= 2 * N ? x >> 1 : x) - N, (y > 2 * N ? y >> 1 : y) - N};
	}

	// Returns the split point of the node, such that 1 <= s <= N.
	int get_node_split(point pt) const {
		int a = int(pt);
		assert(1 <= a && a < N);
		return get_node_bounds(pt.c(0))[1];
	}

	int get_node_size(point pt) const {
		auto bounds = get_node_bounds(pt);
		int r = bounds[1] - bounds[0];
		return r > 0 ? r : r + N;
	}
};

} // namespace seg_tree

seg_tree::in_order_layout layout;

const int INF = int(1e9) + 20;

// range set, point query
struct max_seg_tree {
	std::vector<int> v;
	max_seg_tree() : v(layout.N * 2, -INF) {}
	// inclusive update range
	void update(int l, int r, int x) {
		layout.get_range(l, r+1).for_each([&](auto a) {
			v[a] = std::max(v[a], x);
		});
	}
	int query(int a) {
		int res = -INF;
		if (a < 0 || a >= layout.N) return res;
		layout.get_point(a).for_each([&](auto a) {
			res = std::max(res, v[a]);
		});
		return res;
	}
};

struct min_seg_tree {
	std::vector<int> v;
	min_seg_tree() : v(layout.N * 2, +INF) {}
	// inclusive update range
	void update(int l, int r, int x) {
		layout.get_range(l, r+1).for_each([&](auto a) {
			v[a] = std::min(v[a], x);
		});
	}
	int query(int a) {
		int res = INF;
		if (a < 0 || a >= layout.N) return res;
		layout.get_point(a).for_each([&](auto a) {
			res = std::min(res, v[a]);
		});
		return res;
	}
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, M; cin >> N >> M;

	std::vector<std::array<std::array<int, 2>, 2>> rects(N);
	for (auto& r : rects) {
		cin >> r[0][0] >> r[1][0] >> r[0][1] >> r[1][1];
	}

	std::vector<int> x_coords; x_coords.reserve(N);
	std::vector<int> y_coords; y_coords.reserve(N);
	for (int i = 0; i < N; i++) {
		x_coords.push_back(rects[i][0][0]);
		y_coords.push_back(rects[i][1][0]);
	}
	std::sort(x_coords.begin(), x_coords.end());
	std::sort(y_coords.begin(), y_coords.end());
	for (int i = 0; i < N; i++) {
		rects[i][0][0] = int(std::lower_bound(x_coords.begin(), x_coords.end(), rects[i][0][0]) - x_coords.begin());
		rects[i][0][1] = int(std::upper_bound(x_coords.begin(), x_coords.end(), rects[i][0][1]) - x_coords.begin()) - 1;
		rects[i][1][0] = int(std::lower_bound(y_coords.begin(), y_coords.end(), rects[i][1][0]) - y_coords.begin());
		rects[i][1][1] = int(std::upper_bound(y_coords.begin(), y_coords.end(), rects[i][1][1]) - y_coords.begin()) - 1;

		//cerr << rects[i][0][0] << '-' << rects[i][0][1] << " x " << rects[i][1][0] << '-' << rects[i][1][1] << '\n';
	}

	layout = seg_tree::in_order_layout(N);

	auto build_lims = [&](std::vector<std::array<int, 2>> p) -> std::array<std::array<int, 2>, 2> {
		std::array<std::array<int, 2>, 2> lims{std::array<int, 2>{-INF, INF}, {-INF, INF}};
		for (int i = 0; i < N; i++) {
			bool is_covered = false;
			for (auto [x, y] : p) {
				if (rects[i][0][0] <= x && x <= rects[i][0][1] && rects[i][1][0] <= y && y <= rects[i][1][1]) {
					is_covered = true;
					break;
				}
			}
			if (is_covered) continue;
			for (int d = 0; d < 2; d++) {
				lims[d][0] = std::max(lims[d][0], rects[i][d][0]);
				lims[d][1] = std::min(lims[d][1], rects[i][d][1]);
			}
		}
		/*
		cerr << "lims from " << '\n';
		for (auto [x, y] : p) {
			cerr << x << ' ' << y << '\n';
		}
		for (auto [x, y] : lims) { cerr << x << '-' << y << ' '; } cerr << '\n';
		*/
		return lims;
	};

	auto solve_1 = [&](std::vector<std::array<int, 2>> p) -> std::vector<std::array<int, 2>> {
		assert(M >= 1);
		auto lims = build_lims(p);
		if (lims[0][0] <= lims[0][1] && lims[1][0] <= lims[1][1]) {
			p.push_back({lims[0][0], lims[1][0]});
			return p;
		}
		return {};
	};

	auto solve_2 = [&](std::vector<std::array<int, 2>> p) -> std::vector<std::array<int, 2>> {
		assert(M >= 2);
		auto lims = build_lims(p);
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				std::vector<std::array<int, 2>> np = p;
				np.push_back({lims[0][a], lims[1][b]});
				auto resp = solve_1(np);
				if (!resp.empty()) return resp;
			}
		}
		return {};
	};

	auto solve_3 = [&](std::vector<std::array<int, 2>> p) -> std::vector<std::array<int, 2>> {
		assert(M >= 3);
		auto lims = build_lims(p);
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				std::vector<std::array<int, 2>> np = p;
				np.push_back({lims[0][a], lims[1][b]});
				auto resp = solve_2(np);
				if (!resp.empty()) return resp;
			}
		}
		return {};
	};

	auto solve_4 = [&]() -> std::vector<std::array<int, 2>> {
		assert(M >= 4);
		auto lims = build_lims({});
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				std::vector<std::array<int, 2>> np;
				np.push_back({lims[0][a], lims[1][b]});
				auto resp = solve_3(np);
				if (!resp.empty()) return resp;
			}
		}

		// There must be a solution here
		// If we haven't found it, we can't be in the 1D case, since the greedy works for 1D
		assert(lims[0][0] > lims[0][1]);
		assert(lims[1][0] > lims[1][1]);

		int x0 = lims[0][1];
		int x1 = lims[0][0];

		int y0 = lims[1][1];
		int y1 = lims[1][0];

		min_seg_tree y0_x1_hi;
		max_seg_tree y1_x1_lo;

		max_seg_tree ys_lo;
		min_seg_tree ys_hi;

		max_seg_tree x0_x1_lo;
		min_seg_tree x0_x1_hi;

		min_seg_tree x0_y0_hi;
		min_seg_tree x0_y1_hi;

		cerr << "solving " << x0 << ' ' << x1 << ' ' << y0 << ' ' << y1 << '\n';

		int x0_lo = y0+1;
		int x0_hi = y1-1;

		std::vector<std::vector<std::pair<int, int>>> evts(N);

		for (int i = 0; i < N; i++) {
			auto [xs, ys] = rects[i];
			auto [xlo, xhi] = xs;
			auto [ylo, yhi] = ys;
			int num_cover = (xlo <= x0) + (x1 <= xhi) + (ylo <= y0) + (y1 <= yhi);
			assert(num_cover > 0);
			if (num_cover >= 3) {
				continue;
			} else if (num_cover == 1) {
				//cerr << "got 1 cover " << '\n';
				if (xlo <= x0) {
					setmax(x0_lo, ylo);
					setmin(x0_hi, yhi);
				} else if (x1 <= xhi) {
					x0_x1_lo.update(0, N-1, ylo);
					x0_x1_hi.update(0, N-1, yhi);
				} else if (ylo <= y0) {
					x0_y0_hi.update(0, N-1, xhi);
					y0_x1_hi.update(0, xlo-1, -1);
				} else if (y1 <= yhi) {
					x0_y1_hi.update(0, N-1, xhi);
					y1_x1_lo.update(0, xlo-1, N);
				} else assert(false);
			} else if (num_cover == 2) {
				//cerr << "got 2 cover " << '\n';
				if (xlo <= x0 && ylo <= y0) {
					x0_y0_hi.update(yhi+1, N-1, xhi);
				} else if (xlo <= x0 && y1 <= yhi) {
					x0_y1_hi.update(0, ylo-1, xhi);
				} else if (xlo <= x0 && x1 <= xhi) {
					x0_x1_lo.update(0, ylo-1, ylo);
					x0_x1_hi.update(0, ylo-1, yhi);

					x0_x1_lo.update(yhi+1, N-1, ylo);
					x0_x1_hi.update(yhi+1, N-1, yhi);
				} else if (ylo <= y0 && y1 <= yhi) {
					ys_lo.update(0, xlo, xlo);
					ys_hi.update(0, xlo, xhi);
				} else if (ylo <= y0 && x1 <= xhi) {
					y0_x1_hi.update(0, xlo-1, yhi);
				} else if (y1 <= yhi && x1 <= xhi) {
					y1_x1_lo.update(0, xlo-1, ylo);
				} else assert(false);
			} else assert(false);
		}

		for (int x0y = x0_lo; x0y <= x0_hi; x0y++) {
			//cerr << "trying " << x0 << ' ' << x0y << '\n';

			int y0_hi = x0_y0_hi.query(x0y);
			setmin(y0_hi, N-1);
			if (y0_hi < 0) continue;

			int y1_hi = x0_y1_hi.query(x0y);
			if (y1_hi < 0) continue;
			setmin(y1_hi, N-1);

			// pick the first thing that ends
			int y_first_hi = ys_hi.query(0);
			if (y_first_hi < 0) continue;
			setmin(y_first_hi, N-1);
			//cerr << "have " << y0_hi << ' ' << y1_hi << ' ' << y_first_hi << '\n';
			for (int z = 0; z < 2; z++) {
				int y0x, y1x;
				if (z == 0) {
					y0x = std::min(y0_hi, y_first_hi);
					y1x = std::min(y1_hi, ys_hi.query(y0x+1));
					if (y1x < 0) continue;
					setmin(y1x, N-1);
					if (y1x < ys_lo.query(y0x+1)) continue;
				} else {
					y1x = std::min(y1_hi, y_first_hi);
					y0x = std::min(y0_hi, ys_hi.query(y1x+1));
					if (y0x < 0) continue;
					setmin(y0x, N-1);
					if (y0x < ys_lo.query(y1x+1)) continue;
				}
				//cerr << "y0x " << y0x << ' ' << "y1x" << ' ' << y1x << '\n';
				int x1_lo = std::max(y1_x1_lo.query(y1x), x0_x1_lo.query(x0y));
				int x1_hi = std::min(y0_x1_hi.query(y0x), x0_x1_hi.query(x0y));
				//cerr << "x1y must be " << x1_lo << '-' << x1_hi << '\n';
				setmax(x1_lo, 0);
				setmin(x1_hi, N-1);
				if (x1_lo > x1_hi) continue;
				return {{x0, x0y}, {y0x, y0}, {y1x, y1}, {x1, x1_lo}};
			}
		}
		assert(false);
	};

	auto solve = [&]() -> std::vector<std::array<int, 2>> {
		std::vector<std::array<int, 2>> r;
		r = solve_1({});
		if (!r.empty()) return r;
		r = solve_2({});
		if (!r.empty()) return r;
		r = solve_3({});
		if (!r.empty()) return r;
		r = solve_4();
		if (!r.empty()) return r;
		assert(false);
	};
	auto ans = solve();
	cout << ans.size() << '\n';
	for (auto [x, y] : ans) {
		cout << x_coords[x] << ' ' << y_coords[y] << '\n';
	}

	return 0;
}

→ Ответить

ecnerwala

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

+31

Problem G's semantics seem a little strange. I managed to get AC by disabling liveness checks for direct references but not indirect references. In particular, my AC submission prints

2
fn input()
fn foo(&a, b)
2
a := input()
c := foo(&a, a)
Valid

versus

2
fn input()
fn foo(&a, b)
3
a := input()
b := &a
c := foo(b, a)
Error in line 3

Is this intended? I would've thought that both are supposed to be errors. (My original code was getting WA on test 14.)

→ Ответить

never_giveup

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

← Rev. 2 →

My solution prints an error for both programs. There is a rule for this (which I'm sure you saw but anyway):

You cannot pass a value variable and a reference to that variable at the same time on the same line.

It seems that 34 tests is not enough for this kind of problem, considering that there are 100 tests for others.

→ Ответить

ecnerwala

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

That makes sense, but my solution only passes tests when I changed it to allow the first case :'( Does anyone know what test 14 is?

→ Ответить

wilcot

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

← Rev. 2 →

14 test case was:

1
fn input()
4
a := input()
b := &a
a := a
b := &a

Also, both previous examples should output "Error" due to the rule in the comment above. Here, indeed, 34 tests were not enough.

→ Ответить

ecnerwala

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

Ah ok that explains my bug, I forgot to reassign a a new variable ID. Thanks!

→ Ответить

Qingyu

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

← Rev. 2 →

+13

34 tests is not enough for this kind of problem

I just noticed that my first attempt failed on the last test, which happened to not handle this rule correctly :(

Screenshot 2022-05-02 155347.png

For my first attempt, it prints Valid in the following test (excpected Error in line 2)

3
fn input()
fn f(&x)
fn g(x, y)
2
x := input()
y := g(f(&x), x)

→ Ответить

ecnerwala

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

One question: what does "at the same time" mean? Does it mean to the same function? Are you allowed to use the same variable if it is passed to different function call subexpressions? (Perhaps only if the borrow occurs before the move?) If this is the case, is there a well-specified order-of-evaluation for subexpressions?

→ Ответить

never_giveup

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

I believe in this problem for the sake of understanding you can actually omit "at the same time", since (I think) it only matters if they are on the same line (which we treat as one instruction in this problem).

→ Ответить

wilcot

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

You cannot pass a value variable and a reference to that variable at the same time on the same line.

By our design, this means that you can use the variable by name or you can use its references, but not both on the same line.

This rule is necessary to resolve the uncertainty of the order of function calls, which is not described in the statements.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 19.11.2024 06:50:59 (k1).

Десктопная версия, переключиться на мобильную.

При поддержке