Всем привет! :)
Совсем скоро начнется Codeforces Round #168. haas и я (havaliza) авторы сегодняшнего контеста. Я хочу поблагодарить Gerald и Delinur за помощь в подготовке задач, а также MikeMirzayanov за его систему.
Надеюсь, что Вам понравятся задачи также сильно, как нам понравилось их готовить. ^.^
Good luck and have fun. :)
Это перевод оригинального поста автора, комментарии на английском приветствуются.
UPD1.
Распределение баллов по задачам:
Div2 = standard
Div1 = 500-1000-1500-2000-2000
Всем удачи и подняться в рейтинге!
"также" — в данном случае пишется раздельно, я не прав? Я имею в виду "...также сильно, как нам...".
Нет, вы не правы. Также — наречие.
http://www.gramota.ru/spravka/punctum/58_710 Учите русский язык.
UPD. Я писал к первому "также" до правки вашего комментария :) Со вторым "также" — согласен.
За агрессию извиняюсь. В Вашей же статье(второй) подтверждение моих слов:
Раздельное написание — так же — имеет значение 'таким же образом', например: мне это необходимо так же, как и вам.
P.S топик**п**астера
P. P. S наконец — слитно
Топикстартера, наверное)
Там их два в соседних предложениях.
Упражнение получилось на разницу — хоть сейчас в учебник :) .
Two authors of Round 168 from Iran,BAYAN Contest at Iran. Iran dominates on CF website :) will Iranian authors give us high rates & successful challenges ?
В этом контесте нужно поучаствовать хотя бы потому, что
"Надеюсь, что Вам понравятся задачи также сильно, как нам понравилось их готовить. ^.^"
GL & HF !!!
if someone says GL & HF will get negative votes then if someone says "Bad luck & don't have fun" will he get positive votes =)
just a joke :)
my comment :)
there was no haters there :)
Most of CF's contests take place in the same days of week, is there any special reason or it is accidental ?!
ds
What will the points division in Division 1 ? Thanks .
Will be announced 5-15 minute before the contest.
Thanks for the info . Why is my comment hidden saying " too negative .. " . I was only asking the points division .
I'm guessing because everyone asks that before the contest and it's getting annoying.
Опять про распределение ничего :)
Разве это может повлиять на участие в контесте?
The post says : Score distribution will be: Div2 = standard Div1 = 500-1000-1500-2000-2500 What is standard points division ? I used to think the points division mentioned for Division 1 above is the standard division where every consecutive problems is 500 points more worth than previous problem .
I corrected it :)
ignore this post, posted after correction
Who is mrsa_91 and why he is expert?he haven't enough rating to be expert but he is expert...
he is just lucky guy)
Высокого вам рейтинга!!!
Хороший 9 тест в задаче B Div2))
The scoring for div1 was so weak ...
Can someone please explain the Div2-D statement? I found it confusing. How can we choose the subtree?
Any subtree containing node 1
Can I only select vertices and edges so that every vertex has a direct path to vertex 1?
If I understood you well, no, you can select bigger subtree too not only the neigboring vertexes to node 1...
I said direct path, not edge. For the tree 1 -> 2 -> 3, can I select subtree 1, 3 ?
but vertexes 1 and 3 are not a tree or I misunderstood you example...
Только одну мне показалось условие задачи A(Div1) не валидное? В первом же абзаце противоречие, и совершенно не ясно что надо вернуть при k = 1.
X < Y поэтому необходимо вернуть общее число элементов.
Противоречий нет. "То есть, во множестве не существует двух целых чисел x и y (x < y), таких, что y = x·k." Очевидно, что при k = 1 условие x < y никогда не выполняется и поэтому ответ n.
При k=1 вообще никаких неясностей. Мне трудно представить, как можно выбрать 2 числа x,y (x<y), для которых y=1*х.
Что именно невалидно? При k = 1 в множестве точно не существует двух целых чисел x и y (x < y), таких, что y = xk, поэтому ответ n.
Действительно, первое предложение формально противоречит второму: не сказано, что выбранные числа должны быть различны. А правильное понимание во втором, более формально написанном.
Я понял, что имел в виду автор, но потратил на это штрафную попытку и согласен, что условие могло бы быть лучше. Проблема в том, что подмножество условия (без второго предложения) ставит задачу однозначно и при этом не так, как имел в виду автор. Считаю, что это плохо. После чтения первого предложения не возникает необходимости читать второе — казалось бы, условие уже вполне понятно. Ну я его (и ещё половину текста) радостно и пропустил по принципу "понял задачу — пиши решение".
Ну согласись, что x < y всё однозначно определяет. А потом в условии в формате инпута гарантируется, что все числа различны... Я тоже потратил кучу времени, что бы развязать все противоречия при беглом прочтении условия и определний авторов.
Да, понятно, что из формально противоречащих друг другу первого и второго предложения автор, скорее всего, имел в виду второе. Непонятно, как после прочтения первого предложения догадаться, что второе тоже нужно обязательно прочитать.
Ну моя схема была такая: 1) Прочитал бегло услвовие 2) Наткнулся в ограничениях на случай k = 1 3) Прочитал внимательно условие
Я тоже так сделал, но перечитал не всё условие, а до первого места, после которого всё понятно. А первое предложение идёт перед вторым, и в нём дан точный, но неправильный ответ на случай k = 1. Вот формальный вопрос к условию: как всё-таки после этого догадаться, что нужно прочитать ещё и второе предложение, и всё будет наоборот?
Например, можно прочитать все условие. Полностью. Странно, что некоторые делают не так.
А по-моему, наоборот, странно предполагать, что все делают так. Например, если условия ACM-контеста занимают 20 страниц и на три четверти состоят из легенд — авторы обычно отдают себе отчёт в том, что почти ни одна команда не вчитается в каждую букву.
Я считаю, что условие должно удобным способом донести задачу до читателя. Например, это означает, что нестандартные моменты или нетривиальные ограничения следует повторить несколько раз — во всех местах, где они могут быть важны. Например, в условии, в формате ввода и в примере.
Бывают и другие точки зрения: например, в условие можно специально вставить что-нибудь, чтобы запутать читателя. Обычно такое намерение автора видно по всему условию. Конечно, приходится его всё внимательно читать. Но чаще процесс чтения имеет мало общего с темой соревнования, и автор, наоборот, пытается его минимизировать.
Возвращаясь к текущей ситуации. В условии сегодняшней задачи A есть проблема: первое и второе предложение формально противоречат друг другу. Есть следствие из неё: условие неудобно читать. Есть конкретные проявления этого следствия, описанные в комментариях выше. Можно по-разному относиться к конкретным проявлениям и их локальным причинам (кому как нравится читать условия), но проблема в условии от этого никуда не девается.
Ещё переформулировка: из утверждения "глупо читать плохое условие не целиком" (согласен) не следует "глупо читать любое условие не целиком" (не согласен).
Я не вижу проблем с первым предложением. Там четко написано, что рассматривается множество (т.е. набор различных чисел) и два числа из него (т.е. два элемента). В данном контексте то, что они различны является естественным умолчанием. Хотя бы, так как написано, числа два. Иначе это был бы один и тот же элемент множества, т.е. фактически одно и тоже число.
Следующее предложение формально пересказывает менее формальное первое, т.е. разжевывает его.
Не согласен. В математике, например, выражение «для любых двух чисел из множества S верно P(a, b)» однозначно записывается как
, и это совсем не то же самое, что 
; такое условие всегда оговаривается отдельно. Не понимаю, почему в условии задачи, являющемся достаточно формальным документом, умолчания внезапно становятся другими.
Например, мы же всегда пишем в условиях, что числа целые, когда они целые, а не предполагаем это по умолчанию. Хотя вот тут как раз в подавляющем большинстве случаев даны именно целые числа.
Если исключить субъективные суждения, остаётся только предложение с естественными умолчаниями. Но 'естественное умолчание' с точки зрения математики — словоблудие.
haas и havaliza, спасибо за классный контест) Очень понравилась D в Div2, жаль что не успел решить(
Контест классный и интересный своими задачами. Спасибо авторам за труд!
ty uveren ?
Nice problems specially Div2-D & Div2-E , but I couldn't solve them on time :)
B was harder than C in div-2
I didn't have time in contest to finish my E problem, so I'd like to ask if this algorithm is ok for solving this one:
I tried to find all triangles, that are not containing other points in it or at the edge. And from such triangles the answer is diameter of circumscribed circle. What do you think about this. I'm not sure about the limit, because finding such tringles in my implementation is O(n^4) where max(n) is 100...
Is it worth to try to finish it?
no, there is many things more to consider.
for example obtuse triangle don't create any hole.
iff there is no triangle I'm printing -1
you didn't understand me.
for example test case:
the answer is -1 although there is one triangle
I see, now it's clear to me, thanks for your replies ;-)
edit: it seems that additional check that center of the circle is in the triangle solves this problem
but a square shaped 4 dots will not form a hole with any three of them, but creates a hole eventually in the center of the square
No , take this test:
as you say "check that center of the circle is in the triangle solves this problem"
so you sould answer this test by -1 but the correct answer is sqrt(2)/2
Something is wrong with Div2-B :) Why so many WAs ?
tricky B
Что-то новенькое. Смотрю в таблицу в процессе тестирования. Решение RomaWhite по первой отображается у меня в виде жирного красного -1, и при наведении вижу надпись "после блокировки решение было взломано пользователем aitzhan.askar в 00:23". Хотя на самом деле решение было отправлено в 00:09, взломано в 00:23, потом отправлено еще раз в 00:31 (эта отправка еще не проверена на момент красного -1, потом она получает АС), и только потом — заблокировано.
Так всегда было.
I got 6 WA on problem c, because of long long :(
I used division instead of multiplication and i used INT
+1, brother, you are not alone. I got AC with the same code + __int64)
in problem C(div 2) my algorithm was so
for example n=8 k=3 array(1,6,2,9,3,7,5,4)
sort array: 1,2,3,4,5,6,7,9
I Divide array with sub arrays: {1,3,9},{2,6},4,5,7 so that in each sub array was x,k*x,k^2*x,k^3*x and so on.
and that ans will be sum of (each array length)/2+(each array length)%2+(num of arrays which consist only one element) ans=(3/2+3%2)+(2/2+2%2)+3=6
this solution got WA6 what is wrong?
You need to use LL to calculate k*x or k=1000000000 x=100000000 will kill you
thanks,
Хороший раунд получился!!!
Да, согласен. Понравилось очень то, что первые 2 задачи пишутся легко и изящно
Test case #11 Problem B div2
Судя по таблице, С нужно было поменять с D... Кстати, а как определяется будет динамическая стоимость или нет?
На самом деле причиной такого распределения является эффект таблицы. Все посылали всякие эвристики и прочую ерунду на задачу D и проходили претесты. Все остальные видели это и брались за эту задачу. Меня весь раунд удивляло, как такое решение, как у меня, безбажно можно закодить за такое время, какое некоторые из участников показывали. Добрые претесты этой задачи, похоже, являются главной причиной того, что она получила букву D. Уравнять баллы за задачу D и задачу C было бы, на мой взгляд, более правильным решением.
Нужно иметь быстрые пальцы и коротко писать.
ну вот, искал искал firebug-ом какой код тут у красного цвета, а тут оказывается все скучно) Поздравляю, вас, Павел, с удачным контестом, вы теперь наверняка
Спасибо :) Только жизнь научила меня. Пока не увижу свой handle красным — не поверю.
Поздравляю!
И я тоже поздравляю!
Ухухуху! Спасибо, спасибо :) Тебя, Коля, с тем же праздником!
Div1-A failed because of the anti-quick sort cases .. (where Arrays.sort becomes n^2 in java) Second time to lose a problem because of the same problem, I think you guys need to prevent such cases because it's completely ridiculous.
Always shuffle before sort, fellow Java coder!
or you can just replace int with Integer and long with Long
This is because objects are sorted using merge sort instead of quick sort
Fantastic problems. Truly thanks for your great problem set. Wish to see more contests like this. HF & GL!
А что такого в D на 12ом тесте?
Again, my solution 3159034 for C received TL because Arrays.sort seems to be slow for some special cases, I think my solution is efficient.I changed int[] for Integer[] and it got AC(3162097), I guess that the sorting method for Integer[] is not randomized( perhaps a merge sort), is this true?
Integer is object , and all objects are sorted with merge-sort in java.. I got the problem failed for exactly the same reason..
ma 5alas fahamna :D
ya 3am mateseeb el ragel fe ely howa feh :D
Mine strangely failed because HashSet is apparently less efficient than a TreeSet in this case.
3162811 vs 3162830
Blog entry about this test case
CF really needs top stop messing with java programmers. Can't use this, can't use that! :[
As a programmer you think to yourself and say HashSet is faster than a TreeSet. But If you force all inserts into one bucket then obviously a HashSet is no better than an ArrayList. I just need to remember to code for the worst case instead of the average case on CF.
I love C++ <3 :)
Try not using modulo and division. Those are REALLY slow.
lol C++ (FTW) :p
Aside from the apparent bias towards C++ programmers, do you guys know why they don't do the same for the C qsort / C++ sort? Is it randomized or very difficult to hack?
std::sort uses an algorithm called introsort which has a worst case complexity of O(N log N). Basically it initially uses quick sort but switches to heap sort when the recursion depth gets too large.
Now I understand why such anti-quicksort test cases can not be made for C++ sort. Thanks for replying.
Actually, one possible solution is changing the language of the submission to java 7. That way it uses the tim-sort of java 7 which guarantee n log n worst case.
double pivot quick sort its used for primitives
Oh yes I see [here].(http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%29).
But I also see on the code that they use merge-sort sometimes, at least it seems not too easy to hack...
Авторам спасибо. норм контест)
I got WA in problem B Div. 2 because I've mistyped M with N ... :((
OH GOD WHY?
i'm from 1534 to 1699 points :(
can somebody give me one point :(
Bad luck, bro :D. Look at my first contest :D http://mirror.codeforces.com/profile/Swistakk
Me to Stuck at 1699 :P
I used breadth first search for all vertices with priority Q in Question B Div2. if all black nodes cant be visited the answer is NO and if the no if direction changes >=2 answer is NO the direction changes if the current direction in which a node is accessed is perpendicular to the direction of neighbouring node...
Is this correct approach?
You need to make sure that you can reach every other black node from the black node that you pick as a starting point. Yes, your constraints are correct. I followed a similar approach. 3162770
I solved this problem with a meet-in-the-middle technique approach, O(n^5) I believe this can be improved, but I didn't care too much about this as this passes within the limits...
My solution failed for test 26. Anyone knows what's the complete test case ?
I cannot wait to see the rating to be updated!
Thank you very much for contest.
I am very happy right now because my raiting has grown.
Почему это решение ловит TLE? :( 3152764
Там походу Anti-Java-Hashset тест) Много решений на Джаве словили TLE 43 :)
Is there any one who got accepted problem B-div2 with O(n^5) algorithm?
There are solutions with O(n^4) complexity, but i don't think there is any solution with O(n^5) algorithm at all
Consider any 2 black cell & check 2 possible paths between them with O(n + m) ! I know it's the simples algorithm, but I thought it would get TLE! :(
I got AC with O (n ^ 4) for bruteforce and O (n + m) to check path. So O (n ^ 5) Solution successfully passes all the tests. You can see my submission in upsolving :)
O(n+m) can become O(1) if you pre-calculate it
so total complexity is O(n^4)
My solution is O(n^5) :D
Mine is O(n^5) too. Horrible complexity but no-brain to code :)
About div1 D, if multiple answers exist, anyone will do, right?
for
Answer 1 2 3 4 and 4 3 2 1 are both valid. Am I right?
Yes.
Yes, you are. There are 24 different correct answers possible here. Of course, [1, 2, 3, 4] and [4, 3, 2, 1] are among them.
Thanks.
Thanks for the good contest! (at least for me) Looking forward to see official solutions
I can't wait to see the tutorial for E in div 2... I've seen some ac codes, but I don't know the correctness of the solution. Simply they are finding acute triangle circumcircle center, then find if there are rectangles to form are new hole. Then find the max radiuses of these centers. But how to prove that this solution is right?
"But how to prove that this solution is right?" — hm, it's not :P Look at example: 4 0 0 6 0 3 5 3 2 Aaand if you want to rush with something like "excluding acute triangles with other points inside them" take this one: 4 0 -100 0 100 400 0 -1 0 :) Much more complicated problem than it seems to be.
Waiting for tutorial...
Promlem D DIV2:Is the head of the tree a vetex numbered 1?Whick is the head? How to understand "Select the subtree of the given tree that includes the vertex with number 1."?
No, the root of tree do not need to have value 1.
in this tree there are many subtrees including vertex with value 1, for example:
I got it！thx
"Select the subtree of the given tree that includes the vertex with number 1." just means the subtree containing the root which is number 1, but its value isn't always one.
where in sentence "Select the subtree of the given tree that includes the vertex with number 1." is the word "root"?
Well, I just wanted to point out that the vertex with number 1 is the node with number 1, not the nodes that have value 1. I think this is what he's confused about the head of the tree... (I just represented it to be the root of the tree).
Could you post tutorial for this round?
Sorry for annoying, I did not see that some guys have already asked.
I have a question about problem div1 E. Why does the answer become so small, that is all answers are no more than 200000, and brute force can pass all the tests??? just because k — the number of the blocked cells is small? I think maybe we can construct an input data to make a larger answer and make brute force TLE.
In all, I think the test data of problem div1 E may be too weak and let the solutions that are not optimized enough pass.
Would the problem setter of this problem please give me a reply??
Yes, even 100000 x 99999 empty board will produce a huge answer.
You're right. I didn't manage to generate the tests for this problem more carefully because I didn't have much time before the contest to prepare the tests and obviously I missed lots good of tests. Also random tests with the dimensions I used (mostly both n and m were powers of 10) seemed to have very small answers.
Now I've updated the tests and I've added a lot more tests with huge answer. So the brute-force solutions won't pass anymore.
I'm sorry about this. Hope I do better in my next contests. :)
And another little problem is that previous submissions are still there without being rejudged. Would you please rejudge them?
Gerald told me that it's impossible to do, because It would be unfair to those who've got AC. :)
But now the shortest solution is by me and it's brute force... //also just because this can I find the problem about the tests...
I got the permission to rejudge it :) Thanks!
Thanks for rejudging my wrong submissions! In fact only some of my submissions are correct!Would you please rejudge all of my submissions in order not to mislead others. And I think majority of the solutions of the guys that previously tried to solve this problem and then got AC are correct, would you please also rejudge them in order to show the correct real execution time?
I think it really doesn't matter that much. I rejudged your solutions, but it's not good to rejudge others'. I think everything's ok right now. :)
Thank you for your hard work！ You've made an excellent and enjoyable CF round！ I am looking forward to your next CF round！
Thanks! ^.^
"A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T." This is not true :-/ Also, when I asked for clarifications about this I got "No comment".
Why it's not true? In problem statement you was given a definition of subtree, which you needed to use. Not any other definition from wiki or another place.
Ok, maybe it's true, but definitely not complete. We cannot pick ANY subset of vertices and edges. They do not specify that all vertices must have a path to vertex 1.
Not ANY subsets, you skipped the first part of the definition..."A subtree of a tree T [IS A TREE] with both vertices and edges as subsets of vertices and edges of T"
You are right, thank you! :)
Editorials??
It should be uploaded in about 24 hours. Thanks for you patience. :)
Люди, кто-нибудь мог бы объяснить, как же решается задача С? Да, и если будете выставлять код, то желательно или на Pascal, или на C++.
P.S. Извиняюсь, что не просматривал комменты и там не смотрел, есть ли там что-нибудь про решение С.
Сортируешь последовательность. Пусть ans=0 — ответ. Проходишься по отсортированной последовательности: если элемент a[i]/k еще не использовался, то увеличиваешь ans на 1 (Проверить, использовался ли (a[i]/k) можно с помощью бинпоиска или множеств) и добавляешь a[i] во мн-во или массив(если бинпоиск) использованных чисел
ans — ответ
UPD: Код http://ideone.com/JaKtaj
Here's an idea for Div 2 E: construct a Delaunay triangulation of all the given points (doable in N log(N)). Delaunay triangulation satisfies the property that a circumcircle of points that are connected by the edges of triangulation doesn't contain any other points (except possibly some points lie directly on the circumcircle and not inside of it).
Then for every triangle in the triangulation, check that the circumcenter of the triangle lies strictly inside of the triangle. The triangle with the largest radius of the the circumcircle is the answer. You will also need to handle the "special case" when the circumcenter lies on on of the sides of triangle ABC (let it lie on side AB). A "hole" will be created only if there is a fourth point D on the circumcircle of ABC which is connected by the edges of the triangulation to A and B.
Delaunay triangulation is constructable in N log(N) time, but not sure if it is codable in the contest time.
Anyone knows why Scala is so slow on Codeforces. I tested my program for Div2-B locally and it's as fast as Java, but it failed to pass on OJ.
I am stuck on http://mirror.codeforces.com/contest/275/problem/D . Can anyone help me .??
this problem is solvable with a simple dynamic idea.
run dfs on graph and find for every vertex value of a_i and b_i, in order minimum number of increase and decrease to make value of all vertex in subtree of vertex i equal zero.
for leafs we can calculate it simple, and for non-leafs vertex (i) we can calculate it by this way : for every j that j is children of i
a_i = max(a_i, a_j); b_i = max(b_i, b_j);
and at last we should calculate number of operations that we need to make value of vertex i equal zero.
w = value[i] — b_i + a_i;
if(w<0)
a_i -= w
else
b_i += w
proof of this algorithm is very simple . sorry for my poor English, I hope this help you.
So, my solution is as follows:
root the tree in vertex 1; for each vertex, determine its children
recursive approach: for each vertex, calculate the minimum number of adding and of subtracting operations (each separately) which must be applied on it so that it and all its descendants would get a value of 0
first, calculate the numbers for all its children; then, the minimum for each type of operations is clearly at least the maximum of minimums of this type of operation for all the children (due to the rooting, if an operation is applied on a vertex, it's applied on all its ancestors); by applying these operations, its value v_i changes and you need a minimum of additional v_i subtractions (if v_i is positive) or -v_i additions (if it's negative) to get it to 0
There exists a suitable construction of these operations such that the resulting tree truly is a zero tree — you may think about it.
In any case, the answer is minimum number of additions+subtractions for vertex 0 (by definition). The overall complexity is then optimal O(N).
а будет ли разбор задач? было бы неплохо увидеть его =)
http://mirror.codeforces.com/blog/entry/6759
problem D in div1: it said the brother erased some intergers and change the order of some of its columns. But it also said when "If there exists no possible reordering of the columns print -1" and I think this is a contradiction because we can awalys change it back to the original order against the brother's order. I also the answer of sample 3 is "-1" :(
I have a question.(maybe silly)
Is the word "editorial" correct? shouldn't it be the "tutorial"?
Sorry for my poor English.
Both of them are correct! ;)
Testing speed is amazing. Thank you.That was related to Round 170.Anyway, thank you! :D