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)

you get all N points and you insert tan((y-y0)/(x-x0))in an array tan and the answer is the number of different numbers of array tan .

well, let's count the number of the different slope k = (y — y0)/(x — x0). I think so!

Find the slope of each point with respect to gun. Store them in set. Print the size of the set.
If denominator while calculating slope is zero, assign it some infinite value. I hope it helps.

I calculated the slope of the line (y-tY)/(x-tX) and stored it in a map. In the end I just print the size of the map. Can anyone help me with the complexity of this?

I counted the number of differents tans, but I got WA on test 8. Anyway, what is the test 8?

you choose x1 y1 one point and erase it and ans++ then erase which point on line x,y to x1,y1
if which points on line erase it

I sorted the points by their slope with (x0,y0) and then compared p[i] and p[i-1] using (p[i].y-y0)*(p[i-1].x-x0) == (p[i-1].y-y0)*(p[i].x-x0). If False, increment the number of shots.

I also counted number of unique slopes with a c++ stl set (9839367). It got WA. But surprisingly, replacing scanf with cin got AC !!!

Can somebody explain what's here:

WA: http://paste.ubuntu.com/10226578/

AC: http://paste.ubuntu.com/10226581/

Так ответ не должен начинаться с 0.Поэтому из 900 никак нельзя получить 009.

Там ясно указано, что "Число не должно содержать ведущих нулей."

Еще хз, прошел или нет, кстати

В условии сказано, что число не должно начинаться с нуля.

// не видел ответы выше

"Запись итогового числа не должна начинаться с нуля.", то есть запись числа после применения некоторого количества операций инверсии цифры не должна начинаться с 0, так что 999 не может перейти в 009. Запутаться можно, но условие корректно.

Да, я ошибся, не правильно понял фразу "число не должно содержать ведущих нулей", думал что это эквивалентен "выводить ответ без ведущих нулей" ))

For each query string s with length L, there are 2L possible variants (i.e. replace each character by the other 2, and since you can do this only once, there are 2L such possibilities). You need an efficient data structure to check whether the variants are in one of N strings. I think using trie is sufficient enough.

I use set in C++ to save n string in set S. After that, with string i in m string query, consider position j, we have string x = s and set x[j] = {'a','b','c' \ x[j] != s[j]}. You can find x in set S in O(log(N)). I think it ok because The total length of lines in the input doesn't exceed 6·10^5

you make a robin-karp(hashing) all strings of the dictionary but with a different letter at each step ( if str[i]=='a' you get 'b' and 'c') and you insert this value in a hash at each step... and for queries you make a classic robin-karp at string Q and check if this value is in hash... You should double hashing for safety(two different bases and two different MOD)

I'm not sure if it's correct solution, but you can try to do it with hashing. For each n strings, calculate their hashes without each single letter. Next, do the same with strings from query but this time if any hash of ith string existed before, then answer is "YES" otherwise answer is "NO". There might be some problems, when some strings are equal, but it's not that hard to deal with.

let's define that: a is number of character 'a' b is number of character 'b' c is number of character 'c' we need to find out at least one element in this set: { [a — 1][b + 1][c], [a — 1][b][c + 1], [a][b — 1][c + 1], [a + 1][b — 1][c], [a + 1][b][c — 1], [a][b + 1][c — 1] } and compare them with string t to satisfied the condition! we should use map(or set) to save the input string with [a][b][c]. I think it could process in 3 seconds :D !

I think it's not, I have used hashing to solve it. BTW, during the contest I wanted to hack a solution with set, but when I tried to send the test it was loading for a while and then nothing — I had to try again and then happened the same. If it turns out that set isn't enough I will be kinda sad :D

Unfortunately for me,set is not enough. I passed pretests,but in test 20 I got Time Limit.

Да, я так и делала.

Если написать это неаккуратно, то есть риск поймать TL.

Чтобы улучшить асимптотику, можно вместо бинпоиска по ответу использовать два указатели.

P.S. А дерево отрезков можно заменить на мультисет.