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

sk2wie · 28 Окт 2021

Задача 5: Древнее имя
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

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

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

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

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

Посмотреть вложение 177773
на питоне

xLamantine · 28 Окт 2021

Вы тоже участвуете в олимпиаде и ничего не умеете?

Irval · 28 Окт 2021

Python:

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)

Flowseal · 28 Окт 2021

Python:

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()

goldbann · 28 Окт 2021

Irval написал(а):

Python:

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 секунды

Irval · 28 Окт 2021

goldbann написал(а):
время выполнения 1 секунда по критериям. ваша прога выполняется более 1 секунды

Именно поэтому не нужно использовать Python для написания олимпиад. Сложность алгоритма - O(n^2), в худжем случае это должно занять 105^2 операций (на самом деле даже меньше, т.к. это прогрессия n * (n - 1)), что выполняется компьютером на адекватных ЯП практически моментально.

Irval · 28 Окт 2021

И тут я осознаю, что ограничение входных совсем не 105, а 10^5. Советую сразу исправлять такие косяки при создании темы. Как-никак это олимпиада, поэтому решать ее должны сами школьники (я думаю, нет людей, которых Вы просите за себя учиться). Могу подтолкнуть на алгоритм, который я уже считаю оптимальным.
1. Создаем массив предподсчета на 26 элементов (сколько возможных вариаций у одной буквы). Каждый элемент содержит в себе количество вхождений этого символа (от 'a' до 'z') в строку.
2. Пробегаемся по каждому элементу из исходной строки и приплюсовываем к итоговому count сумму элементов массива предподсчета, начиная с s[i] - 'a'-го элемента.
Итоговая сложность - O(26n). В худшем случае - 2 * 10^6, что спокойно должно заходить по времени.
ВАЖНО: программа будет заходить как минимум на C/C++/Pascal, насчет Python я не уверен.

Flowseal · 28 Окт 2021

Irval написал(а):
И тут я осознаю, что ограничение входных совсем не 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, но это время несоизмеримо с получением элемента из списка по индексу. ну и в конечном итоге можно прийти к меньше рантайму несложными этапами оптимизации..

Irval · 28 Окт 2021

Flowseal написал(а):
а может научимся оптимизировать ХОТЯ бы пайтон?..

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

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

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

Irval · 28 Окт 2021

Flowseal написал(а):
получение элемента из массива тоже забирает большое время рантайма

Меня это, честно говоря, удивило, в том же C++ получение доступа к элементу массива занимает O(1), где константа практически не забирает времени во время исполнения. Еще одна хорошая причина не рисковать своими баллами и писать заранее на более быстром языке.

Flowseal · 28 Окт 2021

Irval написал(а):
Какой толк оптимизировать заранее неверный алгоритм? Тем более, олимпиадные задачи зачастую не подразуевают оптимизаций в области тонкостей языка. Здесь важна идейная составляющая.

конечно, 100к символьный инпут за 1с не пройдёт, но оптимизацию никто не отменял..

Flowseal · 28 Окт 2021

Irval написал(а):
Меня это, честно говоря, удивило, в том же C++ получение доступа к элементу массива занимает O(1), где константа практически не забирает времени во время исполнения. Еще одна хорошая причина не рисковать своими баллами и писать заранее на более быстром языке.

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

EdwardCry · 28 Окт 2021

Flowseal написал(а):
очевидно, что все олимпиады выше города стоит писать на плюсах хотя бы, но раз автору нужно на пайтоне, пускай
(про город я пишу к тому, что я ещё не встречал сложных олимпиадных задач до города, требующего малого рантайма при большом ограничении)

В олимпиаде не обязательно на питоне писать можно на с++

LexaXZ · 28 Окт 2021

Я так понимаю все тут из Республики Башкортостан, Курганской области, Оренбургской области, Самарской области, Саратовской области?

Irval · 29 Окт 2021

sk2wie написал(а):
Задача 5: Древнее имя
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.

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

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

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

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

Посмотреть вложение 177773
на питоне

https://yougame.biz/threads/230162/ - решения всех задач с Вашей олимпиады. Что там можно было решать несколько часов - я не знаю.

sn0wyQ · 29 Окт 2021

Flowseal написал(а):
конечно, 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++:

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++:

int a[MAXN][MAXN];
for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    DoSmthIfILessThanJ(a[i][j]);
  }
}

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