Hello, Codeforces!

I'd like to invite you to Codeforces Round #291 (Div. 2). It'll be held on Saturday, February 14 at 19:30 MSK.

Great thanks Maxim Akhmedov (Zlobober), Vasya Antoniuk (Antoniuk) for helping me preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

Good luck everyone!

**UPD:** Score distribution will be the next — **500-1000-2000-2000-2500**.

**UPD:** Editorial. Sorry for the delay)

wish it will be the way to DIV 1 :-)

I hope your next round will be Div. 1 too :)

This round was a Div1 itself... :D

What a shame ! I have a flight on that time. I will miss that round. I hope not to be busy at next contest on codeforces . Contests make addicted :)

You can participate virtually...

I want to be a Candidate Master...

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.

thanks, my dreams come true xD

That's why I have no girlfriend...

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

Unless you are a brogrammer.

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

hope i will be blue today ...

Why do you need to write that here ?

Psss, nobody needs to write anything here

sorry if you see that I shoudn't write like this..

Have Any Problem Of Valentine's Day?

Today is the birthday of the first electronic general-purpose computer.

Happy Birthday ENIAC.

Only single yellow guys have such excellent knownledge

very interesting problem set, many thanks for not setting a valentines theme.. star wars theme was a pleasant surprise

UPD: Finally, +17:-3, including: 1 triple hack, 4 double hacks, 1 last minute hack.

Well done!

LOOOOL!!

Hopeful of being a room winner for the first time :)

Riiiiiiiiidam

tanx

I think so for myself! :D

That moment when you understand Persian :)))

I ridam too

I got WA at #6 on problem C. Anyone knows what it is about?

I solved the problem using a Trie.

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

can you explain your solution? I also used Trie but got TLE on testcase 10.

Hey, can you please explain your approach using hashmap. I couldn't solve the problem during the contest. But have to solve it anyhow, now.

Try this

2 1

aaa

aab

aaa

answer:

YES

It works on this case.

I've used hashing. It gives right for your test but fails on test #6.

This is test case 6, I think

~~I think I found the case:~~~~Answer: NO, because there should be exactly 1-symbol difference.~~Oops, didn't notice comment on the bottom

I think Pretest 6 has a string equal to original string, when problem says they must differ by

exactlyone position. Such as this, output should be "NO":1 1

a

a

OMG! Thanks...

You're right :-(. I didn't pay attention to '**exactly** one position'. Now it works. Thanks!

How to solve A.Or what is test 8 for problem A.

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

And answer is:

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

So what is anser for 9999.is it 9 or 9000 or what

9000

I don't know... but by 'with no leading zeros' I understood that you can't write 0003 (for example). I think that the statement should say something like 'with the same nuber of digits'.

What do you think?

The problem should have mentioned "with the same number of digits"! :(

Yes , actually this is very poor statement in the question.I am very disappointed like this type of problem statement [user:Zlobober][user:antoniuk].I am also wonder how some top guys think about this in the only first chance.

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

What was the hack test on C?

Overflowing the length in a char array? (up to 6*10^5)

Just time outs?

WA with the same string as in dict?

I submitted a brute force that passed the large pretest (took some work) just to hack on C XD, thinking it was overflowing the char array, but everyone used cin >> string so nothing for me

Somehow no one hacked my solution (maybe not enough time)

EDIT: WHAT, my brute-force C passed systests...

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

WA for using hashes modulo 2^64.

Not necessary 2^64. I have hacked a few solutions that use one hash modulo 10^9 + something. It is also possible to find a collision for two hashes, too(but this generator is slightly harder to implement).

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^TIs in the problem E answer is polynomial of degree ~100?

I think matrix exponentiation is the answer..

Is solution of 514E - Darth Vader and Tree related to matrix multiplication?

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

How to solve B ?

Count the number of groups of vectors (positioned to

x_{0},y_{0}) 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)`

Hey i did the same but got WA on 8th test case ..

http://ideone.com/uzEJcW

My code link ..

Try this test:

You can see my code

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!

I did that but I lost 100 point due epsilon precision. What is the default precision we need to use to compare two doubles?

Consider two doubles a and b equal if fabs(a-b)<=EPS, where EPS is something like 10^(-9).

Then, the number should be 10^(-9). I used 10^(-4) and 10^(-6), getting WA in both. AC after 10^(-9) with the same solution.

Correct answer is

`2`

. With epsilon 10^{ - 6}, the answer seems to be`1`

; the numbers are close enough. (If you're wondering, the differences 6765, 10946, 17711 are consecutive Fibonacci numbers, which is why .)Got it! Thanks.

in such cases when you are not sure of what value to assign to eps, you can use

and let the compiler do the rest.

I did the same, and it worked like charm. 9834951

I tried storing numerator and denominator seperately as int after taking gcd, and it worked. You can view the solution here

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.

Umm did you store the slopes in a double? There could be precision errors then.. not sure though. I prevented myself from doing it this way due to the possibility of this error.

Yeah stored them as long double. I hope there are no precision errors.

Edit: It passed.

I stored each slope in a set of doubles and my solution passed tests. Guess I got lucky.

An alternative would be to write a fraction class as such:

Or perhaps BigDecimal (seeing how this is Java code)

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 guess in the worst case it would be

as you have to insert N different slopes in worst case, and each insertion would take at most logN time.

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

( area == 0 ) this is my solution which WA on test 8 ( area < 0.00001 ) this AC

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/

Guys, it`s magic I just move declaration of set at WA code to main scope and got right answer

Code

Full 8 test

WTF?

Seems like that this magic feature forks only under MinGw G++ 4.8 and 4.9 (at Ms works fine) In my Linux machine with g++ 4.9 with same compile keys it works fine.

Can someone make disasembly of this code(dont have win machine with Mingw right now) or explain ?

Yes, seems magical. Did spent quite some time yesterday. Didn't disassemble as could not produce on local. I did played around quite some using the "custom invocation" of the code forces and have noticed the following(not sure how relevant they are).

Whatever be the case, please update if anybody find the reason for anomaly.

I think this may be the answer: https://isocpp.org/wiki/faq/newbie#floating-point-arith2

Yes, something like this might happened. Thank you for a nice link.

please help me problem C

For each query string

swith lengthL, there are 2Lpossible variants (i.e. replace each character by the other 2, and since you can do this only once, there are 2Lsuch possibilities). You need an efficient data structure to check whether the variants are in one ofNstrings. 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`

well, i solve it with map (as set) and i couldn't submit it in 2 seconds :(((((

"You can find x in set S in O(log(N)) " Not true. Comparing two strings needs O(length(x)) if they have a very long common prefix, so it's O(length(x)log(N)). Consider this case: 1 1 aaa...aa aaa...ab (The first consists of 300000 'a' and the second consists of 299999 'a' and one 'b')

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 that is wrong, check this test case: 1 1 caaa aaab

the answer is NO

4 unrated handle spotted the top 5 in current standing! They're unpredictably good o.O

UPD: In final standing the number decreased become two and both of them are the top 2! Fast system testing by the way.

To solve problem C, Is "c++ STL set" just enough?

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.

I've used unordered_map in problem C, but I've got hacked. What could be the problem?

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 got TLE in test 28 :( .. my time complexity is O(m * l * log(n)) where, l is length of string in each query. m,n are from problem statement. Can anyone explain how this doesn't run in the time limits? Upd: (m*l)<=6*10^5 (from statement) and log n cannot exceed 18

The time complexity of your solution is not O(m * l * log(n)). Just consider the input that consists of two string: each of them is a letter 'a' repeated 3 * 10^5 times. Your solution makes O(n^2) comparisons for this test.

i am submitting div2 3rd ..but its not showing me the case i m wrong on...!!!!

I am very sad about

`problem D.`

This is my code in contest and this is my code after contest. They different exactly one position`L = 0`

and`L = 1`

. If I have`10s`

to think that, then I can`accept`

problem D and`my standing not low`

.Finally, top 10 for me!!! :D

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

I've used Hashing to solve C. Here's my code 9849480.

It failed on the test #27. It's "..." testcase.

What's wrong with my code?

Collision?

Maybe...

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!

Problem A , in my opinion has a very ambiguous problem statement what is the answer to:- 90 90 or 9?

My point is, they should have explicitly mentioned whether the number should not have leading zeroes before printing the answer, or during computation.

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" -_-'

ML in problem C! :(

I got MLE on problem C at #19. I solved the problem using a Trie. Can anyone have a look on my submission, please?

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

The solution is embarrassingly similar to mine. Yet i get MLE. WOW! :-)

That is really strange my submissions in practise is also giving MLE on test #19.

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.Can someone explain the algorithm behind this code: http://codeforces.com/contest/514/submission/9850107

It's a technique which can be used to find

max(a[i..j]) when we have queries of increasingiandjs. 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 ofO(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 pusha[j] into processing) we remove`deque.back()`

while it's smaller thana[j], then`deque.push_back(a[j])`

.Everytime we increase

i(a.k.a popa[i] from processing) we remove`deque.front()`

from the deque if`deque.front()`

isa[i].The answer for each

i..jquery is always`deque.front()`

.In order to limit the sum, each time we increase

j(process the next element), we increaseiuntil {sum} ≤kThanks much for the algo, it's really simple. In step of increasing

jyou forgot to push_back(a[j]).In my opinion Problem A description was not clear.For input 90 output should be 9 according to problem statement but test data says answer is 90."Length of output number must be equal to length of input number" this single line of statement should have been added.

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

You could've assumed that you just had to remove the leading zero.. It's not clear...

You can't assume things in a programming contest.

Any deterministic solution for C?

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.com/contest/514/submission/9843858

For problem C,why people get TLE in test #19?

Suppose,this solution

O(3 ^ len)

which solution will pass? How to optimize it?

You can use Trie data structure ....

My code for problem C : http://codeforces.com/contest/514/submission/9843731

Hope , this will clear your concept about Tire .

Why is rating update taking so long?

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

Updated:)

I can't find my mistake about C problem, I used hash with unsigned long long

this is my soution: 9844038

Is there any problem if I substract from unsigned long long?

This is another similar solution, he used two hash, but I'm sure colisions is not my mistake ...somebody?

9836207

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

Sorry. Got the mistake.

I am sad I took TLE in C using set-stl,but I am happy because I achieved my first goal that was blue. Now it is div1. I hope to achieve that soon :D. I say that,because I want gray-green users that with "correct" practise everyone is able to achieve everything,and never give up.

Guys is there anyone who could help me understand why my submission gives wrong answer in test case #6? By my calculation the output kills 3 droids even though checker comment states my solution kills only 2 of them. Any help is greatly appreciated.

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

Why do I get MLE for problem D? http://codeforces.com/contest/514/submission/9850749

I have used segment tree so 4*N*5 memory, plus one more array of N*5 (both int). As N is just 100000, this should not exceed 256MB memory limit.

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

Yeah, I got it later. I am creating 2 new arrays p,q in every call to query. This must be adding up to the memory as the arrays must get stored in the recursion stack. (Not sure, but I think this may have been the cause). When I removed that part, and instead passed an array to the query function, I got my solution to pass. http://codeforces.com/contest/514/submission/9858833.

Anyways, thanks for your reply! :)

My 2 cents, since everyone writing about problem C seems to have tried hashing:

The similarity condition imposed is Hamming distance = 1. This is a metric space and can be solved with any of the metric tree structures. I used a BK-tree, and I got AC.

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

no one can reach real coders (Even cheaters!)

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

See that '00:28' near his handle? It means he's a virtual contestant (submitted the solutions after the contest finished).

That's virtual contest. I think he first took 5 submissins which passed all tests, started virtual contest and submitted them on the first minute.

When editorial is going to come? It will be interesting to see author's solutions to these problems :)

I'm working on it.

Done.

Still waiting for jury to start upsolving... :/

How could always the new comers be in the top list in division 2 ?!!!

They are usually Div 1 coders that make new accounts.

Is O(M*N*log^2(N)) using segment tree supposed to TLE for problem D ?

No.

Rebryk, I think data set of problem C ( 514C - Watto and Mechanism ) of today's contest was a little bit weak. Consider this submission: 9852063 which fails the test case:

Should not the output be

`NO`

? It gives`YES`

instead.Thanks. :)

Yes. You're right. It's my fault.

became expert for the first time

i am getting memory limit exceeded on test 18 in C... i have used map<string,int> to do it.. can anyone suggest the reason for this? and also what would be a more memory efficient way of doing this question...

When you use

`if (f[s])`

with a new string`s`

, it makes`f[s] = 0`

and therefore uses`|s|`

additional bytes of memory.Try to use

`set <string> f`

and`if (f.find(s) != f.end())`

instead of`map <string, bool> f`

and`if (f[s])`

.thanks a ton :D that was a new thing for me :D

Can somebody please check why I got a run time error on test_25 http://codeforces.com/contest/514/submission/9848840

I have tried the test case on my computer and it worked.

this contest really interesting though i didn't solve any problem. actually i wonder why i can't solve at least problem A, and then i know that because some case (case 8) like this:

input :91730629

my output : 1230320

answer : 91230320

in my opinion, i think my answer actually didn't wrong because we could make the minimum positive number by inverting 1st, 3rd, 6th, and 8th character from the input and discard the leading zero. is somebody has the same opinion with me?

the length of the output should be the same as inputs ! :)

really? then i should miss that in the description :)

btw, which statement says that?

It is exactly because the statement never said that you can discard any digit. Which means you can only invert digits but then the result cannot contain leading zero(s).

You should not make your own assumptions.

Problem description says: "transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits". so you can't discard leading zeros,only operation you are allowed to do is invert some (or zero) digits.

I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.

I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.

Where is editorial???

Sorry, I'm a slowpoke

Done.

Good job)

I got AC on 514B - Han Solo and Lazer Gun,but I alos have a question. gun is situated at the point (x0, y0). can stormtrooper at (x0,y0),too ? if so, i think some code maybe got WA。

I am trying to solve C problem. I see a lot of solutions where there is something like this :

for (int i = 0; i < n; i++) { ... for (int j = 0; j < s.length; j++) {

where n <= 3*10^5 and s.length <= 6*10^5 , so in worst case it works in 9*10^10 ~ 10^11 . Why it pass ? How can I calculate the worst complexity withing given time limit ?

if n = 3 * 10^5 s.length can't be 6*10^5, because 6*10^5 in the worst is a sum of all s.length

Yes, thank you. I misunderstood problem statement. Anyway, is there any good algorithm to determine the worst complexity withing given time limit ?

What does it mean:

withing given time limit?Time limit in this problem is 3sec.

I want to know algorithm with 2 inputs complexity, time limit . The output will be answer YES/NO For example:

C = 10^6 T = 1 s => YES

C = 10^19 T = 1 s => NO etc

1 second on Codeforces is ~ 2 * 10^8

Totallength of all strings in input is 6*10^5, thus, the code you described does 6*10^5 iterations.Your solution couldn't even read input if these two loops would TL

The problem A has too many traps, and some of them is so boring, such as the fist digit can't be zero. I think it is meaningless......

What is/are the other trap(s)?

Why does this give TLE for problem C? => http://codeforces.com/contest/514/submission/9853243

In problem C, I did not understand why the hash value of a string will not overflow long long. And if I mod using a 4 digit prime then there should be collisions.

Given the clue, "The total length of lines in the input doesn't exceed 6*10^5. Each line consists only of letters 'a', 'b', 'c'.", there can be a string of length 10^5 whose hash value can be huge.

I used mod 10^16+3 and base 203. Collisions are still possible but have a very low probability. However, there are solutions that do not use hashes, for example: http://codeforces.com/blog/entry/16394

Thanks for the link :)

Hi, somebody else used hash for the problem C?

I have WA #6 but I don't know why. Any help would be appreciated! :)

http://codeforces.com/contest/514/submission/9860261

The string

mustdiffer by one char, i.e. here's the test: 1 1 aa aaNO

Oh, right... I didn't see that constraint. Thanks a lot!

You helped me 5 years in the future 5 years ago. xD

For hashing, if I use 101 then I get WA for test case 8 but if I use 257 then it is accepted. Why so?

I chose 101 because the ascii value of c 99, hence I thought 101 was enough.

If you see a passed solution you think is wrong, is there a way to hack it in the practice room?

NO

that's too bad, it would be nice to be able to double-check that your hack was correct, and also keep other people for thinking a wrong solution was actually correct.

Codeforces Round #291 (Div. 2) champion ppfdd got AC on problem C.

But there is massive hack for his code.

While hashing, He converted a,b,c to 0,1,2.

So the result for this input:

the output generates

which definitely WRONG ANSWER.

There should have been at least one test case regarding this factor. :3