algorithms

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

problem.txt (2837B)


      1 B. Trouble Sort
      2 time limit per test1 second
      3 memory limit per test256 megabytes
      4 Ashish has n
      5  elements arranged in a line.
      6 
      7 These elements are represented by two integers ai
      8  — the value of the element and bi
      9  — the type of the element (there are only two possible types: 0
     10  and 1
     11 ). He wants to sort the elements in non-decreasing values of ai
     12 .
     13 
     14 He can perform the following operation any number of times:
     15 
     16 Select any two elements i
     17  and j
     18  such that bi≠bj
     19  and swap them. That is, he can only swap two elements of different types in one move.
     20 Tell him if he can sort the elements in non-decreasing values of ai
     21  after performing any number of operations.
     22 
     23 Input
     24 The first line contains one integer t
     25  (1≤t≤100)
     26  — the number of test cases. The description of the test cases follows.
     27 
     28 The first line of each test case contains one integer n
     29  (1≤n≤500)
     30  — the size of the arrays.
     31 
     32 The second line contains n
     33  integers ai
     34  (1≤ai≤105)
     35   — the value of the i
     36 -th element.
     37 
     38 The third line containts n
     39  integers bi
     40  (bi∈{0,1})
     41   — the type of the i
     42 -th element.
     43 
     44 Output
     45 For each test case, print "Yes" or "No" (without quotes) depending on whether it is possible to sort elements in non-decreasing order of their value.
     46 
     47 You may print each letter in any case (upper or lower).
     48 
     49 ---
     50 
     51 Thoughts:
     52 
     53 - n elements in a line
     54 - each element is [a_i,b_i] where b \in {0,1} and a_i is an int
     55 - sort ascending a_i
     56 - can only swap elements of different kinds (b_i != b_j) at each step
     57 - return yes / no if he can/can't sort
     58 
     59 ---
     60 
     61 approach:
     62 - sort a, see if a can be arranged like that with swaps
     63     - min swap problem basically
     64     - elements of same value exist though
     65 - what are impossible cases
     66     - since we can do 0->1->0 are there any?
     67 - are we doing exhaustive search?
     68     - seems unlikely even though only 500 elements at most
     69 - could we do something like bubble sort?
     70     - at each step we swap the current with a smaller if possible
     71         - stop once can't do this anymore
     72         - doesn't work for
     73             - 4 3 2 1
     74             - 0 0 0 1
     75     - is this just always true if > 1 of each?
     76         - 
     77 
     78 
     79 ---
     80 
     81 
     82 Examples:
     83 
     84 10 20 20 30
     85 0 1 0 1
     86 
     87 yes, already
     88 
     89 
     90 3 1 2
     91 0 1 1
     92 
     93 1 3 2
     94 1 0 1
     95 
     96 1 2 3
     97 1 1 0
     98 
     99 so in this one we just find the index that wants our position and we swap with it
    100 
    101 2 2 4 8
    102 1 1 1 1
    103 
    104 done
    105 
    106 5 15 4
    107 0 0 0
    108 
    109 done
    110 
    111 20 10 100 50
    112 1 0 0 1
    113 
    114 target: 10 20 50 100
    115 
    116 10 20 100 50
    117  0  1   0  1
    118 
    119 10 20 50 100
    120 
    121 
    122 ---
    123 
    124 so in this one we just find the index that wants our position and we swap with it
    125 
    126 this doesn't work because:
    127 
    128 10 20  40 15
    129 0   1   0  1
    130 
    131 instead we must:
    132 
    133 - iterate over all elements, ask that question again
    134 
    135 ---
    136 
    137 duh, if there are elements of diff types we can use them to proxy swapping.
    138 
    139 
    140 if count(0) >= 1 and count(1) >= 1:
    141     - yes
    142 
    143 one doesn't have any:
    144     - no swaps, is it good right now?