• Ищем качественного (не новичок) разработчиков Xenforo для этого форума! В идеале, чтобы ты был фулл стек программистом. Если у тебя есть что показать, то свяжись с нами по контактным данным: https://t.me/DREDD

Помогите с олимпиадой

  • Автор темы Автор темы sk2wie
  • Дата начала Дата начала
Забаненный
Забаненный
Статус
Оффлайн
Регистрация
12 Май 2019
Сообщения
53
Реакции
11
Обратите внимание, пользователь заблокирован на форуме. Не рекомендуется проводить сделки.
Задача 5: Древнее имя
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

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

Входные данные
В первой строке входных данных содержится целое число N (1 ≤ N ≤ 105) — длина любимого индейского имени Кати.

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

Выходные данные
Выведите единственное целое число — коэффициент древности имени.

Посмотреть вложение 177773
на питоне
 
Последнее редактирование модератором:
Python:
Expand Collapse Copy
N = int(input())
word = input()
count = 0
for i in range(0, len(word)):
    for j in range(i, len(word)):
        if (i == j):
            continue
        if (ord(word[i]) < ord(word[j])):
            count += 1
print(count)
 
Python:
Expand Collapse Copy
def main():
    input()
    word = list(input())
    k = 0

    for index, i in enumerate(word):
        for j in word[index:]:
            if ord(i) < ord(j):
                k += 1

    print(k)


if __name__ == "__main__":
    main()
 
Python:
Expand Collapse Copy
N = int(input())
word = input()
count = 0
for i in range(0, len(word)):
    for j in range(i, len(word)):
        if (i == j):
            continue
        if (ord(word[i]) < ord(word[j])):
            count += 1
print(count)
время выполнения 1 секунда по критериям. ваша прога выполняется более 1 секунды
 
время выполнения 1 секунда по критериям. ваша прога выполняется более 1 секунды
Именно поэтому не нужно использовать Python для написания олимпиад. Сложность алгоритма - O(n^2), в худжем случае это должно занять 105^2 операций (на самом деле даже меньше, т.к. это прогрессия n * (n - 1)), что выполняется компьютером на адекватных ЯП практически моментально.
 
И тут я осознаю, что ограничение входных совсем не 105, а 10^5. Советую сразу исправлять такие косяки при создании темы. Как-никак это олимпиада, поэтому решать ее должны сами школьники (я думаю, нет людей, которых Вы просите за себя учиться). Могу подтолкнуть на алгоритм, который я уже считаю оптимальным.
1. Создаем массив предподсчета на 26 элементов (сколько возможных вариаций у одной буквы). Каждый элемент содержит в себе количество вхождений этого символа (от 'a' до 'z') в строку.
2. Пробегаемся по каждому элементу из исходной строки и приплюсовываем к итоговому count сумму элементов массива предподсчета, начиная с s[i] - 'a'-го элемента.
Итоговая сложность - O(26n). В худшем случае - 2 * 10^6, что спокойно должно заходить по времени.
ВАЖНО: программа будет заходить как минимум на C/C++/Pascal, насчет Python я не уверен.
 
И тут я осознаю, что ограничение входных совсем не 105, а 10^5. Советую сразу исправлять такие косяки при создании темы. Как-никак это олимпиада, поэтому решать ее должны сами школьники (я думаю, нет людей, которых Вы просите за себя учиться). Могу подтолкнуть на алгоритм, который я уже считаю оптимальным.
1. Создаем массив предподсчета на 26 элементов (сколько возможных вариаций у одной буквы). Каждый элемент содержит в себе количество вхождений этого символа (от 'a' до 'z') в строку.
2. Пробегаемся по каждому элементу из исходной строки и приплюсовываем к итоговому count сумму элементов массива предподсчета, начиная с s[i] - 'a'-го элемента.
Итоговая сложность - O(26n). В худшем случае - 2 * 10^6, что спокойно должно заходить по времени.
ВАЖНО: программа будет заходить как минимум на C/C++/Pascal, насчет Python я не уверен.
а может научимся оптимизировать ХОТЯ бы пайтон?..

возьмём просто пример из 609 символов инпута:
твой код занимает 0.04099с
мой код занимает 0.02699с
это уже как минимум на 35% быстрее

почему?
ну, во-первых,
if (i == j):
эта строчка никогда не будет true (почти, достаточно во втором цикле +1 поставить на старт) по твоему коду, объяснять почему - не буду. Убираем строчку - рантайм составляет уже около 0.0356с
идём дальше. получение элемента из массива тоже забирает большое время рантайма. чтобы избавиться от этого - придётся использовать мой код уже, с получением элемента из массива сразу, без индекса. Конечно n-ое время займёт срез при каждом прохождении первого цикла с i, но это время несоизмеримо с получением элемента из списка по индексу. ну и в конечном итоге можно прийти к меньше рантайму несложными этапами оптимизации..
 
а может научимся оптимизировать ХОТЯ бы пайтон?..

возьмём просто пример из 609 символов инпута:
твой код занимает 0.04099с
мой код занимает 0.02699с
это уже как минимум на 35% быстрее

почему?
ну, во-первых,
if (i == j):
эта строчка никогда не будет true по твоему коду, объяснять почему - не буду. Убираем строчку - рантайм составляет уже около 0.0356с
идём дальше. получение элемента из массива тоже забирает большое время рантайма. чтобы избавиться от этого - придётся использовать мой код уже, с получением элемента из массива сразу, без индекса. Конечно n-ое время займёт срез при каждом прохождении первого цикла с i, но это время несоизмеримо с получением элемента из списка по индексу. ну и в конечном итоге можно прийти к меньше рантайму несложными этапами оптимизации..
Какой толк оптимизировать заранее неверный алгоритм? Тем более, олимпиадные задачи зачастую не подразуевают оптимизаций в области тонкостей языка. Здесь важна идейная составляющая.
 
получение элемента из массива тоже забирает большое время рантайма
Меня это, честно говоря, удивило, в том же C++ получение доступа к элементу массива занимает O(1), где константа практически не забирает времени во время исполнения. Еще одна хорошая причина не рисковать своими баллами и писать заранее на более быстром языке.
 
Какой толк оптимизировать заранее неверный алгоритм? Тем более, олимпиадные задачи зачастую не подразуевают оптимизаций в области тонкостей языка. Здесь важна идейная составляющая.
конечно, 100к символьный инпут за 1с не пройдёт, но оптимизацию никто не отменял..
 
Меня это, честно говоря, удивило, в том же C++ получение доступа к элементу массива занимает O(1), где константа практически не забирает времени во время исполнения. Еще одна хорошая причина не рисковать своими баллами и писать заранее на более быстром языке.
очевидно, что все олимпиады выше города стоит писать на плюсах хотя бы, но раз автору нужно на пайтоне, пускай
(про город я пишу к тому, что я ещё не встречал сложных олимпиадных задач до города, требующего малого рантайма при большом ограничении)
 
очевидно, что все олимпиады выше города стоит писать на плюсах хотя бы, но раз автору нужно на пайтоне, пускай
(про город я пишу к тому, что я ещё не встречал сложных олимпиадных задач до города, требующего малого рантайма при большом ограничении)
В олимпиаде не обязательно на питоне писать можно на с++
 
Я так понимаю все тут из Республики Башкортостан, Курганской области, Оренбургской области, Самарской области, Саратовской области?
 
Задача 5: Древнее имя
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

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

Входные данные
В первой строке входных данных содержится целое число N (1 ≤ N ≤ 105) — длина любимого индейского имени Кати.

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

Выходные данные
Выведите единственное целое число — коэффициент древности имени.

Посмотреть вложение 177773
на питоне
https://yougame.biz/threads/230162/ - решения всех задач с Вашей олимпиады. Что там можно было решать несколько часов - я не знаю.
 
конечно, 100к символьный инпут за 1с не пройдёт, но оптимизацию никто не отменял..
std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); <- после этого за секунду можно спокойно считать порядка 8*10^6 интов (а вывести около 9*10^6). И если в вводе/выводе ожидается больше тысячи чисел стоит эти 3 строки написать.

Через printf/scanf еще процентов на 5 быстрее. А если ты вообще отбитый, то можно самому написать функции для чтения/вывода (еще процентов на 15 быстрее). А это как видно больше 10^8 чисел/порядка 10^9 символов в секунду (вместо 10^5 ошибочно предложенных тобой).

Как человек который прошел в универ через аналог всероса для РБ и по многим олимпиадам в РФ поездил + писал задачи для сборов могу точно сказать - уменьшение константы в 2-3 раза не должно позволять решить задачу. Вообще на нормальных олимпиадах если дано 2 секунды, то решение жюри работает за 0.5 максимум (т.е. гарантируют в два раза, а на практике есть запас в 3-5 раз).

Так что оптимизации вроде давай вместо
C++:
Expand Collapse Copy
vector<vector<int> a = ...;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (i < j) {
      DoSmthIfILessThanJ(a[i][j]);
    }
  }
}
писать
C++:
Expand Collapse Copy
int a[MAXN][MAXN];
for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    DoSmthIfILessThanJ(a[i][j]);
  }
}
не должны влиять на итоговое количество баллов (за исключением очень-очень редких случаев, где у тебя, например, задача с открытыми тестами или оптимизационная задача), несмотря на относительно немаленькую разницу в скорости.
 
Назад
Сверху Снизу