Привет, Codeforces!
4 февраля, в четверг, в 20:05 MSK состоится AIM Tech Codeforces Round.
Раунд подготовили для вас сотрудники компании AIM Tech: Kostroma, riadwaw, yarrr, ArtDitel, ValenKof, bobrdobr, agul, gchebanov и zeliboba. Раунд пройдет во время Петрозаводских сборов, спонсорами которых наша компания стала в этом году.
В каждом из дивизионов участникам будет предложено пять задач и два часа на их решение. Разбалловка будет статическая.
Мы постарались сделать задачи проще, чем в прошлый наш раунд, но не менее интересными. Окончательная разбалловка будет опубликована прямо перед раундом, но сразу сообщу, что сложности задач C,D,E первого дивизиона отличаются меньше обычного, поэтому рекомендуем сначала прочитать их все.
Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, координатора задач Codeforces Глеба Евстропова (GlebsHP) и Марию Белову (Delinur) за перевод условий на английский.
Наша компания занимается проп-трейдингом, ключевыми понятиями в нашей работе являются big data, low latency и high frequency. В нашей работе важно алгоритмическое мышление и умение писать эффективный C++ код, поэтому у нас работает много спортивных программистов. Чтобы придумывать hft-стратегии нужно обладать хорошей математической интуицией и умением подходить к задаче с разных сторон, поэтому их созданием в нашей компании занимаются в основном олимпиадники-математики. В свободное от работы время мы участвуем в разных соревнованиях по программированию и не только, вместе ходим в походы и путешествуем. Прочитать подробнее про нас и наши вакансии можно на сайте aimtech.com. Можно отправить нам резюме через эту форму, даже если вы не участвуете в раунде.
Всем удачи и высокого рейтинга!
P.S. Для участников петрозаводских сборов в пятницу 5 февраля в 19.30 вечера будет организован фуршет в Пауланер Бройхаус.
Разбалловка
div2: 500 — 1000 — 1500 — 2000 — 3000
div1: 500 — 1000 — 1750 — 2000 — 2250
P.P.S. Авторское решение div2A имело погрешность 5e-7, поэтому мы решили пореджаджить эту задачу.
Будем надеятся, что либо ваш фуршет закончится после 11, либо в Пауляйнере в это время можно будет поесть обычным порядком. А то ласточка приезжает только в 22:55
Я думаю, что мы будем там до закрытия, но кухня принимает заказы до 23:30, так что лучше сначала зайти к нам, а потом заселяться ;)
В прошлый раз вроде успели даже после заселения
I hope that the all problems will be more interesting;)
GL & HF
В последнее время всё больше раундов проходят под знамёнами IT-компаний, что не может не радовать, учитывая уровень и качество задач этих самых раундов
Всем удачи! :)
А есть какая-то связь между Aimtech и Wunderfund?
Это разные компании, если ты об этом спросил.
Спросил, потому что вы раньше назывались Aimfund, а по описанию обе компании очень похожими вещами занимаются.
Да, у нас сменилось название.
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.
А можно вместо прикрепить файл, сделать ссылка на резюме (опционально)? Это намного удобнее на самом деле. О вы проводите hftbattle, случайно заметил пост. Для многих будет интересно, думаю стоит закрепить в посте.
Про hftbattle будет отдельный пост. Пока можно оставить свой email через форму на сайте
Про него будет отдельный пост, когда назначим официальную дату начала.
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
сложности задач C,D,E отличаются меньше обычногоРечь идет о первом дивизионе?да
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
Здравствуйте, подскажите пожалуйста, какой дивизион для более слабых? Второй, как я понял? В первый не пустило.
И всем удачи :-)
Конечно Div 2.
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.
Что за фигня — я задачу B даже не сдавал, а пришло сообщение что мое решение B взломали?!
Сложный контест для div1
And here is when I hack Um_nik ! :)
You're welcome :)
Thanks for this
Невозможно сломать вообще, сайт тупо по 5 минут открывает чужое решение( Стратегия со взломами вообще невозможна при такой обстановке, нужно как-то решать этот вопрос.
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 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 a1, (a1 - 1), (a1 + 1), an, (an - 1), (an + 1) as possible GCDs. Trying all the possibilities should be easy enough.
I didn't consider cases for an only for a1 :(
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 pi denote the probability that we've already caught the i-th person. The probability of winning right now is p1·p2·...·pn. For each i we can consider ri — 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:
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 :(
На чем ломают Сdiv2?
Я на этом тесте
Ответ No
Div2 B hack:
Why So Many Ones?
3 1 1 1
is enough
в Б катит динамика dp[i][j][curGcd] = мин стоимость если мы рассмотрели первые I чисел, их НОД был равен curGcd, и j ==0,1,2, в зависимости от того, мы не удаляли отрезок, щас удаляем, или уже закончили удлаять. Ну и там памяти не хватает поэтому по слоям надо писать?
gcd можно рассматривать только из простых чисел взятых из факторизаций a[0]-1,a[0],a[0]+1, a[N-1]-1,a[N-1],a[N-1]+1.
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.
Скажите пожалуйста, как во втором примере в B div 1 получился ответ 7?
Удаляем 13, меняем 11->10, 6->5.
О, точно, спасибо!
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.
In E, my solution was binary searching the answer . To check if that answer is possible or not, I found a upper bound of y for every y[i] , i<=N . Then Finding the corresponding points on x-axis , I checked if that answer is possible or not. The, I rotated the axes , and checked for the answer again . The minimum of those answers are the desired answer .
Is the idea wrong ?
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
accais 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.
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
Получил по C wa17 на претестах. Думал, что решение какая-то шара (а оказывается похоже на авторское) и кинул еще две посылки "на авось". Первая прошла, а вторая получила wa1 по B (не туда отправил). Порадовался, что первая зашла и не стал посылать вторую (разница в бинарном поиске >= и >). В итоге wa40 на сис.тестах, а вторая верная. Обидно :( А можно было в одном решении записать сразу оба варианта и выбрать оптимальный... Не стать мне красным :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 fofao_funk; 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 106, then obtaining the answer in long arithmetics), or using the next trick: take
and represent each coefficient as ai = bi·M + ci, where ci < M and bi < M. Then the multiplication of polynomials with coefficients ai is reduced to 3 or 4 multiplications of the polynomials with coefficients bi and ci. There coefficients are less than M, 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
cinor cast todoublewhen working withlong 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?
Я синий! Эксперт! Еще месяц назад я был безнадежным новичком, а сейчас поднялся на 3 уровня выше) Когда была возможность временно сменить цвет хэндла, я выбрал специалиста — это был предел моих мечтаний на ближайшее время. Но сейчас я превзошел все свои ожидания) Невероятно всем благодарен. Удивительно, как многое для меня стало значить какое-то число на каком-то сайте) З.Ы. У меня достаточно интересный график.
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
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?
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.
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 think div1 problem C has a little bit weak testcases.
My 15925572 code got accepted even though I think it has some mistakes.
Maybe some hero could add more testcases or correct me.