×

MOSCOW JUNIOR WORKSHOPS For ICPC - Solution Outlines

Hello,

While we are in talks with the organizers over detailed editorials for the round, I'd like to share the brief setter's notes we received from them, so that you guys can start upsolving and practicing them :). I tried my best to make the notes reader-friendly as well, and added a couple of alternate explanations/hints etc. Let me know if they can be improved, and dont forget to share your approaches for discussion!!

1. Pizza Cutting

Ans- The answer is easy to guess if you think in terms of $GCD(a2 - a1,a3-a2, ..., an - a1)$. Alternatively, you can try all angles and rotations and brute force.

Reference Solution : Here

Hint- Binary Search

Ans-Binary search on answer. Notice that you can entirely skip groups (of numbers) with the same leading digit and length.

Some more Explanation-

View Content

3 Antimatching

Hint: 1 Corner case + Trivial observation.

Ans- The answer is either the largest degree (trivial to prove) , or $3$ if there is a triangle (corner case).

4 Inverse LIS:

Ans- Place small numbers after $i[k - 1]$ in decreasing order, then $i1, ..., i[n]$, then all other positions in decreasing order.

Corner cases- $k = 1$ and $k=2$ are special cases.

6 Grid Flippers

Ans- $O(n log n log C)$ (not intended to pass): Binary search on answer $d$. Tracks with midpoints at manhattan distance at most $d$ have to have the same orientation (implication of kind 1), also tracks with midpoints on the same horizontal line at distance at most $2d$ can not be both horizontal (same for vertical, implication of kind 1). The implication graph for 2SAT can be made of size $O(n log n)$ with persistent treap.

$O(n log n)$ with small constant: note that only edges of manhattan MST can be left for implications of kind 1, one can find them in $O(n log n)$ with sorting in four diagonal directions. There are now $O(n)$ edges for 2SAT in total, hence $O(n log C)$ in total.

This question is marked "community wiki".

15.4k12066
accept rate: 18%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×368
×11

question asked: 20 Nov '18, 15:44

question was seen: 279 times

last updated: 22 Nov '18, 22:13