This round was a Div1 itself... :D

You can participate virtually...

Not everyone gets what they want. For example I want to be a potato, but I can't... Probably the fact that my name isn't GLaDOS helps.

Hey! I just chanced upon this comment, and I see you've become a Master now. Congratulations.

yeah! that's because making out in valentines day is too mainstream for programmers :3

Relation with Problem.........Codefoces Guy.

Why do you need to write that here ?

Раунды всегда и на русском, и на английском есть, это только тренировки могут быть на одном языке. Плюс автор раунда — русский, так что, скорее всего, изначально условия были написаны на русском, а потом уже переведены на английский. Ну и плюс, в анонсе раунда есть благодарность Марии Беловой за перевод задач.

Only single yellow guys have such excellent knownledge

LOOOOL!!

I think so for myself! :D

That moment when you understand Persian :)))

I ridam too

I've had WA6 too, and that test helped me... input: 1 1 a a output: NO

A hashmap is enough, given the constraints, i think. My approach uses m.log(n)

Try this

2 1
aaa
aab
aaa

answer:
YES

I think Pretest 6 has a string equal to original string, when problem says they must differ by exactly one position. Such as this, output should be "NO":

1 1

a

a

Я думал о каком нибудь Ахо-Корасике или Укконене, но придумать что с ними нормально сделать — не смог

Я написал бор, не знаю упадет ли, но как мне кажется, вроде должен заходить.

UPD: загоняем все строки исходные в бор, затем когда нужно получить ответ, нужно пройтись по бору dfs-ом, с параметрами (curNodeInTrie, curPositionInString, hadDif) как только нашли ответ сразу же вернем его.

Погенерил тесты, вроде нормально, а вообще: сейчас систесты покажут =)

UPD: бор зашел за 184 мс

Code Here

Так он всё-таки искал коллизии? Меня он вроде бы взломал, потому что бинпоиск был кривой.

I failed this pretest in my first submission, i guess it's something like:

9999999999

And answer is:

9000000000

number shouldn't have leading 0 so check if 1st character is 9 or not if it is nine do nothing if not change to 9-s[0] or not accordingly if it is greater than 4 or not . rest all was just checking if character if greater than 4 change to 9 -character less let it be

Some number where first digit is 9, i guess. Like 9631 with answer 9331.

ML/TL for generating all possible strings and putting them into map.

WA for using hashes modulo 2^64.

I don't think people are so brash, but maybe this is the case

UPD. Turns out that post had only Russian version. That post is about hash collision generator, code: http://pastebin.com/JfTEUwCe

The one I hacked is looping with strlen(s), which is, of course, linear time.

pretests are a bit weak, i think. I got pretests passed in my first approach where space complexity was O(n^2) [Unnecessary though]

O(Nsqrt(N)) didn't pass. T^T

I think matrix exponentiation is the answer..

Кажется, я понял

Весьма интересно, что теста на неверное понимание условия задачи не было в семплах.

yeah I'm pretty sure.

I think that it's similar to this problem: https://www.hackerrank.com/contests/w10/challenges/towers.

Let's say that dp[i] is equal to number of vertices at distance i. d[i]<=100, so you need only values of dp[i-1]...dp[i-100] to calculate dp[i]. And this calculation can be represented by matrix multiplication, where variables are dp[a],dp[a-1],...dp[a-100], and you are multiplying this vector by some matrix to get dp[a+1],dp[a],...,dp[a-99].

In order to solve original question you have to add one more variable, ans[i]=ans[i-1]+dp[i].

Count the number of groups of vectors (positioned to x₀, y₀) so that for each pair of vectors in the group, their dot product is zero, and no vectors in different groups give zero as their dot product.

I did a brute force . take the position of gun let it be a,b . then for i=1..n .maintain a array called as killed[i] denoting if you killed ith enemy or not. start a loop from 1 to n check if killed continue. otherwise break .let this position be m. find coefficient of line passing through a,b and this point then for elements m+1..n check if it comes under the line .if it does mark killed[] =1 ; check if all are killed if it did break and print the count

I construct a, b, c in equation ax+by+c = 0 for (x0,y0) with (xi,yi) , i = 1..n. And you should make gcd(a,b,c) = 1 and a > 0. After that, you can sort n equation (a,b,c). Remove (a_i,b_i,c_i) == (a_j,b_j,c_j) by unique in C++. So that you have the result in O(NlogN)