MattTheNub's blog

By MattTheNub, history, 4 weeks ago, In English

Thank you to everyone who participated in the onsite and the open mirror! Congratulations to ikaurov, serichaoo, and Ryazimn for winning the onsite!

There is now a gym for upsolving: https://codeforces.me/gym/106785. Here are the solutions:

106785A - Balanced Tripartition

Solution

106785B - Rutgers Bus Budgeting

Solution

106785C - Lucyyx Never Clear

Solution

106785D - Generatable Sequences

Solution

106785E - Non-Similar Paths

Solution

106785F - Permutation Edit Distance

Solution

106785G - Illuminating Lights

Solution

106785H - Stringmaster

Solution

106785I - Increasing Tree Jumps

Solution

106785J - John Buck Legends

Solution

106785K - 3D Turf War

Solution

106785L - Skyline

Solution

106785M - Balancing Thomas

Solution

106785N - MEX of XOR

Solution

106785O - Squaremas

Solution
Headlands Logo
HRT Logo RUCS Logo Wegmans Logo
  • Vote: I like it
  • +35
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

One detail in F that's easy to miss is that this isn't quite the usual edit distance or even a standard LCS problem.

Since you can only delete the current maximum or insert a new maximum, the elements you keep have to be exactly 1 through k, in the same relative order in both permutations.

So if k is the largest value for which those restricted sequences match, the answer is n + m — 2k. You can delete everything larger than k and then rebuild the target permutation.

That also makes the second sample easier to understand. Only [1] can be preserved, which is why it takes 4 operations rather than 2.

Might be worth emphasizing this restriction, since the problem title naturally makes people think of the standard Levenshtein DP.