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

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

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/

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.

The time complexity of your code is O(n^2) in the worst case. I used a test with two arbitrary strings of length 3*10^5 to hack your solution.

I'm the pathetic No.11 QuQ...

Collision?

WA on same case :(

My hashing has collision. I add checking function for 2 strings when their hashes are the same and it became accepted!

1<=X<=10^18

The number shouldn't contain leading zeroes.

Read the problem statement. You should not have a zero at starting index after performing inversions. 9 is not allowed as it is actually "09", which has trailing zeroes

I asked author what could be the answer for 9 as it was ambiguous and he said "No comments" -_-'

I am stuck at MLE, too. this solution seems to use Trie but does not cause MLE... I don't know why, though...

In your query function, you are passing the whole string and doing recursion. So each time you call query, the whole string will be copied and this increases the memory as well as the time. So I think if you just pass the string by reference string& s instead of string s it might resolve the MLE problem.

It's a technique which can be used to find max(a[i..j]) when we have queries of increasing i and js. However the code given by you is not that efficient. Take a look at this submission: We can use a C++ 'deque<int>' to answer all the queries in a total of O(n) time.

It's lengthy to explain why the algorithm works (after all it's not too complicated), but the whole operation is expressed as follow:

• Everytime we increase j (a.k.a push a[j] into processing) we remove deque.back() while it's smaller than a[j], then deque.push_back(a[j]).

• Everytime we increase i (a.k.a pop a[i] from processing) we remove deque.front() from the deque if deque.front() is a[i].

• The answer for each i..j query is always deque.front().

• In order to limit the sum, each time we increase j (process the next element), we increase i until {sum} ≤ k

Nope. "The decimal representation of the final number shouldn't start with a zero."

I solve it using trie, created a trie for each different length of strings and brute-forced to check if there was a string in the respective trie in each query.

http://codeforces.net/contest/514/submission/9843858

O(3 ^ len)

Even systest is freezed in the end for some reason...

Updated:)

http://codeforces.net/blog/entry/16365#comment-212594

"How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?"

You have been destroyed 1, 3 and 4th droid, so your sequence has length 2. In the correct answer, 2, 3 and 4th droid is destroyed, so the sequence has — better — length 3.

Word 'consecutive' is the key.

P. S. Sorry for my english :)

I also did segment tree and passed. Maybe you can take a look. 9865631

Your solution is interesting. Can you explain your solution ??

How he managed to get the solutions before starting of the contest ??

I'm working on it.