Блог пользователя peltorator

Автор peltorator, история, 4 года назад, По-русски

I've never been good at solving problems about permutations. I find it really hard to illustrate and solve in mind (or on paper) even small examples. Of course, I know that it's a good idea to split a permutation into a set of cycles, but it doesn't really help! I think you understand what I'm talking about. You have these elements that are not in their original positions and you want them to be in the right places. But when you start to make swaps, you should always draw a new picture for every swap to track what's going on.

Yesterday's global round featured this problem about permutations. And it wasn't that hard, but I spent a lot of time trying to figure out what's going on. And this case is even harder because you don't only have a permutation, but also its elements are being flipped every time.

So I'd like to ask you how do you represent permutations and work with them while solving problems?

I personally found out a pretty nice way to do it yesterday. I cut cards out of paper and swapped them with my hands.

You can see that there are two cycles: 123 and 4567. And I could manually swap them and flip while swapping.

It really helped me, but it was still kinda confusing. I needed to perform the same operations several times to figure out what's going on.

I'll be glad if you share your own methods!

  • Проголосовать: нравится
  • +162
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

1) as points(x = i, y = p[i])

2) as (i, mask) — mask of i-th prefix

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I didn't really get the second one. What do you mean by mask in this case?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Mistake, its must be (i, mask, last) — mask of i-th prefix with last in end

      Sometimes we want to bruteforce all permutations

      We can hold prefix and push/pop elements in recursion

      In cases where only matters neighboring of items, most popular — hamilton way search, we can interpretate this prefix as mask of used, and store last

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Ok, I got it. Yeah, it's a different way to think about permutations, but it's more about implementing dp tasks and not thinking about permutations themselves, I suppose.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

I usually just draw cycles on paper and draw across new arrows, when elements are swapped.

So the elements themselves aren't being swapped at all.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Oh, yeah, makes sense! It's definitely better than crossing elements out and drawing them in their new locations. But still, if you draw a lot of lines, it's gonna be messy.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -68 Проголосовать: не нравится

No idea :(

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

After a long time, a post with no negative downvotes in the comments:)