By zeliboba, 5 years ago, translation, ,

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

Editorial

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

• +298

 » 5 years ago, # |   +15 I hope that the all problems will be more interesting;)
 » 5 years ago, # |   0 GL & HF
 » 5 years ago, # |   +18 Why does it say "February 22" when it actually is on February 4th ?
•  » » 5 years ago, # ^ |   +4 fixed
 » 5 years ago, # |   +77 It would be great to make one division contest like previous round :) I think that is more interesting for everybody.
 » 5 years ago, # |   -24 Interesting to watch Bus nearing to the white while he manages to solve almost the full contest xD
 » 5 years ago, # |   +15 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?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 5 years ago, # ^ |   +3 Okay thank you very much!
 » 5 years ago, # |   +23 No T-Shirts ?? Your past contest had 200 T-Shirts which was really awesome.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +24 Next time we are going send T-shirts again =) This round is created mostly for participants of Petrozavodsk Training Camp.
 » 5 years ago, # |   0 In fact I havn't received the T-shirts prized for AIM-FUND ROUND yet! :D
•  » » 5 years ago, # ^ |   0 Send me your tracking number.
•  » » » 5 years ago, # ^ |   0 sended.. :D
•  » » » » 5 years ago, # ^ |   +38 *sent
•  » » » » » 5 years ago, # ^ |   +50 forgive my stupid English :<
 » 5 years ago, # |   +10 difference in complexity between problems C, D and E may be less than usual in Div2 difference in complexity between problems C, D and E may be less than usual in Div1 C div2 = A div1, D div2 = B div1, E div2 = C div1 difference in complexity between problems A, B, C, D and E may be less than usual in Div1
•  » » 5 years ago, # ^ |   +1 div 1
 » 5 years ago, # |   -21 what is high frequency rating?
•  » » 5 years ago, # ^ |   0 Maybe your browser can't display it, but the word "frequency" is crossed out.
 » 5 years ago, # | ← Rev. 3 →   0 As far as I remember, your previous contest was very good.I hope this one will be better.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +91 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.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Agreed, but all problems were good at all.
•  » » » 5 years ago, # ^ |   +2 this contest was better very easy A,B,C and very hard D,E
 » 5 years ago, # |   -7 Be rated or not ?
•  » » 5 years ago, # ^ |   +28 If nothing bad will happen it will be.
•  » » » 5 years ago, # ^ |   0 thx
 » 5 years ago, # |   -16 Will it be a rated contest like division 2 contests ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 It's usual rating contest, except that it's prepared by us
 » 5 years ago, # |   0 Will the score obtained will depend on the time of submission just like any other round?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I believe this round should have the same rules as other rounds. See the last Aimfund Round.
•  » » 5 years ago, # ^ |   0 yes
 » 5 years ago, # |   -6 when I try to submit a code it says i'm not registered !!!
•  » » 5 years ago, # ^ |   +5 you must be registered before start of the contest. usually register is open 24 hours before the contest begin.
•  » » » 5 years ago, # ^ |   0 he/she registered in two contest before how could he/she doesn't know about this
•  » » » » 5 years ago, # ^ |   0 good question for his/her ! I must investigate more , next time.
 » 5 years ago, # |   +120 And here is when I hack Um_nik ! :)
•  » » 5 years ago, # ^ |   +43 You're welcome :)Thanks for this
 » 5 years ago, # |   +4 How to solve problem D div 2 ?Nice problemset !
 » 5 years ago, # |   +4 How to solve Div2C?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +22 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).
•  » » » 5 years ago, # ^ |   +1 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. 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.
•  » » » » 5 years ago, # ^ |   0 Lol yes, I actually just realized this too.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +2 My alternative solution: Obtain reverse graph. (not connected graph) Try to color it in with 2 colors when no edge is connecting 2 nodes with the same color If failed -> No solution. If colored, pick any color as 'a', other colors as 'c'. All non-colored nodes as b. EDIT: probably bad idea, got Wrong Answer on test 26 because I forgot to check that any two different colors are not connected
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Additionally, in step 2. you need to ignore nodes without edges, so they can be colored as 'b' in step 3.
•  » » » » » 5 years ago, # ^ |   0 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).
•  » » » » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 years ago, # ^ |   0 I had brute force solution, lol :))) Of course, it is named as "backtracking", but, anyway, it was too stupid. TL on test 15
•  » » 5 years ago, # ^ |   0 I am DIV2 too, check my solution.15811052
 » 5 years ago, # |   0 I knew How to solve E....If I had just 5 minutes more...
•  » » 5 years ago, # ^ |   -12 Same here. Fucked up on indecies (+/- 1)
 » 5 years ago, # | ← Rev. 2 →   +25 Can anyone give me an idea for B div.1 ? :'(
•  » » 5 years ago, # ^ | ← Rev. 3 →   +4 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: in first pass count best solutions for left prefixes in the second (reversed) pass get best solutions for suffixes and join with the best solutions for prefixes. 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 5 years ago, # ^ |   +5 +1 or -1 of left or right elements may also be present.
•  » » » » 5 years ago, # ^ |   0 Yes, that's what I did. I just forgot to mention it here. Thanks for pointing it out.
•  » » 5 years ago, # ^ |   +37 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.
•  » » » 5 years ago, # ^ |   +3 I didn't consider cases for a n only for a 1 :(
 » 5 years ago, # |   +5 Anybody got stuck too at Div1B — 9th pretest?
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +7 Solutions for Div1 D? Being solved way more than Div1 C for some reason, is there some easy solution?
•  » » 5 years ago, # ^ |   +20 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +38 Let p i denote the probability that we've already caught the i-th person. The probability of winning right now is p 1·p 2·...·p n. For each i we can consider r 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 winning a will change to where c denotes 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: the probability of winning in some turn is equal to the product of chosen values For fixed i the value of is decreasing as we choose this person again and again.
 » 5 years ago, # |   +10 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 :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 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 :(
 » 5 years ago, # | ← Rev. 4 →   0 Thanks for room 23
 » 5 years ago, # |   +1 Div2 B hack: 6 1 1 1 1 1 1 
•  » » 5 years ago, # ^ |   0 Why So Many Ones?3 1 1 1is enough
 » 5 years ago, # |   0 what is test 6 of div1 C?I think this the worst decision I make in my life choosing to solve C first!!
 » 5 years ago, # |   +151 Wow. You really can't make easy contests.
 » 5 years ago, # |   +3 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 !! :|
•  » » 5 years ago, # ^ |   +9 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 :)
•  » » » 5 years ago, # ^ |   +6 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 !!
•  » » » 5 years ago, # ^ |   0 actually A-> 3200 B->2500 C-> 500 . Not a good distribution.
 » 5 years ago, # | ← Rev. 2 →   +10 My hack case for C :4 31 42 33 4I even hacked my own solution with it (i.e. discovered it after locking -_- )__
•  » » 5 years ago, # ^ |   +1 Please, say that acca is the right answer :)
•  » » » 5 years ago, # ^ |   +12 Right answer is 'No' :D
•  » » » » 5 years ago, # ^ |   0 Now I have to go back to my drawing board :)
 » 5 years ago, # | ← Rev. 2 →   +3 Another contest with weak pretests.GL hackers!
 » 5 years ago, # |   +2 wow! so many failed C(div2). and the whole time i was trying to hack with B -_-
 » 5 years ago, # | ← Rev. 2 →   0 My hack case for A(div 1) C(div 2) :5 91 21 31 41 52 32 42 53 43 5bbbac or bbbca
•  » » 5 years ago, # ^ |   0 Both are supposed to be accepted right?
•  » » » 5 years ago, # ^ |   +3 In all testcases 'a' can be swapped with 'c' in the answer.
 » 5 years ago, # |   +68 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 :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +3 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.
•  » » » » » 5 years ago, # ^ |   +1 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.
•  » » » » » » 5 years ago, # ^ |   0 Sound advice.
•  » » 5 years ago, # ^ |   0 I'm interested in how you solved this for the a to z range. You can kindly inbox me a solution approach. Thanks.
 » 5 years ago, # |   +55 lol, in A we should use 'a'-'c' only... I should read statements sometimes.
•  » » 5 years ago, # ^ |   +24 I even asked a question, are 'a' and 'z' considered neighbours.
 » 5 years ago, # |   +80 Uhh... thank you! :D
•  » » 5 years ago, # ^ |   +10 Well share the submission link/username so that i know where to look incase i don't get something from editorial.
•  » » » 5 years ago, # ^ |   +7 15805017Actually I meant "hacker's dream" :D
 » 5 years ago, # |   +5 Hm, ok, that was fast!
 » 5 years ago, # |   +8 Woww. Rating lost after one contest = Rating gained after one contest! :PSuch stability. Much wow. :P
•  » » 5 years ago, # ^ |   +23 Please see gninrael; maybe you can be friends.
•  » » » 5 years ago, # ^ |   +17
 » 5 years ago, # |   +29 Aw...Fast system testing and fast rating changing .. good :)
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   +17 There are two possible solutions: the first is using Chinese Theorem (calculating the answers modulo some numbers about 106, then obtaining the answer in long arithmetics), or using the next trick: take and represent each coefficient as a i = b i·M + c i, where c i < M and b i < M. Then the multiplication of polynomials with coefficients a i is reduced to 3 or 4 multiplications of the polynomials with coefficients b i and c i. There coefficients are less than M, so the usual FFT in doubles is OK for them. For instanse, check Endagorion's solution.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
 » 5 years ago, # |   +3 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.
 » 5 years ago, # |   +5 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%.
•  » » 5 years ago, # ^ |   +27 nice graph!
 » 5 years ago, # |   0 Why printf fails?
•  » » 5 years ago, # ^ |   +6 Either use cin or cast to double when working with long double. It's known problem on Codeforces.
 » 5 years ago, # |   0 During the contest, I received an announcement saying that my B was hacked, but it wasn't.What could it be?
 » 5 years ago, # |   +4 I liked the contest, congratulations.Also I want to say thanks to Codeforces team, and community, for making this a nice place to study and improve. This was my 50th contest and I got (+51) in my contest rating :D
 » 5 years ago, # | ← Rev. 2 →   0 So 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?
•  » » 5 years ago, # ^ |   0 I think you should use statement like: cout << fixed << setprecision(10) << ans << endl;
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   +4 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.
•  » » » » » 5 years ago, # ^ |   0 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!!!
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 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.
•  » » » 5 years ago, # ^ |   0 Why not primes above sqrt(max(a[i]))?Please clarify your complexity analysis.
 » 5 years ago, # |   0 I think it‘s a bit difficult for me,but anyway,I think it's a great round.
 » 5 years ago, # |   +15 wathow is this possiblei don't even
 » 5 years ago, # |   0 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 :)
 » 5 years ago, # |   +12 Why have ratings been reset ?
 » 5 years ago, # |   -9 I love mustard