errorgorn's blog

By errorgorn, 2 years ago, In English

Disclaimer: This blog is entirely my own opinion, please do not get mad at the authors from round 779. If you did not enjoy that round, please do not blame the authors. Personally, I felt that the authors overall did a wonderful job (SPyofgame's div 2F was honestly one of my favourite problems in 2022 so far).

Last week round 779 was held, a common feedback that people seemed to be quite vocal about was that the round was "PermutationForces".

If we look at the actual contest, we do see that problems B, C, D, E all contain the word permutation inside, so it is natural to think that problems are all repetitive. But saying a round is "PermutationForces" is like saying a round is "ArrayForces". Like arrays, permutations are very basic objects that are one of the basic building blocks of competitive programming, claiming that a round has too many problems using permutations is pretty baseless to me.

According to the definition of permutations, a permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Sometimes when encountering permutation problems, we only use the definitions of permutation at "face value".

  • 1658B - Marin and Anti-coprime Permutation — a permutation of length $$$n$$$ consists of distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order, so there are at most $$$\frac{n}{k}$$$ elements which are a multiple of $$$k$$$.
  • IZhO 2015 Day 1 A — a permutation of length $$$n$$$ consists of distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order, so a straightforward approach is just to do multiset comparison using hashing since the multiset of any permutation of length $$$n$$$ is unique.

However, in most permutation problems, we do not have to explicitly care that these values are from $$$1$$$ to $$$n$$$, if we instead say that they are $$$n$$$ distinct real numbers the problem would not change. In fact, in most problems, we do not have to do any arithmetic operations on elements on the array. For example, in the context of the problem given the permutation $$$[1,2]$$$, I can completely don't care that $$$1+1=2$$$. I only need to know that $$$1=1$$$ and $$$1<2$$$. Using this, we can replace the array with something like $$$[e,\tau]$$$ and although it is false that $$$e+e=\tau$$$ (well, unless you are an engineer), it still holds true that $$$e < \tau$$$. In fact, in many problems where we only care about the relative position of elements, there is a trick known as "discretization" where we compress an array of large values into an array only containing values in $$$[1,n]$$$. I feel that for problems that clearly only care about the relative ordering of elements, problem setters should default to using values in $$$[1,n]$$$ except for special cases.

Some examples of problems to illustrate what I am talking about:

  • 1658C - Shinju and the Lost Permutationpower is defined using the $$$max$$$ function, which only cares about the relative ordering of elements. We could possibly have used some array $$$a$$$ of length $$$n$$$ where all elements are in $$$[1,10^9]$$$ instead of a permutation here to prevent the corner case of having only a single $$$1$$$ in the array $$$c$$$ from happening. If you think about this problem more, it is actually about min stacks (wow! data structure in div 2 C? real?)
  • 1658E - Gojou and Matrix Game — not so obvious example that we only care about the relative orderings of the elements here. I suggested that we change the problem to $$$1 \leq V_{i,j} \leq 10^9$$$ but I think it suggested it too late and so we left $$$V$$$ as a permutation in the end. I suggested that we make it in the range $$$[1,n^2]$$$ because of my philosophy regarding not requiring people to discretize and also allowing for $$$O(n^2)$$$ solutions, but I think setting larger limits would have been better here because the fact that we only care about relative orderings is completely non-trivial. Again, permutations play a very small role here and should be treated as "an array with distinct elements".
  • 1641D - Two Arrays — notice that the condition for a good pair $$$(i,j)$$$ is that $$$a_{i,1},a_{i,2},\ldots,a_{i,m},a_{j,1},a_{j,2},\ldots,a_{j,m}$$$ is distinct. That is, we only need the inequality operator — we can discretize without caring about the relative orders of elements as long as our discretization function is a bijection. If you looked at the solution of anyone with $$$O(\frac{n^2\cdot m}{w})$$$ complexity, most likely they would have discretized all values in $$$a$$$.

Another aspect of permutation is studying cycles. Since the permutation is some arbitrary arrangement of integers from $$$1$$$ to $$$n$$$, a common way to view that is to think about the graph where the edges are of the form $$$(i,p_i)$$$. This graph very nicely has the properties of each edge having in-degree and out-degree of $$$1$$$. Also, this gives us a very intuitive sense of what the inverse permutation is — we just flip the edges of the graph we are looking at. It is very common to think about such permutation when the problem asks for something like "sort this sequence and your operation is swapping $$$2$$$ elements". The general approach for such problems is that you draw the graph of the permutation and completely forget that the permutation ever existed then proceed to solve the problem on the graph--- the permutation is just a compact way to represent our graph.

  • 1491G - Switch and Flip, ARC124D- blatant applications of using graph representation of permutation.
  • 1656G - Cycle Palindrome — According to the statement: We say that a permutation $$$\sigma$$$ is a cycle permutation if $$$1,\sigma(1),\sigma^2(1),\ldots,\sigma^{n-1}(1)$$$ are pairwise different numbers. Here $$$\sigma^{m}(1)$$$ denotes $$$\underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(1)\ldots))$$$. This definition is not very nice to work with, instead using the graph representation of the permutation and a-ha, we simply require that the graph is a single connected component, furthermore we can analyze how to "connect" cycles into a bigger connected component without ever thinking about the permutation as a list of numbers.
  • 1647E - Madoka and the Sixth-graders — not a permutation, but the problem statement very nicely shows you what the graphical representation of an array looks like nice.
  • 2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1 Gadamant tells me this is magically related to the graphical representation of permutations.

Finally, permutations may be used when we need to define how to "shuffle" a sequence. These problems usually have nothing related to permutations other than the fact that it is a useful way to define "shuffling" (see 1658D2 - 388535 (Hard Version) and 1526D - Kill Anton).

I hope this blog can convince people that just because many problems in a contest references the notion of permutations, that does not mean that the round is all about a single concept. Although it is valid criticism to say a round has too much of some idea, it simply does not work when you only say "permutation". Just take a look at how many different ways we can view permutations under!

Random Sidetrack

Many times in problems, we have to use a well-known object like a permutation, bitwise operator or a subsequence, we have to paste some definition into the statement. Of course, I feel it is kinda funny that the definition of a permutation has to appear in statements $$$3$$$ times in round 779. Furthermore, it is kind of weird to put the definition of a permutation on something like a div 1C. Do you really think the people who are attempting a div 1C really need to know what a permutation is?

I suggest that we instead have a glossary on CodeForces that defines all common terms that are needed in CodeForces, then like the guide to interactive problems, we can just paste that glossary page link into all announcement blogs so beginners can read up on those page for those "technical terms" that frequently appear. We don't need to paste lengthy definitions in statements, less work for everyone!

  • Vote: I like it
  • +197
  • Vote: I do not like it

2 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Furthermore, it is kind of weird to put the definition of a permutation on something like a div 1C.

Discussion about 1654H - Three Minimums:

  • »
    2 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    What if definitions of standard things were in something like a spoiler?

2 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I agree. Regarding your "random sidetrack", I think div.2D/1B is the highest difficulty for which technical difficulties should be explained in problem statements, as this is probably the highest difficulty for which less experienced CPers would attempt. Defining what a permutation is, after all, does more good than harm for a div2A, and some might complain against having to navigate through blogs to find the definition they need when the setter could just put it in the statement.

edit: this is exactly the point of the comment above XD

  • »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Implementing the possibility of putting the definitions in the statement under spoiler, like on AtCoder, may also improve the statements. Example: arc135_a.

2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Finding unique ideas and scenarios is a pretty slow creative process, and it makes for a pretty inconsistent problemsetting career. On the other hand, picking a random topic like permutations and asking: ‘what else can I ask on this topic’ is a much more consistent way of building a portfolio of 100s of original rehashes with all sorts of unique flavors.

  • »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Not only that. Sometimes you may happen to think of a very unique idea or scenario which might be difficult to explain. And in the end to formally describe the process you have imagined, you have to use permutations.

    Maybe I didn't articulate this well enough in my post but I believe that for most permutation problems, the author did not explictly think of a permutation at all when creating said problem, the permutation was added when thinking about how to phrase the problem into a way that is easy for contestants to understand (or because they could not solve it when the array has 2 values that are the same).

    In my view, the input format of a CP problem should be as "harmless" as possible, and the problem should be nerfed to its simplest form that does not spoil the main ideas of the problems. I think under this mindset, it really is very natural for permutations to appear. Although perhaps round 779 was a big outlier.

2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Wait people said "permutationforces" as a negative? I always thought that "mathforces", "permutationforces", etc. was just a type of joke people said when a certain thing is used a lot in a round and not as a statement against the round. Is it not?