[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 16, 17, 18
Автор Сообщение
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Давайте учиться на своих и чужих ошибках.

Предлагаю ВСЕМ писать ПОДРОБНО в этой теме о тех случаях, когда ВЫ пишете полное решение, но не получаете полный балл по задаче.

И ОБЯЗАТЕЛЬНО - какой вывод Вы сделали, чтобы избежать подобных ошибок в дальнейшем.
Владислав Подтелкин

Темы: 5
Сообщений: 29

Мой профиль
Россия-И. Личные\3 - "Квадратный корень" 96133 Максим Буздалов
Поставил криво константу(10-3) потому что подумал что все равно дробное с целым сравнивается и поэтому хватит. Надо было хотя бы 10-9 и 100 балов.
Вывод: Простая задача совсем не означает что тестировать не надо.
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Это НЕДОСТАТОЧНО подробно.
Приведи КОД - какой был и каким должен быть.
А еще непонятно, КАК определять это константу для сравнения.
Почему 10^-3 мало?
А 10^-6 хватит? Почему?
Владислав Подтелкин

Темы: 5
Сообщений: 29

Мой профиль
Оказалось что там и (-9) не хватает... Я поставил (-30) и хватило.. И еще extended поставил.. А на олимпиаде было double.
Тоже вывод: зачем использовать тип с точьностью хуже.
А как выбрать константу я не знаю(ставил как попало)..
И вообще наверное есть тесты для которых и этой точности не хватит...
Владислав Подтелкин

Темы: 5
Сообщений: 29

Мой профиль
Попробывал убрать константу и просто сравнивать (a = b)
и все равно прошло.. Значит главное что нужно было extended поставить.
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Вас вроде бы еще в ШКОЛЕ с первого класса учат делать РАБОТУ НАД ОШИБКАМИ. Делайте, наконец!!!

И потом ПРАВИЛЬНЫЙ вывод делайте, а не первый, что в голову придет.
Егор Малышев

Темы: 42
Сообщений: 132

Мой профиль
Различия Delphi <-> Free Pascal
На Delphi строковый тип организован очень хорошо,поэтому все операции выполняются быстро,
когда на Free Pascal те же операции выполняются гораздо дольше.
На примере даже для хранения строк,на Delphi очень удобно использовать тип Ansistring,
он динамический само расширяемый,так что память мы возьмём именно ту что надо,и над ним можно выполнять все операции что и над типом String.
Но во Free Pascal этот тип более коварен,он работает медленнее,его для меня сложнее отлаживать в той среде,
а так же,он динамический само расширяемый,но! С самого начала объявления Ansistring занимает память столько сколько и String (то есть 255 символов - 255 byte). Поэтому если мы пишем на Delphi и объявляем массив на 1000000 Ansistring,то всё будет нормально,а на Free Pasсal ваша программа просто слетит по памяти,хоть и будет работать правильно..

Поэтому иногда лучше вместо Ansistring (не всегда!) использовать ограниченный String (String[100]),то есть если у нас в задаче строки длинной меньше 255,то можно с самого начала ограничить тип String потребляемой длинной,но и это не всегда работает лучше,на Free Pascal как показывает,лучше использовать иногда массив *char (array[0..100]of char) с ним можно выполнять все операции что и над предыдущими типами,и работает он быстрее!

Так что нужно правильно выбирать когда и какой тип использовать лучше и комфортнее!
Так как я чаще пишу на Delphi то я использую Ansistring,так как это очень удобно,а когда приходится при этом отправить на Free Pascal то уже приходится выбирать что использовать,что бы результат был максимальным!
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Плохо сделал :-( Много текста и не очень понятно.

Пожалуйста, добавь к твоему тексту "минимальный измененный фрагмент"
Было так:
...
работало за 2.1+ сек

Сделал так:
...
Теперь работает за 0.3 сек

Заранее благодарен :-)
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Ответ по электронной почте Адаму Бардашевичу

Посмотрел сам - у тебя неинициализированы массивы L и R.
А в строке 8 ты их инкрементируешь.
Пакетный компилятор НЕ ГАРАНТИРУЕТ, что массивы L и R будут проинициализированы нулями.
Там теоретически (а на НИТ4 получается и практически) могут быть ЛЮБЫЕ ЗНАЧЕНИЯ (случайные, оставшиеяся в этих ячейках памяти от выполнения предыдущих программ).

Вот твоя программа

var	
 i,n,h,min,ans:longint;	
 a:array[1..300000]of longint;	
 l,r:array[1..600000]of longint;	
begin	
 readln(n,h);	
 for i:=1 to n do readln(a[i]);	
 for i:=1 to n do if odd(i) then inc(l[a[i]])else inc(r[h-a[i]+1]);	
 for i:=h-1 downto 1 do l[i]:=l[i+1]+l[i];	
 for i:=2 to h do r[i]:=r[i-1]+r[i];	
 min:=maxlongint;	
 ans:=0;	
 for i:=1 to h do if l[i]+r[i]<min then	
 begin	
  min:=l[i]+r[i];	
  ans:=1;	
 end else if l[i]+r[i]=min then inc(ans);	
 writeln(min,' ',ans);	
end.	

А это строки из сообщения компилятора (ты САМ мог увидеть)
9 victim.PPW(7,19) Warning: Variable "a" does not seem to be initialized
10 victim.PPW(8,34) Warning: Variable "l" does not seem to be initialized
11 victim.PPW(8,51) Warning: Variable "r" does not seem to be initialized

Про массив A - ложное сообщение.
А про L и R - "в самую точку".

Удивительно, что программист такого класса как ты, до сих пор НЕ ИНИЦИЛИЗИРУЕТ массивы начальными значениями
(нулями в этой программе).


----- Исходное сообщение -----
От: Michael Dolinsky
Отправлено: Sunday, January 10, 2010 3:21 PM
Кому: 'Bardashevich Adam'; AlexeyKaminsky
Копия: Участники олимпиад
Тема: Ответ: 3 - "FIREFLY"

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

Леша Каминский - а ты что посоветуешь?



----- Исходное сообщение -----
От: Bardashevich Adam
Отправлено: Sunday, January 10, 2010 3:15 PM
Кому: Michael Dolinsky
Тема: 3 - "FIREFLY"

Решение стабильно не проходит восьмой тест на "DelTA3 at Nit4", на других серверах проходит все тесты.
Я скопировал файл exe, скомпилированый на "DelTA3 at Nit4", у меня он работает на восьмом тесте верно.


-----Исходное сообщение-----
От: Michael Dolinsky
Отправлено: Sunday, January 10, 2010 2:46 PM
Кому: 'Bardashevich Adam'
Копия: Участники олимпиад
Тема: Ответ: 3 - "FIREFLY"

0,1 0 ошибка во время выполнения
В программе могут быть "динамические" ошибки - которые могут проявляться, а могут нет.
Поэтому корректнее раз 10 (или больше?) послать на разные тест-машины.
И если все эти отсылки будут корректными - есть смысл сигнализировать нам о нашей ошибке.
А если у тебя программа 5 раз проходит, а 5 раз нет - то проблема скорей всего в программе.
(Например, неинициализированые переменные)

Попробуй и сообщи результат.
Спасибо



----- Исходное сообщение -----
От: Bardashevich Adam
Отправлено: Sunday, January 10, 2010 2:35 PM
Кому: Michael Dolinsky
Тема: 3 - "FIREFLY"

Здравствуйте, Михаил Семёнович. Сегодня у меня возникла проблема, связаная с соревнованием в курсе "Программирование - профессионалы (лич. 2009-2010)", точнее с задачей "coci_2006-07\7_Regional\3 - "FIREFLY" 92292 ". Дело в том, что два абсолютно одинаковых решения, у меня прошли разное количество баллов. Я взял код непрошедшего решения, и отправил в дорешивании, он прошёл. И теперь я прошу вас разобраться с моей проблемой, перетестировать меня или поступить, как Вы сочтёте нужным.
С уважением, Бардашевич Адам.
Егор Малышев

Темы: 42
Сообщений: 132

Мой профиль


Михаил Долинский:

Плохо сделал :-( Много текста и не очень понятно.

Пожалуйста, добавь к твоему тексту "минимальный измененный фрагмент"
Было так:
...
работало за 2.1+ сек

Сделал так:
...
Теперь работает за 0.3 сек

Заранее благодарен :-) 

Было ansistring - > 2 сек на Free Pascal.
Сделал type ansistring=array[0..101]of char;
Стало 0.3 сек

Что то типо
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
SnarkNews "Best of 2009" : Публикация года
Александр Бахтурин, Россия, СибГУТИ

вторник, 20 октября 2009 г.
Западно-Сибирский четвертьфинал'09
Началось всё, что естественно, с открытия Мы были рады снова видеть Рояка. Он, судя по всему, тоже был рад, потому что объявил, что получил из Питера ключи компиляции С++ и Java, которые используются на NEERC, и применил их в тестирующей системе.. А сколько радости было в его голосе, когда он сказал, что полученные параметры не содержат ключей для расширенного стека Java!.. - гораздо больше, мне показалось, чем негодования среди нас

Собственно контест начался с того, что у нас на компе не запустился Eclipse. Ничего, мы пересели на другой, где желаемая среда также не соизволила стартануть. В диспетчере задач одно из двух ядер нашего ПК было полностью загружено антивирусом, что не понравилось нам, и мы попросили ассистента, присутствовавшего в аудитории, антивирус выключить (пользовательских прав, как это обычно бывает, было недостаточно). Нам ответили, что не выключат, ибо мы можем назапускать вирусов и вообще, нехорошо это – антивирус выключать. К этому моменту контест шёл уже минут 5-10, мы пишем на непривычном нам С++ решение и сдаём первую задачу. Про то, что в нашей панели участника в тестирующей системе было указано практически для каждой задачи, что она либо уже сдана нами, либо мы сделали по ней неуспешные попытки, мы даже не сообщили жюри – думали, что такой косяк у всех, и что это будет исправлено. Забегая вперёд, можно сказать, что так было только у нас (либо ещё у нескольких команд, которые так же, как и мы, на это забили).

Тем временем, у нас внезапно запустился Eclipse – оказалось, что он всё это время потихоньку стартовал, чем вызывал бурное негодование со стороны антивируса. Нашему счастью не было предела Мы быстренько закодили ещё одну задачку и получили RE#10. Что ж, подумали мы, может, что-то не так у нас. Поскольку возможности распечатать решение и проанализировать его, не занимая комп, не было, мы временно забили на упавшую с RE задачу и написали ещё одну. Submission – и у нас RE#15. Что за ерунда, думаем мы. Может быть, у них корявые тесты?

Делаем валидацию ввода (а программе требовалось считать лишь одно положительное число) – если чтение не удалось, то считаем, что считали «1». Отправляем с полной уверенностью, что получим WA#15. Пришедший RE#7 стал полным сюрпризом для нас – мы в принципе не могли придумать объяснения происходящему.

На наше сообщение к жюри с пожеланием проверить тесты получаем ответ о том, что им, жюри, не ясны основания для подобной просьбы. Хорошо, мы начинаем писать подробное сообщение с номерами тестов, на которых наши решения ловили RE и в каких ситуациях. Тут к нам подходит Рояк, на лице которого читается «опять эта хренова Связь чем-то недовольна». Мы всё подробно ему объясняем, он уходит. Мы смотрим рейтинг и остаёмся в недоумении – команда Алтайского политеха сдаёт эти же задачи с плюсов, а они, как и мы, пишут на Java….

….и вот написана ещё одна задача, которая так же получает RE. Здесь нужно сказать, что у нас впервые за последние несколько лет возникла мысль о том, что в сложившейся ситуации (у нас одна задача, мы еле-еле входим в двадцатку, нас обходит вторая команда нашего ВУЗа) нужно постараться, чтобы хотя бы просто пройти на NEERC.

Мы переписываем одно из трёх готовых на тот момент решений на С++, и она тут же сдаётся – то же самое и с двумя другими. Я заканчиваю очередную задачу, получаю WA. Пока думаю над возможными причинами, Антон пишет ещё одно решение – уже сразу на С++. До меня доходит, что я написал не так, исправляю, и получаю RE на более позднем, чем предыдущий WA, тесте – верный знак, что программа готова к тому, чтобы быть переписанной Антоном на С++, что он и делает.

Несколько сданных за небольшой промежуток времени задач взбодрили нас; взбодрили принесённые девушками вкусные бутербродики и, конечно же, взбодрил Рояк, сообщивший, что в их тестирующей системе была найдена ошибка, в результате которой решения на Java, не закрывающие после работы входной файл, могли получать RE на произвольном тесте. Успокоив нас обещанем rejudge'а, Рояк откланялся, и мы продолжили решать.

Вряд ли мы удивились, когда снова получили RE на джавовском решении. Просто переписали его на С++ и сдали, сказав Рояку, что, не смотря на его слова, проблема, по видимому, ещё не решена.
Остаток контеста прошёл вполне нормально – мы писали на С++ Под конец выяснилось, что последний RE мы получили по другой, нежели предыдущие, причине – формат одного из тестов не соответствовал описанному в условии. А уже после контеста до нашего сведения дошли другие интересные вещи.

Во-первых, оказалось, что косяк в их тестере нашёл наш Скорж, причём для этого он буквально построчно сравнил наше упавшее решение с зачтённым решением алтайцев. Сравнение, как можно догадаться, показало, что алтайцы, в отличие от нас, входной файл закрывали. Прилежность – штука хорошая

Во-вторых, оказалось, что параметры командной строки для запуска решений на Java не изменились с предыдущего НГТУшного контеста и содержали все необходимые ключи для того, чтобы программы на Java не чувствовали себя стестнёнными небольшим объёмом доступной памяти. (Да и вряд ли они могли бы быть изменены – для этого пришлось бы пересобирать тестирующую систему, и кто знает, к чему бы это привело ) В свете этого, совершенно непонятно, что заставило Рояка сказать на открытии то, что он сказал.
Вот так нескучно прошёл очередной, и, что печально, последний для нашей команды Западно-Сибирский четвертьфинал

И комментарии к ней

оригинальный пост: http://vkontakte.ru/note1356659_9679528
Автор: AlphaStream на 0:02
2 коммент.:
nikodim комментирует...
очередной раз удивляет самоуверенность команд, которые не используют пробный тур дря проверки тестирующей системы

11 января 2010 г. 0:13
scorzh комментирует...
nikodim, дело в том, что пробного тура здесь тоже традиционно не было. Надо было это добавить в отчет. Такой вот четвертьфинал. И пишут его иногородние по инету (наверное единственный из всех четвертьфиналов NEERC), а новосибирские участники - онсайт, то есть иногородним дана некая фора - на онсайте нельзя набить заранее шаблон, нет доступа в инет и, конечно, лишь один компьютер на команду. Хотя, надеюсь, участвующие по инету команды соблюдают принципы fair-play.
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Делаем валидацию ввода (а программе требовалось считать лишь одно положительное 
число) – если чтение не удалось, то считаем, что считали «1». Отправляем с полной 
уверенностью, что получим WA#15. Пришедший RE#7 стал полным сюрпризом для нас – мы в 
принципе не могли придумать объяснения происходящему. 
Я не понял эту фразу.
Поясните, пожалуйста, кто понял - что такое валидация ввода в их понятии и как это им помогло или должно было помочь?
Егор Малышев

Темы: 42
Сообщений: 132

Мой профиль
Я так понимаю они думали что тесты корявые,поэтому валидация ввода,проверяет смогли ли они прочитать,если нет,то они запускали программу на 1,что бы получить на том тесте ВА! Но дело было не в тестах
Алексей Данченко

Темы: 0
Сообщений: 40

Мой профиль


Михаил Долинский:

Делаем валидацию ввода (а программе требовалось считать лишь одно положительное 
число) – если чтение не удалось, то считаем, что считали «1». Отправляем с полной 
уверенностью, что получим WA#15. Пришедший RE#7 стал полным сюрпризом для нас – мы в 
принципе не могли придумать объяснения происходящему. 
Я не понял эту фразу.
Поясните, пожалуйста, кто понял - что такое валидация ввода в их понятии и как это им помогло или должно было помочь?  


Они получили Runtime Error, и решили проверить, не падает ли у них на вводе из-за неправильного теста (странное предположение с учетом того, что во входном файле должно было быть одно число). Поэтому они сделали валидацию ввода, то есть проверили, действительно ли они прочитали/могут прочитать число. В случае неудачи, считали, что прочитали 1. При таком раскладе они ожидали получить теперь уже не RE, а WA на том же тесте.
Михаил Долинский

Темы: 1982
Сообщений: 47183

Мой профиль
Спасибо
 
Индекс форума ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2, 3, ... 16, 17, 18
Time:0,064