Codeforces Beta Round #11

2 года назад, # |

+13

Thanks in advance to Jakub for the prepared problems and thanks Julia for translating of everything that it was possible to translate. =)

→ Ответить

Julia

2 года назад, # ^ |

))) That was not me, who translated the problems this time. They were originally in English, and Mike translated them into Russian ;-) I have nothing to do with the coming contest. But thank you anyway for being so kind )))

→ Ответить

2 года назад, # ^ |

-6

I guess that they are in English in original this time. =)

→ Ответить

2 года назад, # ^ |

-4

ohGods! minus 2, for what??

→ Ответить

2 года назад, # |

-2

Ну вот, кто минусует за просто так, признавайтесь.

→ Ответить

imonhf

2 года назад, # |

Thanks for arranging this event.

→ Ответить

udalov

2 года назад, # ^ |

Better to thank after the round... :)

→ Ответить

http://codeforces.ru/contestRegistrants/11

2 года назад, # |

+12

lovexx почему-то зарегистрирован дважды

→ Ответить

MikeMirzayanov

2 года назад, # ^ |

Fixed. Видимо какой-то race-condition. Пофикшу, это просто.

→ Ответить

2 года назад, # ^ |

Вообще у меня во время контеста фатально сайт поплыл... справа, в окошке под названием FAndES с моей фоткой, ссылка Блог была написана аж 4 раза... в окошке прямой эфир тоже все темы по 4 раза, при этом их вместе с копиями всего 15, т.е. как и должно быть... только должно быть без копий. Тестил в хроме и ие.

→ Ответить

2 года назад, # ^ |

везде "блог" написан 4 раза, даже наверху, где "главная"

в прямом эфире тоже всё по 4 раза :)

→ Ответить

MikeMirzayanov

2 года назад, # |

Да, проблема есть. Она не только у вас.

→ Ответить

2 года назад, # ^ |

Кстати.. ещё давно заметил что в таблице рейтинга нет чёткости красный-жёлтый-синий-зелёный... То есть среди синих могут быть и зелёные, а среди жёлтых могут быть синие. Почему так?

→ Ответить

Veldrin

2 года назад, # |

И чужой код после контеста просматривать не могу. Про упразднение этой фичи, вроде, слышно не было

→ Ответить

2 года назад, # ^ |

а, кстати, стоило бы запретить копипастить код другого участника

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

→ Ответить

LoKi	2 года назад, # ^ \| +2 В чем проблема? Пусть ставит галочек, сколько хочет. Это ж в рейтинг не идет. Если кому-то хочется посылать уже готовые решения, это его проблемы. А вот мне иногда хотелось бы прогнать чье-то решение на моих тестах. → Ответить

Veldrin

2 года назад, # ^ |

Ну это проблемы самого читера, а для начинающих чужой код полезен

→ Ответить

2 года назад, # ^ |

а как же процесс "подумать"? он более чем полезен для начинающих

а чужой код не обязательно копипастить; для того, чтобы чему-то научиться, достаточно read only

→ Ответить

LoKi	2 года назад, # ^ \| 0 Пусть думает, кто мешает? Вы как-то странно рассуждаете. Кто не хочет думать, тот вообще не будет участвовать на codeforces. Кроме того, readonly вас не спасёт. Отключите Javascript или откройте исходный код страницы, проблем-то. → Ответить

ivan.metelsky

2 года назад, # |

Thanks for the round!

I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.

→ Ответить

2 года назад, # ^ |

Problem B is wonderful :)

→ Ответить

ivan.metelsky

2 года назад, # ^ |

I wonder what was your problem with B that leaded to so many incorrect attempts.

→ Ответить

2 года назад, # ^ |

I'd tried to know what is 4th test by debug-submits. When I knew it, I'd tried to know what is correct answer for it. It takes about 15 submits.

→ Ответить

slalex

2 года назад, # |

Что за тест №4 в задаче В ?

Большинство на нем падали :(

→ Ответить

2 года назад, # ^ |

n=10^9, правильный ответ 44723 вместо 44722

→ Ответить

Jokser

2 года назад, # ^ |

Надо по-другому решить задачу. Я тоже на нем упал по-началу. Потом применил формулу суммы арифметической прогрессии и сравнивал с abs(x).

→ Ответить

2 года назад, # ^ |

х=abs(x)

Я находил первое число ans, которее сумму s от 1 до ans даст большую либо равную чем х. Потом заметим, что если мы изменим знак любого числа чисел в этом ряду, мы уменьшим нашу сумму s на чётное число (например вместо 1 станет -1, это значит что s уменьшится на 1 и ещё на 1, т.е. на чётное число). Значит если (s-x) - нечётное, мы никак не получим х изменением знаков элементов в ряду. Значит нужно увеличить ans. Так до тех пор, пока (s-x) - нечётное. Т.е. код такой:

	ans=0;
        s=0;
        while (x>s){
                ans++;
                s+=ans;
        }
        while ((s-x)%2==1){
                ans++;
                s+=ans;
        }

→ Ответить

2 года назад, # ^ |

Сори за лишние enter`ы

→ Ответить

2 года назад, # ^ |

У меня подобный код не проходил до тех пор, пока не добавил условие, что (s-x)/2 не должно превышать sum.

→ Ответить

2 года назад, # ^ |

Читать как "не должно превышать s"

→ Ответить

2 года назад, # ^ |

А как может быть при x - положительном (s-x)/2>s ?

→ Ответить

2 года назад, # ^ |

Н-да, затупил я по-черному. Ошибка, очевидно, была не в этом. Сейчас поищу в чем.

→ Ответить

Jokser

2 года назад, # |

Задача 4 решается динамикой по профилю?

→ Ответить

2 года назад, # ^ |

дп по маскам. очень похоже на поиск количества гамильтоновых путей.

→ Ответить

NALP	2 года назад, # ^ \| 0 ну вобщем у меня да. решение динамикой по маске. за O(2^N * N^2) → Ответить

2 года назад, # ^ |

У меня динамика D[mask][last_v], где mask - маска посещённых вершин, last_v - последняя вершина, а D[mask][last_v] - число путей из клетки minimum_bit(mask) в last_v. Переходы - добавляем одну вершину в конец пути (любую v, но всегда v > minimum_bit(mask)).

→ Ответить

Gassa

2 года назад, # |

Ouch! Not being able to read bold text correctly for 40 minutes is something I experienced for the first time.

→ Ответить

Petr	2 года назад, # \| +12 Problem E is very nice :) I've got it accepted 3 minutes too late. The final solution is really short and cute, but it took a long time to get to. → Ответить

Petr	2 года назад, # ^ \| 0 About other problems: I believe problems B and D were too well-known :( → Ответить

meret

2 года назад, # ^ |

I invented B, D and E by myself (the other tasks were Mike's), so I'm surprised to hear B was well-known. As for D, it does look a bit classic, but I've never personally seen it in any contest, and I figured it requires a nice enough idea to deserve a place in the contest :)

→ Ответить

Petr	2 года назад, # ^ \| 0 With the idea being? I'm trying to find previous occurrences of B. → Ответить

meret

2 года назад, # ^ |

Finding all cycles containing a vertex v in O(2^n * n^2), then removing v from the graph and repeating, so that the total number of operations is about is 2^n * n^2 + 2^(n - 1) * n^2 +... = O(2^n * n^2), instead of O(2^n * n^3) achieved by a simple DP approach.

→ Ответить

Petr	2 года назад, # ^ \| +2 Oh yeah, that's a good point indeed. I take my words about D back :) → Ответить

yiuyuho

2 года назад, # ^ |

can you give some insight for how to solve E? Thanks.

→ Ответить

cyph1e

2 года назад, # ^ |

Perhaps many people found A140358.

→ Ответить

2 года назад, # ^ |

Hmm. Conjecture? Interesting... That's why I didn't cope to prove the idea during the contest :)

→ Ответить

RedAnt

2 года назад, # ^ |

Yes ;-)

→ Ответить

meret

2 года назад, # ^ |

I'm surprised it's just a conjencture on OEIS. The proof goes as follows:

Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.

→ Ответить

RosyIsh

2 года назад, # ^ |

Nice Problem indeed.

→ Ответить

pperm

2 года назад, # |

А почему сократили длительность контеста? Ведь было объявлено 2:30 часа, а оказалось 2 часа.
И никакой информации о изменении длительности контеста.

→ Ответить

2 года назад, # ^ |

На мыло было разослано объявление о предстоящем контесте, в нём было сказано также, что время контеста оставят 2 часа.

→ Ответить

pperm

2 года назад, # ^ |

Так как я знал время контеста, то прочитал только заголовок письма и письмо удалил, не получая)

А информация о изменении времени начала и продолжительности, наверное должна быть хотя бы в теме посвященной контесту.

Хотелось хотя бы около 1.5 часов порешать)

→ Ответить

udalov

2 года назад, # ^ |

В письме-оповещении вроде было написано последним предложением.

→ Ответить

2 года назад, # ^ |

Лично мне вчера пришло письмо, в котором оповещалось об 11-ом раунде. Там были такие строки:

"На сайте некоторое время назад было опубликовано, что продолжительность контеста составит 2 часа 30 минут, но после пересмотра заданий соревнования было решено не менять формат и сохранить "стандартную" длительность 2 часа."

→ Ответить

pperm

2 года назад, # ^ |

Интересно когда на сайте 2:30 заменили на 2:00?
Вроде и сегодня еще было 2:30 часа. Хотя может я был не очень внимательным, и просто не ожидал замены)

→ Ответить

sdya

2 года назад, # |

Странно получилось, за 2 секунды до конца отправил решение задачи C, но оно, как выяснилось не отправилось, при этом никаких уведомлений об этом не было. А потом, когда отправил в дорешивании, оказалось, что решение правильное... Обидно, что из-за багов системы не сдаются задачи...

→ Ответить

2 года назад, # ^ |

А сайт упал в последние секунды, насколько я понимаю.

→ Ответить

2 года назад, # ^ |

Может и упал, а может и таймер в браузере отстаёт (часто замечал это). Поэтому когда у тебя ещё оставалось 2 секунды, на самом деле всё могло закончиться секунд 10 назад.

→ Ответить

sdya

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

Я в первые ~5 минут тоже ничего не мог открыть, так же как и сразу после конца. Правда, старт вроде бы сдвинули из-за этих проблем.

→ Ответить

sdya	2 года назад, # ^ \| +1 Я тоже думал, что сдвинули, по крайней мере таймер показывал что остается 15 минут до старта, а потом когда сумел зайти в контест, оказалось, что он уже 5 минут как идет :) → Ответить

2 года назад, # |

В разделе "Рейтинг" результаты 11-го раунда залазят на "Прямой эфир" и т.д.

→ Ответить

2 года назад, # ^ |

Это известный баг, который сов временем будет исправлен.

→ Ответить

2 года назад, # ^ |

А в хроме всё нормально :-D

→ Ответить

2 года назад, # ^ |

Чувствую, скоро Opera меня наконец-то задолбает, и я перейду на Хром :-)

→ Ответить

2 года назад, # ^ |

На самом деле я люблю оперу.. просто там щас у меня много вкладок и я боюсь туда заходить :) поэтому щас пользуюсь хромом... Хром у меня достаточно часто глючит :)

→ Ответить

2 года назад, # ^ |

Сохрани сессию (сохранить сеанс), закрой все окна (не по одному, конечно =) =)) и работай в чистом окне на здоровье. =)

А потом сеанс сможешь восстановить.

→ Ответить

2 года назад, # ^ |

Сто раз так делал... ниразу не восстанавливал... если сохраню - считай что похороню :)

→ Ответить

2 года назад, # ^ |

во-во ))))

→ Ответить

2 года назад, # ^ |

Раз так - забей на вкладки. =)

→ Ответить

2 года назад, # |

На 12-ый раунд зарегестрировано несколько синих. Наверно, это вызвано тем, что регистрация на 12-ый раунд началась до завершения 11-го. :-)

→ Ответить

2 года назад, # ^ |

блин, я тоже хочу в див 2 =)

→ Ответить

2 года назад, # ^ |

И я хочу. И скоро там буду. =) =)

→ Ответить

2 года назад, # ^ |

...если очень повезёт, то попадёшь на мой контест ;-)

→ Ответить

2 года назад, # ^ |

Это который 12й? Или 14й? =)

→ Ответить

2 года назад, # ^ |

как с Майком договоримся ;)

→ Ответить

2 года назад, # ^ |

Ну вот напишу 13й контест, попаду во 2й див и напишу 14й.

Хотя может он 13й и несчастливый и я не попаду во 2й див.

→ Ответить

2 года назад, # ^ |

:-D Прикольно... Повезло людям...

→ Ответить

adamax

2 года назад, # |

Where can I read about problems like D? (Counting cycles, Hamiltonian paths etc)

→ Ответить

2 года назад, # ^ |

Rus: где можно почитать про число гамильтоновых циклов и путей?

→ Ответить

2 года назад, # ^ |

нашел что то отдаленно напоминающее
http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77
и разбор:
http://informatics.mccme.ru/moodle/mod/book/view.php?id=489

а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))

→ Ответить

2 года назад, # ^ |

и все таки не могу найти что почитать на эту тему оО только разве что порешать.

самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)

→ Ответить

2 года назад, # ^ |

хороша идея!)

→ Ответить

2 года назад, # |

I have problem in my head or codeforce has problem in its head....

my contest code of B got WA in test 4 using scanf and printf

but in practice same code got AC using cin and cout?

is there any explanation anyone can give?

here is my WA in test 4 code

http://pastebin.com/cbBH5nzz

if u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<<i<<endl; it gets AC ...

→ Ответить

2 года назад, # ^ |

As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!

Or you can just make all variable int (it's enough) and use %d.

I tested it just now.

→ Ответить

2 года назад, # ^ |

I'm wrong. (c)

From 2005 version VS supports both %I64d and %lld.

→ Ответить

KADR	2 года назад, # ^ \| 0 Try to replace scanf("%lld",&num) with scanf("%I64d",&num) and printf("%lld\n",i) with printf("%I64d\n",i). → Ответить

KADR	2 года назад, # ^ \| 0 Beaten :) → Ответить

2 года назад, # ^ |

I submited my code in GNU C++,,GNU supports long long ,right?

→ Ответить

2 года назад, # ^ |

As you see, no.

→ Ответить

2 года назад, # ^ |

then its a shame to me...I have been coding knowing that GNU C++ supports long long ...I haven't faced any problem except this.even in my windows pc GNU C++ compiler(CodeBlocks) supports long long well....If codeforce's GNU C++ doesn't support long long ,,then I have nothing to say. :)

→ Ответить

SkidanovAlex

2 года назад, # ^ |

Codeforces uses MinGW, which DOES support long long, but DOES NOT support %lld. %I64d should be used instead. Or you can simply submit using MSVC compiler, in most cases it will be fine.

→ Ответить

2 года назад, # ^ |

Thanx. this thing really pissed me off in the contest time. I should have known it earlier.

→ Ответить

2 года назад, # ^ |

But you wouldn't forget it in future. =)

→ Ответить

muntasir

2 года назад, # ^ |

AFAIK, gcc actually uses the OS's C library to make the call to printf. That's why on Windows the format for long long is %I64d because the Windows C library uses that format, even though the compiler is gcc.

→ Ответить

2 года назад, # ^ |

If anyone wants to see my both code but cant see from the provided link..I will paste it here.

→ Ответить

2 года назад, # ^ |

Btw 2008 VS works with %lld. So don't be uncertain.

→ Ответить

2 года назад, # ^ |

yah,,

→ Ответить

2 года назад, # |

+11

Do all hadn't a respond from the site at the start of a contest?

→ Ответить

adamax

2 года назад, # ^ |

I couldn't open any page for about 5 minutes, but judging by the standings page, many people submitted A at 0:03-0:04...

→ Ответить

2 года назад, # ^ |

It's strange.

→ Ответить

yiuyuho

2 года назад, # ^ |

Same problem here. But I guess that doesn't really make a big difference.

→ Ответить

rem

2 года назад, # ^ |

I think it does make a big difference. If you lost 5 minutes in the beginning and solved N problems then you'll get 5*N extra penalty time.

If I could access the site immediately from the beginning I'd be 1 or 2 positions higher in the ranklist, and will probably be red today.

→ Ответить

MikeMirzayanov

2 года назад, # |

Thank you, Jakub, for interesting problems. It is an essential aid for Codeforces. I'm very glad to work with you.

→ Ответить

itomatik

2 года назад, # |

Does anyone knows why I'm getting "Denial of judgement" ? :)

→ Ответить

Jami_CSEDU

2 года назад, # |

Does anybody want to share the solution of problem D and E?

→ Ответить

2 года назад, # |

задача С это простая задача которую нужно было решить теоремой Пика?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

Не смотря на то, что там квадраты? :)

→ Ответить

2 года назад, # ^ |

точно еще и квадраты:)

→ Ответить

2 года назад, # ^ |

Я делал так:

Идём сверху вниз, слева направо. Если встречаем 1, то это либо левый верхний угол квадрата, либо верхний угол "прямоугольного ромба", либо баг. Проверяем первый случай - пока 1 идём вправо, таким образом выявим длину стороны квадрата. Если получили длину 1 - значит это либо квадрат со стороной 1, который нам не подходит, либо прямоугольный ромб. Если нет, то проверяем, чтобы это был квадрат, у которого вне него есть минимальный квадрат из нулей и внутни него максимальный квадрат из нулей. Т.к. при известной длине стороны и левого верхнего угла у нас квадрат фиксирован, мы проверяем тупо фором, без появления двоякх ситуаций. В случае с повёрнутым квадратом мы тоже проверяем его стороны... это как и с квадратом сделать достаточно легко. Потом чтоб не париться, проверяя смежные клетки, я просто для всех точек этого квадрата смотрю сколько у этой точки соседних точек. По восьмисвязности у каждой точки должно быть ровно 2 смежные 1-цы. В итоге этого алгоритма я получаю квадрат и увеличиваю ответ на 1, или не получаю квадрата. В любом случае я запускаю восьмисвязную рекурсию от этой точки, таким образом удаляя этот квадрат, или этот баг - мне и то и то нужно удалить.

→ Ответить

Egor	2 года назад, # ^ \| 0 Не всегда ровно 2. У обычных квадратов точка, примыкающая к вершине имеет 3 соседки, а если сторона квадрата 3 - то 4 → Ответить

2 года назад, # ^ |

Я же написал, что это для повёрнутых квадратов. Для обычных тупо фором смотрим наибольший квадрат из нулей внутри и наименьший квадрат вне. Также можно было сделать и в случае перевёрнутого.. но там много гемора и я не стал так делать.

→ Ответить

Egor	2 года назад, # ^ \| 0 Ясно. У меня просто все решение основано на количестве соседей → Ответить

SkidanovAlex

2 года назад, # ^ |

Или, или, можно сделать так: для каждой точки считаем, сколько единиц слева от нее, сколько справо, сколько по диагонали главной и сколько по побочной
Также для нулей.
Теперь проверить, что у нас квадрат легко - просто сравниваем количество единиц. Проверить, что он не касается ничего тоже не сложно - проверяем, что вдоль наших сторон количество нулей достаточное.
Кодяки правда надо атата скока :о(

→ Ответить

NALP

2 года назад, # ^ |

DFS-ом выделяем компоненты. считаем по ним Xmin, Xmax, Ymin, Ymax. теперь по ним просто тупо строим квадраты, какими они должны быть и тупо сравниваем множества (выделенную компоненту и квадрат). для быстроты введены всякие хаки вида (Xmax - Xmin == Ymax - Ymin), проверки на то, что размеры выделенной компоненты 4(d-1) - вертикальный квадрат или 2(2d-1) - наклоненный квадрат, где d - высота квадрата, т.е. d = Xmax - Xmin + 1 = Ymax - Ymin + 1, и числовой юзед =) мне представляется это самым простым и коротким способом, да еще тут набажить негде =)

→ Ответить

2 года назад, # ^ |

Я закодил этот алгоритм вообще без ошибок компиляции и сдал с первой попытки, для меня это редкость :)

→ Ответить

2 года назад, # ^ |

Этот - это мой

http://codeforces.ru/blog/entry/331#comment-4127

→ Ответить

ardmn

2 года назад, # |

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

→ Ответить

2 года назад, # ^ |

это в статусе по контесту или по нажатию на что то вроде

x465 напротив задачи. а там уже нажимаем на номер понравившегося решения.

→ Ответить

ardmn

2 года назад, # ^ |

Спасибо)

→ Ответить

2 года назад, # ^ |

Но так можно посмотреть только последние сдачи.. а как увидеть другие сдачи? Решения самых лучших как раз и не видно

→ Ответить

LoKi	2 года назад, # ^ \| 0 Попробуйте отсортировать по разным параметрам. Например, по времени сдачи — обычно самые лучшие и сдают раньше. Хотя это, конечно, хак. Должна быть возможность хотя бы перелистывать страницы и фильтровать по языку. → Ответить

2 года назад, # ^ |

Это даже не хак.. потому что сорт происходит тех данных, которые уже расположены на странице и более ранние посылки всё равно не подгружаются.

→ Ответить

LoKi	2 года назад, # ^ \| 0 Нет, это не так. Сортируются все данные. Попробуйте ещё раз. → Ответить

2 года назад, # ^ |

Новые видимо появляются так: происходит сорт со всеми и выбираются последние или первые "несколько" (в зависимости от критерия). Поэтому т.к. Petr пишет быстро и на яве это обеспечивает ему шифрабильность на простых задачах :) Кстати у меня всё же нет возможности увидеть самых быстрых кодеров, потому что сорт по времени сдачи происходит и дальше выбираются последние, т.е. первых я в этом списке не увижу.

→ Ответить

LoKi	2 года назад, # ^ \| +1 Изначально сортируются по убыванию, да. Но можно вручную подправить параметр и получить сортировку по возрастанию: http://codeforces.com/contest/11/status/A?order=BY_ARRIVED_ASC → Ответить

2 года назад, # ^ |

Здорово! Спасибо! Что-то я сам не придумал как его подправить...

→ Ответить

2 года назад, # ^ |

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

→ Ответить

LoKi

2 года назад, # |

Thanks for the problems, but I'd like to pay attention to some inaccuracies in them.

1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1, 1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go either back or forth with each jump."

2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.

3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square?

4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?

Thanks.

→ Ответить

vdmedragon

2 года назад, # ^ |

I think the authors should explain the examples for all the problems in the contest.

For example: the authors should explain why the result is 1 for the 1st test case, 2 for the 2nd test case... for the problem C.

→ Ответить

LoKi

2 года назад, # ^ |

Look, there are 3 squares in the first example, but two of them (2x2 in the left bottom corner and big square of type 2) are "touching" each other, so they don't count. There is also a single "1" in the top right corner, but "A square should be at least 2×2". So only one remains - the 2x2 square of type 1, which is located in the bottom right corner of the matrix.

As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.

But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.

→ Ответить

LoKi

2 года назад, # ^ |

As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.

But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.

→ Ответить

LoKi	2 года назад, # ^ \| 0 Sorry for duplicate comment. It is a bug of the site. → Ответить

2 года назад, # ^ |

You mean explain withit problem statement?

If yes, I'll agree with you.

→ Ответить

vdmedragon

2 года назад, # ^ |

yes, this is exact what i want. Hope the problem setter will do it next contest.

→ Ответить

adamax

2 года назад, # |

В дополнение к предыдущему комментарию скажу, что перевод на русский был не очень, в смысле, с ошибками.

→ Ответить

LoKi	2 года назад, # ^ \| +3 Я уже жаловался автору на просторечное «заместо» в задаче Е, но ничего исправлено не было :( → Ответить

satoshii

2 года назад, # |

Did anyone solve problem B using DP solution?

I want to do but I can't...

I hope someone show me the code.

Thanks.

→ Ответить