Привет, Codeforces!
Я рад анонсировать, что компания Rocket Fuel Inc. снова будет проводить соревнование Rockethon! Контест подготовили сотрудники компании Эльдар Богданов, Антон Ломонос, Лаша Лакирбая, Александр Рафф, Никил Гоял и я, Евгений Соболев. Мы надеемся, что каждый из вас найдет для себя интересные задачи на контесте и от решения этих задач вы получите не меньше удовольствия, чем получили мы от их подготовки. Как и в прошлом году, лучшие участники получат ценные призы и футболки. Помимо этого, Rocket Fuel заинтересован в рекрутинге людей после соревнования, поэтому, пожалуйста, заполните простую форму при регистрации.
О Rocket Fuel
Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!
We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.
Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).
Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.
Мои впечатления
Около года назад я зашел на Codeforces и увидел объявление о Rockethon 2014. Моей первой мыслью было: "Круто! Еще одно соревнование от крупной компании!" Я поучаствовал, выступил достаточно неплохо, после чего со мной связались рекрутеры Rocket Fuel и назначили несколько собеседований. Я прошел собеседования и теперь я здесь, в Rocket Fuel.
Работа в Rocket Fuel — это отличная возможность изучить продвинутые вещи в software engineering, так как вокруг работают много умных людей, которые всегда готовы делиться своими знаниями. Конечно, наша деятельность не ограничивается только лишь написанием кода — мы играем в баскетбол, футбол, настольный теннис. Я приглашаю каждого из вас принять участие в соревновании и буду рад услышать если вы задумываетесь о трудоустройстве в Rocket Fuel.
Обзор соревнования
Контест начнется 7-го февраля в 20:00 МСК.
Продолжительность контеста — 3 часа.
Тестирование посылок будет производиться сразу же после их отправления и вердикты тестирования будут немедленно показаны авторам посылок.
В контесте будет 7 задач, каждая из которых может иметь от одной до трех подзадач. Каждая подзадача будет стоить некоторое фиксированное число баллов. Если несколько участников наберут одинаковое число баллов, выше будет стоять тот участник у которого будет меньше штрафное время, вычисляемое аналогично ACM-системе.
Призы
Три лучших участника получат следующие призы:
1) IPhone 6 (16 Gb)
2) Участник может выбрать Apple Watch или Samsung Gear S
3) Участник может выбрать Apple Watch или Samsung Gear S
Лучшие 150 участников получат футбоолки Rockethon с оригинальным дизайном соревнования.
Если вы не можете принять участие в соревновании, но заинтересованы в трудоустройстве в Rocket Fuel, мы будем обрабатывать резюме отправленные через специальную форму.
Would it be rated ?
Yes, it will be rated.
is this fuel shop? xD
You might want to move it, it intersects with COCI. In general, if you're planning a contest one weekend ahead, chances are high that it intersects with something.
Thank you for your feedback, we have moved our contest by 1 hour.
would you delay it for another half an hour or at least a quarter? i mean it's really hard to do contests 6 hours nonstop, we would like to have a pee break or something
You're joking, right? 6 hours nonstop?
yes i am joking :|
It will be a rated div1+div2 contest... This fact should give a huge motivation to participate in a contest for most CF users, unless MikeMirzayanov changed rating calculation after Good Bye 2014 :)
If I happen to get red during this contest then maybe it will not feel like an achievement :(
That's cute :)
Sorry, del
Where are your engineering offices situtated? Your site gives quite a long list of offices but I suppose not all of them are engineering offices. The form you provide on CF seems to assume US to be the location for the candidates, is it correct?
Currently, the only office where the software development takes place is our HQ in Redwood City.
America: 9AM Vietnam: 0AM i'll go to sleep at 3AM :v
Are there any internships being offered too?
Most probably yes. I work at Rocket Fuel and I was told about a week ago that we're planning to hire interns for summer.
We do offer internships but we do not sponsor visas for internships so if you are not in the US you will be responsible for providing your own work authorization.
It's 0am in my country, another sleepless night :D
ACM ICPC Rules?
like acm format？
For registration CV is Necessary. But I have Not Prepared CV yet :D
If you are not planning to apply to Rocket Fuel, you do not need a CV. Please, wait some time for regular registration for the round.
Thank You Very Much Sir
Will the contest be according to ACM rules or the codeforces normal round rules ?
"Contest Overview" section of the announcement has already answered the question.
A typo in "About Rocket Fuel" section : "commercial banks, telecom, commercial banks"
I'm very sorry, but what is TBD?
One of the first results of the search is some torpedo bomber :
Douglas TBD Devastator
Of course, I'm not against the idea of owning a plane, but it seems a little bit strange :)
Maybe it's "To be decided"?
Usually "to be done".
"to be defined" i guess
To be determined wiki
"To be declared" :P
To be Ferdinand de Lesseps.
Nice :)
thanks all and hope for nice rating :)
I have a question :)
rated?
Yes, it will be rated.
Thanks so much :)
ну ок
In the registration page, I cannot upload my CV. Is there any workaround to solve this issue?
UPD: It's worked now :D
+
Are you sure that the file is non-empty?
Yes, I'm sure of it :)
Thanks. I've found some issue on contest registration page (not separate apply page). I'll fix it ASAP.
UPD: Fixed. Thank you again!
Thank you for the great work, Mike :)
Backup standings this time :)
I'm very sorry, but what is CV?
http://bit.ly/1F57t42
http://bit.ly/1Cv4Zha
Problems will be sorted in the order of the difficulty?
Each problem will be worth a fixed amount of points and you'll be able to see these points. And these points are our estimation of the difficulty.
Штрафное время будет учитываться за первую или последнюю успешную посылку по подзадаче?
Штрафное время будет учитываться отдельно по каждой подзадаче.
Вы, кажется, не поняли вопроса. Вопрос, как я понял, касался прошлогодней тактики сдать быстро подзадачу с меньшими ограничениями и потом на ней проверять на правильность решения дальнейших подзадач, потому что по прошлогодним правилам попытки после первой зачтенной не учитывались и не добавлялись в штраф. Поэтому вопрос — как считается штрафное время, если продолжать отсылать решения по уже сданной подзадаче?
Да, точно, спасибо! Конечно, после первого OK по конкретной задаче за эту задачу нельзя получить больше штрафа. То есть так же, как это было в прошлом году.
Может, тогда стоит запретить делать посылки по уже сданным задачам (как это делается, например, на IPSC)? Так будет и нагрузка на сервер проверяющий поменьше, и задачи решать более "честно" придется. Правда, не уверен, что это сейчас поддерживается на платформе Codeforces.
а в чем "не честность"? казалось бы, если все в равных условиях, значит честно..
A necessary Problem
Rated? ;;)
did you read the first f ing comment?
Yes,
Rated?
ok then it's unrated :|
No, you are wrong it's rated :-"
Are you sure you've read the first comment and the first reply to it? If so, why doesn't it answer your question?
http://mirror.codeforces.com/blog/entry/16140#comment-210444
Shhh
I want to share an idea, That if there is no limit can improve ranking.
If you want to solve a problem for a large N directly you think that increasing N doesn't matter in your solution, submit it to the large N (before testing for small N) then if you realize that its not good enough or some serious bug you can get the small N without penalty.
PS: It work in case you have a brute-force solution for small N, this used to work in Rockethon 2014
You can use this in case there are some not-so-big test in the large subproblem to verify correctness. However, once your code is too slow, you will have no idea whether it is because of big N or the solution itself. Anyway, it's not the big deal if you already have a brute force solution. I would just submit it for small tests and use the small tests to double check my solution for large test (I guess this works since problems are in ACM style).
Actually this was my fault in Rockethon 2014 I missed the big N and also got penalty for small N.
I took the risk like "Okaye I will get the three sub-problems at once, no waste time for brute-force" .
Yes, In case you want to go step by step this is nothing.
Sponsor visa for full-time job offer ?
Yes, our company will sponsor visas for full-time job offers.
"The ties between contestants with the same score will be broken by penalty time which is computed similar to ACM scoring system." — from this phrase I conclude that each wrong submission will be penalized with extra 20 mins, while since this is an individual contest and shorter than ACMs I think that GCJ penalties (4 mins or something in between) will be much better. Is it possible to apply this?
We did the same scoring system last year and it wasn't bad, so I assume that it is completely fine to use it again this year.
On second thought, if someone solves task with 2 subtasks then time is doubled, so 20 mins penalty has lower impact.
Obviously, one always can find some advantages and disadvantages in any scoring system. But in general almost all of them are relatively fair.
Your bets, will this contest beat Good Bye 2014 by number of participants?
I bet it will
It did
How do the subproblems work? Do we need to make a separate submission for each subproblem?
Each subproblem can be seen as single problem. Yes, you need to make a separate submission for each subproblem.
I see, thanks!
At first : WOW Iphone 6 , cool :D
Later : Damn it tourist has registered.
As you expected, tourist got the iphone6~
You mean Gold version of Apple Watch? No body's gonna be first :D
5
rated? (:
will "WA/RE/TL/etc on test 1" count?
Because it is ACM style, so i guess they will count.
On Round #289 I've made a WA1 submission and it wasn't counted.
How do we check whether a participant has registered or not from the list of all registered participants?
The most simple way I know is to add him to friends and open Friends Only list.
Add them as a friend (by click star next to their name in profile). Then in registration click the friends tab and you can see all of the people you have selected as friends that have registered.
You can add him as your friend and then check it. nic11 and poikniok were faster ..
6200+ registrants, sounds great ^_^
It didn't sound that great when we had that queue :D
3 hours before the end of registration! O_O
Since it's ACM-ICPC format, there's no need to put people into rooms (because there are no hacks) and thus there's no reason to stop accepting registrations after the contest starts (except that the late participants lose the time missed).
6000+ registrants and full feedback. I'm pretty scared of what the queue will look like, hopefully it won't get stuck :P
Edit: No offence, Mike, but it was kind of obvious that there would be flood of submissions? If you can't afford a good enough system to get so many participants then either limit the participants or don't accept hosting competitions for companies, as now they're getting bad advertising from this contest...
Edit2: At least it was fixed fast enough to not have a serious impact on the results :)
My task A (which submitted 10 minutes ago) haven't been judged. :(
Or we could have a tougher first problem to begin the contest with.
Что происходит? Мое решение уже 12 минут в очереди.
Why judging is too slow?
here's my guess:
1) Since it's ACM-ICPC format, it needs to run all the system tests instead of pretests.
2) The number of participants is simply a lot.
17 minutes in queue for me... Also what happened to problem D1 and D2? It says "Statement is not available." in my computer...
I guess you should make it unrated. We have no chance to check if we are correct or not.
I've found mistakes in my code and resubmitted my B1 and B2, and my A is still "in queue"!
The site is very slow... can I just safely assume that it will be unrated and go to bed? :(
I have decided to go to the bed anyway :D
I have uploaded my solution nearly more than 10 minutes ago still it is in queue waiting for my submission result.I am very disappointed with that.
Год назад была точно такая же ситуация. В этом году не сделали ничего, чтобы ее предотвратить. В таких условиях смысл и удовольствие от контеста теряется.
Прошу прощения. В этот раз изнутри совсем другая ситуация получилась. Просто снаружи все выглядит похоже. В данном случае на пределе стал работать головной nginx, а сервисы Codeforces нормально себя вели. Запас в requests-per-seconds есть не менее двух раз, тут оказалось дело в количестве concurrent sessions скорее + возможно в том, что он еще и статику отдает (хотя там все кэшируется).
Такое понятно как тестировать и понятно что с этим делать, я думаю, что этот issue будет скоро закрыт.
Тяжело побивать рекорды — к сожалению и такие неожиданности случаются. Но я вам гарантирую, что работа ведется ежедневная, в том числе и над подобными issues.
Еще раз приношу извинения. Сам переживаю сильно.
Shit, I haven't noticed for 40 minutes that my A hasn't been submitted because of server fault =(
I request the organisers to please make this contest unrated being full of unexpected delays and problems.
Guys, I'm sorry for technical issues. This time they came from unexpected side. Codeforces services work fine, but nginx (or something else in front of Codeforces) doesn't work well. I'm worry about the issue very much, the more that being sick for a long time I did really good testing and preparation before.
Good news are that it looks quite straight-forward to diagnose it and fix. I'll do it ASAP.
Sorry again, I guarantee you that a work to improve the system is doing every day.
Thank you sir.So is the round unrated?
It should be rated.Codeforces was unavailable only ~1/6 of contest time,its usual for cf.
Amazing! I have seen that at the same time there are at least 50 submissions judged! (Because there are only 50 submissions in one page...) How fast!
That awkward feeling when you've found a lot of patterns, but still did not solve the problem.. :|
I hardcoded B1 . saw all the permutations but couldn't figure out any pattern :(
The same thing happened to me for quite a while on B :P
The real pattern is amazingly simple: start with an empty permutation, now put 1 in either end of the permutation, then put 2 in either end of the remaining blank space, then 3, ...
:o
Oh, that's why cntn = 2n - 1! Wow, cool!
Is it permutation B2? Because I had that moment too :)
A pattern was floating in front of my minds. But could not code it. -_-
This feeling is probably the worst.
Расскажите пожалуйста как решать задачи на мат. ожидание... Или что можно почитать по этому вопросу? (википедия не помогает :()
Всегда (по крайней мере пока что) мне хватало того, что матожидание некого числа — это сумма его во всех исходах, поделенная на их количество.
Не-а. Забываешь умножать на вероятность исхода. А исходы могут быть неравновероятными.
Решение задачи C у меня такое. Пусть x — возможный ответ. Перебираем значения x от 1 до 10.000. Считаем вероятность того, что ответ (т.е. второй максимум) будет равен x, пусть это P(x). К математическому ожиданию добавляем величину x * P(x).
Это и есть определение математического ожидания.
Осталось только научиться считать P(x), это нужно объяснять?
А как нормально считать P(X)? Я перебирал победителя + множество, кто поставил ровно x (при этом считая, что при равной ставке выигрывает фирма с наименьшим id). Получилось 40 строк кода, отсутствию ошибок в которых я очень удивился.
Я так перебирал — для каждой компании есть три принципиальных варианта — поставить меньше x, поставить ровно x, поставить больше x. Итого для n компаний у нас получается 3 ** n вариантов.
Переберем их все, это не больше 243. Их них оставим только те, которые подходят — это варианты, в которых ровно одна компания поставился больше x и не менее одной компании поставили ровно x или вариант, когда хотя бы две компании поставили ровно x и ни одна компания не поставила больше x.
Тем самым мы про каждую компанию определили, сколько она должна поставить (больше x, ровно x, меньше x). Далее просто — перемножаем вероятности этих событий.
Вот код, он у меня несложный получился, но не очень короткий: http://pastebin.com/cZLhU44z
Можно считать вероятность того, что второй максимум больше либо равен х (по ней легко вычислить вероятность, что равен)
P(max2 >= x) = 1 — P(все ставки меньше х) — P(одна ставка больше или равна х, остальные меньше).
P(все ставки меньше х) — просто произведение. P(одна ставка больше или равна х, остальные меньше) — сумма n произведений.
Пользовался только тем, что Мат. ожидание = значение * вероятность
Для C и G1 достаточно было знать определение мат.ожидания. Ну и влоб его насчитывать.
Aaaaand the IPhone is gone...
How to solve F?
F was max flow problem.
If you solved it did you do anything special with the max flow? I got TLE on test 92 all contest on it and I don't understand why.
I used Dinic max flow. It was fast enough without any optimization.
There is O(n6) solution. Will be posted in editorial.
Same complexity here. Maximum 2 * N^2 push-flows ina graph with O(N^4) edges which yields O(N^6) solution. Guess the time limit was a little to tight for the general max-flow.
I looked to your code, and I see that your solution has complexity of O(N8). You are calling dfs with complexity O(N4) N4 times.
Oh, sorry. Yep, that's the problem. Thanks a lot :-)
I think you can get rid of binary search here. Instead of binary searching the answer you can add the edges in the order of their increased cost until you get the desired max flow value. The only key difference here is that every time you add an edge you do not calculate max flow from scratch, that will obviously TL. Instead you resume the previous computation of max flow (which can be done quite natural if you use Dinic algorithm for max flow). That should be plain O(N6) with no log factor.
Actually it is O(N8), but the idea is right.
I'd say it's O(N6), I just didn't give away all the details :) There are some tricks there regarding when to run DFS, when the max flow will be increased, etc.
Then your solution is right. Still, I think, you will need to try more than that to get Java solution. Unfortunately, TL for C++ was too big, and TL for Java was too little.
Sigh...When I read this problem statement and realized it can be solved by maxflow, it was 5 minutes left... I spent(wasted) too much time on G3. I thought of the matrix all the time.
Why made the example for task D so weak?
I thought "a b LEFT" means b is the left son of a, and stuck for over 1 hour..
"System" tests (at least for D1) were weak, too...
My brute-force solution passed... even though it stated there is solution for the following input:
(which is clearly impossible as 3 would have to be both in the left and right subtree of 1).
same here lol, the statement of task D is really confusing...
yea, thought every node suppose to have 0/2 child... forgot the definition...
Can someone tell me what's wrong with my solution got G1? Thank you!
http://ideone.com/x0oF5P
Can you post link, not full code there?
Ok changed. What is wrong?
It is a problem when you post your code like that because it takes a lot of space and disrupts the discussion here, but I would say that -72 is a bit overreacting.
UPD: I'm sorry... I thought you were asking what's wrong with posting source code like that; you were asking what's wrong in your solution :)
The first problem — K may take a value of 4, but the second index dp [1000] [4] can not. Second — do comparison "dp [x] [k]! = 0.0" is unsafe. Read about comparsion of doubles. Finally, you didn't calc inv[0] — inversion in start permutation.
My freaking English better than this solution, sorry.. Why dont write easy dfs without any states and get 3 points?
Контест будет рейтинговый?
То чувство, когда после системного тестирования в самом конце ты становишься 151ым вместо 150го...
UPD: А потом ты еще понимаешь, что твоя D1 работает и на ограничениях D2...
What is wrong with my code for problem C? Kidding, can someone tell how to approach it? :P
For each amount of money that the company who won has to pay, you calculate the prop by using bitmask.
Let fixed the amount of money x. 1. If the winning company bid x unit. Then there has to be at least another company bid the same x. 2. If the winning company didn't bid x unit, the company had to bid higher, and there are also at least one company bid the same amount x.
Here is my sol: Code
For each possible value v, compute the probability of: 1) [1 company bidding more than v] * [k companies bidding exactly v] * [n-k-1 companies bidding less than v] 2) [p companies bidding exactly v] * [n-p companies bidding less than v] (where p >= 2)
The probability that the value to be paid is v is equal to 1) + 2).
In order to compute 1) you can iterate over all companies (to choose the one that bids the maximum amount) and inside that iterate over all subsets of companies (ignoring the ones that contain maximum bidder) to pick the ones who are bidding exactly v.
To compute 2) you simple have to iterate over all subsets of companies that contain at least two companies.
The only primitives you need to compute 1) and 2) are p_bid_more_than(company, value), p_bid_less_than(company, value), p_bid_exactly(company, value) which can be computed in O(1) given L and R for each company.
You're a mean minion :P
Yep :P
What's B2 TC #20?
I suppose smth to get rid of solutions O(n!), just huge amount of permutations.
I've WA, not TL, so interesting why. I tried to find a case, but didn't.
UPD. Ok, now I understood: I used to convert too large number to its binary representation using "sprintf" function. Using "bigint" module didn't helped here.
Ideone gives me the correct answer which equals to that Codeforces expect. 9765553
probably something related to long long int. I got WA on #20 and it went away after I changed "m" to long long int.
Yes, I got WA 20 first and then fixed. The problem for was
long longliteral type. I did a bit shift1 << lengthwhile it is supposed to be1LL << length.I'll understand if this is asking too much, but is there any chance shirts could be offered in Tall sizes? Some stores have them, and they're basically two sizes longer. So a medium tall would be roughly M in width but XL in length.
We inquired about this with our manufacturer. Unfortunately, the whole batch has to be either in normal or tall sizes so we'll stick with normal since this is the preference for most people.
Alright, thanks for checking. I have never seen tall sizes be an option at special events, but I hope to see some eventually. Great contest! :)
Ничем хорошим это не могло закончиться
Могло.
I'm waiting to see what's the magic to solve G3 with complicity like O(n3log(k)), but I saw this:
In tourist's 9761881.
The possibility will be stable.... I tried to find the matrix A for dp(n-1)*A=dp(n).... But failed.
Yes, I know the reason that could pass is "The possibility will be stable".
But I still want to know if it is the intended solution (I thought is is not) — if yes, then that's too crazy. :P
This observation is a part of intended solution. But the complexity of intended solution was O(N2·K) (with K capped at something like 10N). Unfortunately, all of the competitors who solved it during the round got AC with much slower solutions.
Does our new rating depends on the previous contests rating?
Yes.
Got WA on D1 and D2, because of
a == bcase.Very sad.
Can somebody explain me in detail problem C and E?
Task C.
For every guy a, for every guy b ( b != a), for every number (bid) k from range of guy b:
What is probability that a is a winner and b has second place with a bid k? It is easy if you don't have problems with draws. We can say that with some equal bids a guy with lower index is a winner. With this trick we have easy implementation. my code
у меня для того, что бы зашла задача C нажну было написать typedef double LL...
My solution for D2 was judged as RE because of stack overflow. I thought stack overflow would result in ML, not RE. I tried the same test locally with
-Xss64M, and it worked fine. It's strange that you have 256 MB of memory but can't use it for stack.I can hardly name a resource where stack overflow causes ML, but not RE.
Had the same problem. Looks like java commandline was different from described here.
In order to solve this problem in java you need to construct inorder order iteratively instead of recursively. It is interesting that you don't actually need to change the main algorithm of constructing the tree; it can remain recursively.
I know that, that's how I solved it :). But recursive inorder construction should work too if -Xss64M is set.
Why did my submission for G1 print out a crazy number?
http://mirror.codeforces.com/contest/513/submission/9761884
Because MinGW. It cannot print
long double, you should convert it todoublefirst.Thank you!
You can use "cout" for long double...long double is not prepared in printf/scanf
Thank you!
I want to suggest that penalty time for problem should be scaled proportional to the number of points it costs, because now if you solve simpler problems you get much more time spent, than if you solved more difficult problems.
You also get more points and points are the main ranking factor. If two people get the same number of points, then you can't say one was expected to take more time than the other.
Or do you mean the case where you start with hard problems?
I think he means in case of a tie, person that solved 4-point problem has a huge advantage to person that solved 2+2.
But then the 4-point problem should be that much harder to do. Difficulties don't scale linearly with points, so the time needed to solve a 4-point problem may be 10 minutes, contrary to 1 minute for the 2-point problem.
I'd say it's actually the opposite, when solving hard problems gives you a greater penalty than solving a lot of easy ones, just because the easy ones are so easy. It's similar to the problem with point values for hard problems dropping too quickly with standard CF scoring.
And I'm not accounting for subtasks here, since that question wasn't raised (but it is an artificial fix and messes things up).
Will there be an editorial?
Yes
There's one here http://mirror.codeforces.com/blog/entry/16260
4th again. Argh
Is there any internship opportunities?
Here
thx
I wrote my address a moment ago, not recognizing that the information disappeared due to the Black Day of Codeforces. Can I still get a T-shirt?
Same here.
The participants eligible for the T-shirt will need to fill out a separate form (address, phone, T-shirt size) which is not ready yet.
[deleted]
Has anyone received his/her t-shirt yet?
Will there be Rockethon 2016?
why soo hard