1 раунд FHC в этом году пройдёт в субботу 17 января, в 9 вечера по Московскому времени.
Эта и прочая информация есть здесь. Во второй раунд пройдут первые 500 участников, а также все, кто наберёт столько же баллов, сколько и участник на пятисотом месте.
1 раунд продлится 24 часа, и это будет не виртуальный контест, который ты начинаешь в любой момент в течение этих 24 часов, а полноценный 24часовой контест и это весьма неординарное решение. Понятно, что организаторы хотели, чтобы все смогли найти удобное время порешать задачи. Надеюсь, проблемсет будет таким, чтобы состав участников второго раунда не очень зависел от того, кто сможет порешать пару часов, а у кого — весь день свободен. Возможно, предполагается, что будет определённый набор задач, доступный для большого количества участников, гораздо большего, чем 500, но гораздо меньше, чем 500 человек смогут решить что-то ещё.
А штрафное время будет влиять на проход в следующий раунд в случае, если я набрал не меньше баллов, чем все люди в топ-500, но штрафное время хуже(сам я не в топ-500, допустим)?
"все, кто наберёт столько же баллов, сколько и участник на пятисотом месте."
I've been wondering — why do we need send output file AND source code? Why not only source code?
Probably for finding cheats out.
how can find cheats with outputs :-?
I meant code for finding cheats out (MOSS) and output because you are free to chose language.
If we send only source code, they'd have to run it to produce output to verify it, and that would inevitably limit the # of languages available (and increase implementation complexity on their side). This way we can use any language/tool we want at no cost for them.
So why do we need send source code? o.O
To make sure you didn't cheat! cuz otherwise you can just take someone else's sour code and use it to produce your output, they would have no idea whether you cheated or not.
what about sending a correct output with source code only print Hello World :D
You will likely get WA on that problem. They hopefully do some simple checks, plus you can be reported by the community. It won't be immediately, but somewhere in the process between preliminary and official results.
#pragma comment(linker, "/STACK:134217728") It works for Visual Studio.
These rules seem slightly weird. Regardless of problem difficulty, if there are at least 500 participants with lots of free time, the round turns into "advancers == people who solved everything". And if there are hard problems in the problemset, this gives huge advantage to people with lots of free time.
I wonder how do they come up with such rules, and did they have any meaningful discussion (because discussion would definitely make this problem obvious).
Well, last year it turned out fine. The 4 tasks weren't too hard, but they had some corner cases, so lots of people failed some. Still, everyone who did any 2 tasks (except for the easiest two, that wasn't enough) passed to the next round. Even just the hardest task alone was enough to pass.
Yes, either of the scenarios you mentioned are possible and is highly undesirable, but I hope that organizers are aware of that as well.
Yeah, our 24-hour rounds are a little bit different. They're kind of a stepping stone between the qualification round where you merely need to solve something, and the actual timed rounds.
The idea is to make sure that there's another round in which all time zones can compete comfortably. We aim to make the problems at a difficulty that doesn't require all of them to be solved to advance. Right now it looks like 60 or 75 points will be the qualification cutoff.
who can hack facebook in this round this is important
Whoever succeeds to hack Facebook during round deserves to pass to the next round, right? :D
Not really funny, no.
Not a native speaker, but I think you're missing some articles. Maybe this makes it better:
FHC Round 1 starts in January, 17, at t̶h̶e̶ 18.00 UTC.
See this and other information here. The top 500 finishers will advance to Round 2, as well as any contestant who gets the same number of points as the 500th contestant.
Round 1 will last 24 hours. This is not a virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is an unusual decision. It is clear that organizers want all participants to find a convenient time to solve the problems. I hope the problemset will be completed in such a way that how much time the participant can spend to solve the problems, 2 hours or 24, will not have a big impact to his result. Perhaps it is assumed that a certain set of problems will be solved by a large number of participants, much more than 500, but very few people will be able to solve something else.
(I will be glad to see the remarks about translation mistakes)
Translation is pretty OK though I'm somewhat puzzled by:
I thought it is usual way of conducting Round 1 over several last years (i.e. like Qual but 1 day instead of 3), but probably I'm missing something.
Some contests open for a long window, but each participant can only use a part of it. If I recall correctly, this is similar to USACO. The contest is open for around 72 hours to let participants choose their most convenient time, but upon starting, they only have 4 hours to solve the problems. Compare to this Facebook Hacker Cup round where the entire 24-hour window is also the entire time to solve problems.
To the experienced Facebook Hacker Cup people, what can we expect from Round 1 problems? About the same difficulty as a Div 2 round in Topcoder/Codeforces? Slightly more difficult than the Qualification Round problems?
Try the last year's problems for Round-1 yourself.
For me easiest of them usually seemed as hard as 3-rd problem of Qualification round.
Is it possible to submit the practise questions of old hacker cup contests?
yes
dis like me pls
Best of luck to everyone participating!!
Is participation in the qualification round required to participate in round 1? I didn't realise it would be held so early!
Yes, one solved problem in the qualification round is required.
А если мы здесь будем обсуждать перевод и неоднозначности условий, это будет нарушением правил?
UPD будет нарушением. в правилах параграф 12 гласит, что дисквалифицируют за такое: Communicating or publishing information concerning the content of the problems, or solutions to the problems, with other competitors, either directly or indirectly, before the end of the Round.
"content of the problems" — вроде это содержание задач. Мне кажется, имеются в виду только обсуждение по существу. То есть, пояснить, что в точности написано в условии можно, а переформулировать условие уже нельзя.
Я все же не стал бы с таким рисковать :)
Даже если то, что написано в условии задачи — это не content, то при попытке перевода можно неумышленно помочь.
..
I upvoted you for your avatar!
не могу зайти на олимпиаду :(
Уже могу)
как?
https://www.facebook.com/hackercup/problems.php?round=344496159068801
"Autocomplete":
правильно ли я понимаю, что инпут надо скачать за <<6 минут? А что если подключение к интернету очень плохое? Не хотелось бы получить 0 только из-за этого))
Я только что чуть не получил именно из-за этого:(
Да, надо скачать, зарешать и отправить обратно ответ с решением за шесть минут.
При посылке на часах оставалось 5 секунд...Почувствовал себя героем боевиков, который разминировал бомбу.
I upload both output and source of first problem
simultaneously when I tried to click submit my lab suddenly freezes with unexpectable behaviour from windows :( :(
I guess contestants with slow Internet connection already have some special feelings about those 20mb-large input files...
My internet downloads 20 mb in 18 minutes, I have a great problem... xD
Probably the best solution is to allow participant download encrypted input archive at any moment and display password when he starts 6-min timer.
This doesn't work for 18mb output, though. But I don't remember tasks with large output on FHC before.
For outputs, jury can just ask to upload some cryptographically secure hash of the output file.
If the output is (almost) unique.
But there still will be problems with different endlines, extra spaces, #'s etc
Ask for hash in 6 minutes and for the actual output in unlimited time. All such problems are trivially solvable in cryptography.
Nice idea, agreed
This is getting too complicated, at least compared to the solution: just don't ask for large outputs.
Are there even programming problems that require huge outputs and aren't extremely technical? I don't remember any.
Sure there are such tasks. For example these 4 tasks from my rounds on Codeforces:
321C - Ciel the Commander, 388B - Fox and Minimal path, 472E - Design Tutorial: Learn from a Game, 472F - Design Tutorial: Change the Goal
They are all about construct a valid solution, so the output is far from unique.
And, well, there is always a solution by cryptography: we can use interactive proof system -- I remember there are methods to transmit few bits to check if x makes f(x) = true for a function f.
You're misunderstanding. I'm asking about problems that require && huge outputs, not allow || non-verysmall outputs.
The difference being: your examples don't really go beyond 2-3 MB of output size (not even my code on 472F, and considering how sloppy I usually am when such constraints are loose...). That's roughly an order lower than 20 MB. 30 minutes vs 3 minutes of uploading? That's a huge difference.
Random query/update problems would be examples as good as yours, but that's not what I'm looking for. (Specific IPSC-styled problems aren't either.)
I was wondering about problems which have output size comparable to the 20 MB that were the problem this time. Even by including several large cases in a single input file, the point is that it's really huge per one execution of the code, and ideally, that it actually matters.
Oh, I see. But if there are 20 test cases there will be huge amount of bits to upload, right?
"Random query/update problems would be examples as good as yours" -- I will argue this a bit: for this kind of problem, we can just ask the hash of the output. But for my examples, this will not work.
I know this doesn't scale, but just a trivial zipping the inputs reduces the size from ~19MB to ~3MB. I guess organizers just didn't consider the possibility that someone doesn't have fast internet connection.
Judging by the bandwidth that the facebook mobile app needs, it's safe to say that facebookers ignoring the possibility of bad internet connections is not very unusual.
Yeah, we obviously made a mistake with the input sizes in this round, and it won't happen again. For this round we're letting people email us their solutions if the download doesn't finish in time.
We like iterating and trying new things, but obviously this wasn't a good choice :)
In the end everybody should end up with the right score though.
Does it mean just before the deadline (before an hour or before a few minutes), because I don't see any changes in the scoreboard and would like to understand that it's the wrong solution/answer, or the scoreboard hasn't changed yet. Thank u!
The manual submissions will be added to the scoreboard before the round ends. It will probably be close to the end of the round so we can compile the results and put them in in one batch.
Oh. Ok. I understand the situation. Thank u for your answer!
i got the input file when only 10 seconds were left & couldn't submit ultimately. i've sent feedback immediately but as this happened at the last hour, i'm afraid i will be asked to submit the source code before the round ends. what do i do? :/
How do you justify that a person using this "send-solution-by-email" was really not be able to download, not a person that exceeded the 6 minute timit limit and used it as a hack?
We have logs showing the download times, and we still require that people submit their source code which we can check manually.
I had to do the e-mail thing because really my lap-top couldn't download and process the whole input thing in time, after that I kept working on my pc, when I got the input file on the mail, I sent my source code and output, and screenshot of that job being done in 6 seconds. I really couldn't think of better way to prove that I didn't have something like WA or my program was exceeding time limit, hope this should be fine.
How exactly do you plan to use the logs to tell you if a contestant has tampered with the source code after the 6 minute timer ? By how much time has passed between the moment he downloaded it and the moment he contacted you ? That doesn't seem very reliable.
I have used File Input/output (freopen) in my manual submissions.does this affect my result while you use a batch to run ? by the way,after send my feedback request,i go out to have my dinner .....So i send my source codes a period of time later...does this affect?My source codes can finish tasks in several seconds,but the mail time is not following closely to the download time.
How to email to you my solution for task Autocomplete? The download process for me took more than 6 minutes. I submitted feedback a few hours ago but I didn't receive any answer!
I'm interested to know how you will compile and run the manual submissions for the last problem. Will you use the default stack size or you will increase it? Will you use the C++ optimizer or no? In all cases, it will be totally unfair, because many contestants failed to submit the correct output because they couldn't increase the stack size. And if you are going to keep the default stack size, what if who sent the solution manually was aware of this and prepared his machine to run with a large stack?
I wasn't affected by the stack size issue, and I wasn't affected by the the large inputs. And I might be qualified by just 60 points, but I believe this round should be canceled and make another one next week or so. I don't see any way to make it a fair round.
We're using a large stack, and I agree that this may give a few people points they otherwise would not have received. We'll be using the 500th place cutoff before considering manual submissions (should they be different), so anybody who would have qualified before considering manual submissions will still qualify.
I don't think this should be a huge concern to the eventual top 100 who will advance from Round 2. If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion). That said, we have records of all of these manual submissions, so if any such people do make the top 100 in Round 2, we can make sure they're well audited, and we can always make provisions for a couple more advancers from Round 2.
I know that a lot of people don't have ambitions for the top 100, but do have winning a T-shirt in mind (like me in GCJ every year). We can probably expand the range of competitors that receive T-shirts as well so nobody feels that they were beaten out of a T-shirt by some illegitimate competitor.
I definitely don't like the situation any more than you. It's a mistake we won't repeat. Running a new round introduces a different sort of unfairness in that we've already announced the schedule, and people may have planned for it. Adjusting the schedule would be unfair to anybody who would be unable to compete in a make-up round. Another alternative is tossing Round 1 and advancing everybody to Round 2, but that's just more false positives.
Good. I agree that this is the right thing to do at this point.
Any estimate on when the results will be up?
My current estimate is about 6 hours.
Do you plan to give T-shirts for top500 + top500 after excluding people with manual submissions?
And, anyway, it would be great to know stats about how much people got AC with manual submissions(and got 75+ pts).
There are about 725 competitors going to Round 2. I would estimate that we added about 100 ACs to Autocomplete, and about 40 for Corporate Gifting. The number of people that advanced only after considering their manual submissions is probably around 50-70.
We're increasing the number of T-shirts for Round 2 to 550 so nobody should feel that they failed to get a T-shirt because of somebody who sent manual submissions.
First of all, thank you for the problemset — it was good yet not ideal.
Secondly, if rules already changed so many times (more T-shirts, more advancers to the next round, manual submissions), why not to change it one more time and set manual cut-off to be equal to number < 75 points? Let's say, 40 points — then in total only 1944 contestants will advance.
Such decision will have several advantages:
Anyways, emails with final results were still not sent out so there's still possibility to make a lot of people happier and make competition more fair.
Thank you for the attention.
Hi Wesley, Just wanted to check if you guys had a chance to look into the logistics of the T-shirts yet. I didn't make it to round 3 but I qualified to win a T-shirt (a first for me!) and I am a bit too excited about it! :P
The T-shirt design was finalized yesterday. I'm not sure about the ship date at the moment.
It was unfair, I spent almost 20 minutes to download the input file, close to 1 minute to open the file plus running time of my code, resulting in a Time Exceeded.
Открыл Б. Получил stack overflow на тесте жури. Не смог исправить. Обида.
Для С++ (g++) под виндой (под линуксами размер стэка не ограничивается отдельно, насколько мне известно) можно изменить ограничение на стэк можно путём добавления следующего ключа (цифра лепится в байтах по желанию):
-Wl,--stack,9001А можно поподробнее? У меня в ответ на это компилятор выкидает unrecognized option --stack.
А что за версия g++? (
g++ --version)g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2
Там ошибка в синтаксисеЯ использую так,:-Wl,--stack=268435456:равно, а не запятая (потом что параметр кможно и равно, и запятую (см.ниже). Размер всё так же в байтах (например, тут он равен 256 МиБ).ldвыглядит как--stack=8192)Такое, к сожалению, у меня тоже не заработало. Впрочем, ulimit -s unlimited решило все мои проблемы.
Да, на линуксе —
ulimit -s, на винде —-Wl,--stack=...в gcc или нужная#pragmaв visual studio.Это не ошибка в синтаксисе. Из документации:
Arguments to multiple-letter options must either be separated from the option name by an equals sign, or be given as separate arguments immediately following the option that requires them.
Соответственно,
-Wl,--stack,268435456интерпретируется какld --stack 268435456, что тоже разрешено спецификацией.what is the time limit of the questions in the contest? I am not talking about the duration of the contest, but the time limit of every problem.
Не смог найти в правилах. Можно ли использовать заранее написанный шаблон для решения задач и прочий pre-written код?
Я использовал.
<бабах>
Кто-то знает почему изменение соответствующей строки в advanced настройках при создании таски в CHelper не увеличивает размер стека? Т_Т
</бабах>
А ты output класс запускаешь? МОжет настройка влияет только при запуске как таска?
Да, наверное, ты прав:(
What is the time limit of the questions in the contest? And i am not talking about the duration of the contest, but the time limit of the problems.
You have 6 minutes to send the solution.
I was talking about the 'time limit' of a question, which if my program exceeds, my program gives time limit exceeded (TLE). That is usually 1-2 sec in codeforces, is that 6 minutes on hacker cup?
There is no explicit time limit. You should solve all tests cases downloaded on your computer during six minutes and then upload answers and source code. Source code won't be run, but they still need it so it'll be possible for jury to check that you're possibly not a cheater (i.e. your solutions looks like correct one for the problem, it is not same with someone's, etc).
They don't run your code locally so there is no such verdict as TLE. You have to produce and upload the output in 6 minutes, this is the only limit.
I have solved the second question. I want to download the input file , BUT my internet connection is poor. I'm afraid that the 6 min time limit will pass before i get to download the input file. its about 20 Meg.
Not Fair :(
There is a clarification there to contact them in case if you had problems downloading huge input file on slow connection.
Remove all expired time and change 6 min to 15 min ;)
tnx but how ?
edit: not funny :(
Why you are so bad? Liar!
Facebook should know that internet speed is not good in many countries. I heard that many coder got timeout but couldn't finish downloading the inputs. This is totally unfair.
Actually, in my case, I had to solve at mid night because of downloading the input =))
Locally solved all 4 questions, but could submit only solutions of problem 1 and 3. Due to huge sizes of input files of problem 2 (12.4 MB) and 4 (18 MB), the 6 minute timer expired for ever in downloading of input file itself and hence I couldn't upload the solutions and output files. (can't say if they are actually correct before system testing)
I passed to Round 1, I solved the first problem, but lost the submission time. I'm a loser, I already know :( . The next year I hope to be more preparated for this event.
Sorry.
Please do not discuss anything regarding content of tasks before the end of the round.
I don't see how this is different or any worse than people discussing the large testcases, which is happening. Anyway, I apologize for bringing this topic up, was just curious to see what people thought.
Large testcases do not relate to content of tasks, it's rather technical issue, so there's nothing wrong with it. Talking about estimation of cutoff can include something like "Many people will fail task XXX, because there are tricky corner cases", which is obviously not what we want here.
I don't think it has to do with the problems' content as much as the point values and generally sorting by difficulty. To me, it sounded like a reaction to this comment.
As it has been mentioned already, an input file for one of the problems is almost 20 MB in size. I find this unfortunate, as this puts contestants with slow Internet access at a significant disadvantage (and there are many people with slow Internet access, for some of them, downloading a 20 MB file will take much more than 6 minutes).
Unlike Facebook, Google seems to have considered the problem of slow connections, so input files in Code Jam never exceed 200 KB in size (their problem preparation guide is worth reading). If they need to supply a large input, they generate it using a PRNG, as in this problem.
A suggested alternative approach is to let the contestants download input files in advance in password-protected archives and then provide the passwords instead of input files. This approach is used by IPSC, for example.
At least they realised it doesn't work as well as intended and are trying to fix things (?).
The IPSC solution is probably the best as long as there aren't different input files, since its only requirements are an unzipper and a working Internet connection (let's define "working" as "can download several megabytes at all") and doesn't put limitations on the set of usable problems. For the more interactive GCJ format, it probably wouldn't work, but it seems usable here in case it was seriously necessary to use large input/output files.
For a contest similar to GCJ, it is possible to encrypt different files in one archive with different passwords. This way, it is possible to put all the input files into the same archive and maintain fine-grained access to individual files at the same time.
My computer couldn't handle the large input files. On BOTH the second and last problems :(.
What do you mean by "can't handle"? I've never seen a modern (<15 years old) environment for which 20MB file is very big to proceed.
Microsoft Notepad))
You can't install anything better?
Install? No I mean I got a certain error due to something related to the computer. I went and tried my program on my Toshiba computer, and it worked :\ :(.
Then why did you say "MS Notepad"? I know it has trouble opening large files, so I assumed it was the problem.
what?
I did not say MS notepad (though i used that to open my file.)
Oh wait. It wasn't you I was initially replying to... I didn't notice because your previous post seemed like it was.
Yup, we overestimated what a reasonable input size would be pretty badly, and it won't happen again.
We're not particularly fond of using a PRNG as it takes away time from solving the actual problem. Downloading input in advance is interesting, but a little clunky. We'll probably just aim for problems that don't rely on large input in the near future.
For this round, we're letting people email us their submissions if the input doesn't download in time, so hopefully everybody will end up with the score they deserve.
To who am i supposed to mail the solution, please clarify??
"If you're having trouble downloading the input for Autocomplete or Corporate Gifting in 6 minutes, please submit a feedback request by clicking "Give Feedback" at the bottom of any problem page."
So you have to send a feedback and follow instructions.
Was anyone lucky to get the response for such "feedback"?
Yes I got a response, and sent my solution. Now, waiting for adding the problem before the round ends(as they said).
What? I sent them a response but got none back :\
You should have sent the feedback before the round ended. I did send a feedback before the round, and received a response within 20-30 minutes. You may receive a mail soon, because of the load at the current moments(testing, grading, manual submissions...etc).
I think i sent it ~40 minutes before the round ended.
I found these GCJ problems that use PRNG-generated input, and these PRNGs don't seem to add much complexity. They even have a problem where the contestants had to download and run a program that generates the input locally.
Скажите, люди добрые, как лечить переполнение стека на g++ на ubuntu?
Вроде как-то так. Но за пять минут можно и не вкурить...
My god! I nearly had a heart attack!
I coded a solution, checked it locally, and it worked OK with the small cases. So then I proceeded to download the input file. When I ran it, my program crashed. "Damn! What's wrong!?" I thought. I immediately realized it was the stack size on my local compiler, which was too small. Then I rushed to Google and searched for a way to increase the stack size. I tried one, it didn't work. I kept on searching, found another one, tried it..... didn't work. Only 1:30 mins left by that time, I was getting really desperate. Finally, with less than a minute left, I found another linker option, tried it out and it miraculously worked! I submitted the problem with only 40 seconds left. Now I know the next time I have to try out the bigger cases as well before downloading the input file.
Let's hope it was not all in vain and I get correct answer for that problem!
Same here :D D:
I tried
ulimiton OS X, and it didn't seem to work. With only 3 minutes left on the clock, I quickly decided to switch to my good'ol Linux virtual machine, ssh'ed into it, and moved all the necessary files to it.I realized that I forgot the command to compile, as I always run my program with a prewritten script :D, and had to look up for it, which costed a lot of time...
Then, for a couple of seconds, I had to think of the size I want to give ulimit... 64MB, 128MB? In the heat of the moment I just entered
ulimit -S 100000000(or a couple more zeros in it :P). I compiled my program, ran with the input file, and could submit my answers at the right time.This ulimit trick is something I learned two years ago, which pales a little bit, when compared to some linker options that I've just discovered because of FB Hackercup!
ulimit -s unlimitedshould helpNice. This actually worked!
That moment when you discover the solution to your problem on codeforces comments
What was the fix? I had the same story but with a different ending. :'(
I wonder how many more people will fail because of this stupid reason :'(
The fix is somewhere in CF already, I don't want to help people during the contest more than we already have by hinting that this is a problem.
This problem is not really related to the actual programming.. :\
It's not really fair to fail people for this reason :|.
i have failed because of this and i think i must wait for another year :/
i think it's unfair to share such thing in codeforces. I had the same issue. If i noticed this before i could get accepted from that problem.
true sad story
yes the same for me; my timer expired because I couldn't fix that damned stack overflow error in time! This is completely UNFAIR!!
Same for me in D. I managed to rewrite my DFS to be iterative, but it was intense ;)
Same here, but with memoization you can do this:
print calc(0,...);
Or random calls if you still get RTE.
I'm surprised that many very experienced people (that replied to this) didn't face with this problem in the earlier competitions... I definitely learned this one the hard way.
Странная система... зафейлил одну задачу, смотришь в топ500 все со 100 баллами и дорешиваешь остальные в надежде что большая часть из них сфейлится(
Will I get WA if I use file input/output?
No
When will see results? Right after round ending?
Soon after we should have tentative results. We still take a bit of time to weed out cheaters and look into suspicious submissions before sending out the official advancement emails.
Может, пусть, пока не поздно, они добавят хоть одну задачу не со второго дива, чтоб можно было нормально отобрать? Как вы считаете, друзья? Наверняка, некоторые из вас знают оргов лично)
UPD Второй див, не минусуйте, плз.
Уже поздно.
some people might love the 6 minutes timer kind of submissions, until unless they come across situation like: Download inputs -> run the code -> minor bug -> correct it(while praying timer doesn't goes off) -> again run the code -> HURRAY correct output -> try to submit -> KABOOM...Timer expired (few second back) :(
When I downloaded input for last problem and run it I got Stack Overflow error and spent a some time searching how to increase it in Java, and then there were some errors with stack size >= 256 Mb, but luckily it worked with 128 Mb and I did submit it 10 secs before time expired :)
BTW, It would be cool to see in scoreboard problems failed due to time limit to better understand current situation, wouldn't it?
Guys, how did you solve 4th problem?
i'm not sure it's right solution, but i did DP on tree DP[V][COL] = minimum sum for subtree of vertex V, if vertex V have color COL. 1 <= V <= N, 1 <= COL <= 10 i did.
I did the same, but took 50 instead of 10.I think 20 is enough, but took 50 for insurance.
I think 10 is not enough for COL. Try running your test case by using 20 to see if the results change (mine did). If they don't you got some lucky test cases then :P
yes, i tried it yesterday, and in 1 testcase answer decrease by 1 xD with COL == 15 or more.
COL == 11 is good enough for AC!!!! WTF Big Fail :\
If you swap colors, you can use 5 colors or even less — look at my comment above and my submission at Gym
I'm pretty sure that COL <= log (N) + 1. But in the given test case, I just need about 10 or 11 distinct colors. N is the number of employees.
my solution crashed on 5th test case))
Mine too on local machine, but passed here in Gym. May be stack size? (I am talking about Corporate Gifting)
dp[v][j] -- minimum amount of money when we would have j in node v.
One can prove that in a correct answer j must be ≤ degree[v] + 1.
To calculate it quickly one can precalculate the first and the second minimum among j for each v.
What if we have 1 in all leaves and minimum excludant from labels of children in other nodes? Is it wrong?
i also guessed it at first. But when I simulated it , it gave more value . So its probably not right way .
Suppose root has 2 children and one of them has 1 child. You'll get 1 + 1 + 2 + 3, while you can draw it 1(root) + 2 + 2 + 1(child of child)
Your coloring is
3 1 2 1 1while we are able to make1 2 2 1 1.DFS bottom up. Keep track of the first and second optimal answers for each nodes.
With the first and second optimal answers for all your children, you can then compute the first and second optimal answers for the current node.
For N vertices it's not necessary to use presents more expensive than log(N).
Proof: Let a[x] denote the minimum amount of vertices for which it makes sense to use present with price x in a root. To put x in a root, clearly we spend one vertex on the root itself, and then its children have to give presents with prices of 1, 2, ..., x-1 — otherwise we can clearly use a price smaller than x in a root without conflicts. So we get:
It's easy to see that a[x] = 2^x.
So we can do a DP: a[x][y] — what is the minimum money that can be spent to process subtree with root in vertex i and so that vertex i buys a present with the price of j. To calculate these DP values fast enough, it's sufficient to remember for every vertex x after calculating all the values for it, what is the minimum value in a[x], on what y it's achieved and what is the second minimum value in a[x].
Once you prove that lemma, a straightforward a[x][y] dynamic programming which stores the answer for all
would suffice. Unfortunately, I didn't notice this and did the minimums idea which was not easy to code, at least for me.
Well, I stored the minimums because I got scared of O(T * N * log^2 N). By storing the minimums you can get down to O(T * N * log N).
but what if there are more than a child that give you present with price x-1, does it change the recursive formula? i mean:
a[1] = 1 a[x] = 1 + m * a[x-1] + a[x-2] + ... + a[2] + a[1]
where m are the number of people that give you presents with price m
oh sorry, now i get it, is the minimum so you need the minimum in each child, thanks
Is your assumption of the vertex with color x have exactly x-1 children valid one?
By the above assumption you are assuming a particular kind of tree structure.
http://imgur.com/vqssnWe
It needs to have x-1 children with all prices from 1 to x-1 for us to be forced to pick a price of x in the root. If it has more than x-1 children, those children subtrees are dead weight and do not limit our ability to pick a price for the root in any way. Since we are looking for the minimum required vertices, we ignore them.
I think there is: a[1] = 1
a[x] = 1 + 2 * (a[x - 1] + a[x - 2] + ... + a[2] + a[1])
At least 2 v values must appear in children. If there is only one v < x value, you can swap it with root and you have v in root.
So a[x] = 3x - 1 I assumed second y < = 13. I hope it's enough. (curiosity — When I set y < = 5 it doesn't change results for my input).
Yeah, log(N) is a really rough estimate, you need a lot more vertices than 2^x to actually have x as a price in the solution. What I wrote was just the easiest proof I could do without going into tricky details of swapping the prices and it was enough.
My friend (Ralph) pointed out to me that the required sequence might be the number of order-consecutive partitions of n. So, the required sequence is:
For the Corporate Gifting problem, in order to find the maximum $gift used, we need to take the inverse of the sequence.
I have not completely verified it in full (i.e., I do not have a rigorous proof yet of the precise bijection between the two ideas), but it seems right to me and I followed the intuition behind the correspondence. If you have another way to look at this problem, let me know! Also, I want to point out that the sequence is related to a pot-limit poker.
Any comments from the community is welcome.
I had to chew around each of the problems after the contest (i.e., upsolving) to make sure I digested the solution techniques and here is my first attempt at it :)
Edit: click here for my CF blog entry about 2015 Facebook Hacker Cup Round 1!
Nit: did you think about cases where a node has 'cost' x, its parent cost x-1, and then only existence of x-2, x-3, .. , 1 children costs are implied.
I do not know whether it is right or wrong. As my program crashed with stack overflow and i failed to find a way to increase the size of the stack during my 6min time...... half of the time gone only to download the input file.
My idea was .... Dynamic programming... We can convert the problem to coloring a tree, we only need to use log(n) colors to minimize the cost....
How to increase stack size when using gcc ??
http://codeforces.net/blog/entry/4004#comment-184036
The problem asks for what known as a "chromatic sum".
This paper E. Kubicka and A. J. Schwenk. 1989. An introduction to chromatic sums. http://dl.acm.org/citation.cfm?id=75430&dl=ACM&coll=DL&CFID=619242039&CFTOKEN=73545678 has a linear-time algorithm for finding a chromatic sum of a tree.
Unfortunately, I couldn't find the full text of the paper on the Internet for free, but you can preview it here: https://www.deepdyve.com/lp/acm/an-introduction-to-chromatic-sums-74F705JQIj?key=acm The algorithm is on the last page.
Full text of the paper in second result :
https://duckduckgo.com?q=E.+Kubicka+and+A.+J.+Schwenk%2C+An+introduction+to+chromatic+sums&t=canonical
There's a clean pseudo code as well
What link is the "second result"?
If you mean http://dl.acm.org/ft_gateway.cfm?id=75430&type=pdf&coll=portal&dl=ACM , then you can get the full text for free only if you (or your university) have the ACM library subscription.
Sorry, my bad ..
I have uploaded it here for reference : http://home.iitk.ac.in/~skmanish/p39-kubicka.pdf
I tried to look for the free version of paper for almost 10 hours yesterday.
I think you cannot distribute private papers like this.
It's not a private paper. The copyright notice at the bottom of the first page states that the paper can be copied in full "provided that the copies are not made or distributed for direct commercial advantage." I'm not a lawyer, but I'm confident that it's legally and morally okay to download this paper for free.
закончилось! как решать четвертую?
Главное доказать, что если какой-то работник выбрал подарок номер k, это означает, что в графе не меньше, чем 2k вершин. Это понятно, потому что если он выбрал подарок номер k, это означает, что он не мог выбрать подарок с меньшим номером, а значит, его подчинённые или начальник уже выбрали номера с 1 по k - 1, а это значит, что, по индукционному предположению, в графе есть как минимум 1 + 2 + 22 + ... + 2k - 1 + 1 вершина.
И это замечание позволяет решать задачу за n·log(n) динамикой по дереву.
А можно просто считать динамику по поддеревьям, которая возвращает два лучших (по стоимости) цвета сына. Чтобы ее пересчитывать, мне пришлось воспользоваться персистентным деревом отрезков. Код.
Возможно, я набагал, но мне не пришлось использовать дерево отрезков. Код
Для каждой вершины сортируем потомков, что занимает сумму степеней вершин на их логарифмы. Поскольку логарифмы <= log N, а сумма степеней вершин — O(n), суммарное время O(n log n).
Я понимал, что можно сделать и так. Но при этом мне показалось, что получится много случаев, а дерево отрезков я напишу быстрее и без багов:)
Так и я вычислял два лучших номера (точнее, я сохранял лучший номер и две лучших величины). С этим каждая вершина вычисляется за O(log(n)) + O(количество сыновей вершины), безо всяких деревьев.
А зачем тут O(log(n))? Разве не просто за O(кол-во сыновей)?Ведь оптимальные два номера вершины явно не больше чем число сыновей+2. Тогда и суммируется в O(n), а не O(n log(n)).
Действительно. Но я об этом не подумал и считал ответ для всех подарков от 1 до log(n) и находил два оптимальных из них, так как O(n log(n)) было вполне достаточно.
What is the solution of 40pt problem? I could not get it may be because not solved too much graph problems. Have surrounded around bfs/dfs, types of tress , and vertex coloring but could not come up with solution. All idea were wrong I think. And I think only one who solved all 4 problems will reach 2nd round.Congratulations to them.
https://www.facebook.com/hackercup/posts/901120689920120
Мда.
а кто-нибудь понимает, почему нельзя было сразу сверять ответы, а результаты показать сразу по завершению тура? если проблема в читерах, то почему бы их не отлавливать после предварительных результатов?
Там написано, что они руками тестируют решения тех, кто не мог загрузить большой инпут.
И хотят показать результаты сразу для всех.
Irrelevant, I wrongly assumed that large files are the same.
Aren't inputs different for every participant?
Hm... I believe they are the same in Code Jam, not sure about Facebook Hacker Cup actually. Post your hash of any of the input files?
They are different; according to a comment on the qualification round; they said that they have a total of 48 test cases from which they select 20 random test cases for every user. Some test cases are included in all files though :D
UPD: No, they are different in Code Jam as well. I have no idea why I was under the strong assumption that they were the same.
OK, I thought the whole point behind the system was to test your code on as large number of tests as possible and then to avoid just sharing the output file, you need to submit the code as well.
This is better in a way that it eliminates randomness. In Code Jam small tests, where they are unique for every attempt, you can quite easily get lucky even with an incorrect solution. You can resubmit though, so it's not a huge deal. However on large input, where you can't resubmit, if it's the same, you can't get two participants with the same wrong solution, where one gets AC and the other gets WA just because one is more lucky and didn't get any bad test cases.
I still believe Code Jam's large input is one for everyone for these reasons, unless someone can show that I'm wrong.
How to simply calculate this hash?
http://lmgtfy.com/?q=md5+calculate
Actually you don't have to; you can find it if you open your submission from the problem page...
Yeah, I was pointing out that there's no need to ask questions that can be answered by a single Google search.
A: d0ee7647ad6dd0014a1dd5d197805964 B: 57664116c970da2d8be396e36c872a61 C: 24da720c50105b958cd5ae9129c2653b D: dd04084a224c69ea300931f1fca8ef69
Indeed it looks that there are at least two different inputs :)
And here are my inputs (the larger ones are still uploading): https://drive.google.com/folder/d/0B2d37tm1YmE3a0xMLTJFdDZyams/edit
If somebody is not lazy enough, please post the MD5s of your outputs on these inputs :)
Note, that endlines(win vs linux), extra spaces, #s will affect md5 but not correctness. Solutions are quite small so its easier to compare them directly
Would you share your outputs? I get both hashes different:)
My outputs
Hashes with \n as newline
Mine have Windows newlines, no extra spaces, and have #s.
I'm doing this from a phone, copying outputs would be cumbersome :(
Got the same output with these 4 inputs.All i need to do next is bless the manual judgement will give the correct answers.....
all outputs match :)
I got the same hashes for output files (\r\n after every case, including the last one) with your input files for all problems.
OK, got same hashes with \r\n newlines
Either we made similar mistakes...
I have the same hashes for A,B,C)) Thanks for sharing!
All my hashes are different from yours. So let's hope our inputs are different :)
According to adelnobel they are different. I also forgot about line endings.
Reference
https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2015-qualification-round-solutions/1043281905687710?comment_id=1043297972352770&offset=0&total_comments=103
Note to self: 1<<20 is smaller than 1e7.
Rule of thumb for quickly estimating powers of two:
What is the answer for the 3rd problem's input: 1-0
1 1?
1-1
it should be 1 1 cause only one way to achieve this
1 1. Since there always is a way to meet the requirements (AA...AABB...BB for first and BB...BBAA...AA for second) and there is only one way irregardless of any restrictions anyway.
Thanks, I also think 1-1 is the right answer.
OK, looks like I made a dumbest mistake ever. My output is "1-0". But at least I believe I solved D. Congratulations to all advancers!
So a victory of 1-0 is stress-free and stressful at the same time?!
This makes no sense whatsoever :)
1 1 makes sense for 1-0:
stress-free: you score the first point. Only 1 point, only one way.
stressful: you score higher only when opponent reached final score. He never scored, so he reached 0 points automatically.
Formally yes, when considering this part of the statement: "In a stressful victory, you never have more points than your opponent until after their score is equal to their final score."
But it is rather difficult to follow a transition from "The two most extreme kinds of victory are called stress-free and stressful" to "well, they can actually be one and the same thing" :)
Well, it's also quite difficult to imagine a match with score
2000-1999, if we want to think this way...It can be "1 0" also.
Why thinking bottom-up is so much harder than recursive DP :(
Because u need to then know the order in which uhave to run the loop in a directed way, but when u have a recursive dp this order is already maintained by recursion, It means that having the recurrence with you you just need to know the order in which to evaluate in bottom up, well both are same , choose what u like, i prefer bottom up dp..
I prefer recursive DP, but there is a big cost of doing that. Sometimes a O(n^2) recursive DP can be achieved via a O(n) bottom up dp.
Almost 1000 people answered all four problems.... looks like you can't make any single mistake in order to go to the next round...
Last years showed near 50 percent wrong submission and two any problems were enough.
Submitted on != answered correctly.
I know... but given that there are 1000 people...
If only 499 don't fail on at least one of the 25pt problems, 75 will be enough to go to the next round.
In my opinion, the sample tests for the two 25pt problems seem pretty strong. Especially the last test case for the third problem. Also, the Trie and DP implementations seems pretty standard as well. I don't think the fail rates would be high for these two problems.
I guess most failed submissions would be on the last problem because of the weak samples and more corner cases. But I still wonder the fail rate could reach 40 to 50%....
One test:
1-0.I found that one when I manually tested my solutions (strategy) and I think a lot of DPs can fail on it.
Autocomplete doesn't have a truly large test and, while the samples warn about one word being a prefix of another, they're not that strong. It will probably have a higer AC rate (discounting possible download fails), but failing it means losing as many points as when failing Sports, further increasing the number of people with exactly 75 points.
I also thought about this testcase. It's both stressful and stressfree, right?
Yes.
Eh, it's kinda bad if the difference between passing into Round 2 or not is in handling that corner case, to be honest, it could be included in sample tests.
You have 24 hours and are free to use them however you want. I tested my solutions manually, using bruteforces, checked if they don't fail on large random tests etc. It's about an hour or two more, but finding that missing case was worth it. At this point, anyone can pass as long as they deserve it (can solve the problems) and aren't careless.
(If you don't have the time — that's your choice of time management.)
Nothing about the format selecting people basically based on how much time they had available, then?
I thought you were the guy complaining about how topcoder was supposed to be more about thinking and less about avoiding dumb mistakes.
There's a HUGE difference between 1.25 hour and 24 hour contests.
You don't see me complaining about tight time limits or this troll problem (find the missing piece of information) in Codechef Long contests. It's the same thing — there's a place for everything. Just as short contests aren't the place for overly technical problems or little given info, long contests aren't a place for no hard problems.
Just imagine that you assign a score to each contest — the chance of getting a good result. That chance depends on the quality of samples, syllabus, feedback, the problems' intended difficulty distribution, name what you want — but also contest duration. You can't cast judgement without taking into account a lot of these things, and that's what I did in my recent rant against the recent low success rates of TC problems.
Tl;dr if SRMs were 5 hour long, I would shut up.
UPD: And no, "I don't have enough time because I'm doing something else" is not a valid complaint, since you got something out of doing that something else. There were like, 3.5 hours intersecting with other programming competitions (1.5 out of which was the Cookoff server crashes).
Well I ain't saying that it's okay to make mistakes like one I mentioned, but sometimes you just skip that corner case, by accident(it surely happened to you a lot of times, maybe before you became that good), the pass to Round 2 shouldn't be that hard achievement, and some really silly mistake can take it away from you, if the 0-case got included into pretests, everyone with correct C solution would have all the points required, like in D task, they included the test where bottom-up strategy didn't work and it prevented a lot of possible wrong answers.
If you notice, I actually started out saying that many people failing this could get them and more people to round 2, since 75 points (for example) would be sufficient. We don't know the results yet; it would seem that I have a full score, but I can still fail and... well, I did my reasonable best (I checked my solutions a lot, but didn't spend the whole 24 hours on it), but there's still a possibility of failure to deal with and it's kind of silly to attribute it to thinking "it's just round 1, it will be easy to pass". Last year, user:WJMZBMR failed the qualification due to trying just one problem and getting it wrong. That's also negligence.
We get such lessons sometimes.
And 500 isn't much, that's like passing from GCJ round 2. Except there are time tiebreakers there (and the problems are harder).
According to you, what should be the correct answer for this testcase should it be 1-1 or 1-0.
Read the comments above.
I'm guessing that many people will fail on C and some will fail on D. It seems hard to fail on A or B. I'm not sure if 75 points will be enough to qualify; I'm curious to find out.
(many people will fail on C) Why do think so? what's the deal? :D
Tests like 1-0 or 1000-0.
Correct answer is "1 1" for both, right?
Yes.
Why do you think there will be many wrong answers with these test?
People first iffing out the j = 0 case, then the j = b case. :)
I might be wrong though.
lol and I'm proud to say that I'm one among them who will fail this case , good case and silly mistake didn't think about it and yes I think many will fail in this case .
I'm very curious on what were your approaches. I mean, I had no need to handle any kind of strange case explicitly (they were implicit on how my DP was built), but it seems the aforementioned mistake is, in effect, made by lots of people.
I'll be glad if you share them with me :)
Please note that we will not accept any manual judging requests after the round has ended.
How did some contestants guess that they should submit their code for manual judging?
There was a notification for majority of the round:
If you're having trouble downloading the input for Autocomplete or Corporate Gifting in 6 minutes, please submit a feedback request by clicking "Give Feedback" at the bottom of any problem page.
"Feedback request" doesn't mean "manual judging". In particular, it doesn't say anything about submitting just the code, which is the main problem here.
I assume that this meant, please write to us and then we will explain to you what to do. If they made a public announcement "if you had problems, please send your code to this e-mail", I fear that they would receive enormous amount of non-legitimate submissions, which would have taken ages to process correctly.
Yes, that's possible, and could be the answer to Rubanenko's question. Under "manual judging", I imagined just submitting the code without the output, since judging these could be made a lot more automated than a few admins answering a lot of mails.
Послушайте историю невероятного успеха/провала (нужное подчеркнуть).
Решил я 4 задачу. Написал решение, проверил на тестах из условия, ещё потестил, внимательно перечитал код. И решил посылать. Скачал тест (всем известных проблем у меня не возникло, так как интернет у меня быстрый). Запускаю своё решение — и оно валится! Я покрываюсь испариной и начинаю искать баг. Как ни странно, баг нашёл, программа валилась на создании массива векторов
vector <int> son[n](кстати, что в этом плохого?). Я заменил наvector < vector<int> > son(n, vector<int>(0));и за 40 секунд до конца всё заработало. Я возликовал и вставил нужные окошки output file и source file. И тут мне пришлось в голову, что надо проверить, работает ли исправленная программа на примере из условия. Зачем? Ведь, во-первых, этот фикс не мог ничего испортить, а во-вторых, я бы всё равно не успел ничего исправить. Но я привык перепроверять работоспособность программы после любых изменений, даже если очевидно, что точно ничего не могло испортится. Я стал создавать другой тестовый файлик, и когда создал, посмотрел на страницу. Оставалось 2 секунды! Я в панике схатил тачпад и потянулся к кнопке "послать" и даже нажал на неё, но было уже поздно — было написано time expired.Некоторое время я бился головой об стол. Затем посмотрел на страницу результатов, и увидел там у себя галочку. Потом посмотрел на страницу с задачей. Там всё ещё было написано "time expired", но и "Last valid submission at * ago" тоже было написано.
Я замешательстве.
Если ты зайдешь во все остальные задачи, то там тоже будет написано Time expired. В том смысле, что ресабмитить нельзя.
Аааа. Значит, видимо, в порядке. Но однако я отчётливо видел, что надпись "time expired" появилась до того, как я нажал.
Ну так понятно, что это JavaScript, и возможна рассинхронизация с сервером
Тест из условия можно было скачать прямо на странице с условием.
Да! Но мозг меня плохо меня слушался в этот момент.
vector <int> son[n]создает на стеке n векторов, аvector < vector<int> > son(n, vector<int>(0))создает на стеке только один, остальные в куче. Наверно, у тебя был Stack Overflow.i have sent a clarification due to submit issue in last 10 minutes but no answer tell now?!!
Let's judge our solutions in Facebook Hacker Cup 2015 — round 1: http://codeforces.net/blog/entry/15864
It will be a long day at Menlo Park. :)
Indeed, it's been a long few days this round :)
We made a lot of unnecessary work for ourselves and others. Luckily, we've learned a valuable lesson that shan't soon be forgotten.
when you show us the results?
The tentative results should be announced later this evening.
Ok, Thx.
Now you'll be testing future rounds on a typical internet connection? ;)
Oh yes, yes indeed :)
shiplove
Last problem is same as one of the boi 2003 problems. I assume you expected few accepted from last problem since it was the hardest one.
By the way why limit of N is 200000. Anybody get hurts if it was 50000 or something? You could have get rid of 20MB issue.
What I am trying to say is from my point of view Facebook hacker cup is the worst online competition I participated in this year. I have never encountered interesting problems, just technical situations!
Except from looking at the solution, the expected solution at BOI (Baltic OI, for the reference) 2003 was O(N^2). Which eliminates the need for understanding that you can limit the numbers you are using, which is exactly what makes the task interesting and challenging, in my opinion. Also I highly doubt that a lot of people knew exactly the same statement was used there (I didn't, and it was from my region, although before I competed). Including the organizers. Coming up independently with exactly the same task isn't too difficult.
As for N = 50000, I believe O(N^2) could pass with these restrictions.
You are wrong. Just because constraint of N is 10000 you can not say expected solution was O(N^2). You are judging like in 2003 we had same computers. 10 years ago computers were much more slow. Also official solution of the problem is O(N).
All I can see regarding the solutions for BOI 2003 is the archive from the former Lithuanian IO website. My claim that the intended solution is O(N^2) was from the fact that there is a quadratic array and I assumed was used for DP. I was wrong. Inside it is a "solution" for the task, which uses constraint <= 1000, stores the graph in O(N^2) memory and assumes we won't use number greater than 3, which is incorrect. I have no idea about the origins of this archive, it looks like it's rather unofficial but I cannot find anything else. Still, to do a quadratic DP, we actually need to store all of the values, and they had only 64 MB of memory, so yeah, likely not O(N^2).
I claim that you're also possibly wrong, though. For O(N), the restriction is way too small (they had N <= 10^6 restriction in one of the other tasks). If you can show any proof that the official solution of that problem was O(N), please kindly do so. I believe it was O(N log N), in this case.
As tom pointed out upper bound of colors is not log N it's 5. So we can assume it as constant factor. Official solution uses 3 colors too. So why do you think complexity of solution is O(N log N). It is obviously O(N).
If the problem in BOI is exactly the same, for my input of FBHC the results changed when I increased the number of colors until 20 (e.g between results using 5 or 6 colors, 6 and 7 colors, and so on), some other people needed 15. So I think around 20-25 should be the minimum number of colors to be sure it is correct, which is approximately to log2(200000). Also a friend found a thesis manuscript about the subject proving that it was O(lg n), I'll try to find it to link it here.
It's obvious that log n is enough. But I'm not sure it is necessary. Is there a proof that we need at least log n colors?
Unfortunately I cannot find the paper I mentioned, but if 3 colors were enough for the other contest with lower limits and at least 15 are needed for this one with higher limits then the number of colors seem to depend on N and not be constant, but I am not sure how to prove the exact growth rate.
It looks like number of necessary colors is polylog n.
One obviously can construct an example where k colors are required for any given k. Just start from 1, and on the k'th step attach lots of constructions for k - 1, k - 2, ..., 1 to a new vertex.
Besides, your arguments like "As flashion pointed out upper bound of colors is not log N it's 5. So we can assume it as constant factor" are ridiculous. It almost seems like you have no idea what is a rigorous mathematical proof.
You are right 5 does not have to mean constant. But in practice it is close to log log n which is too little.
Where did you get log log n from? Please stop making random statements out of nowhere and try to prove what you're saying (or at least read the comments above). It is O(log n), as pointed out multiple times in the comments, e.g. here.
In fact, at the k-th step it's enough to add 2 (k-1)'s, 3 (k-2)'s, ..., and k 1's. With this construction, the size of the tree at the k-th step is given by this sequence: http://oeis.org/A007052 which grows exponentially, and therefore the log N bound is tight.
Let me translate what you said:
"As tom pointed out, on his input data his answer doesn't change if he uses only 5 colors. So we can assume that if we have N vertices, amount of colors used is O(1)".
I'm not sure if there's any point in continuing this if you're making arguments like that. Also you keep mentioning official solution without ever providing a link to one. Writing "obviously" doesn't make one right.
I'm not saying that you're wrong, I can imagine that the actual bound might be different, but you need to provide valid argumentation for your points, otherwise this whole conversation is a complete waste of time.
Here is link to the solutions Link There is no proof tough.
No, this is an archive (which I have posted a few comments ago *), and as I mentioned a few comments ago *, this archive doesn't look like an official solution, since its author is a Lithuanian (whether BOI 2003 was organized by Estonia, perhaps things have changed recently, but as far as I know (and I was on the organizing team of BOI 2012) other countries submit tasks only, whether actual task selection, test generation and solution implementation are left to the organizing country). He also participated in online contest of BOI 2003 and scored 0 on this task.
(*) Are you even reading replies to your comments?
Imagine you have n trees that you need 1<= i <= n : i colors for painting those trees with min cost.
Lets form the tree with n+1 colors with min cost:
You get the root node.
you will connect to it ((n+1)+1) nodes with cost 1,
You will connect to it ((n+1)/2+1) nodes with cost 2. ... you will connect to the root: ((n+1)/i+1) nodes of min cost:
The root will have n different colors connected to it. So the root need to be painted of the color n+1.
What about try to swap colors? You can figure out that is is more expensive. With this I conclude that you may need variable colors for painting the tree with min cost. I haven't prove that you need lg n colors. A friend did research and found an algorithm O(n) in time but anyway you need variable colors for painting it with min cost.
It was also given at CERC 2 months ago as a problem on testing session. And its significantly harder version was present in snarknews new year's contests (problems -> http://newyear.snarknews.info/files/2014/prob_p.pdf ) (that fact implies also that this was given on some Russian ACM-ICPC style contest)
I've added the round to the Gym: 2015 Facebook Hacker Cup, Round 1. Feel free to submit your contest solutions in practice mode to get expected verdict right now.
Memory limit exceeded on test 2 (Autocomplete) However it runs fine in my 8G machine :)
Hi mike , what will be the running time for each and every problem ? does the 6 minute timer means that your problem will be allowed to run for 6 min ? if there is time limit applied to the problems in FB hackercup can you mention them here ? thanks .
My solution for A (Homework) runing more than 2 sec on my computer (4Ghz processor) and les than 1 sec on codeforces (3.5Ghz). How it's possible?
I think it is because of the options you use for compilation. For example, codeforces uses the '-O2' flag, maybe you aren't using this.
For problem 4, this paper explains a simple O(n) algorithm — http://www.public.asu.edu/~halla/papers/OCCPWG96.ps
My implementation — http://codeforces.net/gym/100579/submission/9468814
This problem on uva is pretty similar http://uva.onlinejudge.org/external/113/11307.html
Problem #3 is a problem dating back to ~1880, with a very short closed solution:
"In combinatorics, Bertrand's ballot problem is the question: In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?"
http://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem
Solution to problem 4 was dp + dfs.
Here is mine accepted solution of it in codeforces gym. http://codeforces.net/gym/100579/submission/9474632
It will be great if you could post your solution somewhere else since users who did not solve this problem can't see your solution. In codeforces gym, you can't see solution by other people unless you have solved that problem.
Here is the ideone link of the solution http://ideone.com/oGmWhE
Thanks!
In the 3rd problem "WinningSports" for the case of x-0 the number of stress-free win should be 1 and stressful win should be 0 or both should be 1.
both one
I did this mistake during the contest :(
There was no chance to debug our code or correct our algorithm in proper time. That's not a good idea I think.
Actually, there was time for "corrections", which has caused my failure in this competition: implemented solution according to the formal problem statement ("1-0" -> "1 1"). Downloaded test file, generated the output, had some time to inspect test data and my results. Noticed those "n-0" cases. Intuitively my response seemed wrong (how can the same sequence be both stressfree and stressfull at the same time, I thought), so I went to fix my solution to return "1 0". There was enough time for that, and for submitting the "fixed" solution:(
It's all my fault, I know. But I just hate when formal problem statement contradicts common sense.
There was no time for what?
I speak about getting WA on some pretests like codeforces, or on small input like codejam.
... Then, Do you think that 60 points is enough to advance to Round 2?
I hope yes, but think no
Definetly NO :) Bloody hell! :@
Guys... ranking has been changing... I hope it's final migration of manual submissions
Интересно, а как квалифицируется попытка послать source code у людей, которые не успели скачать тест за шесть минут, если программа работает правильно, но 5 минут 55 секунд?...
В случае чего — нужно говорить ничего не знаю и знать не хочу, у меня локально летает, а у вас там просто железо древнее.
Да, и из-за людей, которые будут так говорить, проходной балл поднимется с 60 до 100.
Он оказался 75, даже если не учитывать все посылки вручную.
А если твоё решение не отработало за 6 минут, то, разумеется, тоже надо пожаловаться, что ты не успел скачать тест.
Эх, надо было, наверное, заслать тот ужас, что я написал во время контеста, и который работал 1.5 минуты :( А я решил, что, раз файл скачался за 5 минут, то факт, что я не уложился в минуту — мои личные проблемы. Быть честным — вредно и неудобно, оказывается.
UPD: While 500th place got 100 points, if manual submissions are omitted, 500th place have 75 points, so as promised by organizers, the cutoff will be 75 points. It's a reasonable cutoff, allowing contestants to fail one of three easier tasks, so my original comment below is a rant about what could've happened. Still, I'd like to organizers to remember that in the future, to avoid having rounds with cutoff of full score, as it would've happened if not for the whole saga with 20 MB inputs.
Since there are now 1140 people with pending 100 points, I believe the most likely scenario is that the cutoff will be 100 points — I don't believe there is a case so tricky that more than half of the people will fail something. Don't really think that even selecting top 500 before adding manual submission will help the issue here. In case it's miraculously not 100, everything said below is irrelevant and I apologize. I also apologize for technically speculating on the cutoff, however I believe that it's the most likely scenario and would like to express my opinion before official results are released, especially since the organizers are reading Codeforces.
The cutoff of 100 means that the organizers screwed up big time and turned this round 1 into "whoever doesn't make a silly mistake" contest. With that in might, I find the organizers claim:
"I don't think this should be a huge concern to the eventual top 100 who will advance from Round 2. If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion)".
rather hilarious. Yep, guys, if you made one tiny mistake in one of the four tasks (and keep in mind, this is not Code Jam, where you at least can be semi confident in your code by small test case), your chances of getting to top 100 are extremely slim in their opinion. Setting aside all input data size disaster, I believe the organizers should admit that they screw up qualification round, potentially eliminating lots of strong candidates in early round and at least set the cutoff to 61, essentially allowing people to go through with bugs in A and (B or C).
Before comments claiming I'm just rage posting start to flow in, just want to mention that I myself am passing all the tests at Codeforces, so I expect to get a 100. Which doesn't eliminate my opinion above that this round failed to fairly select 500 participants. Some people were worried even before the round due to the format, however last year Round 1 didn't suffer from any of these problems and distribution was really fair despite it being 48 hours, so I still believe it's possible to have a fair elimination round with this format, it's just difficult to pull it off.
In this case I will be a saaaad panda with 90 pts.
You were heard. :)
"The manual submissions have all been entered, so the scoreboard now shows the pre-judging results. Before the manual submissions, 500th place had 75 points. But afterwards, the top 500 all had 100 points! In the interests of maximal fairness, we'll be using the pre-manual submissions cutoff of 75 points for advancement. We'll be revealing the judged solutions in about an hour, so stay tuned!"
Well, they promised that they'll use pre-manual submissions cut-off beforehand. So yeah, cut-off ended up being reasonable purely because of the problems with downloading times. In essence, they avoided a fail by having another fail.
We were hoping for a cutoff of 60 or 75 when we made the problem set, so we definitely misjudged the difficulty of the set. Last year I think the cutoff ended up being 40 so I guess we overcorrected. Let's call it binary search :)
And you'd think someone who showed clear inexperience would pick one of the "reasonably easy to get right" format options... This is just asking for trouble.
While you do have a point, overall your comment is way too aggressive IMO. I understand that one can be very frustrated because of some troubles with a contest (I myself did such a mistakew in the past, aggressively criticizing contest because of some issues, and then re-reading my own comments and being ashamed of them), but try to put yourself in the shoes of organizers: they've spent lots of their time preparing the contest, and now participants post comments like this one. It must be very demotivating.
IMO the critics should be mild and constructive. This time, there were two issues:
Large inputs. I wouldn't even blame FBHC organizers for this: if you look at recent products build in Bay Area, most of them suffer from this problem (i.e. they're not slow-connection-friendly). I think the whole industry would benefit a lot if there is a mandatory "dial-up day" in the whole Bay Area once per month :) With bandwidth 56Kbits/s for everyone, so that developers experience their glorious creations over slow connection.
Round structure: 24h, cutoff is the score of the 500th person => tiny mistake leads to failure. Indeed this was pointed out before the contest, and indeed many strong participants and finalists of the previous years did not advance (e.g. niyaznigmatul, Jacob). Yes, this was a mistake, and people should learn from such mistakes. But stating something like "organizers claims are hilarious" is a bit too much IMO — we should be respectful to organizers.
I have tried to be fair and did not make claims that it was "worst online competition" as some people did in this thread. As I mentioned in the beginning, I no longer have such a strong view of the situation, since the situation would be much worse than if the cutoff would have been 100 points.
Still, I have the same position on that quote, and I can't really see anything disrespectful in pointing out that their claim was hilarious. I rather find it disrespectful from the organizers to release this quote under any circumstances with or without imo clause. In this particular case, when the task selection was inappropriate for the purpose under the given format, I found this quote to be funny as well, since it was clear that some really strong participant would be applicable to this (when at least D was definitely going to be mandatory). So, turns out that wjomlex made an indirect statement that ACRush and niyaznigmatul in his opinion have extremely slim chances of getting into top 100. Which is obviously not true, and obviously wjomlex wouldn't ever made this statement in this form. This is why one needs to be careful about what he says and how it can be interpreted before publishing it, especially if he represents one of the biggest programming competitions in the world.
And I didn't blame organizers for large inputs, since I can understand that this issue might be completely overlooked by accident. Not thinking about the fact the given problemset might quite possibly be solved completely by more than 500 people is much less understandable. I haven't also heard any apologies or reflections on problemset or format in the end. For all we know, the organizers might think that the problemset was reasonable under this format.
Ah, I think my comment was misconstrued. For ease, let me repeat it here:
"If there is anybody who did not legitimately succeed in Round 1, their chances of ending up in the top 100 in Round 2 are extremely slim (in my opinion)."
By "did not legitimately succeed", I mean anybody that managed to get into Round 2 because their manual submission was accepted even when they wouldn't have succeeded themselves under normal circumstances. As people have pointed out, there are likely a few manual submissions that would have not been ACs because of stack overflows if we weren't handling them.
I definitely didn't mean "anybody who failed to advance to Round 1 would definitely have no chance advancing from Round 2". That would be silly. I've been in this situation before when I failed to advance from Round 1 of Hacker Cup because I was modding by 0xfaceb00c as an integer, and not as a long :P
As mentioned in a comment above, we did overestimate the difficulty. We were aiming for 60 or 75 to be the cutoff. Would we have adjusted the cutoff if everything went well and >= 500 people scored 100? That's tricky. On one hand, following the rules seems decent. But I'm pretty consequentialist, and I think that lowering the cutoff to 75 anyways would be a better plan in such a situation.
60 was definitely the cutoff I was rooting for before we started. This was my first time helping build a problem set for a 24-hour round and I think we ended up with something that would have been pretty decent in a 3-hour round, so now I'm better calibrated on this front.
Thank you for your clarification. I do get what you meant now and it indeed makes sense. I apologize if I offended you due to my misinterpretation of your quote.
In any case, one of the solutions I suggest if you want to keep 24h rounds in the future is to adopt Code Jam's approach to long rounds and avoid selection by rank and just define the cutoff yourselves, stating that everyone who gets X points advances to Round 2.
Yeah, I'm definitely interested in doing multiple sub-rounds like GCJ or, like you say, simply picking our own cutoff.
I can easily see a very good coder using the loophole to fix the stack overflow, so I still don't agree 100% with the quote. But as Swistakk pointed out below, you handled this issue in the best way possible, so that was a positive point.
I think for the ideal cutoff you would need 3 problems to pass (so A+B wouldn't pass, but A+B+C would, and D is there for some buffer room). One of the issues was that you picked easy problems, but the biggest problem is that you picked a format which does not allow you to misjudge the difficulty. Hopefully we'll see some improvements in that front next year.
Yeah, 60 would allow for any 3 problems, which I would generally prefer. I would imagine that next year we would just set the cutoff.
Daaaaaamn. Cutoff is 75 ;____;. I'm so sad :<.
That problemset was too easy to fairly choose 500 people :(.
Fully agreed. A textbook trie exercise (I can't even call that a problem), followed by an amazingly obvious DP.
How did they think this would work to select 500 people? Just look at the problemset for Code Jam Round 2, which was a lot harder to select the same amount of people with a much smaller duration.
Maybe this problem set is easy for you but I see a lot of people failing the first try of few problems here
registei ca só pra dizer que vc ta falando MULEKADA. Fácil pra vc, não para milhares de pessoas.. Seja mas HUMILDE quando FALAR em PUBLICO...
It's obvious that people that didn't train for these kinds of contests would not find the problems easy. I did not mean to imply otherwise.
However, precisely because difficulty is such a relative term, it needs to be properly calibrated for the event in question. You wouldn't use the same standards to select members for the running team in your school and to select runners for the Olympics. Similarly, a round that proposes to select only 500 people from the whole world and in which more than 500 solved all problems is definitely too easy. My and your relative skills have nothing to do with that.
Now that you found this awesome website, maybe you can train harder for Hacker Cup 2016? :)
At least I am not sad at all, because for me it means just losing a t-shirt:)
But still it looks like organizers screw up this time. Lot of guys who usually participate in onsite rounds of such competitions — haven't qualified at all.
And GCJ looks much better in picking top-contestants for late rounds, comparing with this edition of FHC. FHC don't have to copy GCJ contest rules, but maybe they should look for some ideas there. I don't know actual goals of FHC. On the one hand, good performance can give additional motivation for beginners, increase popularity of competitive programming and so on. On the other hand, I don't think that they really want to see some random folks in next round, instead of Endagorion, ACRush, niyaznigmatul...
I think they should provide some "not div2" problems next year (at least like last year... or maybe even a bit harder; not just 4 textbook exercises), if they want stronger field in Round 2. Last year netkuba got 55 points in round 1 (failed both B and C) and later got #18 at Finals; niyaznigmatul was #4 in Final round with 55 points in round 1 (only A and D submitted). RAVEman got 7th place in Final with only 40 points in Round 1 (A and C; failed B and D). andrewzta is ranked 6th in Final with 60 points in Round 1 (B and D; failed A and C).
Best algorithm for goal "picking top-contestants for late rounds":
The only good thing so far about FB Hacker Cup is that it has shown us to appreciate Code Jam.
Apparently, in the first problem, a lot of people decided to combine 2 steps of "finding primes" and "use them to calculate the number of prime divisors for every number" into a single step by using the same approach as in Sieve of Eratosthenes and forgot that unlike in sieve we do need to consider primes greater than sqrt(N) in the second step.
The manual submissions weren't fair at all. There are people who claimed they didn't have time to submit in the feeback form when, in truth, they suffered from stack overflow and modified the solution before sending it by email, while other people resigned themselves with this and didn't cheat. I don't think Facebook had the means to check whether such a feedback form was a valid complaint or a scam. At least they tried to compensate by taking the pre-manual-submissions cutoff, otherwise I'd call this entire round a joke.
True, but anyone who went to Round 2 like that won't get t-shirt or advance even more, so nothing bad happens, and they even set the number of points to advance without manual submissions, so noone gets anything bad because of the manual submissions, right?
There are people in the top 500 who have pulled this off and will get a T-shirt. And advancing to round 2 is a reward in and of itself, which has been denied to some and granted unfairly to others.
EDIT: My bad, I now understand that the top 500 people in round 2 will receive T-shirts. Still, my second argument holds.
Well, maybe they granted advancing unfairly, but it's not denied to anyone, and the guys who cheated to advance like that won't be able to succeed even more, right?
Once bad stuff happened, what they did with that mess was pretty wise. Taking premanual cutoff was a very good decision.
Ребята, вы серьезно? Это же соревнование по программированию, а не по математике. "Поставить стек побольше" -- нормальная процедура, ничего сверхъестевтенного.
Можно было же локально потестить, ограничения дали.
Можно было за 6 минут гуглануть и тыкнуть.
Зато теперь многие знают, как работает ulimit, какие макросы надо писать в вижаке и как его менять в Джаве. Пользы явно больше, чем гипотетическая футболка.
С++-онисты могли не сразу догадаться, что падает из-за stack overflow (пример — Jacob), Javaи (даже при том, что джава пишет, в чём именно проблема) тоже могли не справиться с проблемой. И это примеры очень опытных и умных участников.
Честным решением было бы сделать cutoff = (первая задача) + (третья задача) (т.е. не затронутые большими файлами), но видимо организаторы не хотели толпу зергов во 2ом туре.
Как обычно, FHC не смог не оказаться саксом и пройти без косяков.
Я по D не успел за 6 минут даже инпут загрузить (компании, претендующей на лидерство в IT, сложно было догадаться зипник приложить?), написал им, мне ответили — отправьте что есть туда-то, мы подгрузим в табличку результаты тестирования решения. Отправил. Конечно же, ничего не подгрузили, на мои комментарии не отреагировали. Получи чувак -40 баллов и иди в ж..у, если у тебя интернет медленный. Ну, спасибо, учтем-с на будущее.
Мне кажется, можно было этот комментарий написать и на английском, учитывая, что в этом топике есть представитель FB, который отвечает на вопросы, извиняется за ситуацию и выше уже отписывался на подобные заявления, что "мой клар проигнорили", там выяснилось, что товарищ забыл прочитать ответ. А так просто грязью полить, в чем смысл?