We hope you liked the problems! Before we go ahead with the editorial, let us make some general comments about this round.

Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems.

There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I has already appeared in a contest (most likely also in Polish contest, if you know it please tell us in the comments). See also this comment.

**Pre-contest predictions**

Let us now make some predictions (you, future reader, can check whether we were right or wrong). We promise not to change these predictions after the beginning of the contest.

- After 20 minutes someone has solved 4 problems.
- After 40 minutes someone has solved 6 problems.
- After 70 minutes someone has solved 7 problems.
- After 100 minutes someone has solved 8 problems.
- At least one contestant solves all the problems.
- There is a big difference in number of solves between F and G (let's say a factor 3).
- The best Italian contestant solves 6 problems.
- There are $$$\ge 10\,000$$$ solves for problem A.

The contest is now finished and our predictions are far from being perfect, but, for intellectual honesty, we are not changing them.

**Detailed overview on the problemset and a bit of behind-the-scenes**

In problem 1552A - Subsequence Permutation you had to sort a sequence by changing the minimum number of elements... you better not touch elements which are already in the correct position! Fun fact: this problem appears again, as an optimization step (not really required to get accepted), in problem G.

Problem 1552B - Running for Gold, about the ongoing Olympic Games, had a real-life statement and an obvious quadratic algorithm which had to be improved to get accepted. It could be solved either by an intuitive observation (only one athlete can win the gold medal!) or with a super-simple randomized approach. This problem was added (and changed) last-minute (that is, 2 days before the contest) to make the problemset more balanced. Bonus version: with the same constraints, find the number of athletes who are "likely to get a medal", i.e. who are superior to all but (at most) $$$2$$$ other athletes.

In problem 1552C - Maximize the Intersections you had to maximize the number of intersections of chords in a circle. It's natural to add the new chords so that they all intersect each other... it turns out that this is enough to solve the problem! This was a subproblem of a harder problem that we discarded because it did not fit the problemset (and it was not particularly nice).

Problem 1552D - Array Differentiation, in which you had to write an array as differences of the value of another array, was an undercover graph problem. Once the necessary and sufficient condition is identified, coding it is very easy. Until 5 days before the contest, this was problem B. Since it was too hard for a B, it was moved to D and a new problem B was added.

Problem 1552E - Colors and Intervals is a combinatorics problem that asks you to select some "almost disjoint" intervals respecting certain properties. It can be tackled by unexpected simple greedy algorithms. Some variations of this problem appeared in the past (we know of at least two similar problems), but since it is a nice problem and nobody found this version anywhere we decided to give it anyway.

At first sight, problem 1552F - Telepanting, about an ant moving and teleporting, seems to require an exponential amount of time to be solved. Once one notices that the states of the portals satisfy a rigid property, it is not hard to come up with a polynomial (actually pseudo-linear) solution. If one drops the assumption $$$y_i<x_i$$$ it becomes impossible for the authors to solve it.

Problem 1552G - A Serious Referee presents you with a daunting task: you are given a "generalized" sorting network and you must tell whether it really is a sorting network or not. Standard knowledge about sorting networks is useful but not sufficient to solve the problem.

Problem 1552H - Guess the Perimeter is a strange interactive problem in which you must guess the perimeter of a hidden rectangle. The number of available queries in astonishingly small and one has to come up with a way to find the perimeter without really identifying the rectangle. Initially cip999 had proposed it with $$$7$$$ queries, then dario2994, after failing to solve it for a couple of days, came up with the $$$4$$$ queries solution.

In problem 1552I - Organizing a Music Festival you have to count the number of permutations with certain sets of values which are contiguous. The statement is very simple but the solution is a bit of a mess to find and also to code. This is the only problem of the problemset whose implementation is involved. It entered in the problemset when we noticed that the previous problem I could be solved by a dull heuristic (which made cip999 really sad). The first version of the problem had $$$n=20$$$, it was a problem E/F and could be solved by subsets-dp, but antontrygubO_o said (and rightly so) "I am afraid this is too standard". This rejection pushed dario2994 to solve the problem in polynomial time and send it back to antontrygubO_o, who finally accepted it. The official solution can handle also $$$n=1000, \, k=1000$$$, but, since it was only a bigger pain to code, we decided to give the "small constraints" version. Sadly, it turns out that the problem was not new for some participants (but there were also some genuine solutions to the problem during the round).

**Which author did what?**

- A: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- B: Original statement and preparation by dario2994.
- C: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- D: Original statement and preparation by cip999.
- E: Original statement by cip999, current statement by dario2994. Prepared by cip999.
- F: Original statement by cip999, current statement by dario2994. Prepared by dario2994.
- G: Original statement by cip999, solution by dario2994. Prepared by dario2994.
- H: Original statement by cip999, solution by dario2994. Prepared by dario2994.
- I: Original statement and preparation by dario2994.

**Some thoughts from cip999**

This was the first round ever that I (co-)organized, so I'm eager to share some of my experience with the Codeforces community!

During the problemsetting phase of the preparation I've been the main proposer, basically for two reasons:

- dario2994 didn't have much time to think about problems;
- I was totally new to problemsetting and felt the need to propose every problem I came up with, no matter how horrible it was. (Regarding the second point, I believe I am going to write a separate blog post, where I will comment on the negative aspects of some of the ugliest problems I proposed, so that, hopefully, future problemsetters won't repeat my mistakes.)

As a result, most of the problems ended up being mine, at least in their original formulation (with most of their optimal solutions being dario2994's).

However, the more problems I proposed (and the more feedback I received from dario2994, who, during this stage, acted as a coordinator), the better I became at inventing problems: I began to notice when a problem was too mainstream or technical or didn't require any interesting insight; I gradually developed an eye for statements that seemed nice and "natural"; I aimed at the right amount of beauty and originality. I still got rejections, but fewer of them. In the end, I feel that I am now a way better problemsetter than I was in the beginning, and I have to thank dario2994 for that!

The problem preparation phase was another thing entirely. Previously, I had prepared a reasonable amount of problems for the Italian Olympiad in Informatics and the Italian training camps, but in a Codeforces round (and, to a greater extent, in a Global Round) everything must be thought of with the utmost care: there is no room for major mistakes.

- Statements must be
**clear**. As I'm writing this, dario2994 is telling me that the statement of problem A has to be clarified (and it's less than 24 hours before the contest!). - The generation of tests is by far the most critical part. If you want to avoid heuristics to pass systems tests (or, maybe worse, pass pretests and get FST), tests must be
**strong**. - In order to test the generator, it is essential to write a lot of heuristic/suboptimal/slow solutions and make sure they fail on a reasonable amount of tests.
- On the other hand, writing the validator and (when needed) the checker is way easier and almost relaxing.

Two problems were discarded after or during their preparation because we found unbeatable heuristics: one was the former problem C, the other was former problem I. Both problems were proposed by me, so I was a bit disappointed when that happened (especially for problem I, which neither dario2994 nor antontrygubO_o could solve). However, we were lucky to find those heuristics and save us from unwanted AC on wrong solutions. Hopefully we have caught them all!

I had a whole lot of fun organizing Global Round 15, and I discovered that I like inventing problems more than solving problems invented by others! For this reason, I think that, sooner or later, I will try to organize another round here on Codeforces (provided that I find the time to do so).

## Hints and solutions

**A**

**Hint 1.**

For sure, one must permute the $$$k$$$ characters by sorting them alphabetically.

**Hint 2.**

If a character is not among the $$$k$$$ shuffled characters, then it must be already in the correct position.

**Hint 3.**

If a character is not in the correct position, then it must belong to the $$$k$$$ shuffled characters.

**Solution**

**Implementation**

**B**

**Hints for Solution 1**

**Hint 1.**

The "superiority" relationship induces a complete directed graph with $$$n$$$ vertices and $$$\binom{n}{2}$$$ edges.

**Hint 2.**

There can be at most one athlete who is superior to everyone else.

**Hint 3.**

Morally, the problem is equivalent to finding the maximum of an array (performing not too many comparisons).

**Hints for Solution 2**

**Hint 1.**

Try to optimize the obvious quadratic solution.

**Hint 2.**

Maybe put in some randomization?

**Solution**

**Implementation of Solution 1**

**Implementation of Solution 2**

**C**

**Hint 1.**

If two chords do not intersect, "swapping them" so that they intersect strictly increases the number of intersections.

**Hint 2.**

If we repeat the above-described strategy, we will end up with a configuration where all added chords intersect.

**Hint 3.**

There is only one configuration so that all added chords intersect.

**Solution**

**Implementation**

**D**

**Hint 1.**

Consider the graph induced by the edges $$$(j, \, k)$$$ so that $$$a_i = b_j - b_k$$$.

**Hint 2.**

Such graph contains $$$n$$$ vertices and $$$n$$$ edges, so it has a cycle.

**Hint 3.**

The sum, with the right signs, of the $$$a_i$$$ over the vertices of a cycle is $$$0$$$.

**Hint 4.**

The above condition is necessary and sufficient.

**Solution**

**Implementation**

**E**

**Hints for Solution 1**

**Hint 1.**

It is always convenient to choose $$$a_i, \, b_i$$$ so that the color $$$i$$$ does not appear in $$$a_i + 1, \, a_i + 2, \, \dots, \, b_i - 1$$$. So, for each color there are $$$k - 1$$$ "candidate intervals".

**Hint 2.**

$$$(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$$$.

**Hint 3.**

Choose the intervals in chunks of $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$. The intervals in the first chunk should be strictly to the left of the intervals in the second chunk, which should be strictly to the left of the intervals of the third chunk, and so on.

**Hint 4.**

For the $$$t$$$-th chunk, only consider (among the remaining colors) the candidate intervals whose left endpoint is the $$$t$$$-th occurrence of its color.

**Hints for Solution 2**

**Hint 1.**

Try to come up with a greedy algorithm.

**Hint 2.**

Order the candidate intervals (defined as above) by second endpoint.

**Hint 3.**

Scan the sorted intervals and always select one if you are allowed to.

**Solution**

**Implementation of Solution 1**

**Implementation of Solution 2**

**F**

**Hint 1.**

If you are at position $$$x$$$, what can you say on the state of portals with $$$x_i < x$$$?

**Hint 2.**

All such portals must be active.

**Hint 3.**

Try to solve the problem under the assumption that initially all portals are active.

**Hint 4.**

You must compute the time necessary to go from $$$x_i$$$ to $$$x_i$$$ again assuming all portals are active.

**Solution**

**Implementation of Solution 1**

**Implementation of Solution 2**

**G**

**Hint 1.**

Testing only arrays with $$$0$$$ and $$$1$$$ is sufficient (why?).

**Hint 2.**

A *quantum array* is a $$$0$$$-$$$1$$$ array so that some entries can be both $$$0$$$ and $$$1$$$. Start with a completely undetermined quantum array and apply the algorithm, fixing its values only when necessary.

**Hint 3.**

How many quantum arrays will this algorithm have to deal with?

**Solution**

**Implementation**

**H**

**Hint 1.**

The perimeter is twice the base plus twice the height. Figure out them both!

**Hint 2.**

Ask a query with all points. The result is a simple expression in terms of base and height.

**Hint 3.**

Ask only queries of the form $$$(di, \, j): 1 \le i \le \lfloor \frac{200}{d} \rfloor, \, 1 \le j \le 200$$$. Let the result be $$$f(d)$$$.

**Hint 4.**

For which values of $$$d$$$ is $$$f(d)$$$ nicely related to $$$f(1)$$$?

**Hint 5.**

Binary search on the $$$2$$$-adic evaluation of the number of points on the base of the rectangle.

**Solution**

**Implementation**

**I**

**Hint 1.**

The valid orderings have a rigid structure.

**Hint 2.**

Let $$$S_i$$$ be the singers liked by friend $$$i$$$. Consider the graph on the friends where there is an edge between $$$i$$$ and $$$j$$$ if and only if $$$S_i \cap S_j \ne \varnothing, \, S_i, \, S_j$$$.

**Hint 3.**

Distinct connected components are independent.

**Hint 4.**

Up to obvious identifications, each connected component has exactly $$$0$$$ or $$$1$$$ or $$$2$$$ valid orderings.

**Solution**

**Implementation**

If you find any typo, feel free to tell us with a comment. Moreover, if you want to share your opinion on the problemset, we are eager to read it.