Доброго времени суток, друзья)
Приглашаем вас на очередной раунд Codeforces #175 для участников Div. 2. Как обычно, участники Div. 1 могут поучаствовать в этом соревновании вне конкурса.
Задачи для вас вновь готовила группа авторов в следующем составе: Павел Холкин (HolkinPV), Артем Рахов (RAD), Фефер Иван (Fefer_Ivan) и Геральд Агапов (Gerald). Как всегда благодарим Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon, а также Марию Белову (Delinur), которая перевела условия задач.
Распределением баллов публикуем заранее) cегодня оно будет стандартным: 500, 1000, 1500, 2000, 2500.
Откроем небольшой секрет этого соревнования, сегодня во всех задачах вы столкнетесь с перестановками)
Надеемся, что соревнование окажется для вас удачным, желаем всем высокого рейтинга, успешных взломов и хорошего настроения)
UPD1: соревнование завершилось, надеемся оно вам понравилось)
UPD2: разбор задач уже можно найти здесь)
UPD3: поздравляем победителей:
1) hechuan
2) TroyI118
3) BekzhanKassenov
4) ahmed_aly
5) lxgsbqylbk
O(no_of_users !) :P.
swap(standings[0], standings[find(standings.begin(), standings.end(), {insert your username here}) — standings.begin()]);
Today is the first day of the new solar year! Happy new year to Iranians!
Today is the first day of the new solar year! Happy new year to Iranians!
If you tell your congratulations twice — you will get twice more "+")))
dadash njuri k nemishe ! Man be hame ye Iranian saale no ro tabrik migam va aarezuye saali khosh ba rating haye bala baraye hame daram ;) injuri baiad begi payam haye vatanio ina nafahman, hamegi her her beshun bekhandim :P
I think, it will be a very interesting round!!! Everyone, successful hackings and have fum ;)
I think, it will be a interesting round!!! So... Happy Hackings & Have Fun...
Why it'll be a interesting round?
Happy new year to Iranians and have a nice time
nice info, i will prepare next permutation code which i found some time ago in java :P
You may take a look at the first comment here which have a next permutation code in C++ :P
If this round like round 171 doesn't have editorial please tell me to solve all the problems ;)
I have just relised that HolkinPV always make Div.2 Contest, Why don't he try to make some Div.1 contest?
Actually I prepare two div1 rounds long time ago) and also not only by my self. Now I take part in the group of authors and we prepare div2 rounds for participants. Maybe we prepare div1 contest) wait) and enjoy our problems)
Hope to be an interesting round... Good luck for solving the problems and good luck at hacking ;)
Farmer john was lucky for me, and I want that this contest will be lucky for me :D
Regarding next round, 176, why is it so early on Saturday? Can you move it on Sunday at normal time 7:30 pm as before please?
..::Happy New Year::.. عید بچه های گل ایرانی مبارک more about Nowrouz: http://en.wikipedia.org/wiki/Norouz
3003 registered....
its 3000+ and a palindrome number
palindrom
Зарегистрировалось 3003 человек!
3003 -- палидром!
Является-ли последовательность {1, 2, 3} перестановкой (имеется в виду, для системы тестирования).
да
это первая перестановка из трёх элементов
Пожалуйста, задавайте вопросы членам жюри через соответсвующий интерфейс в системе. Кнопка "Задать вопрос" находится внизу страницы "Задачи"
Осознал свою ошибку, спасибо.) Впредь буду задавать вопросы по задачам именно туда.
Отличная задача D!
Последние div-2 only Контесты стали в духе 2-3 халявки один гугл и гроб.
Я именно так ее и решал)) А что значит это: "Also the number of "good" permutations on 2n+1 elements"?
Ну, заняться вам нечем. Можно переборчик написать с парой отсечений и precalc для 15.
Да я знаю. Просто переборчик, как видно, можно было писать и без отсечений)
Это за какую такую асимптотику переборчик?)
Переборчик вроде как не работает. Во всяком случае я один такой на контесте сломал.
Так надо его не в систему отправлять, а сначала дома ответы посчитать.
Ниже написали уже: http://mirror.codeforces.com/blog/entry/7087#comment-127073
Мне кажется, что и первого отсечения хватит. Оно довольно очевидно. И там ответ порядка 30 миллионов.
Только хотел узнать, откуда у всех этот чудо-массив, вуаля. Нечестно однако...
Ну почему же нечестно? Правилами не воспрещается, да и не явно ответы искать же надо) А так-то была задача, где в разборе написано что-то вроде: "Поймите, что это числа Марсенна и нагуглите их".
Ну я все посчитал, нашел как искать ответ, дошел до мертвой точки.
1, 3, 15, 133. Теперь думай, что дальше? Весь контест не мог найти полную последовательность.
Nice contest, but I don't usually like problems where user machine does matter upon the solution.
What do you mean?
It's not that hard to come up with a brute-force solution on problem D which wouldn't run in time on the real competition, unless you've a nice machine so you can pre-calculate all the results in your own micro and just print it.
I've tried to think about one brute force but all of them needs more than 2 hours.
Edit: seems many contestants got brute force that runs in a less than 2 hours
At least you have to use a not-so-naive brute force to solve it. My solution can run up to N = 14 and it takes 10s for N = 15.
My brute force solution took about 10min for N = 15. That's why I'm willing to buy a Core2Quad Processor, I'd have done this problem a lot faster.
Как решать E? Я в недоумении!)
Уровень задач, на мой взгляд, был A-A-A-D-E :)
как решать Д? час думал, не догадался
Нужно было предпосчитать / нагуглить (ненужное зачеркнуть) ответ :)
Пишем n! ^ 2 перебор, ответы до 7 можно найти. Дальше если вывести получившиеся перестановки (часть конечно) можно заметить что они все делятся на группы с некоторой размерностью. Делим ответ на n! и получаем последовательность чисел, вбиваем в OEIS, немного копи-паста -- AC.
У меня два отсечения: 1) Можно сказать, что первая перестановка — 1,2, ... , n. ответ умножить на n! 2) Можно сказать, что первый элемент второй — 1. ответ умножить n. Работает для 15, 16 где-то полминуты (даже если забыть про то, что ответ[2*n] = 0).
Что-то я второе отсечение не совсем себе представляю. Можете поподробнее расписать?
Ну смотрите, если прибавить один (по модулю) ко всем элементам второй перестановки, у суммы тоже прибавится единичка ко всем элементам. Значит, все вторые перестановки делятся на группы по n.
Умно однако с первым отсечением придумано, респект.
А вот для 17 уже 2 минуты. Это значит, что без второго отсечения — 2 * 17 минут, а без первого можно просто умереть. Наличие гугла все испортило. Задачка хорошая.) А жаль.
Плохо считаю, 7 минут. То есть, поднять ограничения на 2, и без второго никак.
someone explain the solution of problem E please ;)
Кому написать по поводу: при обновлении страницы взлом продублировался. То есть вместо одной попыки стало две. Нажимал на кнопку взломать — ничего не происходило, потом появилось две посылки.
Математика, математика, математика... Контест — скучнее некуда. Три абсолютно идиотские и легкие задачи. Задача C, которая решается даже синими за две минуты, Задача D — на знание OEISа и мертвый математический гроб — задача E.
Обидно за задачу D. Зачем в ней этот идиотский модуль? И без него все прекрасно можно посчитать. Я почти сразу же решил эту задачу честной динамой и послал ответы, но весь контест не догадывался почему у меня WA3. Задача прекрасно решается без всяких модулей, зачем тут они — ума не приложу. Ну и задача на OEIS в роли задачи D... Браво! Дай бог, чтобы из второго дива хотя бы один человек сдал D динамой, а не тупым запросом в гугл.
good problems! thanks :)
To be sincere, they are not good
How to solve D?
Isn't contest unfair to those not having high speed computers? as-if-anyone-cares
Also: "g++ -Ofast D.cpp"
http://oeis.org/A006717
The number of distinct permutations of b for each permutation a is same so ans=fact[n]*k
Hi, A person in my room has a TLE solution because his/her quicksort is binary cut: http://mirror.codeforces.com/contest/285/submission/3369236. All time in contest I can't make the test that kill his/her bug. Can anyone show me how to make the test to kill that quicksort code? Thanks.
See what happens if pivot element is always maximal element in the subarray.
На чём ломали C?
Хотел на переполнении int, не нашлось :)
Это претестами ловилось.
A rare one , most of the passed pretests guaranteed passing the systests...
I think the number of the tests for D could be more.... 16 was to small, It's possible to get an array and save the answer for each test! EDIT: I saw the editorial! It seems that the solution is making an array!! Interesting! I haven't seen a problem like this!
Sadly... C# implementation of quick sort isn't perfect :( My solution for C problem failed.
There's a well known story how Petr once got TLE because of that :)
I don't know about that story. Maybe I should choose another programming language for algorithmic contests...
Or you can just shuffle the array before sorting it.
done :) thanks
В D при переписывании массива констнатного (1, 3, 15, 133...) пропустил одно число. Сразу после контеста бомбануло так, что прожег половину комнаты со всей мебелью, да еще и рухнула одна из стен, общая с соседями. Теперь я живу в коммуналке, спасибо тебе, "37851".
Ты такой не один :)
http://noise.podst.ru/posts/981/
Hi all, a simple question here. For Problem A test case 3, input (3 2), why is (1 3 2) not an acceptable output?
Since there is only one number, which satisfies p > p + 1
I think we misread the problem in the same way :( At first I thought we just need pk>pk+1 It's not until 1 hour later where I understood that the coeff is referring to the number of such k where the above statement is true. Felt so stupid haha
No wonder...thanks!
I didn't get it. I thought we need to make sure that Pk is greater than P_(k+1).
is that not the case?
in the first test, 5 2
Pk = P2 = 5 (second position in the array)
P_(k+1) = P3 = 2 (third position in the array)
so that's why that's the correct output. But shouldn't 5 4 3 2 1 also be correct?
So it's not just me and "ssi7415" haha. No, we all misread the problem. What is required that the number of such k is equal to 2. NOT that there is only one such k, and that k=2.
So, for 1 5 2 4 3, there are 2 such k's where pk>pk+1. That is, 5>2 and 4>3.
respect to the guy/gal who submitted this!
http://www.codeforces.com/contest/285/submission/3375139
answered a D problem in ONE LINE!!
WOW!
so i got TLE for #175 div2 C. But most solutions where similar & passed written in C++. so i tried to write it in C++ after the contest, it passed fast (500ms). furthermore, when i chose Java 7 it TLE at test 8, java 6 TLE at test 7. finally i changed long to Long, then it passed (1312ms)???
so why long TLE, and Long doesn`t?
http://mirror.codeforces.com/contest/285/submission/3376354 http://mirror.codeforces.com/contest/285/submission/3376365
in other words in java, why is Integer[]a faster than int[]a, or Long[]a is faster than long[]a? does this mean Integer a is faster than int a?
in terms of performance.
UDP: Sorry, I misunderstood the comment.
Because Long and Integers are objects, but long and int are primitive types. So every time you add one Long to another Long, they are converted to primitive types, then they are added and then they are converted back. But if you use long directly, they are just added. So this is why long is faster then Long.
Primitive types such as int and long are sorted by qsort, which in worst case may work in O(n^2) time. But Long and Integer aren't primitive types, they're objects. And objects in java are sorted by mergesort, which always works in (nlogn) time. That's all magic.
Because for sorting arrays of primitive types it uses quick sort, for others classes — merge sort.
IMHO, in first case java converts basic type(long) into object (Long) of every element and makes sort after that. and converts backward. I think so.
P.S. Sorry for my english.
Also you can just randomShuffle array before sorting. (It seems that there are a special array, on which java quick sort works for O(N^2), but merge sort does not)
Why so many minuses? I am right. http://mirror.codeforces.com/contest/285/submission/3377006
It is your code, but with random shuffle.
No idea. But mostly your code is slow because you're using Scanner to read 10^5 numbers. You can browse solutions of high-rated Java coders and use their I/O code.
yeah using tokenizer made it about 500ms faster. but like aircube & Resurgent pointed out. it is the sorting that TLE. i just tried my merge sort instead of Arrays.sort() and it passed with about the same time as using Integer[] did. proving that Resurgent & aircube had a point there.
one less thing i don`t knw
WOW! you are too fast! tnx :)
The first time I solved 4 out of 5. The problem D was a little bit tricky for me, but finally I managed to solve it :)
Опять у этих двоих одинаковые решения уже по 4-м задачам.
metalopocalipsis : А — 3367731, B — 3368553, C — 3372596, D — 3375755.
lawliet_djez : А — 3367389, B — 3368933, C — 3372757, D — 3375514.
И еще один баг codeforces:
metalopocalipsis Обратите внимание на рейтинг,
1512, а это должен быть эксперт..Это не баг.
Это его так MikeMirzayanov наказал.
aitzhan.askar уже давно должен быть синим...
Не хочу, и не буду !!! :D
Интересно, рейтинг -> expert, а есть ли возможность участвовать в див1.?
В этом Кф официально принимали участие с такими же багами. Так что им скорее всего нельзя участвовать за див1.
По какой закономерности в D числа {0,1,0,3,0,15,0,133,0,2025,0,37851,0,1030367,0,36362925,0} ?
Если я прав, то это объясняется так.
q[] = {0,1,0,3,0,15,0,133,0,2025,0,37851,0,1030367,0,36362925,0};
q[i] — количество массивов b[] длинной i, при a[] = {0, 1, 2, 3, 4, 5, ..., i}, и при этом сумма массивов a[] и b[] является правильной перестановкой.
Объяснение суммы можно прочитать в условии задачи.
Ну ясно, что q[n] (q[i] — количество массивов b[] длинной i, при a[] = {0, 1, 2, 3, 4, 5, ..., i}, и при этом сумма массивов a[] и b[] является правильной перестановкой.) надо умножить на n!. Не ясно почему q[n] будет именно такое.
Надо просто немного почертить :)
.
Представим, что слева у нас числа из перестановки A, а сверху — числа из перестановки C. Тогда на пересечении определённой строки и столбца будет стоять число, которое нам необходимо поставить в перестановку B, чтобы получилось
Ещё немного почертив, нетрудно заметить, что нам нужно из этой квадратной матрицы выбрать ровно N различных чисел так, чтобы в каждой строке и каждом столбце стояло ровно по одному числу. Так как равные числе у нас образуют диагонали в матрице, то всё к сводится как раз к задаче о расстановке ферзей на тороидальной доске (доске, у которой верхняя сторона соединена с нижней, а левая — с правой, образуя таким образом "замкнутость" диагоналей).
Количество способов расставить ферзи на тороидальной доске размера (2N + 1) * (2N + 1) и есть последовательность A006717 в OEIS.
Спасибо.