Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2018-11-12 19:07:04

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Оптимізатор рішень

Зробив невеличкий сервіс, що компілює С++ файли з оптимізаціями і видає cpp файл з асемблерною вставкою. За 2 кліка зробить ваше рішення у кілька разів швидшим.
Для першого туру користі великої не буде, але для 2-3 туру сервіс допоможе зосередитись на розв'язуванні задачі, а не на різних безглуздих маніпуляціях з кодом, таких як заміна рядка "a = min(a, b)" на рядок "if (b < a) a = b;" (і я зараз серйозно, така маніпуляція може зробити рішення до 15-20% швидшим (якщо пошук мінімумів - одна з основних задач коду. Якщо це єдина задача, то прискорення може бути навіть більше), якщо воно збирається без оптимізацій, як на NetOI. Дуже важлива маніпуляція. Мабуть примус до заняття подібними "оптимізаціями" має дуже потужний педагогічний ефект).

В якості невеличкого бонусу є можливість компілювати рішення з новими версіями стандарту. Використовувати нові фішки стандартної бібліотеки не вийде (точніше, використовувати можна, але на сервері NetOI отриманий файл не злінкується), але якесь, скажімо, автовиведення типів (auto) - працюватиме.

Сам сервіс:
https://netoi.dim0v.com/

Відредаговано Dim_ov (2018-11-12 21:45:50)

Поза форумом

 

#2 2018-11-13 18:16:12

monx94
Олімпієць
Зареєстрований: 2018-10-10
Повідомлень: 16

Re: Оптимізатор рішень

Дякую!

Поза форумом

 

#3 2018-11-15 03:41:08

Петрик П'яточкін
Олімпієць
Зареєстрований: 2018-11-15
Повідомлень: 3

Re: Оптимізатор рішень

Себто рішення треба залити вам на сервер? Геніяльно!

Поза форумом

 

#4 2018-11-15 10:46:41

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Оптимізатор рішень

Так, треба залити на сервер. JS компіляторів C++ я, нажаль, не знаю. Якщо ви про такий знаєте - поділіться. Я з радістю оновлю сервіс і зроблю компіляцію на стороні клієнта.

А так, загалом - нічого не треба. Все ж добровільно. Просто на одну можливість більше стало. Можна залити код на сервер і отримати швидший код у відповідь. Можна самому зібрати рішення з ключами -O{2,3,fast,чи що ваша душа бажає} -S, провести кілька нехитрих маніпуляцій вручну і отримати той самий результат. Можна написати #pragma GCC optimize і отримати рішення, де будуть оптимізовані хоча б власні функції, а бібліотечні залишаться повільними. Можна вручну зайнятися роботою компілятора з перестановки інструкцій, розгортання циклів і такого іншого і писати свої велосипеди замість використання бібліотечних структур, як і було, схоже, задумано творцями олімпіади. Варіантів багато. В тому числі і для тих, хто боїться, що його рішення вкрадуть.

Але для інших новий варіант може виявитися зручнішим. Особливо для нерейтингових учасників, які тут просто зі спортивного інтересу і на життя яких в принципі NetOI особливо ніяк не вплине.

Додав в опис попередження про потенційну можливість викрадення коду злим мною

Відредаговано Dim_ov (2018-11-15 11:26:58)

Поза форумом

 

#5 2018-11-15 20:47:25

Петрик П'яточкін
Олімпієць
Зареєстрований: 2018-11-15
Повідомлень: 3

Re: Оптимізатор рішень

А в чому проблема зробити цю утилу опенсорс і викласти на гітхаб, щоб всі зацікавлені могли безпечно юзати та розвивати?

Поза форумом

 

#6 2018-11-15 21:39:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Оптимізатор рішень

Головних проблем 2. Перша полягає в тому, що всі зацікавлені, які могли б щось тут розвивати, напишуть собі аналогічну утиліту за кілька годин. А якщо не давати до неї публічний доступ і відповідно не паритися з приводу захисту сервера від юних хакерів і взагалі наявності веб-інтерфейсу, то створення скрипта з аналогічною функціональністю займе хвилин 5)
Друга полягає в тому, що параноїки, які при цьому з якоїсь причини не мають можливості зробити собі аналог, все одно жодним чином не зможуть переконатися, що у мене на сервері знаходиться саме цей код, а не якийсь інший, що відправляє рішення в ІДІЛ smile


Ну але взагалі пропозиція резонна. Викладу через пару годин, коли доберуся додому.

Поза форумом

 

#7 2018-11-15 22:16:33

Vlad
Олімпієць
Зареєстрований: 2017-11-11
Повідомлень: 13

Re: Оптимізатор рішень

Dim_ov написав:

Можна написати #pragma GCC optimize і отримати рішення, де будуть оптимізовані хоча б власні функції, а бібліотечні залишаться повільними.

Цікаво, що навіть це не працює на NetOI (чи, може, я щось неправильно роблю). Наприклад, я написав такий код:

Код:

#pragma GCC optimize("O3")
int main()
{
    for(int i=0;i<1000000000;i++);
}

На NetOI цей код отримує TL, хоча оптимізація мала б видалити цей цикл.
Зрозуміло, що цей код працює за долі секунди в мене на комп'ютері і на інших сайтах. А також на NetOI після обробки Вашим оптимізатором.

Відредаговано Vlad (2018-11-15 22:20:01)

Поза форумом

 

#8 2018-11-16 04:26:43

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Оптимізатор рішень

Петрик П'яточкін написав:

А в чому проблема зробити цю утилу опенсорс і викласти на гітхаб, щоб всі зацікавлені могли безпечно юзати та розвивати?

Ось, розвивайте на здоров'я:

https://bitbucket.org/dim_ov/netoi-compiler

Поза форумом

 

#9 2018-11-16 13:13:53

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Оптимізатор рішень

Vlad написав:

Цікаво, що навіть це не працює на NetOI

Дійсно. В GCC 4.4.7 ця прагма ще працює криво. Ну що ж, на одну можливість менше smile

Можна вручну окремі функції позначати атрибутом:

Код:

void f() __attribute__((optimize("-O3")));
void f() {
  for (int i = 0; i < 1000000000; ++i);
}

int main() {
  f();
}

Так оптимізуватиме

Відредаговано Dim_ov (2018-11-16 13:20:11)

Поза форумом

 

#10 2018-11-16 18:01:59

ikovrigin
Олімпієць
Зареєстрований: 2017-11-13
Повідомлень: 26

Re: Оптимізатор рішень

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

Поза форумом

 

#11 2018-11-17 08:55:21

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Оптимізатор рішень

ikovrigin написав:

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

У международной олимпиады и у NetOI несколько разные задачи. Основная цель нашей олимпиады - вовлечь в это движение как можно более широкий круг школьников, особенно из регионов, где нет "звездных" тренеров, дать шанс лучшим из них попробовать себя на 4-м этапе.  Это, конечно, здорово, что есть среди участников опытные и "крутые"...

Поза форумом

 

#12 2018-11-17 09:29:35

ikovrigin
Олімпієць
Зареєстрований: 2017-11-13
Повідомлень: 26

Re: Оптимізатор рішень

Жюри_Пасихов написав:

ikovrigin написав:

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

У международной олимпиады и у NetOI несколько разные задачи. Основная цель нашей олимпиады - вовлечь в это движение как можно более широкий круг школьников, особенно из регионов, где нет "звездных" тренеров, дать шанс лучшим из них попробовать себя на 4-м этапе.  Это, конечно, здорово, что есть среди участников опытные и "крутые"...

Мой посыл был строго противоположный. Я не говорю об уровне задач, я говорю о правилах олимпиады. Указание ограничений по времени и по памяти. Настройки компиляции. Список тем которые (не)должны использоваться в решениях (для примера прошлогодние задачи на вычисление длинны ремня имхо это задание для лабораторной работы, а не для олимпиады). Все это упростило бы вход в олимпиады для новичков. Повторюсь это мое мнение, однако мне кажется что правила должны быть одни и те же, различия должны быть только в уровне задач. Нельзя обучаться шахматам играя в шашки, правила "игры" должны быть определены заранее. Если бы ограничений не было или они были более "мягкими" это бы могло объяснить их отсутствие в условиях, в нашем же случае ограничения как на обычных олимпиадах х2.5-х3 от авторского решения, но при этом участники о них не знают.

Відредаговано ikovrigin (2018-11-17 09:46:23)

Поза форумом

 

#13 2018-11-17 11:56:08

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Оптимізатор рішень

Жюри_Пасихов написав:

У международной олимпиады и у NetOI несколько разные задачи. Основная цель нашей олимпиады - вовлечь в это движение как можно более широкий круг школьников, особенно из регионов, где нет "звездных" тренеров, дать шанс лучшим из них попробовать себя на 4-м этапе.  Это, конечно, здорово, что есть среди участников опытные и "крутые"...

І "вовлеченный широкий круг", у якого цілком закономірно може бути купа питань (в силу відсутності досвіду і тренера, якому можна було б їх задати), потрапляє на форум, де і журі, і "досвідчені й круті" учасники ці питання ігнорують. До учасників якісь претензії висувати було б дивно, але від журі (особливо, якщо журі ставить однією з основних цілей олімпіади залучення новачків) очікуєш, що вони на питання відповідатимуть хоча б раз на тиждень. В тому числі й словами "відповіді немає", щоб не плодити пусті обговорення, які, врешті решт майже завжди скочуються до підказок.

І мені так само, як і ikovrigin'у, не дуже зрозуміло, яким чином використання загальноприйнятих опцій компіляції завадить "вовлечению".
І те ж саме щодо правил по оголошенню тайм-лімітів. Взагалі ідея цікава і мені особисто подобається. Добре, коли є якась різноманітність у правилах і форматах змагань, а не всі контести як під копірку на одному і тому ж єджаджі проводяться. Але це цікаво якраз для досвідчених учасників. Новачок не може адекватно прикинути необхідну асимптотику алгоритму виходячи з обмежень і умови задачі. І тим більше новачок не зможе оцінити, наскільки можна знизити "приховану константу" у його реалізації і коли варто зупинитися з оптимізаціями. Особливо коли правила вимагають "оптимізацій" подібних тим, що в початковому повідомленні теми. В плані залучення новачків ці правила важко назвати корисними. А в поєднанні зі специфічними параметрами компіляції я б їх ще назвав такими, що формують "шкідливі звички" у програмуванні.

Поза форумом

 

#14 2018-11-17 17:26:04

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Оптимізатор рішень

Dim_ov написав:

Жюри_Пасихов написав:

У международной олимпиады и у NetOI несколько разные задачи. Основная цель нашей олимпиады - вовлечь в это движение как можно более широкий круг школьников, особенно из регионов, где нет "звездных" тренеров, дать шанс лучшим из них попробовать себя на 4-м этапе.  Это, конечно, здорово, что есть среди участников опытные и "крутые"...

І "вовлеченный широкий круг", у якого цілком закономірно може бути купа питань (в силу відсутності досвіду і тренера, якому можна було б їх задати), потрапляє на форум, де і журі, і "досвідчені й круті" учасники ці питання ігнорують. До учасників якісь претензії висувати було б дивно, але від журі (особливо, якщо журі ставить однією з основних цілей олімпіади залучення новачків) очікуєш, що вони на питання відповідатимуть хоча б раз на тиждень. В тому числі й словами "відповіді немає", щоб не плодити пусті обговорення, які, врешті решт майже завжди скочуються до підказок.

І мені так само, як і ikovrigin'у, не дуже зрозуміло, яким чином використання загальноприйнятих опцій компіляції завадить "вовлечению".
І те ж саме щодо правил по оголошенню тайм-лімітів. Взагалі ідея цікава і мені особисто подобається. Добре, коли є якась різноманітність у правилах і форматах змагань, а не всі контести як під копірку на одному і тому ж єджаджі проводяться. Але це цікаво якраз для досвідчених учасників. Новачок не може адекватно прикинути необхідну асимптотику алгоритму виходячи з обмежень і умови задачі. І тим більше новачок не зможе оцінити, наскільки можна знизити "приховану константу" у його реалізації і коли варто зупинитися з оптимізаціями. Особливо коли правила вимагають "оптимізацій" подібних тим, що в початковому повідомленні теми. В плані залучення новачків ці правила важко назвати корисними. А в поєднанні зі специфічними параметрами компіляції я б їх ще назвав такими, що формують "шкідливі звички" у програмуванні.

1. ЖЮРИ СТАРАЕТСЯ отвечать на все вопросы по условиям, которые требуют ответов, проводит вебинары-консультации по условиям задач каждого тура.. Часть вопросов, особенно ОПЫТНЫХ и "поднаторелых" участников, являются не вопросами по сути условий, а троллингом или обсуждением мнимых или действительных недостатков правил или системы проведения олимпиады. На это просто нет времени. Недостатки есть. Однако много раз говорил - старая ГДР-овская  детская спортивная телепрограмма называлась "Делай с нами, делай, как мы, делай лучше нас". Однако предупреждаю, что "делать лучше" вам придется на волонтерских "засадах" (олимпиада не финансируется), в свободное от работы и иных обязанностей время. Готовить 20 задач для каждой олимпиады,  поддерживать работоспособность системы, и 18 лет подряд вежливо пояснять:
- идея проведения олимпиад в Интернете реализована нами в Украине ПЕРВЫМИ. Эджадж еще никто тогда не видел, да и вряд ли он существовал в 1997...;
- правила мы придумывали сами, исходя из НАШЕГО понимания того, какой должна быть олимпиада с ДЛИТЕЛЬНЫМИ заочными турами. С ними можно не соглашаться. Их можно совершенствовать. Однако вряд ли на начальных этапах обучения спортивному программированию указание "время на тест... память...." полезнее для новичка, чем "Реализуйте самый эффективный алгоритм в своем решении". А "вбить" решение при помощи "изысков" в виде ключей оптимизации или особенностей той или иной библиотеки-это ИМХО, слегка для других олимпиад...
- и, наконец, все равно побеждает сильнейший. Умеющий лучше думать и больше знающий.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt