What's your meaning?

Feel like you are drunk.

Your commitment counts more than your performance. Looking at your history you definitely have commitment and I have the utmost respect for that!

Which glitch are you talking about? If I am not mistaken, I don't see any glitch there.

And also in Div.2 :V

Наверное они просто "накинули" сказку на свои задачи, потому-что сказки в условиях редко бывают (я лично не встречал ни разу), либо условия прекрасно под неё отлично "ложились" .

просто ничего не выйдет решить:)

i think so :/ , but i need to change my rating :"(

Thanks :) !

Thank you

Если суммарно больше 7 цифр, то ответ 0, т.к. все не могут быть разными по принципу Дирихле. Иначе перебираем втупую и проверяем, перебор — 7^7 операций, выходит довольно быстро.

Максимальная длина числа не может быть больше 7 разрядов (так как цифры обязательно будут повторяться): 6543210₇
По этому критерию мы уже отфильтровываем числа n > 823543₁₀ = 7⁷

Зная максимальное число цифр (допустим оно равно 7), мы можем определить минимальное число, начиная с которого нам стоит проверять числа. Если максимальное число содержит 7 разрядов 6543210₇, то минимальное число, с которого нам нужно проверять — это 0012345₇.

Don't know if you meant the division 1 B, but for Div2 I brute forced it, manually swapping two elements at a time when necessary and after every swap checking if it's sorted.

He's talking about Div.1 C I believe.

I don't think he is talking about div2 C :P

I used the same approach but failed. It might be easier if the distance was asked instead of the actual point :(

I can't understand, can you elaborate please? How does 4 dimension help? Also, can anyone suggest some problems which can be solved in similar way?

What is wrong with that check?

Solving B after 50 minutes seems relatively slow for you :p

Ternary search on one coordinate z. For fixed z I have four inequalities and I claim that the value of answer is maximum of distances between parallel inequalities. This allows to find optimal z but not to find optimal x, y then.

Maybe I should then ternary search the next coordinate but I think it's hard to implement. So instead for the found four inequalities I imagines drawing four lines, then I found two intersections (an intersection of leftup and leftdown lines, and an intersection of rightup and rightdown lines) and then the answer should be in the middle of segment connecting the two intersections. I didn't know if I can round the answer (found x, y) to closest integers so I checked brutally all 2² possibilities of rounding.

Is this correct for 2D version ?

A=(min(Xi+Yi)+max(Xi+Yi))/2;

B=(min(Xi-Yi)+max(Xi-Yi))/2;

and you can get answerX and answerY from this

answerX+answerY=A;

answerX-answerY=B;

answerX=(A+B)/2;

answerY=(A-B)/2;

I used same solution for 3D (4 coordinates for each point) , but got WA 6

It really is the same, you can consider: x + y + z, x + y — z, x — y + z and y + z — x. Transforming a point in such a tuple, it becames similar to 2D version(the rotation in 2D) and binary searching is enough. The very very stupid thing is that you really have to take care of overflow and of some parities as well and it's pretty ugly. The problem would have been much nicer if they fixed the limita 10^17 and the problem had a higher score. I didn't even had time to think at the other tasks and still have to write some more lines...I guess that in k-D plane, you have 2 ^ (D — 1) elements in tuples. I really liked that the rotation can be generalizate but the overflow really destroy the task

Let x+y+z=C, x-y+z=D, x-y-z=E, x+y-z=F.

There is integral solution to system if and only if C,D,E,F all have the same parity and C-D+E = F.

What I did was, for each possible parity, take C,D,E to be the smallest possible and calculate value of C-D+E. Then try to make it fit into range of F inequalities by increasing C/E (if C-D+E is too small) or increasing D (if C-D+E is too big).

Turns out that bruteforcing a 3x3 cube around the non-integer solution works. No need to do any parity fiddling.

18693710

But problems were nice and there were no issues. #smallmiracles

And I liked the fact that pretests were strong.

Выдает 0 для степеней 7.

Моё тоже, после некоторых костылей.

just had to do a n--,m--; at the start done the same mistake :(

LOL same xD

Answer?

Shouldn't it be 0? Any single digit hour will have leading zero and so the single digit minute too? 01:02. Then 0 is duplicated (?)

Answer to the Ultimate Question of Life, the Universe, and Everything...

My idea is tree dp. Here's a brief sketch of my idea :

Do standard subtree size dp. For each node, determine the maximum subtree size of its children. Then, we calculate the answer for each node which is closest to the root. (actually I think I implemented something slightly different in my solution) We consider whether the node itself is actually a centroid and also which nodes to take from the childrens. This sketch is not very detailed but this is briefly what I did.

UPD : It got Accepted! Basically, I stored a "jump pointer" on each node, which is initially the answer for that node (after we finish dfsing the node). Then, when we process the parent, this "jump pointer" jumps depending whether jumping to the parent will yield a better centroid (better centroid means maximum subtree size is lesser, with ties broken using distance from root). Using this, for each child of a node that we're currently processing, if the node itself is a centroid, we take the node. Otherwise, we check the jump pointers in the childrens.

Code

Brief basica idea:

• dp on tree
• when you process subtree rooted at v check if v can be centroid
• if it can't be centroid, then the centroid will be on the path largest_child_of_v -> centroid[largest_child_of_v]

It is enough to start with the centroid on the largest child and move up by parents until you find the centroid of the v. Amortized time os O(n).

The solution in the editorial uses O(nk) memory. I had two arrays of size n*k each, they require some 228 MB. 256 MB memory limit definitely seems too strict if you intended to allow O(nk) memory solutions to pass.

Same with me. I resubmitted in panic, only to realise it wasn't necessary!

My bruteforce seems to give TLE on pretest 13. Plz look at this code: http://mirror.codeforces.com/contest/686/submission/18685502