Нет, вы не правы. Также — наречие.

Там их два в соседних предложениях.

Упражнение получилось на разницу — хоть сейчас в учебник :) .

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 :)

ds

Will be announced 5-15 minute before the contest.

Разве это может повлиять на участие в контесте?

I corrected it :)

ignore this post, posted after correction

he is just lucky guy)

Any subtree containing node 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.

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

Я понял, что имел в виду автор, но потратил на это штрафную попытку и согласен, что условие могло бы быть лучше. Проблема в том, что подмножество условия (без второго предложения) ставит задачу однозначно и при этом не так, как имел в виду автор. Считаю, что это плохо. После чтения первого предложения не возникает необходимости читать второе — казалось бы, условие уже вполне понятно. Ну я его (и ещё половину текста) радостно и пропустил по принципу "понял задачу — пиши решение".

Контест классный и интересный своими задачами. Спасибо авторам за труд!

no, there is many things more to consider.

for example obtuse triangle don't create any hole.

tricky B

Так всегда было.

I used division instead of multiplication and i used INT

+1, brother, you are not alone. I got AC with the same code + __int64)

You need to use LL to calculate k*x or k=1000000000 x=100000000 will kill you

Да, согласен. Понравилось очень то, что первые 2 задачи пишутся легко и изящно

На самом деле причиной такого распределения является эффект таблицы. Все посылали всякие эвристики и прочую ерунду на задачу D и проходили претесты. Все остальные видели это и брались за эту задачу. Меня весь раунд удивляло, как такое решение, как у меня, безбажно можно закодить за такое время, какое некоторые из участников показывали. Добрые претесты этой задачи, похоже, являются главной причиной того, что она получила букву D. Уравнять баллы за задачу D и задачу C было бы, на мой взгляд, более правильным решением.

Always shuffle before sort, fellow Java coder!

public static int[] shuffle(int A[])
	{
	int N=A.length;
	for(int i=1;i<N;i++)
		{
		int j=(int) (Math.random()*100000)%(i+1); // 0<=j<=i;
		int temp=A[i];A[i]=A[j];A[j]=temp;
		}
	return A;
	}

Integer is object , and all objects are sorted with merge-sort in java.. I got the problem failed for exactly the same reason..

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?

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.

Bad luck, bro :D. Look at my first contest :D http://mirror.codeforces.com/profile/Swistakk

Me to Stuck at 1699 :P

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 ?

Там походу Anti-Java-Hashset тест) Много решений на Джаве словили TLE 43 :)

There are solutions with O(n^4) complexity, but i don't think there is any solution with O(n^5) algorithm at all

Mine is O(n^5) too. Horrible complexity but no-brain to code :)

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.

"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.

No, the root of tree do not need to have value 1.

    2
   / \
  1   2
 / \
2   3

in this tree there are many subtrees including vertex with value 1, for example:

1.
    2
   / \
  1   2
 /
2 

2.

    2
   /
  1 
 / \
2   3

3.

  1 
 / \
2   3

"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.

Sorry for annoying, I did not see that some guys have already asked.

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. :)

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.

It should be uploaded in about 24 hours. Thanks for you patience. :)

Сортируешь последовательность. Пусть ans=0 — ответ. Проходишься по отсортированной последовательности: если элемент a[i]/k еще не использовался, то увеличиваешь ans на 1 (Проверить, использовался ли (a[i]/k) можно с помощью бинпоиска или множеств) и добавляешь a[i] во мн-во или массив(если бинпоиск) использованных чисел

ans — ответ

UPD: Код http://ideone.com/JaKtaj

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