Доброго всем времени суток!
Приглашаю Вас поучаствовать в 194 раунде, автором которого я являюсь. Это мой четвёртый раунд, хотя предыдущие три были очень давно: Codeforces Beta Round 79 (Div. 1 Only), Codeforces Beta Round 94 (Div. 1 Only), Codeforces Round 110 (Div. 1) (прошу прощения у div-2 участников, что упоминаю только div-1 раунды, просто ссылка даже на один раунд уже чересчур громоздка).
В этот раз, как в раунде Codeforces Beta Round 79 (Div. 1 Only), вы вновь поможете мальчику Геральду разобраться с его проблемами. На этот раз его проблемы настолько серьёзны, что он стал координатором контестов на Codeforces и помог мне сделать этот раунд, чтобы спихнуть их на вас.
Хочу поблагодарить Gerald за то, что он очень хорошо выполняет работу координатора. Работая с ним, ощущаешь, что всё действительно под контролем. Кроме того, спасибо Марии Беловой за перевод условий на английский. Также спасибо Seyaua и Aksenov239 за тестирование задач.
Этот раунд состоится в необычное время — 12:30 по Московскому времени.
Разбалловка стандартная, 500 — 1000 — 1500 — 2000 — 2500.
Всем спасибо за участие, добро пожаловать в разбор.
Мои поздравления победителям:
Дивизион 1:
1. KADR
2. RAVEman
3. PavelKunyavskiy
4. Dmitry_Egorov
5. RAD
6. sy2006
7. mmaxio
8. riadwaw
9. niyaznigmatul
10. RomaWhite
Отдельно хочу отметить сразу двух украинских участников, которым единственным покорились все пять задач!
Дивизион 2:
1. IMOiguanas
2. savsmail
3. suyash666
4. AntiForest
5. kang205
6. jschnei
7. littlepanda
8. langdamao
9. 9mmlitswe
10. Renkai
Следуя многочисленным просьбам к авторам раундов, расскажу немного о себе. Меня зовут Валера Самойлов и мне 24 года. Gerald не смог сходу вспомнить более старшего автора Codeforces раунда =) Я закончил мат-мех СПбГУ пару лет назад (тем, кому это о чём-то скажет, ПОМИ-группа + кафедра алгебры, диплом по теории графов). Сейчас я работаю в области химической укладки графов и вместе с женой воспитываю годовалую дочку. Кроме того, последние 8 лет я учу детей математике (а в последний год ещё и программированию) в ЮМШ (Юношеской Математической Школе, это в Питере), которую я и закончил в своё время. Всё это объясняет, почему я так долго не делал раундов, хотя задач у меня придумано предостаточно. Тем не менее, летом, пока жена с дочкой на отдыхе, а учить некого, я улучил на это время и надеюсь, что вам не покажется, что я провёл его зря.
а что такое химимческая укладка графов?
Дана молекула, сложная. Её надо нарисовать на плоскости так, чтобы химикам было приятно и удобно её разглядывать.
One of the best announcement posts in CF :)
No,this announcement forgot to:
1)Indicate that the round will be at unusual time
2)Thank MikeMirzayanov for the system
lol :)
There were probably enough "thanks for the system" after last round for quite some time forward
thanks for alerting us for the unusual time.
I wasn't aware of this
Glad to see someone coming back and help setting problems in codeforces. Shows the interest people have for the field :)
Стоит упомянуть в анонсе совсем необычное время раунда.
Не плохо было бы открыть регистрацию на несколько часов раньше.
upd. Открыли на 5 часов раньше чем предполагалось :)
Неплохо было бы ограничить регистрацию ибо тормозит.
Будет как-то не честно, ведь есть пользователи которые регистрируются и не участвуют. А тормозит в основном из-за тестов.
Это ж как веб-фронтенд из-за тестов может тормозить? Надо не ограничивать регистрацию, а оптимизировать (или scale'ить) систему.
То-то тестирование первые 30 минут вчера шло с очередью на 23 страницы. Как же этот веб-фронтенд такое допустил?
ОК, это тоже проблема. Но ИМХО, когда тормозит веб-фронтенд, не открываются страницы и не сабмитятся челленджи — это на порядок хуже.
Hope for a round with clear and easy-understanding problems' statement~
Best ratings to all participants~
and "easy" english, so i don't have to open google translator :)
wow !!! this contest time will be very comfortable for me and I hope for other. if contest time will be at 19:30 i didn't attend. I hope a lot of participant attend in this contest.Thanks codeforces !!!
Good Luck & Have Fun !!!
Unusual time.Good luck to every one.
Have Fun — Every One!
Good Luck — Motherfuck!
"This time his problems are so serious that he became coordinator of contests on the Codeforces, to be able to throw his problems to you."
I liked this :D
Wow! Great memories from your last contest(#110)! Hope this one to be even better :) Thanks for setting problems again.
I hope your daughter and wife go on vacations more often,so CF users get to read more such awesome announcement posts.
Qiu Qing Nve!!
what will the scores for each problem? thx.
is codeforces slow with me only or with all?
Well, i'm fine.
I don't understand problem A and B T_T
fucked up english!
took 30mins (asking questions) to finally understand #B
Problem statements are easy to read, but difficult to understand...
I can't understand Problem C
For Problem B,what are the 3 points for the first example?
x1=0,x2=1,x3=2 y1=0,y2=1,y3=2
In problem D,What does "He moves each chip from its original edge to the opposite edge" mean? It means the point can only move in one derection?
more formally:
if chip starts at (1,k) it should end on (n,k) and vise versa
if chip starts at (k,1) it should end on (k,n) and vise versa
Also I think it means that it goes directly to its destination point. Otherwise the last given example would have a greater answer.
yes,number of minutes=n-1
Number of minutes doesn't seem to enforce anything in this case, because there is no requirement to reach destination during this period. The only requirement is not to fail.
what does problem C mean???
can't understand either...
I couldn't understand whether we should minimize or maximize something and what exactly is this something.
after 3 times of "wa in test 3",i guess it correctly....
что мне пишет что я не зарегистрирован,что за бред...я решение не мог отправить из-за этого
Было бы не плохо, если бы вы Print Screan сделали.
без регистрации я мог бы просматривать задачи или нет,потому что при отправке решения,мне система пишет,что для отправки необходимо зарегится на соревн.
Задачи видят все, не только те, кто зарегистрирован на соревнование
Неужели все быстрые кубы в D посдавали? Или у меня опять помутнение рассудка сегодня?
n^2log 1e9 у меня
Как?
Сперва бинпоиск, внутри все тупо, просто надо понять, что там квадрат суммарно.
Код
Да, совсем я отупел. Это же очевидно
Ну и жаль, что С так мало стоила
бинпоиск дает нам матричку из 0 и 1 где надо найти 4 единички в вершинах прямоугольника. Тогда будем добавлять по строчке. Если наше множество единичек пересеклось с множеством какой-то предыдущей строки больше чем в одной единичке, то у нас есть прямоугольник. А иначе сумма количеств единичек в столбиках, в которых у нас единички <= n по принципу дирихле.
Перебираем клетки начиная с большей, храним для каких пар столбцов уже есть строчка, в которой оба значения уже обработаны (т.е. они достаточно большие). Как только какая-то пара повторилась, это означает, что мы нашли прямоугольник.
Квадрат с бинпоиском
Нет, у меня
А как за такую сложность сделать? У меня еще все домножается на m/30
Взять все числа из таблицы, сделать бинпоиск по ответу. Теперь надо узнать, есть ли прямоугольник такой, что в углах числа ≥ const. Ну например сделать так, если есть пара строк, такая что в обеих есть пара столбцов, в которых числа ≥ const, то существует. Пар столбцов m2. Берем все строки, в каждой строке перебираем пару хороших столбцов в этой строке, если такая пара уже встречалась в какой-то предыдущей строке, то мы нашли ответ.
Вообще, имхо, почти все кубы должны слететь на тестах из одних 0 и 1, с ответом 0, но числом единичек большим чем линейным. Я умею делать n*log(n) (жаль, что багу в генераторе нашел слишком поздно, так бы еще поломал скорее всего), но думаю, что можно и O(n^2) — основная идея напихать в строчку как можно 1 так, чтобы все расстояние между ними были различными, а потом прокрутить ее n раз.
А можно пример такого теста?
Вот генератор на n*log(n). http://pastebin.com/S0uZRaq0
В D куб должен заходить?
у меня взломали
Мой вообще по WA взломали. Надо багу искать. А так в запуске на тесте 1000*1000 работало ~ 1.5 с.
Ну, кубы очень разные бывают
У меня не зашло даже на C с ускоренной итерацией указателями.
А у меня зашел куб на логарифм.
Там еще вроде как 1/32 есть. Так что это примерно как просто куб.
Ну да, делить на 32. Но асимптотически это куб на логарифм, все-таки.
I wonder what does Problem C want??? Please explain test 2 in detail...
As we have to maximize the number of coins. Ans is 2 from case 2.
Какая разница, сколько и каких проверяющих серверов, если, как обычно, за несколько минут до конца на десятки секунд притормаживает всё остальное... :(
At problem A: It says: Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible.
But for 13 the answer seems to be 5 ( 3 + 3 + 3 + 3 +3) when 15 can and must be obtained from the above statement from 9 + 3 + 3
"Among all combinations choose the maximum of the minimum number of coins."
I can't understand what you want to say.
One day an unlucky buyer came. He did not have the desired sum without change
Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible. What is the maximum number of coins he could get?
And then they explain it again: We consider all the possible combinations of coins for which the buyer can not give Gerald the sum of n marks without change. For each such combination calculate the minimum number of coins that can bring the buyer at least n marks. Among all combinations choose the maximum of the minimum number of coins. This is the number we want.
I know that you russians are the best at programming but please learn english
Another confusion, for me, at problem A is for the second example: if the buyer had a coin of 9 marks, why would not he pay it? The answer in this case is one.
Because we are considering all cases where the buyer cannot pay the right amount, and choosing the one where the minimum number of coins payed by the buyer is the largest.
In this case that occurs, for example, for a buyer with coins 3 3.
If the unlucky buyer doesn't have any 9-coin (in particular, he only has 3-coins), he needs to pay with only 3-coins.
It says that "Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible". Therefore the buyer should have such coins in order to minimize the number of coins he gives away and it is better for him to have only a 9 marks coin.
this two are different combinations. As the buyer MIGHT bring 5 coins of value 3, the buyer MIGHT need to use 5 coins even if he want to minimize the coin usage.
I was thinking about the same: Why not just give 3^x, where x is a large number, then the answer will always be 1.
But you have to find the maximum out of all combinations.
9 + 3 + 3 is a valid combination, 3 + 3 + 3 + 3 + 3 too, but it is also the maximum one.
What if we consider the sum 3^0 + 3^1 + 3^2 + ... + 3^k? There is only one possibility to pay it, with k+1 conis.
9+3+3 is possible assuming the customer has a 9-mark coin.... 3+3+3+3+3 is when the customer has only 3-mark coins (possibly he may have 1-mark coins also) that's why 15 is the correct answer
For each such combination calculate the minimum number of coins that can bring the buyer at least n marks.
In this sentence, it seems that "number of coins" means "change".
A bitset round!! My solution to both D and E used bitset to optimize brute force algorithm.
Yes, I tried using bitset for E and some randomized algorithm, but the constants were too large so that I kept getting TLE until contest ends :(
Спасибо за классный раунд)
В Е существует решение, которое работает быстрее, чем за O(n*n*(n/64)*log(n*n))?
У меня, например, без логарифма.
как ты избавляешься от бинпоиска?
Сначала сортирую длины между парами вершин и добавляю по одной пока не получиться треугольник.
Надо просто отсортировать ребра и перебирать их в порядке уменьшения длины, а дальше битмасками за n/32 проверять. Я послал именно это.
Да просто перебирать пары вершин тоже катит)
Только не на Java. Чудесно сбалансированные тайм лимиты
Объясните пожалуйста, что и как проверяется битмасками?
Добавляем ребро (a, b).
Проверяется, есть ли такое
c, чтоaсоединено сcиbсоединено сc. Соседи каждой вершины — битсетыЯ эту задачу не сдал. Но мне кажется что решение такое. Бинпоиском подберем ответ. Переберем одну из вершин ответа. Выкинем все достаточно близкие вершины. В оставшемся множестве найдем две наиболее отдаленные друг от друга точки(O(nlogn)) и проверим что они нам подходят. Решение O(n*log(n)*n*log(n))
Я тоже думал над таким решением, но мне кажется, что на практике оно получиться более медленным, чем n^3 / 64.
Если отсортировать все точки в начале, то получим решение за O(N2·log(N)). Я как раз такое сдал. Но его все же обогнали оптимизированные решения за куб с битсетами.
Я сорчу все ребра, дальше по ним бин поиск
Затем между всеми помечаю в бит масках только те ребра, которые больше рассматриваемого, после чего перебираю все пары вершин, между которыми ребро больше либо равно просматриваемого, и для них за n/64 проверяю, есть ли хоть одно подходящее
Моё решение работает за
. Если кратко, идея в том, чтобы перебрать точку и отсортировать относительно неё остальные по углу, а потом для каждой проверить за 
, можно ли с ней вплотную два круга нарисовать, чтобы нашлась ещё третья точка на необходимом расстоянии.
Please codeforces, i beg u for proper english...took me 1 hr to understand Prob c div 2
Although the question were pretty wonderful...But native english speakers face a lot of problem understanding the problem statements...
Thank you Sammarize for preparing this wonderful round and good problems. After Codeforces Round #193 I became disappointed but now I'm happy to participate in this round.
Учитывая количество пройденных претестов, в Div1 D действительно существует какое-то простое решение? У меня сложилось впечатление, что претесты слабые в ней: лажа, которая дает неправильный ответ на тесте
претесты проходит. UPD. Вопрос снят. Претесты в D и E действительно слабее остальных:
Контесты действительно становятся все сложнее и сложнее? Два года назад обычно решал две задачи, иногда одну, иногда три. Сейчас знаю намного больше, а решить вообще ничего не могу. При этом на других соревнованиях — GCJ, RCC — вроде бы на таком же уровне выступаю.
А мне наоборот кажется =) Раньше вечно то геометрия с точностью в А-В попадется, то еще что-то невпихуемое без монтировки...
Сейчас понял, что задачу A вообще неправильно распарсил. Ну хватит уже делать "найдите минимум из максимумов минимумов максимов", правда. Stack overflow при прочтении же.
Да, я тоже потратил много времени чтобы понять условие.
А у меня почему-то стойкое ощущение, что уровень участников постоянно падает. Хоть это и абсурдно, и, скорее всего, неправда. Но "не тупить и сдавать шару" когда-то означало не такие высокие места, как сейчас. К примеру, в прошлом матче 3 простые задачи за разумное время — место около топ-20, в этом — около топ-25.
Может быть, у меня просто взгляды на "шару" меняются со временем.
Из-за новых регистраций возникает инфляция рейтинга. Поэтому, R=1700 два года назад это не то же самое, что R=1700 сегодня.
Даже не об этом речь.
Год назад я смотрел на то, что надо решить на место, скажем, в топ-50, и у меня были мысли "омг, какие-то мегасложные структуры данных, какие-то мегасложные непридумываемые задачки, да они еще и решают это так быстро". Теперь же я смотрю и вижу что-то вроде "ну это я сдал, это сдал, это не сдал, но ведь тоже халява... да и что в ней писать целый час?..".
При этом рейтинг у меня особо в плюс не убежал за это время, так что с учетом предполагаемой инфляции — вообще бред. Я вроде как в уровне упал, но при этом задачи мне кажутся проще.
trappy Div2 B…
@ Codeforces team:
Please, hire a proofreader with excellent English. TopCoder has misof that always checks all problem statements very carefully, word-by-word. Therefore we almost never have confusion in SRM statements.
Sincerely,
Contestant who took much longer time to understand problem A and B than to actually write the solutions
In my opinion, it is better to have someone whose native language is English but knows Russian, not the other way around. It usually works better.
I can't agree more. In Codeforces Round 192 (Div. 1), I was really confused about problem A. And in this contest div.1 (Codeforces Round 194 (Div. 1)), problem A and B both have a poor expression in English.
Вы серьезно не хотели n^3 / 32 в Е? А то очень странно, что мое не проходит, вроде везде очень простые операции
Нет, мы хотели n^2logn. Но, к сожалению, я не придумал n^3/32. Если бы придумал, то или сложность была бы другая, или ограничения.
Самое неприятное что в итоге это решение проходит на С++, но не проходит на Java...
Егор, я посмотрел твой код, и... у нас разные n^3/32. Ты ищешь что-то вроде ориентированного цикла по сути, вместо неориентированного. Итого в самом вложенном месте у тебя две битовые операции, вместо одной. Ну избавления от лишней вложенной индексация наверняка немного поможет. В любом случае, n^3/32 на C++ не просто заходит, а залетает — у меня 1934мс при TL 9с. Ну не верю я, что Java 7 настолько медленнее, честно.
P.s. У mmaxio на Java 7 куб/32 зашел за те же 2с.
Я в дорешку заслал такой же куб, как у тебя — все равно tl. Возможно, я слишком высокого мнения о Java оптимизаторе, но мне казалось, что таки вынести обращение к массиву в переменную в месте, где в массивы не пишут — он умеет
Ок, оказалось, что дело в сортировке 4 500 000 чисел, тормозила именно она
Она всегда медленная, или там был какой-то антиквиксорт тест?
Нет, просто слишком много виртуальных вызовов, это я поправлю сам
Fast system testing! Thank you.
Why can't I upload a data input file which larger than 256kb? Today I have lots of chances to HACK!!!! My data is not large enough to stop many solution which not pass the system test!
You should use the test generator
I'll try next time.
nice contest :)
yongheng5871 and sspa write the same code for problem D and E.
D: 4179664 and 4179733
E: 4184415 and 4185562
the same solutions by error202 and Williamacm (problems A, B, D, E):
4176567 4181629 4179729 4184648
4176503 4184451 4179783 4186312
I found they are all from the same city.
And their codes of C are the same too. sspa's code of A is the same as error202 and Williamacm's.
@CF_team, What's your treatment to cheating?
Fun Div 2 contest, but I really wish B's statement hadn't referred to the missing central point as "the average" (and used a test case in which it was) when it wasn't required to be.
Totally agree with you, I was confused the whole time about whether the middle point shouldn't be included or the "average of the 9 points" shouldn't be included, which could be two completely different things
Awesome contest ! But in Div 2 problem B You should have stated that points can be repeated or at least include it in pretests.
despite getting a wrong answer due to this, i don't agree with you, especially because they had mentioned "You do not have any other conditions for these points." in the problem statement. to all coders who failed B because of this, hopefully this will teach us to take NOTHING for granted in future, and read the constraints properly!!
My submission for D (4187066) gives WA on pretest 1, answer 1, but locally it gives 0, what could be the problem?
In function possible, add "return false;".
Number of people who passed each problem: C:14, D:135, E:33.
I guess it will be better if we use dynamic scores.
If the statement on A div 2 says that "You need to print n lines, on the i-th line print n integers", then, why people can print (n*n)/2 lines with only 2 integers each. I tried to hack this solution following the statement but he was right. Why? Thanks in advance.
all whitespaces are considered equivalent...don't know why, but that's the way it is.
also, before you attempt to hack a solution, just below the "Hack" button it says "be careful, whitespaces will not be considered" or something like that just to alert you to this possibility!! so from next time, read properly before hacking!
I guess the checker thinks any kind of whitespace (space, newline, etc) as a single separator. In particular, you can replace any space with newlines, and any number of them is considered a single whitespace. Yes, you can even output everything in a single line, with spaces separating them. If the checker uses scanf in C++ or similar, this makes sense; scanf considers any stretch of whitespaces as a single space/newline.
EDIT: Sniped qq
Problem B div2 was really tricky! It seemed to be really easy(and it was), but a lot of people got hacked or wrong answer after system testing because of weak pretests.
Please explain why the answer for div2D 'pretest 6' is 4? Test case :
0 0 1 1 0
1 0 0 0 0
0 # 0 0 0
0 0 0 0 1
0 0 0 0 0
1-chip, 0 — free cell, #- blocked sell
Oh right! Thanks. I kept thinking that according to rules we should only place on one side of the row, which was wrong. :(
One solution is 2,1 1,3 1,4 4,5
(1,4) (2,1) (4,5) (5,3)
Gerald will put the chips in cells (1,3) (1,4) (2,1) and (4,5).
you can put your chips on this cells to get 4 points (2 1) (1 3) (1 4) (4 5)
Ааа я желтый ураураура
Отныне всегда актуально, я так думаю...
Ну так да, но сам факт того, что я хоть чуть-чуть желтый радует :)
Changed cin to scanf in problem D and got accepted :(
You may be interested
Some questions are hard to explain with pure words. It's better to attach simple graphs explaining the ideas. Also, give one "meaningful" example with a detailed explanation on how to arrive the output would be very helpful too. I suppose it doesn't take a lot of work from the problem writers.
Is the intended solution for D1-D is O(N^3 lg max{a}) + bitmask for speedup?
Editorial says only about O(n^2 log max) solution
why does codeforce run test cases after the contest?
that results in wrong answer even if pretests passes
1 for faster test during the contest 2 to give chance for participants to hack solutions
During the contest your solution is tested on a number of tests called "pretests". If your solution passed those tests it does not mean that it is correct. Therefore it has to pass the entire set of tests so that it may get accepted.
A question about D,if we sort number in order,insert them from big to small,and use brute force to check.It can pass system test.But what is the upper bound of numbers inserted?I can construct a test case that should use O(nlogn) numbers.
11010001
01101000
00110100
00011010
00001101
00000110
00000011
00000001
Почему в Д неправильно перебирать пару строк, а потом идти и искать за линию второй максимум? Почему это падает? :(
Это правильно и даже проходит по времени, если грамотно сделать отсечения, и не забыть про ещё одну хитрость.
27 тест имеет такую структуру: нарисована табличка в которой числа расставлены произвольно, но с условием, что любое число на строке i меньше любого числа на строке i+1 (для любого i). И потом взяли один произвольный столбец и одну произвольную строку и все числа в этом столбце заменили на одно и тоже число mx, которое больше всех остальных чисел в таблице.
Этот тест, кстати, специально для того, чтобы TLлились решения наподобие Вашего, если в нет той самой хитрости ;)
Так а что за хитрость-то?
Надо перемешать строки =) Иначе, если всё написано так, как сказал Rubanenko, работать будет за O(n3).
(N^3)/2 на кф не зайдет в три секунды при N=1000? Вы смеетесь?:)
У Вас же там не 500 000 000 операций. Это только количество проверок при заходе во внутренний цикл. Ну, посмотрим.
4188472 без перемешивания зашло
А почему такое решение так быстро работает? У меня почти идентичное, но ТЛится.
А у него, между прочим, 2652 мс, так что писать надо аккуратно.
Я не просто так спросил, я потестил его решение пару раз. Результаты разные, но вот, например, вообще около секунды. А у меня код очень очень похож, но никак не пихается. И я что-то совсем не вкуриваю почему.
UPD. Но то, что время так скачет — это, конечно, жесть. Полторы секунды разницы у одного и того же кода.
Не пихается из-за того, что минимум вычисляется до проверки. Сделаете наоборот : две проверки, потом уже считаем минимум , и зайдёт.
У меня в третьем цикле по большей части производится лишь одно сравнение, так как ответ обновляется далеко не на каждом шагу. У тебя же сразу ищется минимум, а потом еще сравнения.
============================== Надо же, зашла, спасибо. Неужели присваивание и пара сравнений настолько увеличивает константу?
Ну при выполнении 5*10^8 раз двух сравнений или допустим 4 сравнений константа вроде как почти в два раза вырастает
Так там не ТЛ, а ВА. Вообще, для моего решения это ничего не меняет, ибо у меня отсечений нету, и, на мой взгляд, при таких ограничениях тестирующей системе они не нужныю
Да, я понял, что WA, я специально описал тест, чтобы Вам было проще найти ошибку.
Вроде у тебя тебя на паскале тоже самое, что у меня на плюсах, но я свое никак не могу упихать дальше десятого теста. Объясните кто-нибудь, пожалуйста, что за фигня?
А зачем все хранить в линейном массиве? У тебя же умножений куча ненужных.
Да вроде так всегда быстрее работало, чем в двумерном. Сейчас попробую без умножений.
UPD. Не пашет
http://mirror.codeforces.com/contest/333/submission/4188307
Исправлено
else mx:=max(mx,x);и все числа integer, а не longint потому, что так ТЛ.Если в делфи ещё и директивы R и Q выключить, то вообще за 2,1 проходит http://mirror.codeforces.com/contest/333/submission/4189027
Может я туплю, но скажите, как в задаче 334A - Пакетики с конфетами проходят вот такие решения:
Если сказано что надо вывыести n строк, а тут выводится n^2/2
Просто чекеры принято использовать нестрогие(забивающие на whitespace'ы)
Т.е. всегда можно выводить все в одну строчку или каждое число на отдельной стороке вне зависимости от того, как сказано в задаче и не бояться, что это будет неправильно воспринято? Или лучше все таки придерживаться условия?
По наитию. Если чекер нестандартный, то там не ясно что. Если возможно использовать стандартный, то скорее всего он используется и скорее всего безопасно так делать. В любом случае, вам почти всегда скажут, что на первом тесте упало, если что-то не так.
Один раз уже было, когда такое давало преимущество.
Спасибо, буду в курсе
We can solve E in O(n^2 log n) in such a way (my solution wasn't accepted, I think that it is some bug in my code rather than in and idea). Firstly sort the points from left to right and let's do the binary search on result. For each point P we throw away points which lies closer to P than our actual value from binary search and we have to check if there are a pair of points that distance between them is at least that actual value. But we can find the furthest pair of points among them, there is a well-known algorithm for that problem, which runs in O(n) (recall that we sorted points from left to right at the beginning, so we have O(n) time instead of O(n log n)), so we are done.
I've got AC with the same idea. However, there are many O(N3) solutions optimized with bitsets which work much faster than this O(N2·logN) one.
A funny solution about E. 4187525
KADR — ZADR!
I think you guys should seriously start improving the english translation of the problems. I find it unfair that some people can read the grammatically correct version of the problem in Russian while others have to read it in a translation that sometimes is far from perfect. Just a suggestion
I got TLE at problem 333D - Characteristics of Rectangles in contest with 4185508, but I've resubmit the same code three times and got accept in 4188799, 4188820 and 4188829 for just 2214ms. I didn't use any random algorithm in the code, would it possible the new judging machine lead to the unstable result?
This is the one of the few contests where code reuse may be helpful :))
"Отдельно отмечу отметить" — что-то тут не так
Спасибо.
А почему рейтинг перепосчитали? У меня было 1594 после контеста, а теперь стало 1595.
Обычно после контеста обнаруживаются нарушения, совершёные некоторыми участниками, их верные, но нечестные попытки игнорируются и они опускаются вниз. А Вы поднимаетесь чуть-чуть наверх. Соответственно, Ваш рейтинг тоже.
I think 333E - Summer Earnings is not a good problem for 2500 point -- it's more like a 1500-point problem! I'd like to know the solution of author, because so many people use std::bitset to solve it and they get AC.
Well, you can read the editoral.
Oh, O(n^2*log(n)) is more reasonable... Maybe you should set the time limit to 5 sec...?
a O(n^2*log(n))-complexity problem is really embarrassed and hard to find data to TLE the O(n^3) or O(n^2*log(n)*log(n)) algorithm.
I didn't take part in the contest, but was interested in language problems people reported. So I started to read A (fushar got +41 and +52 claiming that A and B were hard to understand due to poor English statements). I think I understand the description, although it would be hard to understand even if it was written in my native language. So I don't understand why do they blame English translations.
I suggest instead of repeatedly complaining about statements in general, give at least one example of what was said in a wrong way and how it should be correctly and clearly. Otherwise I assume (and so should the contest author) that you just don't know English well enough and the translations are ok and the complains are void.
Thank you for the support!
"Gerald is very particular to eight point sets" should instead be something like "Gerald is very fond of eight point sets". See the definition of particular to see why the confusion.
"...except for the average of these nine points" in this case case the problem was referring to the middle intersection point in both the x and y axis between the intersections of 3 horizontal lines and 3 vertical lines. Such middle intersection point does not necessarily has to be the average point.
"At least one of the chips at least once fell to the banned cell" could be, for example, "One of the chips falls in the position of any of the banned cells"
And this are just a few examples when the real meaning of the sentence is somewhat hidden. There are other small mistakes that make the reading very rough like misuse or lack of articles for example.
I know that you are not native english speakers (me neither) but I'm just saying that it would be nice to have a native english speaker proof-reading the problems so that we can all focus more on solving the problem than in understanding it.
All the examples come from
Bother problems, which I didn't read. Your remarks sound reasonable. Probably with A the case was different. I saw some people having problems with understanding the Russian statement of A too.UPD: In Russian version the same problem of "average" exists, so this is not translation problem. The rest of language imperfections doesn't lead to misunderstanding the problem, I think. So it kind of defends my point: the translations (although not perfect) are not real problem.
I was wrong.
средней may potentially mean average or middle. Definitely middle in this context. So it should be except for the
averagemiddle point of these nine points. And it was a translation problem. I hope this time I'm right.