NVAL's blog

By NVAL, 3 years ago, In Russian,

Решал одну из простых задач Damascus Collegiate Programming Contest (DCPC 2015). А именно задачу F. Само решение очевидно, буквально пару строк. Поэтому WA крайне удивил. Больше часа искал очевидный баг, случайную запятую после какого-нибудь if'a и так далее, но безуспешно. Посмотрел сабмиты других участников наиболее похожие на мой код и стал плавно менять свой код приближая к чужому AC-коду.

В итоге такой код получает WA: http://pastebin.com/0ErXg0Nw

А такой код AC: http://pastebin.com/Kt585TgD

Разница в том, что строки стали глобальными.

Кто-то может объяснить что вообще происходит и почему так? :|

UPD: проблема решена, тесты по задаче "кривые"

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By NVAL, history, 4 years ago, In Russian,

Ссылка на страницу с результатами и задачами

Сегодня виртуально решали этот четвертьфинал и возникло два вопроса:

1) Зачем давать задачу I, которая в точности до символа копирует условие задачи с Osipovsky Cup 2014 (декабрь, Ковров), проходившего в центральном же регионе? Причем некоторые команды естественно присутствовали на этом соревновании, а некоторые нет (например команда занявшая 3-е место и не сдавшая её).

2) Я правильно понимаю, что задача E в предоставленных ограничениях не решается? :| Т.е. при циклах нулевого веса.

Других обсуждений, к сожалению, не нашел.

Read more »

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

By NVAL, history, 4 years ago, In Russian,

Доброго времени суток!
Окончательно запутался с этим методом и прошу помощи у более опытных и знающих членов сообщества.
Допустим есть число до 1018, требуется его факторизовать.
Очевидно, что делители до 106 легко перебираются в лоб. Остальные делители будем, допустим, искать методом факторизации Ферма. Какова будет сложность в худшем случае?
2 года назад в тренировке 2011-2012 Waterloo Local Contest, 19 June, 2011 я сдал задачу на факторизацию с 106 итерациями и с тех пор поверил, что этот метод фактически работает за кубический корень для чисел до 1018.
Однако теперь я внезапно наткнулся на то, что число 100000007700000049 = 1000000007 * 100000007 совсем не хочет раскладываться с таким количеством шагов. Причиной заблуждения, что тот код был верный оказались предельно слабые тесты (в тестах было лишь на 2 числа больше, чем в примерах входных данных)
Теперь хочется узнать — это неверное понимание работы метода или его неверное применение?
Пример кода можно найти на e-maxx

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it