Hi, Codeforces!

AIM Tech Codeforces Round will take place on February, 4 at 20:05 MSK.

The round is prepared by AIM Tech employees: Kostroma, AlexDmitriev, yarrr, ArtDitel, ValenKof, bobrdobr, Agul, gchebanov and zeliboba. Round will take place during Petrozavodsk Winter Camp, which is sponsored by our company.

We made our problems a little easier than at our last Round, but we promise they won’t be less interesting. Scoring system will be static. The final distribution of points will be announced right before the round, however you should note that this time difference in complexity between problems div1 C, D and E may be less than usual so our strong recommendation that you read them all first.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces, problem coordinator Gleb Evstropov (GlebsHP) and Maria Belova (Delinur) for English translation.

Our company specialises in proprietary trading, the key concepts in our work are big data, low latency and high frequency. Our team mainly consists of graduates from the MSU Faculty of Mechanics and Mathematics and Moscow Institute of Physics and Technology (MIPT).

We wish you good luck and high ~~frequency~~ rating!

P.S. For all participants of PTZ gathering we are glad to announce evening buffet that will take place at Paulaner Brauhaus and will start Februrary, 5 at 7:30 pm

**Scoring**

**div2: 500 — 1000 — 1500 — 2000 — 3000**

**div1: 500 — 1000 — 1750 — 2000 — 2250**

P.P.S. Author solution of div2A had precision error 5e-7, so we decided to rejudge this problem.

I hope that the all problems will be more interesting;)

GL & HF

Why does it say "February 22" when it actually is on February 4th ?

fixed

It would be great to make one division contest like previous round :) I think that is more interesting for everybody.

Interesting to watch Bus nearing to the white while he manages to solve almost the full contest xD

It says the scoring system will be static, does this mean that the points for submissions of a problem won't decrease as time goes by?

As far as I know, No it means that the scores of problems won't be changed during the contest ,this means if problem C is for 1500 points before the contest it can't be changed to 1250 or 1750 points during the contest even if number of submissions for that problem increase or are relatively less.

Okay thank you very much!

No T-Shirts ?? Your past contest had 200 T-Shirts which was really awesome.

Next time we are going send T-shirts again =) This round is created mostly for participants of Petrozavodsk Training Camp.

In fact I havn't received the T-shirts prized for AIM-FUND ROUND yet! :D

Send me your tracking number.

sended.. :D

*sent

forgive my stupid English :<

div 1

what is high frequency rating?

Maybe your browser can't display it, but the word "frequency" is crossed out.

As far as I remember, your previous contest was very good.I hope this one will be better.

I think you mean very tough.

In div 2 the standing was very unusual, from the 27th to the 1500th all of them solve A and B only !!!

very easy A,B and very hard C,D,E. I think the difference in difficulty should be normally increasing not exponentially.

Agreed, but all problems were good at all.

this contest was better very easy A,B,C and very hard D,E

Be rated or not ?

If nothing bad will happen it will be.

thx

Will it be a rated contest like division 2 contests ?

It's usual rating contest, except that it's prepared by us

Will the score obtained will depend on the time of submission just like any other round?

I believe this round should have the same rules as other rounds. See the last Aimfund Round.

yes

when I try to submit a code it says i'm not registered !!!

you must be registered before start of the contest. usually register is open 24 hours before the contest begin.

he/she registered in two contest before how could he/she doesn't know about this

good question for his/her ! I must investigate more , next time.

And here is when I hack Um_nik ! :)

You're welcome :)

Thanks for this

How to solve problem D div 2 ?

Nice problemset !

How to solve Div2C?

First observation: each 'b' symbol will be connected with every other symbol in the string.

So, find all symbols connected to all others and add them to first set ('b').

First symbol that is not 'b' will be 'a'. Add this symbol and all symbols connected to him to a second set ('a').

All other symbols not in first two sets will be in third set ('c').

Now validate sets 'a' and 'c' so each symbol in the set connected to each other (set 'b' is valid by its definition). If not — answer 'No', if yes — print the answer.

Complexity is O(N^2).

Oh, and now I realized my solution is wrong, because it's not enough to check this. You also must validate that any 'a' and 'c' are not connected.

Lol yes, I actually just realized this too.

My alternative solution:

EDIT: probably bad idea, got Wrong Answer on test 26 because I forgot to check that any two different colors are not connected

Additionally, in step 2. you need to ignore nodes without edges, so they can be colored as 'b' in step 3.

Well, these would be ignored anyways as all 'b' nodes would not exist in the reversed graph (because 'b' nodes are connected to every other node).

It depends on your method for generating the reverse graph. If you don't remove the nodes that are not connected to any other node, then there is a risk of coloring them as 'a' or 'c' in step 2.

I got AC with this kind of solution, I checked the string 1000 times to try to find new symbols, then filled the rest with 'b' and checked the answer: 15798901

I had brute force solution, lol :))) Of course, it is named as "backtracking", but, anyway, it was too stupid. TL on test 15

I am DIV2 too, check my solution.

15811052

I knew How to solve E....

If I had just 5 minutes more...

Same here. Fucked up on indecies (+/- 1)

Can anyone give me an idea for B div.1 ? :'(

Factor a[0]-1,a[0],a[0]+1, a[N-1]-1,a[N-1],a[N-1]+1. Then for each prime from that factors, do:

Solution for prefix is basically a run of modifications such that gcd(run) = p and then run of deletions. Deletions from prefix solution join with deletions from suffix solution.

PS: there may be a mistake in idea, I didn't get AC.

PS: it's actually easier to make one pass of DP for each prime

My idea was that either the left element or the right one will be present in the final array, so try for every prime factor of those numbers (plus 1 and minus 1 too) the minimum cost to build an array with all numbers multiple of that prime.

I did it with prefix/suffix DP and some operations of addition in between. I don't know if my solution is correct though.

+1 or -1 of left or right elements may also be present.

Yes, that's what I did. I just forgot to mention it here. Thanks for pointing it out.

Note that you only need to consider prime divisors of

a_{1}, (a_{1}- 1), (a_{1}+ 1),a_{n}, (a_{n}- 1), (a_{n}+ 1) as possible GCDs. Trying all the possibilities should be easy enough.I didn't consider cases for

a_{n}only fora_{1}:(Anybody got stuck too at Div1B — 9th pretest?

Stupid mistake, when factoring by trial division forgot to check if the rest of the number is > 1 and then it should be added to prime list too.

9th test is the first when a large prime appears.

Solutions for Div1 D? Being solved way more than Div1 C for some reason, is there some easy solution?

I am not sure why it should work, but here is my approach, which passed pretests. First of all guess each friend once (order doesn't matter now). After that I always greedily guess the friend which gives me the biggest profit as a matter of probability that you win in that turn. I simply do that with a heap and while I have enough time.

Let

p_{i}denote the probability that we've already caught thei-th person. The probability of winning right now isp_{1}·p_{2}·...·p_{n}. For eachiwe can considerr_{i}— the probability that we've already caught this person or we will catch him/her in this turn (assuming that we're going to try to catch him/her now). The probability of winningawill change to wherecdenotes a person chosen in this turn.Why can we greedily choose the biggest ? I won't show the formal proof but the following two arguments are enough:

ithe value of is decreasing as we choose this person again and again.Today Codeforces was extremely slow :( I was hacked and didn't refresh manually. It took 25 minutes for Codeforces to warn me :( I went to other heavy websites but my connection was totally okay :(

I had the same problem: my A solution got hacked 9 min before contest's end, but I got the notification only when it was over :( So I spent 9 last minutes on D rather than finding bugs in A. Seems like manual page refresh is a must :(

Thanks for room 23

Div2 B hack:

Why So Many Ones?

3 1 1 1

is enough

what is test 6 of div1 C?

I think this the worst decision I make in my life choosing to solve C first!!

Wow. You really can't make easy contests.

Another contest by unusual scores and difficulty of problems... at Div. 2 Problems A,B was very very easy and so Problem C a little ... for this a lot of people solved problem A,B,C and the force(competition :D ) of contest was for a few of Time!! All are the same !! :|

Well I think ABC tasks was very good for div2: difficulty is raised from A to B and from B to C significantly (there were like 3000+, 2000+ and 1000+ solved participants).

But D and E was too hard (only 15 and 1 solved). Imo, D should be actual E and there needs to be a simplier task between C and D to be perfect problemset for Div2 :)

Now I see Problem C has just about 500 AC after system tests... This mean that Problem C was not normal so... Now All the same at solve Problem A && B :D !!

actually A-> 3200 B->2500 C-> 500 . Not a good distribution.

My hack case for C :

4 3

1 4

2 3

3 4

I even hacked my own solution with it (i.e. discovered it after locking -_- )__

Please, say that

`acca`

is the right answer :)Right answer is 'No' :D

Now I have to go back to my drawing board :)

Another contest with weak pretests.

GL hackers!

wow! so many failed C(div2). and the whole time i was trying to hack with B -_-

My hack case for A(div 1) C(div 2) :

5 9

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

bbbac or bbbca

Both are supposed to be accepted right?

In all testcases 'a' can be swapped with 'c' in the answer.

I thought the string in problem A can have any character from a to z. So I solved the harder version and failed system test. After contest I changed upper bound of character from z to c and got AC :(

I think I also had it bad. Forgot to print "Yes" in the special case ( n = 2 and m = 0 ) and got WA78. But I fixed it after the contest and it got accepted. I kind of hate myself right now.

This kind of mistake may sometimes be avoided by having only a single line in which you output Yes and No. If you don't have any "return" statements above the line has to be executed always.

Yes, you're right. It's entirely my fault that I implemented the code like this with multiple Yes or No lines, and avoiding it is actually very easy, but I think I'm way too lazy for that kind of "refactoring". I mean, it's the "accept rush". But just seeing your solution fail simply because you didn't format the output properly is a real pain in the neck :/

Also, the "Yes" bit is really redundant. It should've been the string / No from the start.

I understand the "accept rush":) And if the code is already written then there is obviously no time for refactoring. But if you start writing the solution by introducing the bool variable and then serializing it to "Yes/No" only once at the end, it somehow makes it more difficult to forget to set it properly. And there is no chance of forgetting about the output, because it's always there at the end.

Sound advice.

I'm interested in how you solved this for the a to z range. You can kindly inbox me a solution approach. Thanks.

lol, in A we should use 'a'-'c' only... I should read statements sometimes.

I even asked a question, are 'a' and 'z' considered neighbours.

Uhh... thank you! :D

Well share the submission link/username so that i know where to look incase i don't get something from editorial.

15805017

Actually I meant "hacker's dream" :D

Hm, ok, that was fast!

Woww. Rating lost after one contest = Rating gained after one contest! :P

Such stability. Much wow. :P

Please see gninrael; maybe you can be friends.

Aw...Fast system testing and fast rating changing .. good :)

Can someone tell me how to deal with precision problems at div1E? I was using FFT(but had same big values due to modular inverse) and modulo being very big, I was getting values with a big error.

There are two possible solutions: the first is using Chinese Theorem (calculating the answers modulo some numbers about 10

^{6}, then obtaining the answer in long arithmetics), or using the next trick: take and represent each coefficient asa_{i}=b_{i}·M+c_{i}, wherec_{i}<Mandb_{i}<M. Then the multiplication of polynomials with coefficientsa_{i}is reduced to 3 or 4 multiplications of the polynomials with coefficientsb_{i}andc_{i}. There coefficients are less thanM, so the usual FFT in doubles is OK for them. For instanse, check Endagorion's solution.I was thinking about Chinese reminder theorem too but it seemed too slow and hard to code. I'll try to implement the trick tommorow(hope it'll work). Thanks

Hacked B(in Div.2) three times. Problem C could have been just a little more easier. PS: Thumbs up for the fast system testing and ratings.

Well, screwed up somewhere in A and couldn't find the bug. Would have to start over so skipped. Messed up my approach to B.

Looked like I might score zero for the round.

I checked the C, D, and E problems just in case one of them was easy. Bingo! Problem D was a very easy one hidden among the toughies.

So I end with about 1300 points for solving one very easy problem and screwing up another very easy and an easy. I really thought it was going to be a disaster of a contest after the first hour with nothing to show at all. Instead I ended up in the top 15%.

nice graph!

for Div2A,

My AC: http://www.codeforces.com/contest/624/submission/15794996

WA : http://www.codeforces.com/contest/624/submission/15793258

Why printf fails?

Either use

`cin`

or cast to`double`

when working with`long double`

. It's known problem on Codeforces.During the contest, I received an announcement saying that my B was hacked, but it wasn't.

What could it be?

I liked the contest, congratulations.

Also I want to say thanks to Codeforces

team, andcommunity, for making this a nice place to study and improve. This was my 50th contest and I got (+51) in my contest rating :DSo I did the Div2A in the practice room and got WA when just using "cout" for the answer. Got AC with printf(".6lf").

I read the statement carefully and it says if "absolute or relative" error does not exceed 10^-6. So why is the printf needed instead of just cout? I would think the extra digits after the 6th digit would be less than 10^-6 and thus OK within absolute error tolerance.

Should it be both absolute AND relative error < 10^-6? Or is the example about checker saying that for results < 1 it will use relative error?

I think you should use statement like: cout << fixed << setprecision(10) << ans << endl;

Well I know how to print the answer to get accepted, but I am asking WHY it has to be printed to exactly 6 decimal places, because the statement says "relative or absolute" are both OK.

If you don't output at least 6 digits after decimal then your output can fail both the conditions (i.e. relative and absolute both). Just like if you see your submission with cout, correct output is 2.6666670 and your output is 2.666670. The relative and absolute both the errors are >= 10^-6.

Oh wow, I didn't count the number of digits with "cout" properly and didn't notice that it only outputs 5, not 6. Thanks!

And then, in practicing problem Div2B I didn't accumulate the sum with long, so that failed also on the first submit.

So I failed both A and B in practice. I was going to take part in this round but wasn't able to, so I missed a great chance to fail two easy problems in a Live contest. Now my rating is artificially too high. This is terrible!!!

The biggest mistake to make during rounds is to not read the problem carefully. Could not solve B because I missed I can make those operations only once. Any ideas about the solution if I could use them infinitely?

Haha glad i wasn't the only one. The only solution i was able to come up with is n*sqrt(max(a_i)): go over all the possible divisors up to sqrt(max(a_i)) and for each number a_i, calculate if it's best to delete this number (we can do deletions infinitely so we don't need to care about contiguous segments) or to change it to be divisible by the potential divisor. At 30 billion such operations this is too slow for the given time limit though. We can improve this by taking only into account prime divisors, which brings it down to at most 3 billion operations, which is also too slow, but getting close at least.

Why not primes above sqrt(max(a[i]))?

Please clarify your complexity analysis.

I think it‘s a bit difficult for me,but anyway,I think it's a great round.

wat

how is this possible

i don't even

Any ideas about Div2 E? I passed 8 pretests and then got stuck at 9. I don't know if my idea is totally correct :/ or there could be some mistake with the implementation :( but as it is so hard, I think an amateur like me obviously can't solve it. So, I guess I passed the 8 pretests submitting totally wrong code :/ anyways, ideas please? I have mu exams going on so I don't wanna check the tests which failed me right now. Will do it 2 days later. Meanwhile, please help :)

Why have ratings been reset ?

I love mustard