algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (4516B)


      1 D. Portal
      2 Finished
      3 Practice
      4 time limit per test: 2 seconds
      5 memory limit per test: 256 megabytes
      6 You are given a permutation∗ p of length n . There are also two portals located at positions x
      7 and y (x < y).
      8 A portal at position i is initially located between the i -th and (i + 1) -th elements of the array.
      9 Specifically, if i = 0, then the portal is located before the first element of the array, and if
     10 i = n , then the portal is located after the last element.
     11 You may perform either of the following two operations as many times as you like:
     12 1. Remove the element to the immediate left of one portal and insert it to the immediate right
     13 of the other portal.
     14 2. Remove the element to the immediate right of one portal and insert it to the immediate left
     15 of the other portal.
     16 Let O denote a portal. For example, if p is [3, O, 2, 4, O, 1]:
     17 → Virtual participation
     18     19 Virtual contest is a way to take part in past contest,
     20 as close as possible to participation on time. It is
     21 supported only ICPC mode for virtual contests. If
     22 you've seen these problems, a virtual contest is not
     23 for you - solve these problems in the archive. If you
     24 just want to solve some problem from a contest, a
     25 virtual contest is not for you - solve this problem in
     26 the archive. Never use someone else's code, read
     27 the tutorials or communicate with other person
     28 during a virtual contest.
     29 Start virtual contest
     30 → Clone Contest to Mashup
     31 • Using operation 1 on the left and right portals respectively results in the arrays
     32 [O, 2, 4, O, 3, 1] and [3, O, 4, 2, O, 1].
     33     34 You can clone this contest to a mashup.
     35 Clone Contest
     36 • Using operation 2 on the left and right portals respectively results in the arrays
     37 [3, O, 4, 2, O, 1] and [3, 1, O, 2, 4, O].
     38 Find the lexicographically† smallest permutation you can obtain using these operations. Note
     39 that portals do not affect the lexicographical comparison of permutations.
     40 ∗A permutation of length n is an array of length n containing each integer from 1 to n exactly once.
     41 †A permutation a is lexicographically smaller than permutation b if there exists an index i such that aj = bj
     42 for all indices 1 ≤ j < i and ai < bi .
     43 → Submit?
     44 Language:GNU G++23 14.2 (64 bit, msys2)
     45 Choose
     46 file:Browse… No file selected.
     47 Input
     48 The first line contains an integer t (1 ≤ t ≤ 2 ⋅ 104 ) — the number of test cases.
     49 For each test case, the first line contains three integers n , x , and y (1 ≤ n ≤ 2 ⋅ 105 ,
     50 0 ≤ x < y ≤ n).
     51 The second line of each test case contains n integers p1 , p2 , … , pn — a permutation of
     52 length n .
     53 The sum of n over all test cases does not exceed 2 ⋅ 105 .
     54 Submit
     55 Output
     56 For each test case, output a line with n integers — the lexicographically smallest permutation
     57 you can obtain.
     58 
     59 ---
     60 
     61 thoughts:
     62 
     63 - given a permutation p of length n
     64 - there are two portals at positions x and y s.t. x < y
     65 - a portal i is between the ith and ith + 1 elements
     66     - at end, append
     67 - do the either of the following as many times as you'd like (I think we can jump between them over time)
     68     - remove element to the left of a portal and put it to the right of the other portal
     69     - remove the element to the right of a portal and put it to the left of the other portal
     70 - find the smallest lexicographically permutation using only these ops
     71 
     72 ---
     73 
     74 example:
     75 
     76 4 0 4
     77 3 1 4 2
     78 
     79 n = 4
     80 x = 0
     81 y = 4
     82 
     83 p 3 1 4 2 p
     84 
     85 what do ops do?
     86 
     87 - are there just two seperate sets that are disjoint, the sets that are on each side of a portal, can they get to the other side?
     88 
     89 1 4 2 3
     90 
     91 p 1 4 2 3 p
     92 
     93 I guess this is just one swap, moving the 3 -> p -> left of p2
     94 
     95 ---
     96 
     97 3 1 2
     98 3 2 1
     99 
    100 3 p 2 p 1
    101 
    102 3 -> p -> end - 1
    103 
    104 p 2 p 3 1
    105 
    106 okay, so is this just about sorting the two smaller groupings, it does seem that there's no group movement possible.
    107 
    108 ---
    109 idea: while swapping to the other side results in a smaller lefmost character then swap them? how?
    110 
    111 ---
    112 
    113 5 1 3
    114 1 3 5 2 4
    115 
    116 1 p 3 5 p 2 4
    117 
    118 (that's pretty bad bc that moves the rightmost to being 3)
    119 
    120 p 3 5 p 1 2 4
    121 
    122 don't do that
    123 
    124 1 p 3 5 p 2 4
    125 
    126 1 2 p 3 5 p 4
    127 
    128 1 2 3 5 4
    129 
    130 ---
    131 
    132 2 0 1
    133 1 2
    134 
    135 
    136 p 1 p 2
    137 
    138 this is good as is
    139 
    140 i guess we can do a two pointer-based comparison.
    141 
    142 like what we'd do is this:
    143 
    144 - should we move elements on the right of p2 to the left of p1?
    145     - if the current element is smaller than the element to the right of portal, yes
    146 - should we move elements on the left of p1 to the right of p2
    147     - if the element on the right of p is smaller than the element on the left then yes
    148 - do we have to consider the other cases?