Japanese Olympiad in Informatics (JOI) Spring Camp 2021

4 years ago, # |

+80

On one hand this looks great, I remember JOI got great quality problems. But on the other — these hours... Would it be possible to make these time windows longer by at least 2 hours or sth (end them 2 hours later to be precise)?

→ Reply

ppavic

4 years ago, # ^ |

+75

Yeah, two hours later and even two hours earlier would be perfect. Because for us in school, we have to pull an allnighter and it starts too late to end before school. :*(

→ Reply

atharv

4 years ago, # |

+43

Do we know yet if there will eventually be English editorials for the problems?

→ Reply

yutaka1999

4 years ago, # |

+73

Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).

→ Reply

4 years ago, # ^ |

+38

Thanks!

→ Reply

4 years ago, # |

+34

Day 1 seems to be over.

What strategies did people use on the output only?

→ Reply

4 years ago, # |

+24

Interesting problems!

How would you solve food court and IOI Fever?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+18

Food court: we do two passes over the operations. In the first pass, we find for every ice cream, what is the index of the person who gets it (with the $$$i$$$th person added to a queue having index $$$i$$$). In the second pass, we get the groups of these people.

For the first pass, maintain in segment trees the total amount of people added to each stall so far, and the current amount of people at each stall. Given a query $$$a\ b$$$, let $$$t$$$ and $$$c$$$ be the total added so far and current number for stall $$$a$$$. Then, if $$$b \leq c$$$, the ice cream goes to the person with index $$$t - (c - b)$$$.

For the second pass, sort the indices of people for every stall. Maintain for every stall, the number of people that must be added to the stall before the total number of people added so far is at least the next index. Whenever you get a range add operation, subtract from the range, then while there is some stall with value at most $$$0$$$, answer its query with the group of the current operation, and increment its value by the difference between the current and next indices.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

+18

I thought of something similar during the contest. However, I wasn't sure how to calculate the number of people at a certain stall (c) at any given time. I could only think of calculating it using segment tree beats, but I didn't implement it because I thought it would be too slow. Will segtree beats or smth similar pass, or am I just being stoopid?

Edit: I just glanced at the code you posted, and it seems like segtree beats does indeed pass! I feel silly for not implementing during contest :sob:

→ Reply

4 years ago, # ^ |

+13

I tried segment tree beats and got TLE. Thankfully, you don't need it, since you only query $$$1$$$ index at a time. Storing interval maximum, and value to add to interval is enough.

→ Reply

dorijanlendvaj

4 years ago, # ^ |

+37

It's also possible to do it with lazy propagation; the tag is $$$(a, b)$$$ which means that, if the value in the segment tree is $$$x$$$, it should be changed to $$$min(x-a, 0)+b$$$. Sadly that got TLE too; it was about 2x slower than getting the groups of the people, which had an extra log. I didn't know lazy propagation had such a huge constant...

→ Reply

PedroBigMan

4 years ago, # ^ |

+15

Yes, i got TLE on that too. It seems that JOI has super tight time limits.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+18

IOI Fever: assume person $$$1$$$ starts at $$$(0, 0)$$$. select the direction person $$$1$$$ moves to. This uniquely determines the directions of every other person: there is only one direction, such that there exists some $$$t$$$, such that moving in that direction, at time $$$t$$$, the person is at most $$$t$$$ units away from the origo.

We will compute for every person the first time that person is infected (multiplied by $$$2$$$ for convenience). This is easy to do in $$$\mathcal{O}(n^2 \log n)$$$. To optimise it, we do the following instead:

For each of the 8 directions E, SE, S, SW, W, NW, N, NE. For every direction $$$d$$$, make a vector containing every person, sorted by

Which direction that person is going to
Which line in direction $$$d$$$ that person is on
How far along the line that person is

Now, write a segment tree that maintains two sets of values $$$a_i$$$ and $$$b_i$$$, and supports queries

Output $$$i$$$ with minimum $$$a_i + b_i$$$
Set $$$a_i \leftarrow min(b_i, x)$$$ for all $$$L \leq i \leq R$$$
Set $$$b_i \leftarrow x$$$

Make one such segment tree over each of your $$$8$$$ vectors. set the values $$$b_i$$$ to be how far along the line the person with index $$$i$$$ in the sorted order is, multiplied by $$$-1$$$. Initially set $$$a_i = 0$$$ for $$$i$$$ corresponding to person $$$1$$$, and $$$a_i = \infty$$$ for all other $$$i$$$.

Now, handle persons in increasing order of time of infection. Assume a person is infected at time $$$t$$$, and is going east. They hit exactly three types of people:

People further on the same NW line, going south
People further on the same W line, going west
People further on the same SW line, going north

Further, the people they hit after getting infected are exactly the people at least $$$2t$$$ away (in manhattan distance) on the same NW, W or SW line. This corresponds to a segment tree operation of type $$$2$$$ on some interval, which you can binary search!

To get the person with next smallest time of infection, get the minimum value over the 8 segment trees. Once you handle a person, set all $$$b_i$$$ corresponding to them to infinity, so they do not get selected again.

→ Reply

gamegame

4 years ago, # ^ |

+20

I had a workaround which helped me to avoid segment tree. Let the last edge of the shortest path to reach $$$v$$$ from a certain direction is $$$u -> v$$$, and then $$$v'$$$ be the previous node on this direction. Then either you cannot go directly from $$$u$$$ to $$$v'$$$ (due to distance being too short), or the last edge of the shortest path to reach $$$v'$$$ from this direction is $$$u -> v'$$$, and that the distance to $$$v'$$$ is shorter than distance to $$$v$$$ from this direction.

Thus, we can run dijkstra with $$$8n$$$ nodes (but only $$$\le 3n$$$ will be visited) and when we visit a node $$$v'$$$, we only add the closest one we can reach in each direction ($$$\le 3$$$ edges of the form $$$v'->x$$$), and we should also take care of the above case and add edges $$$u->v$$$ suitably.

Still, my code is 200+ lines... So much pain

→ Reply

4 years ago, # ^ |

+41

Key idea is to sweep per the indices of stall, not per the indices of query (which is naturally suggested).

Solve the problem offline, and maintain a segment tree with query index as a key. Sweep by the index of a stall. You can capture all relevant queries stored in a data structure, for each stalls.

Consider push as number +k, pop as number -k. Then, the current people in the queue at time i, is the maximum sum subsegment that exactly ends at index i. Computing this value is standard.

With this information the index of k-th person can be found by descending down the tree (or maintaining separate fenwick trees)

→ Reply

Jarif_Rahman

4 years ago, # |

when will the registration for day 2 start? Also do I need to re-register for day 2 or use the username and password of the previous day?

→ Reply

Lakshi4h

4 years ago, # ^ |

I think the 4 days are continuous.

yes. I just checked. Day 2 has started.

→ Reply

SpaceIndex

4 years ago, # |

Where can I find Day 1 problems? Are there PDFs or text files available?

→ Reply

4 years ago, # |

+21

I'm really interested in how Shopping could be solved, seems impossible :O

Best I can do is a bit over 8000 bits, by having A output the 9 most significant bits of L and R, and B output a binary representation of the cartesian tree, that has a vertex for every value in the two $$$2^{11}$$$-length blocks containing $$$L$$$ and $$$R$$$, and a single vertex representing the minimum in between (+ its index).

→ Reply

ksun48

4 years ago, # ^ |

+46

Solution idea which uses ~1k: we have interactive binary search between Bruno and Anna, Bruno picks some interval [a,b] such that a-1 and b+1 are cheaper than everything in the interval, and Anna responds whether L and R are both contained in the interval. If they aren’t, then we can discard items [a,b], if they are we can restrict to this interval. We can find such an interval of size between n/3 and 2n/3.

At the end we do the same as above, sending Cartesian tree.

This approach can be improved somewhat but doesn’t seem like it can get down to 18+300 queries.

→ Reply

Rebelz

4 years ago, # |

+48

Where can I upsolve the problems?

→ Reply

4 years ago, # ^ |

ojuz usually uploads the problems to oj.uz after the test data gets published but the test data is not published till now.I think they will publish it after all the 4days get over

→ Reply

MatheusLealV

4 years ago, # |

How to solve Day2 A (escape route) ?

→ Reply

4 years ago, # |

← Rev. 3 →

+26

How tf did all of you guys managed to fit road_construction in TL xd? I coded $$$O(n \log^2 n)$$$ in three different ways and after an hour of optimizing it I finally managed to pass subtask with $$$n \le 10^5$$$, but still a long way to go to 250000 xd

→ Reply

Normie28

4 years ago, # ^ |

← Rev. 5 →

Same here.

My optimizations include:

Rewriting the code in order to compress coordinates in $$$O(n)$$$ per binary search iteration
Replacing segtree with BIT (which should help to reduce the number of function calls?)

It still failed on 250000 (Took 11.25s on one of my own tests). I'm curious about how so many people passed TL while I couldn't. Was there a way to solve the problem in $$$O(n log n)$$$ that I didn't know about?

→ Reply

ijxjdjd

4 years ago, # ^ |

I'm really curious about the $$$n \log^2n$$$ solution because I passed with something like $$$N \sqrt{N}\log{N}$$$, albeit with a lot of time spent optimizing and probably relatively weak tests.

→ Reply

tdas

4 years ago, # ^ |

+13

Binary search the last value. Use and ordered_set to get roads less than the last value.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Yes,it can be solved in O(n log n), though I pass it with two logs.

→ Reply

dalex

4 years ago, # ^ |

Can you also solve this in NlogN? They are very similar, but k is large and you need to output only the k-th distance. I don't know how.

→ Reply

Normie28

4 years ago, # ^ |

← Rev. 2 →

Code in case anyone wants to help me. It's roughly the same solution as the $$$O(n$$$ $$$log$$$ $$$n$$$ $$$log$$$ $$$x)$$$ one ko_osaga described.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+11

I just used vanilla order_statistic_tree with PBDS and it passed on the first try.

order_statistic_tree template


template <typename K, typename V, typename Comp = std::less<K>>
using order_statistic_map = __gnu_pbds::tree<
	K, V, Comp,
	__gnu_pbds::rb_tree_tag,
	__gnu_pbds::tree_order_statistics_node_update
>;

template <typename K, typename Comp = std::less<K>>
using order_statistic_set = order_statistic_map<K, __gnu_pbds::null_type, Comp>;

// Supports
//  auto iterator = order_statistic_set().find_by_order(idx); // (0-indexed)
//  int num_strictly_smaller = order_statistic_set().order_of_key(key);

→ Reply

4 years ago, # ^ |

Wow, I thought that "maybe I can use this problem in an educational way for learning pbds", but then thought "no way I will pass with this, cause this is probably gonna be much slower" xd

→ Reply

ksun48

4 years ago, # ^ |

+24

I think mine is n log n w/ persistent segment tree.

→ Reply

dalex

4 years ago, # ^ |

+31

Half of the comments are downvoted for no reason, but I don't care about contribution, so can you tell how to do it in NlogN?

→ Reply

mnbvmar

4 years ago, # ^ |

← Rev. 2 →

+39

I didn't code it like that (I had a slower solution), but I imagine it could work as follows:

Let's say that for each point, you want to find the closest point in the Manhattan metric. Let's simplify the problem a bit: for each point $$$(x, y)$$$, find the closest point $$$(x', y')$$$ such that $$$x' \geq x$$$ and $$$y' > y$$$. I hope you can easily see that the non-simplified problem reduces to $$$4$$$ runs of the simplified problem, for $$$0^\circ$$$, $$$90^\circ$$$, $$$180^\circ$$$, and $$$270^\circ$$$ rotations of the plane.

You can solve the simplified problem by sweeping from right to left using a segment tree: when reaching a point $$$(x, y)$$$, store $$$x+y$$$ at the position $$$y$$$ of the segment tree, and read from the segment tree the minimum value of $$$x'+y'$$$ over the points $$$(x',y')$$$ such that $$$y' > y$$$; the sought distance is $$$|x' - x| + |y' - y| = (x'+y')-(x+y)$$$, since $$$x' \geq x$$$ and $$$y' > y$$$. (I'm sweeping the coordinate compression under the rug, but it's quite trivial.) This can be easily done in $$$O(n \log n)$$$ time.

Now, back to the original problem. Do the four runs of the sweep-line algorithm as above, but make the segment trees above persistent. Now, for each point on the plane, we have four persistent snapshots of a segment tree, each created when reaching this point on a sweep-line. In other words, for each point $$$P$$$ and for each of the quadrants of the plane centered at this point, you know the closest point $$$Q$$$ to $$$P$$$ in this quadrant. You can put the distances from $$$P$$$'s to $$$Q$$$'s in a priority queue. When you remove a pair $$$(P, Q)$$$ from the priority queue, you remove $$$Q$$$ from the corresponding snapshot of the segment tree, producing a new snapshot, from which you can read the closest point from $$$P$$$, different than $$$Q$$$, in the quadrant containing $$$Q$$$. Continue till you find $$$k$$$ pairs of points. The total time and space complexity is $$$((n + k) \log n)$$$.

Actually, since the problem is symmetric, you can notice that you don't need four rotations; only two ($$$0^\circ$$$ and $$$90^\circ$$$) are necessary because the remaining two will produce the same pairs of points as the first two.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

My $$$\log n \log X$$$ solution uses coordinate compression + fenwick tree and passes in 4s first try.

Probably, if you want $$$\log n$$$ solution, you can maintain persistent segment trees for each quadrant. Then for each point, you can capture relevant neighbors in the segment tree. To visit the top-k candidate for each point, pick some interval, find the maximum, and split the interval per the maximum's occurence. To do it globally, you can use priority queues.

→ Reply

4 years ago, # ^ |

Could you share your log n log X solution? It sounds the most similar to mine, so I would probably be able to understand how I could have done that more efficiently.

And thanks for explaining log n solution. Sounds nice in theory, however it would be at least a few times harder to implement.

→ Reply

4 years ago, # ^ |

Here's my $$$\mathcal{O}(n \log n \log X)$$$ with coordinate compression and fenwick tree. I don't remember how fast it was, but it did pass first try.

code

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

const ll INF = 1e12;

// returns number of elements strictly smaller than v in vec
template<class T>
int bins(const vector<T>& vec, T v) {
	int low = 0;
	int high = vec.size();
	while(low != high) {
		int mid = (low + high) >> 1;
		if (vec[mid] < v) low = mid + 1;
		else high = mid;
	}
	return low;
}

class Fenwick {
	private:
		vector<ll> val;
	public:
		Fenwick(int n) : val(n+1, 0) {}

		// Adds v to index i
		void add(int i, ll v) {
			for (++i; i < val.size(); i += i & -i) {
				val[i] += v;
			}
		}

		// Calculates prefix sum up to index i
		ll get(int i) {
			ll res = 0;
			for (++i; i > 0; i -= i & -i) {
				res += val[i];
			}
			return res;
		}
		ll get(int a, int b) { return get(b) - get(a-1); }

		// Assuming prefix sums are non-decreasing, finds last i s.t. get(i) <= v
		int search(ll v) {
			int res = 0;
			for (int h = 1<<30; h; h >>= 1) {
				if ((res | h) < val.size() && val[res | h] <= v) {
					res |= h;
					v -= val[res];
				}
			}
			return res - 1;
		}
};

ll count(ll max_d, const vector<pair<ll, ll>>& pts, const vector<ll>& xs, const vector<ll>& ys) {
	int w = xs.size(), h = ys.size();
	Fenwick fenw(h);

	int j = 0;
	ll res = 0;
	for (int i = 0; i < pts.size(); ++i) {
		ll x = xs[pts[i].first], y = ys[pts[i].second];
		while(j < i && xs[pts[j].first] + max_d < x) {
			fenw.add(pts[j].second, -1);
			++j;
		}

		int a = bins(ys, y - max_d);
		int b = bins(ys, y + max_d + 1);
		res += fenw.get(a, b-1);

		fenw.add(pts[i].second, 1);
	}

	return res;
}

vector<ll> solve(ll max_d, const vector<pair<ll, ll>>& pts, const vector<ll>& xs, const vector<ll>& ys) {
	int w = xs.size(), h = ys.size();
	Fenwick fenw(h);
	vector<vector<int>> inds(h);

	int j = 0;
	vector<ll> res;
	for (int i = 0; i < pts.size(); ++i) {
		ll x = xs[pts[i].first], y = ys[pts[i].second];
		while(j < i && xs[pts[j].first] + max_d < x) {
			fenw.add(pts[j].second, -1);
			++j;
		}

		int a = bins(ys, y - max_d);
		int b = bins(ys, y + max_d + 1);

		ll cur = fenw.get(a-1);
		while(a < b) {
			a = fenw.search(cur) + 1;
			if (a >= b) break;

			ll nxt = fenw.get(a);
			ll cou = nxt - cur;
			cur = nxt;

			assert(cou <= inds[a].size());
			for (ll ind = (ll)inds[a].size() - cou; ind < inds[a].size(); ++ind) {
				int j = inds[a][ind];
				res.push_back(max(abs(xs[pts[i].first] - xs[pts[j].first]), abs(ys[pts[i].second] - ys[pts[j].second])));
			}
		}

		fenw.add(pts[i].second, 1);
		inds[pts[i].second].push_back(i);
	}

	return res;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	// Standard transformation: (x, y) -> (x+y, x-y)
	// -> d((a, c), (b, d)) = abs(|a - b|, |c - d|)

	// 1. Get minimum distance such that it finds k
	// 2. Get distances < k

	vector<ll> xs(n), ys(n);
	vector<pair<ll, ll>> pts(n);
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		pts[i] = {x + y, x - y};
		xs[i] = x + y;
		ys[i] = x - y;
	}

	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	ys.erase(unique(ys.begin(), ys.end()), ys.end());

	for (int i = 0; i < n; ++i) {
		pts[i].first = bins(xs, pts[i].first);
		pts[i].second = bins(ys, pts[i].second);
	}
	sort(pts.begin(), pts.end());

	ll low = 1;
	ll high = INF;
	while(low != high) {
		ll mid = (low + high) >> 1;
		if (count(mid, pts, xs, ys) >= k) high = mid;
		else low = mid + 1;
	}

	vector<ll> res = solve(low - 1, pts, xs, ys);
	while(res.size() < k) res.push_back(low);

	sort(res.begin(), res.end());
	for (ll v : res) cout << v << '\n';
}

→ Reply

4 years ago, # ^ |

→ Reply

4 years ago, # ^ |

+13

Lol I think it's just fast because of breaks in L41

→ Reply

zscoder

4 years ago, # ^ |

+15

I coded the $$$O(n\log n)$$$ persistent segment tree solution and it still took more than half of TL (6s-ish :|).

→ Reply

dolphingarlic

4 years ago, # ^ |

+13

My solution was basically:

Rotate the plane by 45 degrees.
Modify the line sweep used to find the pair of closest points by Euclidean distance to find $$$K$$$ closest pairs of points by Chebyshev distance instead.

I only needed to use a std::multiset, which was quite surprising. I have no idea what the time complexity of this is, but it passed first try without any optimisations. Do you think the test data was weak?

→ Reply

seduneon

4 years ago, # ^ |

← Rev. 2 →

Could you explain how do you rotate the plain by 45 degrees? (I mean how the coordinates will change?)

→ Reply

dolphingarlic

4 years ago, # ^ |

+28

Map coordinates $$$(x, y)$$$ to $$$(x + y, x - y)$$$. This is also convenient because it turns Manhattan distance into Chebyshev distance

→ Reply

Sorting

4 years ago, # ^ |

I was able to cheat it with $$$O(n^2logX)$$$ and some optimizations — https://pastebin.com/UymFvR2j

→ Reply

PedroBigMan

4 years ago, # ^ |

+23

Ahaha I spent all the time frustrated trying to optimize the solution to that problem. In the end my submissions together cleared all the test cases though I only got 18 points. I am not a very experienced competitor, so I'm curious, don't these tight time limits ruin the fun of a contest for you higher rated guys?

→ Reply

4 years ago, # ^ |

-16

I think intended solution is O(nlogn) with persistent segment tree.(which is what I did)

→ Reply

Normie28

4 years ago, # ^ |

← Rev. 3 →

Subtask 2 is likely $$$O(n$$$ $$$log^2$$$$$$n)$$$ — the simplest solution involves sorting the points by $$$x$$$-coordinate and then do a binary search over the length of the k-th distance, and in each iteration we would do a binary search for each point to know the number of points within a distance $$$\le$$$ a given number $$$x$$$ from that point. Because of this I assume a $$$O(n$$$ $$$log^2$$$$$$n)$$$ overall solution is intended to pass.

Actually now that I think of it, subtask 2 can also be solved in $$$O(n$$$ $$$log$$$ $$$n)$$$ by using two pointers, taking advantage of the fact that the points are already sorted, so now I'm not sure what is the intended complexity either.

→ Reply

ppavic

4 years ago, # |

← Rev. 2 →

+272

The problem Shopping inspired me for this little poem.

Whether you're red
or you're blue
there's always a problem
you don't even have a clue how to do

→ Reply

generic_placeholder_name

4 years ago, # |

← Rev. 3 →

+52

A solution for Ancient Machine that gets 100 points:

First, I will describe an algorithm that gets us maximal good removals, provided that we know the values of all indices:

Step 1: Let $$$f$$$ be the first occurence of $$$X$$$. We remove all indices before $$$f$$$.

Step 2: Let $$$lst$$$ be the last occurence of $$$Z$$$. Initially, we set $$$lst$$$ to $$$f$$$.

Step 3: Loop all indices $$$i$$$ from $$$f + 2$$$ to $$$n - 1$$$. If we encounter an occurence of $$$Z$$$, we remove, in reverse order, all indices from $$$i - 1$$$ to $$$lst + 1$$$, and then remove $$$i$$$ and set $$$lst$$$ to $$$i$$$.

Step 4: Remove the remaining numbers.

It is possible to prove that this algorithm is optimal.

Now, we have to send the position of the first $$$X$$$, as well as all following $$$Z$$$s. This is possible to do with a bitstring of length $$$n$$$. We will try to compress this bitstring.

Notice that, in the aforementioned algorithm, if we have an occurence of $$$Z$$$ that is immediately before another occurence of $$$Z$$$, it doesn't matter if we remove it or not. Therefore, we ignore all such indices.

By doing so, we obtain a bitstring that has the property that no two values of $$$1$$$ are adjacent to each other. Therefore, for every block $$$n$$$ of this bitstring, there are only $$$fib(n+2)$$$ possible states, where $$$fib(i)$$$ is the $$$i^{th}$$$ fibonacci number. Furthermore, it is possible to map each bitstring to an unique number by a simple dynamic programming.

We divide the bitstring into blocks of $$$T$$$ elements. For each block, the number of bits needed to display the value of this bitstring is $$$\left \lceil{log_2(fib(T+2))}\right \rceil$$$, therefore we can estimate the total number of bits to be $$$n \times \frac{\left \lceil{log_2(fib(T+2))}\right \rceil}{T}$$$. This number is small enough when $$$T = 93$$$, where the value is about $$$n \times 0.699$$$.

As a side note, as $$$T$$$ increases, the value converges to $$$n \times log_2{\varphi}$$$, which is about $$$0.694 \times n$$$.

P.S. Sorry for causing a solution leak. I realized this several minutes after I posted this, but CF didn't allow me to delete anymore.

→ Reply

4 years ago, # ^ |

+42

The contest is still going on.

→ Reply

generic_placeholder_name

4 years ago, # ^ |

+34

Oops, sorry.

→ Reply

4 years ago, # ^ |

+16

Nice solution :)

→ Reply

Luca

4 years ago, # ^ |

← Rev. 2 →

-6

Deleted

→ Reply

4 years ago, # ^ |

+13

Here's a solution that I think is correct:

First, identify the first X, the last Z, and the last Y before the last Z; clearly anything before the first X or after the last Z is useless. Also, identify all occurrences of "YX" as a substring between the first X and the last Y before the last Z. Mark all of these 3+2k characters as "special". Then, Bruno should do 3 passes:

Remove all non-special characters going left to right.
Remove all special characters except the last Z, going from right to left.
Remove the last Z.

The proof of correctness essentially comes from considering the runs of Ys and non-Ys. Each run of Ys can cause at most one good removal, and we need to pick one character from each run of non-Ys to act as borders of the good removals. For each run of non-Ys, we arbitrarily decide to using its first character (either X or Z). If the first character is Z, then there is a good removal in the left-to-right pass. If the first character is X, then we save it for the second pass.

To compress this data, we can directly transmit the locations of the first X, the last Z, and the last Y before the last Z in about 60 bits. For the rest, we use the same observation that, because we're trying to send a list of non-overlapping substrings of length 2, the number of possible strings is a Fibonacci number, so we can compress by a ratio of $$$\log(\phi) / \log(2) \approx 0.694$$$. I compressed blocks of 250 characters into 174 bits each, but other choices of block size work too.

→ Reply

satashun

4 years ago, # ^ |

Almost exactly the same solution as ecnerwala, but I used only the first X information (for the 2 part, erased until the leftmost X appears). In addition to checking whether the character is Z or else, I marked only Zs whose left character is not Z, then the number of states follows fibonacci sequence. I enumerated fibonacci numbers and compare $$$ceil(\log2 fib_i)$$$ and $$$i * 0.7$$$ to find bucket size (I set 63).

→ Reply

4 years ago, # ^ |

+31

Huh? The algorithm works in that case. With the removals, we have

run on case XYXYZZ

I also got 100p with the same algorithm, but a dumber interaction protocol. I output the distances between the Z's, packed with an optimal code.

→ Reply

Luca

4 years ago, # ^ |

← Rev. 2 →

My bad, I misread and therefore misunderstood the way the algorithm worked. Thanks for clearing it out with the example.

→ Reply

4 years ago, # |

+18

What a nice changeup to be able to get 100 points within 18 minutes after two days of doing basically nothing xD (I didn't take serious attempts at first two days, but still)

→ Reply

JT.TXDY.

4 years ago, # |

+29

Most problem have tight time limit :(

→ Reply

yutaka1999

4 years ago, # |

← Rev. 3 →

+87

Solution for Shopping:

First Step: when Bruno knows some index in Anna's interval (15 bits for Anna and 300 bits for Bruno)

Second Step: Anna sends one index in her interval in a proper way

Summary

→ Reply

Bruteforceman

4 years ago, # |

+63

When is the final rank list going to be published? We were using this contest for the team selection in our country. Contestants were told to do the contest right after the window starts so that they cannot download problems from fake accounts beforehand. But without the rank list, it's quite hard to verify this. I hope we would be able to see submission times in the final rank list.

→ Reply

4 years ago, # |

← Rev. 3 →

Lol, my code started working on sample 25 seconds before contest ended. I submitted it with some time left, but it didn't evaluate before time ended and my access was shut xd. Can I get to know in any way the result of my submission xd?

EDIT: OK, I created second account and submitted from there xd. Sorry for hypothetical spoiling the ranking, but that should not be a big deal. I got 0/100 and since the timer was quickly running out I was checking my code only on the 4th sample close to the end, but it didn't work even on 1st one, so I got 0/100 :). But I already got 100/100 and that was really a quick fix :<

→ Reply

4 years ago, # |

+16

Navigation was a really cool problem, my favourite from whole camp I think.

I got a feeling that whole set of 12 problems was really DS and implementation heavy. Problems with standard format were really not varied and rather boring. Bodyguard, reporter, food court, road construction for sure + events, fever, meetings to some extent as well (oh, did I mention 7 out of 8 "batch" problems xd?). Good that communication tasks helped with variety and originality a lot

→ Reply

PurpleCrayon

4 years ago, # ^ |

-8

How do you get more than 50 points in navigation?

→ Reply

4 years ago, # ^ |

+52

You divide all cells into 9 equivalence classes by remainders modulo 3 in both dimendions. Wherever Bruno stands, he sees exactly one cell from each such class (but he doesn't know which is which).

Let us highlight all cells from arbitrarily chosen equivalence class and give them unique number (e.g. 14 in a version where we aim at 14 colors). Then Bruno is able to tell to which equivalence classes cells he sees belong to. We can take 7 of the remaining 8 equivalence classes and say that i-th of them will have information about i-th goal. Let us now focus on some particular cell that will keep information about i-th goal. If it is close to it, at most 1 far apart in both coordinates, it says in which out of these 9 surrounding cells the goal is. If it is further away then there is a direction in which it is at least 2 cells far apart. If we see that cell then we are at most 1 far apart from this cell, so we can safely make a step in that direction and that cell will tell us which way to go (4 possible values). Note that we didn't use one equivalence class at all.

In total we use 9 (for cases when goal is close) + 4 (for cases when goal is far) + 1 (for highlighting one class) = 14 colors what gives 75 pts.

Getting it down to 12 colors is quite a challenge as well. Main idea used to that is that there exist 2 classes so that they have no goals on them and I highlight both of them with one color and gain 2 colors that way (since there are 7 instead of 9 colors needed for the case when goal is close). One issue is that telling which cell belongs to which equivalence class based on highlighted classes is harder since we have two highlighted cells in our proximity, but it can be uniquely determined as 3 is odd (details left to the reader).

→ Reply

Benq

4 years ago, # ^ |

(details left to the reader)

Mind elaborating?

→ Reply

4 years ago, # ^ |

Let's say that we have two of these classes and call them $$$A$$$ and $$$B$$$. If we are allowed to use one more color then we can color $$$A$$$ with 12 and $$$B$$$ with 13 and we can always get our relative position to 12 which we used to determine where is information for $$$i$$$-th goal. What if we color $$$B$$$ with 12 as well? One may think we don't know anymore, but that's not true. For exactly one of these classes it is true that second one is the first one translated by one of vectors from the set $$${(0, 1), (1, -1), (1, 0), (1, 1)}$$$, so we can actually tell them apart and save one color. In a visual way, no matter what two classes you choose they will form a set of touching pairs and these pairs will not touch between each other and you can fix one element in each pair for each of 4 shapes these pairs may form.

→ Reply

Benq

4 years ago, # ^ |

What exactly do you do with the remaining $$$11$$$ colors?

→ Reply

4 years ago, # ^ |

+10

Well, it's basically written in my comment from yesterday, but I will try to explain it more clearly maybe.

I distinguish 9 classes and take two of them which don't have any goals on them. I call them A and B. Alice colors them with 12. Whenever Bruno sees 9 cells, he always sees exactly 2 occurences of 12 and he is able to tell which one Alice called A and which one B (using the method from previous comment). Alice and Bruno agreed on some way of telling which classes will keep information about which party (relative to A). E.g. if you take a square that has cell of A in its top-left corner then you can list cells of that square in lexicographic order and assume that i-th cell that is not from A and B (there are 7 of them) keeps info about $$$i$$$-th goal. So Bruno is able to tell which out of $$$9$$$ cells he looks at keeps info about $$$i$$$-th goal. There are 9 cells around this cell (some of them not seen by Bruno at the moment), but 2 of them are from A and B, so there are only 7 close cells that hypothetically can have $$$i$$$-th party. I use 7 colors for cases when that $$$i$$$-th goal is close to that cell to denote which out of these is the one with party and 4 to denote direction Bruno should go at if it is further away (note that these directions should be valid no matter where Bruno stands cause there are 9 possibilities for that, but since goal is far away it can be satisfied)

Here are my codes: https://ideone.com/GzvnZS (Anna.cpp) and https://ideone.com/sJkSF0 (Bruno.cpp), but I wouldn't look at them unless you are desperate :P

→ Reply

Benq

4 years ago, # ^ |

Makes sense. So the 85-pt solution below could also be adjusted to do 13 using only 8 of the 9 cells and 12 using all of them.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+64

85 points

→ Reply

4 years ago, # ^ |

+15

I definitely agree that bodyguard/worst_reporter/food_court/road_construction were all pretty standard/well-known DS/implementation problems, but that didn't seem like too much (especially for a team selection contest; testing implementation/fundamentals is probably the best way to pick a team).

The other problems were pretty interesting to me. Fever had some really nice observations (afterwards it was kind of like bodyguard, but it was a good implementation challenge), meetings was short and sweet, and events had some interesting ideas. I'm a little surprised you didn't mind escape_route actually, I thought it was a little boring and the time limit was ridiculously tight.

→ Reply

4 years ago, # ^ |

I did not mind escape_route cause I didn't take serious attempt at Day2. Unfortunately I had only around 2.5 hours for it and road_construction took me basically all of it just to get 32 points. Escape route looked rather implementation heavy as well, but I didn't give it enough thought to be confident about my opinion about that problem.

→ Reply

4 years ago, # ^ |

How would you solve escape route?

→ Reply

4 years ago, # ^ |

+15

If I didn't state it clearly — I did not spent on this problem longer than a minute, I have no idea :P

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+38

I definitely enjoyed foodcourt / fever / escape_route / meetings2. Fever was implementation oriented, but I don’t mind. And foodcourt is really simple: it’s not that all probs are impl heavy because they have segment trees inside :)

On the other hand, event2 was boring because it was a reiteration of APIO2009B.

→ Reply

Alx

4 years ago, # |

+29

Could someone who got AC on the Worst Reporter share their solution?

→ Reply

4 years ago, # ^ |

+31

Let us solve version with tree. Medusas are just annoyance.

This is basically LIS, but on trees. From each subtree you want to have a representation of full information "what is the lowest cost so that guy with the lowest rating in this subtree had rating >=x?". You can think of this as a staircase-type function with argument x. Of course you can do coordinate compression, so there are only $$$O(n)$$$ valid values of $$$x$$$, not $$$10^9$$$. However if you look more closely, result can only change for values of x that are present in this subtree, so in fact there are only $$$subtree\_size[v]$$$ valid values of $$$x$$$ in subtree of $$$v$$$. After you choose your favourite way to represent this knowledge you can apply "smaller to larger" method in order to handle merging subtrees.

I chose some messy way, but apparently the cleaner way do represent this function is to keep a map telling us by how much our function changes in each point. Adding two such staircase function is then very easy cause you just add point-wise two maps. You need to also support adding new vertex, but that can be done. Since maps result in additional log factor, whole solution works in $$$O(n \log^2 n)$$$ time.

→ Reply

Amtek

4 years ago, # ^ |

← Rev. 2 →

Is it possible to solve this problem in $$$O(n \log n)$$$ time? I spent the whole contest optimizing $$$O(n \log^2 n)$$$ and couldn't get rid of TLE on one case ;-;

→ Reply

4 years ago, # ^ |

← Rev. 2 →

+28

You can merge two BBSTs of sizes $$$m \le n$$$ in $$$O(m \log(n/m))$$$ using treaps or splay trees. This sums up to $$$O(n \log n)$$$ time to merge $$$n$$$ elements instead of $$$O(n \log^2 n)$$$ time. I don't know of a more elementary way though.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I think you can replace BBSTs with segment trees.

There was a CF article about mergeable segment tree. It was by some Chinese, but I can't find it now. It was very simple to implement, just the analysis required some potentials.

→ Reply

PurpleCrayon

4 years ago, # ^ |

Blog by TLE, I think this is the one you were talking about.

→ Reply

4 years ago, # ^ |

Yeah, I was talking about this. Thanks.

→ Reply

https://paste.ubuntu.com/p/zqSXYR7XRc/

4 years ago, # ^ |

← Rev. 2 →

+15

There is another solution using HLD and set ,which is much easier to implement.

Consider the tree case:

You can build a tree where a[i] is the father of i.Let dp[i] means now consider the subtree of i and i is selected to be unchanged , what is the max sum of c[i] of unchanged people in the subtree of i.

dp[i] = $$$c[i]+\max {\sum_{u\in S} dp_{u}}$$$,where no two element in S is ancient and son.And $$$\forall h[u] \geq h[i],(u\in S)$$$

Analysis the process ,you can implement is easily:

Add the node to the tree in the decreasing order of h[i] .
If you add i-th node this turn ,you start from i and hold a val=c[i] and go to the root.
There may be some tags in some nodes, if you meet a tag in the j-th node:

tag[j]>=val, then tag[j]=tag[j]-val,and val become zero.
else , then tag[j] become zero ,and val=val-tag[j]

If you jump out of the root , the current answer:$$$ans=ans+val$$$,and tag[i]become c[i].

After you add all nodes ,the final answer $$$=\sum c[i]-ans$$$

A short solution which gives 79 pts:

For dag,you can change it to tree!

In a scc you can link them from small to big.

The 100pts solution: https://paste.ubuntu.com/p/hGxpz8Z9dT/

Time complexity ：O(n log n)

→ Reply

4 years ago, # ^ |

Your code clearly looks $$$O(n \log^2 n)$$$. You do std::set operation for each heavy chain in path...

Though, I think top trees can optimize this to $$$O(n \log n)$$$.

→ Reply

4 years ago, # ^ |

+10

When visiting a element in a set you either delete it or end the process,so it is O(nlogn)

→ Reply

4 years ago, # ^ |

-10

Oh, I see.

→ Reply

Alx

4 years ago, # ^ |

How would you combine two staircase function maps? Would it simply just be adding the contents of one map to the same indexes in the other?

→ Reply

4 years ago, # ^ |

If you store the deltas, it's just adding the contents.

→ Reply

Alx

4 years ago, # ^ |

I see, thanks for the clarification and thanks Swistakk for the solution

→ Reply

4 years ago, # ^ |

← Rev. 2 →

You basically execute the binsearch LIS algorithm on tree, but do extra three things:

Value have weight W: Just consider them as a W-time duplicate, and think that you are dealing with unweighted version where you have W vertices in path. Then if you compress the same value in RLE-like way, it works the same, just do some amortization.
Have more than one childs: Merge the sorted map small to large.
Cycles: The value should be same all throughout the cycle. You can try all candidates.

→ Reply

https://codeforces.me/blog/entry/88748?#comment-774036

4 years ago, # ^ |

→ Reply

realcomplex

4 years ago, # ^ |

After making the functional graph and dealing with the cycle at the end, you can just do dp on each tree similarly to CEOI 2019 Tree.

→ Reply

4 years ago, # |

← Rev. 2 →

+30

Problem Statements for all 4 days

→ Reply

4 years ago, # |

← Rev. 2 →

+29

Thanks for the contests! There was a lot of data structure implementation, but that is just what I like 8)

My favourite problem was shopping, even though I had no chance on that one :D

→ Reply

4 years ago, # |

+57

When will day4 scoreboard and the test data be released?(it currently shows only day1,2,3)

→ Reply

Luca

4 years ago, # ^ |

+44

You can at least already upsolve on the contest website if you want.

→ Reply

4 years ago, # ^ |

+18

Day 4 results are now out

→ Reply

4 years ago, # |

How would you solve escape routes and bodyguards?

→ Reply

AlexPop28

4 years ago, # ^ |

+16

I barely got 70 points in contest on escape routes with the following solution, but I hope it helps. Basically, the solution divides the queries into buckets (pairs (start_node, start_time)) such that from the moment another day starts, the paths start from the same node. To get these buckets, you run dijkstra backwards from each end of an edge, from the moment it becomes unusable. You end up having some time intervals that are equivalent for each starting node. Now, you just need to run dijkstra normally for each of these pairs (start_node, start_time) and get the answer for a query based on these. Complexity is $$$O(N \cdot M^2)$$$. I would also be interested in a solution that gets 100 points, if anyone can share it. Code

→ Reply

4 years ago, # ^ |

+45

For 100, I calculated for every pair of vertices $$$s, t$$$, and every edge $$$(s, u)$$$ incident on $$$s$$$, the minimum amount of time it takes to reach $$$t$$$ from $$$s$$$, if we start from $$$s$$$ at the last possible time we can cross edge $$$(s, u)$$$. I also added edges $$$(s, s)$$$ with last possible crossing time $$$0$$$, to calculate the minimum times to reach $$$t$$$ from $$$s$$$ if we start at the start of a day.

Then, for every vertex $$$s$$$, we handle all queries starting from that vertex. We do sweepline, from the last second of the day to the first, maintaining the minimum time it takes to reach every vertex we can reach without waiting for the next day, and adding edges as we become able to cross them.

Whenever an edge becomes crossable, we update minimum times to reach every vertex by the time it takes to reach the vertex through the edge.

Whenever the time decreases past a query, answer the query. Either travel directly to the target within the same day you started, or loop over which vertex you wait for the next day on.

This has complexity $$$\mathcal{O}(n^2 m \log n + n Q)$$$. The $$$\log n$$$ comes from using Djikstra in the first phase.