Задача манипулирования строками

Вам дано N строк, и одна из них недействительна. Каждая строка имеет вес, равный сумме весов ее символов. Вес символов представлен следующим образом

вес а равен 1 вес b равен 2 вес c равен 3

и так далее

Вы можете выполнить следующую операцию над строкой

  1. Выберите строку и увеличьте ее вес на 1
  2. Выберите строку и уменьшите ее вес на 1

Ваша цель — уравнять веса всех строк, кроме одной (мы называем ее недопустимой строкой), выполняя эти операции любое количество раз. Найдите неверную строку, т.е. приравняйте всю строку, кроме недопустимой строки, к некоторому весу W, такому, чтобы количество требуемых операций было минимальным.

Примечание

Строка содержит только буквы нижнего регистра Есть только одна неверная строка

Пример у нас есть 5 строк

чакшу пекка панк голем тяги

выход

пекка

Объяснение

Вес струнной чакшу равен 3 + 8 + 1 + 11 + 18 + 8 + 20 = 71. Точно так же для пекки, панка, голема и тяги это 44, 62, 52 и 62 соответственно.

Теперь считайте чакшу недопустимой строкой, операций, необходимых для выравнивания остальных, 28. если pekka недействителен, требуется 19 операций если панк недействителен, нам нужно 37 ходов, чтобы сравнять Аналогично для голема и тяги нужно 27 и 37 операций Таким образом, pekka - недопустимая строка, так как для ее удаления требуется наименьшее количество ходов.

Что я пробовал до сих пор

t = gets.to_i

hsh = {}
('a'..'z').each_with_index{|elem, index| hsh[elem] = index + 1}

while t > 0 do 
  n = gets.to_i
  result = {}
  while n > 0 do 
    str = gets.chomp
    result[str] = str.chars.map{|d| hsh[d]}.sum
    n -= 1
  end
  puts [result.min_by{|k, v| v}].first.first
  t -= 1
end

Но это решение проходит только тестовый пример. Когда я запускаю все тестовые примеры, это дает мне неправильный ответ.

Дайте определение «неправильно» в конкретных технических терминах, чтобы мы знали, где помочь.

tadman 19.12.2020 17:45

Я полагаю, вы имеете в виду: «Теперь считайте чакшу недопустимой строкой, операции, необходимые для выравнивания остальных, равны 28. Если pekka недействительна ...», а не «... 28, если pekka недействительна ....».

Cary Swoveland 19.12.2020 20:47
Пошаговое руководство по созданию собственного Slackbot: От установки до развертывания
Пошаговое руководство по созданию собственного Slackbot: От установки до развертывания
Шаг 1: Создание приложения Slack Чтобы создать Slackbot, вам необходимо создать приложение Slack. Войдите в свою учетную запись Slack и перейдите на...
0
2
671
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Минимальные шаги, чтобы сделать вес всех строк равным, будут состоять в том, чтобы сделать строки равными медиане строк. Недопустимой строкой будет строка, которая уменьшает общее количество шагов на максимальную величину.

Итак, для вычисления медианы мы вычисляем веса каждой строки и сортируем их, чтобы найти медиану. Затем мы вычисляем индекс строки, которая принимает максимальное число. шаги, чтобы добраться от медианы и вернуть его в качестве ответа.

Проблема в приведенном выше алгоритме возникает, когда длина списка строк четная. Поэтому нам также необходимо рассчитать общее число. предпринятых шагов (исключая шаги, предпринятые недопустимой строкой) для достижения медианы. Таким образом, ответ из двух строк соответствует минимальному нету. Всего шагов.

Это код Python для вышеуказанного алгоритма. Я сильно прокомментировал, если вы ничего не понимаете, просто спросите в разделе комментариев.

def get_weight(char):                     ### gets ascii value of character then 
  return ord(char)-ord('a')+1             ### subtract ascii of 'a' to get weight

def get_max_steps(weights,length,median):
  max_steps=-1                     
  max_indx=-1
  total_steps=0
  for indx in range(length):              ###  for each word
    tmp_steps=abs(weights[indx]-median)   ### calculate steps req to reach  
    total_steps+=tmp_steps                ### median weight
    if max_steps<tmp_steps:               
      max_steps=tmp_steps                 ### store the max steps required in max_steps
      max_indx=indx                       ### and index for which its required in max_indx
  return total_steps-max_steps,max_indx   ### exclude the max_steps from total steps for the invalid string

def function(words,length):
  weights=[0 for i in range(length)]      ### array to store weights of each word
  for indx in range(length):              ### for each word
    weight=0                              ### 
    for char in words[indx]:              ### calculate weight of each word 
      weight+=get_weight(char)            ### 
    weights[indx]=weight                  ### store it in the array
  sorted_weights=sorted(weights)          ### sort the array
  median=sorted_weights[length/2]         ### get median do Integer divison
  total_steps,max_indx=get_max_steps(weights,length,median)  ### calculate the total steps required to 
                                          ### reach median of weight excluding the steps for invalid string at max_ind  
  if length%2==0:                         ### if array's length is even 
    median=sorted_weights[length/2 -1]    ### get second median and do similar step as above and do Integer division here
    ntotal_steps,nmax_indx=get_max_steps(weights,length,median)  
    if ntotal_steps<total_steps:          ### if the total steps using second median is less  
      max_indx=nmax_indx                  ### then the string by this median is appropriate choice for invalid string

  return words[max_indx]                  ### return invalid string
  
tests=int(input())                        ### taking no. of test cases as input
for i in range(tests):                    ### run for-loop for tests no. of times
  length=int(input())                     ### taking array's length and array of strings 
  words=input().split()                   ### as input
  print(function(words,length))           ### printing the functions result

Какова будет временная и пространственная сложность?

Aniket Tiwari 25.12.2020 10:27

это будет зависеть от суммы длин слов в массиве слов. Пусть эта сумма будет m. И длина массива слов будет n. Тогда временная сложность равна O(m+ nlogn).

devShaurya 26.12.2020 06:28

Начнем с создания метода, вычисляющего вес каждой строки.

def weight(s)
  base = 'a'.ord - 1
  s.each_char.sum { |c| c.ord - base }
end

или

def weight(s)
  s.each_char.sum(&:ord) - s.size * ('a'.ord - 1)
end

Например,

arr = ["chakshu", "pekka", "punk", "golem", "tyagi"]
weights = arr.map { |s| weight(s) }
  #=> [71, 44, 62, 52, 62]

Затем создайте метод, определяющий минимальное количество итераций, необходимых для выравнивания весов всех строк, кроме одной. Предположим, уравненный вес равен x. Легко показать, что значение x, минимизирующее сумму абсолютных отклонений от x, равно медиане весов.

def steps_required(wts)
  median = wts.sort[(wts.size+1)/2]
  wts.sum { |w| (w - median).abs }
end

Например,

steps_required(weights.values_at(1,2,3,4)) #=> 28
steps_required(weights.values_at(0,2,3,4)) #=> 19
steps_required(weights.values_at(0,1,3,4)) #=> 37
steps_required(weights.values_at(0,1,2,3)) #=> 37

Теперь нам нужно только объединить все это в метод, который вызывает методы weight и steps_required, которые я создал выше.

def find_invalid_str(arr)
  weights = arr.map { |s| weight(s) }
  all_indices = (0..arr.size-1).to_a
  i = arr.each_index.min_by do |i|
    steps_required(weights.values_at(*(all_indices-[i])))
  end
  arr[i]
end
find_invalid_str(arr)
  #=> "pekka"

Какова будет временная сложность этого?

Aniket Tiwari 25.12.2020 10:26

@AniketTiwari, сейчас речь идет о O ((n ^ 2) log (n)), где n = arr.size, но завтра я сделаю редактирование, которое сделает O (n log (n)). Спасибо за вопрос.

Cary Swoveland 26.12.2020 09:25

Я буду ждать решения n(log(n))

Aniket Tiwari 26.12.2020 15:35

Другие вопросы по теме