Напоминаю, что в воскресенье в 00:00 по Москве состоится второй раунд Facebook Hacker Cup 2015. По результатам первого раунда, 732 участника продолжат борьбу. Во втором раунде, 100 лучших пройдут в третий раунд, а 550 лучших получат футболки. Раунд продлится 3 часа. Для участников, задачи будут доступны здесь, а таблица результатов тут.
UPD: Раунд закончен, опубликованы предварительные результаты. Катоффы по ним:
- Проход в третий раунд: 55 очков (A+B+C) с временем ≤ 2:21:53
- Майка Facebook Hacker Cup 2015: 10 очков (А) с временем ≤ 30:23
Я бы сказал, что завтра в 0:00. И добавил ссылку на задачи и таблицу результатов.
Спасибо, добавил. Хотя лично я фанат японской нотации времени, где считается нормой указывать времена в формате 26:00 и.т.п. для сохранения ассосиации к одному дню (например, ТВ или бары).
В такой нотации не очень понятно, когда заканчивается один день и начинается другой.
А зачем это понимать?
Я не знал, что это японская система нотации времён, но в расчётах сам мысленно всегда так и соображал: "ага, этот раунд начнётся завтра в 24:00 и закончится в 27:00". Понятно, что для большинства людей в моём часовом поясе раунд, который длится с 00:00 по 03:00 воскресенья, это именно продолжение дня субботы, а не раннее начало дня воскресенья.
Did they send notification by email this time? I didn't receive it...
I got one.
Also, 50 more shirts! Yay!
Hmm contest starts 5am here.. Not sure if I should go to sleep or stay awake (・_・ヾ
same here
Good luck, everybody! May we have a smoother round than last time :)
Is ranking going to be online during the contest? Is it going to be frozen before end of the round? When will we know the official results?
The live (pre-judgment) scoreboard is available to everyone during the contest. It never gets "frozen" (in the ICPC sense) because you don't actually see the judgments until the end of the round. The scoreboard should be revealed shortly after the end of the round.
Why can't people not competing see the problems? Can't think of any cheating argument or anything else. Would make it more exciting as a spectator to be able to see what problems people are solving.
Agreed. We're going to make sure this is available for next year. We unfortunately don't really have any time to do development on the system during the contest season because we're busy with the administration of the contest. But I intend to make a bunch of improvements for next year.
I just made a post with the problem statements: https://www.facebook.com/hackercup/posts/904095026289353
One thing I would like to add if possible divide a problem into two set, like gcj one having small test and another large. Otherwise it is painful to do small mistake which you can not correct after 6 min.
Could you reupload the image for the last problem (Fox Socks) in bigger resolution, please? It is possible to read it, but it is quite problematic.
There's an image?
You can click "Options" and then "Download" (if you're on a desktop).
I am, and I don't see "Options"; neither does Ctrl+F.
Could you share an estimate on when the results will be available? Does it make sense to wait or should we go to sleep?
On an fb post, they said about 30 minutes
Announced estimate from home page was 30 minutes ;-)
Last problem: does the queries mean:
From bin Ai to Bi or from bin Ai to bin (Ai + Bi-1) ?
Edit: nevermind, I got response from organizers. It was Ai to (Ai + Bi — 1)
I want to express my gratitude towards the authors of the last task. I believed I love segment trees so much that I can code them really quick. You showed me how wrong I was.
LoneFox is the author of that one. I think it's a really cool problem :D
How to solve the 25 points problem?
I've tried a greedy approach by picking up the string that will decrease the cost and in case of equal the one that has less similar suffix strings. But unfortunately I got a bug that I couldn't discover before the 6 minutes passed :(
Is my approach correct?
I used dynamic programming (for trie nodes in DFS order), but I don't know if a greedy solution is possible.
I did a dynamic programming, after you sort the strings: best[i][j][l], the minimum cost if you put the i-th string, you already have j other strings, and the cost of adding it is l. When you add another string, you look at the last one added and it's cost l, and see if by adding the new string you'll change the cost, so you can take this into account (since the cost of a string i is determined by the previous and the next in the sorted array)
It ran in in about 3 minutes.
Greedy approach:
start with all possible one character prefixes as S
until you have K prefixes do steps 3-4:
remove shortest prefix X with most direct childs from S
add all prefixes starting with X and one character longer then X into S
print sum of prefixes lengths in S (K oldest if you have too many)
Special cases:
if prefix has only one indirect child there is no reason to remove it
if prefix is only direct child of its parent use its parent length for step 5
use word+'#' so every word ends in leaf. just make sure 'abc#' prefix length is 3.
Обожаю дебагать деревья отрезков в 4 ночи :/
Seems like last problem needs only accuracy, accuracy and accuracy :(
It also requires some interesting insights (imo). When I first saw it I thought it was a segment tree problem with a bunch of complexity thrown in for the sake of making it take longer.
It took me quite a while to realize that you need to have two trees (or a tree with two sets of values) for the odd- and even-numbered bins to handle the fourth operation. Figuring out what to store in the tree to handle the first two operations was interesting too.
IMO, to solve this problem one should use two straightforward, but complex techniques.
That was said by author of this problem: http://codeforces.net/contest/504/problem/D :]
In this problem you don't need to use complex techniques, just straightforward:)
Why not N ≤ 100000 and M ≤ 100000 on Fox Socks? My computer couldn't run 1000000 in time...
Maybe to avoid bruteforces ran on supercomputers...
My laptop is more than 5 years old, and it processed the input in time in 1 thread. Either you need to write faster code, or your computer is too old. Still I didn't expect the input to consist almost entirely of max tests.
I won't say, how I am impressed by the innovative and interesting task D, but am I the only one, who wrote log N solution per query, and I was able to get answers only to 11 of 20 tests due to big constant of segment tree and slow notebook?..
:) I ran my solution using 3 parallel threads, and got all cases solved in ~5 minutes. I guess you could also use parallelization to squeeze through.
How to come up with last problem?
Hmm, lazy propagation can handle this one
This one too
We can use it for this problem either
...
Lets merge all of them to make single problem and see who codes faster?
Oh it could be worse...
Why not use a tree (in preorder numbering) instead of a line?
Why not make the tree dynamic?
Just 4 queries? Pfft, add several more — with min/max conditions, some bitwise operations for good measure, both updating and counting ones
and increase the limits on N, M.
'tis a dangerous path no problemsetter should ever tread!
You forgot about creating cactus out of tree by adding one more edge. :)
You forgot about dynamic cactus graphs.
// Whoops, it means I'm not the only one who thought about this :D
I think the interplay between the 1st and 4th operations is a really interesting part of this problem. I agree that when I first saw this I thought it was a chimera, but there are subtleties at work that make it much more than the sum of its parts.
If that is the only interesting part of this problem, why not get rid of queries 2 and 3? There are already dozens of problems on queries 1, 2 and 3.
I think 1 and 2 together force a bit more consideration as to what gets stored at each node in your segment tree.
If this is the first time such problem appear, you are correct. But unforetunately, FBHC is not the first one, nor the second one to come up with such problem
(・_・;). Given that this problem is painful to code + already appeared on the Internet, I think many competitors felt like(╯°□°）╯︵ ┻━┻(at least 36 people downvoted your 1st comment).Also, about the 3rd problem, isn't it too old too? DP on tree, at each vertex you need Knapsack DP to select K vertices from subtree. I solved it many times already. And it was quite straight-forward to reduce to that problem.
(˘_˘٥)Overall, so far I haven't seen any interesting problems (all are old, only more complexity is added). Since next round is to select top 25, I hope the quality of problems will significantly improve..
ヽ(•‿•)ノI understand where you're coming from. If you have some particular favourite problems from any contest in the last few years, I'd love to see them, and this goes for everybody else too. I've always been a huge Derek Kisman (SnapDragon) fan.
I'm probably a little out of touch because I haven't been a regular competitor at all for the last few years. But yeah, any problems you or anyone else has been really fond of recently I'm quite interested in seeing. This is the kind of feedback that really helps improve future years.
My opinion:
[2013 Round 3]
Digits War:
(˘_˘٥)Name the Baby:
(˘_˘٥)Greedy Entertainers:
ヽ(•‿•)ノ[2013 Finals]
Archiver:
ヽ(•‿•)ノColored Trees:
(˘_˘٥)Minesweeping:
(╯°□°）╯︵ ┻━┻Teleports:
ヽ(•‿•)ノ[2014 Round 3]
Secret Santa:
(・_・;)Pizza Baking:
ヽ(•‿•)ノRestaurant Chains:
ヽ(•‿•)ノ[2014 Finals]
Intervals of Love:
(・_・;)Lunch at Facebook:
(・_・;)Fortunate Wheels:
(˘_˘٥)Tours:
(˘_˘٥)Duly noted. I was thinking more about contests other than ours, but feedback about our contest is pretty important too :)
Some very nice problems from recent CF rounds:
http://codeforces.net/contest/506/problem/E
http://codeforces.net/contest/497/problem/D
http://codeforces.net/contest/497/problem/E
The polygon one is definitely something I like. I'm not great with applying matrix multiplication so I'll need to read those other two more.
In my weekly contest summaries (http://petr-mitrichev.blogspot.com/), I try to highlight problems that have caught my attention for one reason or another, but usually for being interesting :)
In my last post, I mentioned http://codeforces.net/contest/506/problem/E (which Makoto has also covered below) and http://community.topcoder.com/stat?c=problem_statement&pm=13346&rd=16277
Two weeks ago, it was problem 43 "Nanobugs" from here http://newyear.snarknews.info/files/2014/prob_p.pdf
One can probably go further in the archives :)
When I was active I read your blog voraciously, and I ought to pick it up again indeed. Thanks for making it :)
I usually prefer problems that are different from tradiational problems from contests. Some of my favorite problems:
How about the fact that the array was circular? Doesn't add much to the problem.. just the need to split the query in 2.
If we omit the last operation (which is really just a few more lines of code), it becomes one of the first hard problems I ever encountered in a competition. Around 4 years ago. No, it's not very original. Not to mention it's practically impossible to code it in time if you don't know all the catches already.
If it's really necessary to give a DS problem in a contest like this, then you should've omitted one type of updates and significantly decreased the point value.
Last problem, I finished implementing my code when there were 10 minutes left. My code passed first 4 pretests and failed the last one :(
What a great feeling.
I found like 10 different bugs that didn't change answer on first 4 pretests, so if it makes you happy you can't really know how close you are to answer based on that :P
Furthermore, problem C has a tricky case from using DP approach if K = 1. If not considered separately, the code might output 0 instead of 1. However, no case with K = 1 was present in at least two people's inputs.
No comment on whether this is good or bad, but I hope K = 1 case wasn't present in only some people's inputs.
Yeah I also noticed the same. My input also didn't have the case.
You're right that there was no K = 1 case. That was an oversight on my part. If we had it, it definitely would have been included in everybody's files.
Can someone share tests/answers? I'm adding a training to the Gym. I have my answers for A-C, but not sure about them.
Mine are here. Zlobober's solutions give same answers as mine.
2015 Facebook Hacker Cup, Round 2
30 seconds for D are probably not enough.
Mine are here.
I want to say that quality of tests is... well, I don't want to use the word awful.
In my input for task C there wasn't any test with K = 1. Are you serious? At least there should be following test:
I'm sure that 10% of AC solutions for this task will handle this test incorrectly. Techincally, the answer 0 here works (since we choose some word and empty prefix is enough to pick it), but there was a remark in the statement regarding non-empty prefixes.
It is such simple idea that there should always be testcases attaining maximum/minimum possible values of constraints...
Well, yes, on the other hand one might argue that it's good to not penalize contestants who solved the task correctly and forgot to add one if statement.
The only absolutely necessary requirement is to either give this case to everybody or give it to no one. Out of four people who shared this information, no one has it, so hopefully no disaster here.
In case you don't want to penalize contestants for that, why not set the constraint as K>=2?
Good point.
Yes, I was astonished to discover that test case is missing...
Most of the participants who didn't consider this special case in their solution would just manually fix it once they see "0" in the output. So IMO missing this case is not a big deal.
10% in my comment is my estimation for the number of contestant that do not pay attention for zeroes in their output. Actually I think this number may be even bigger... That really affects the final scoreboard.
I've added the test to the Gym's version. After rejudge the number of solvers reduced from 52 to 33.
Looks like YuukaKazami (Tom Chen) have submitted his solutions for R1 instead of R2 and thus got zero points instead of first place. What a pity.
I thought there could be some victims when I saw all T=20...
I have some suggestion to FHC:
1) That kind of errors could be prevented if FHC does more sanity check on the output file. The output of Round 1 A is positive integers, but Round 2 A is yes/no.
2) Change the number of test cases between the problems: Why T=20 for all problems?
3) Even if sanity check found output file is wrong, the font for notifying this is not bolded or underlined, so there is some possibility to neglect the message. Some red-background box, like notifying problem statement changes, will work.
1) Yup. For next year I plan to always include the sample cases as the first K cases in everybody's input. Then we can confirm that you at least match the sample output. That'll catch this along with a slew of other problems, like:
2) Yeah, I intend to change this too.
3) Agreed. I'd like a more eye-catching UI for things like this, and for clarification announcements. The current UI is at least 4 years old.
Any progress on "For next year I plan to always include the sample cases as the first K cases in everybody's input."?
As far as I noticed, they are always included but somewhere in the middle because tests are shuffled.
I came here to ask the exact same question! I think the sample cases were also included in a random order last year, so it seems they didn't implement this, which would be a really good change. I guess I should have bugged wjomlex personally when I got to see him :p
Yeah, currently the samples are always included, but mixed in. We took a different approach of catching more PEs before they happen. If you have the wrong number of cases in your output, or the wrong number of tokens (contiguous non-whitespace characters) in a case, or your first tokens aren't "Case" and "#xx:", you'll get a formatting error right away and you'll be asked to resubmit.
The idea of matching on the samples up front was largely to prevent PEs, not WAs, so if you have the right format, but don't match the samples, we won't say anything.
We finally changed our legacy "every problem has 20 cases" thing this year (that was very silly), and we stopped requiring a specific number of decimal places for real values.
You increased number of T-shirts by 10%.
I suggest you to increase the number of the advancers by 10% too.
Just an idea from the guy on the 110-th place.
There are 550 Tshirts :)
Yep, I know. But there were only 500 of them before round 1.
Oh, sorry, misunderstood the comment :(
Good idea, johnasselta took 111th place :]].
;_;
This is the best reply I've ever seen on CF.
+105 :)
BTW, there are people in top 100 with wrong answers for this test case. Of course, I won't mention their names, because this is both unethical and unfair, but increasing the number of spots in Round 3 may actually be a good idea.
In case you think, that I am complaining just because I didn't made it to the Round 3 — I'm truly not. I support fairness, that's all.
Would it be fair for those who legitimately got to top 100?
They want to compete among 100 participants as rules say, not among crowd.
Before my submission, I had thought of this case.
Then, I checked if there were "0" in my output, and opened the input file, searching for " 1".
There were no such cases.
Therefore, I ignore this situation, and submit the "wrong" code.
Can you give an estimate regarding the T-shirt shipment timing? It's not really a crucial thing right now, but I'm kinda worried about them getting stuck somewhere in the process. Smooth round by the way, I'm glad there were no technical issues this time.
I'm going to change address in 5 months. I don't know if I should enter my current address, since if T-shirts does not come in 5 months, I'll lose it..
I had the same issue a few times and the easiest solution for me was to send the T-shirts at my parents address (which changes an order of magnitude less often than mine).
I'm not sure we have an estimate at the moment. I would say message me in a month and we should have a better idea then. The T-shirt logistics are one thing that I'm not really a part of.
Hi, I recently figured out that my address was incorrect and I fixed it like 10 minutes ago.
Wasn't it too late?
No problem. We don't have the shirts printed yet :)
Did you notice to ZhengJie rank 101 ? his total time is 2:21:54!! Just 1 second more than rank 100. Is it unfair or we should call him so unlucky person ?
And what is unfair exactly?
I remember that in ICPC World Final 2013, they gave a bronze medal to rank 13th just because of tiny difference in total time with the rank 12th.
There was a debate on this here
Anyway, I think it's not unfair if they accept all participants with total time less than 1 minute with rank 100.
ICPC and FBHC are too different contests, why do FBHC organizers need to care about the decisions of ICPC organizers at all? This is not a common practice, I never seen this kind of "additional prizes" anywhere except ICPC, where all rules are weird (e.g. in Asia regionals, last year & the year before that, there was rule that in each of Singapore & Hong Kong, only 1 team can advance to WF).
There are lots of reasons why we should not accept participants with 1 minute more:
Bad luck "only"...
For Fox Socks, the gap between the 4th and the 5th sample testcases are quite huge. I failed all the sample testcases on my first run. Luckily, the first four sample testcases are small (N=5) and I can debug them. I fixed several mistakes and managed to get the first four sample testcases correct, but the last sample case is too big to debug with. Can't get the last sample correct until the end of the round :'(
Anyway, I'm still qualify to Round 3. Yeay!
Nevertheless, correct output on last sample wasn't a proof the program correctness. At some moment (with some combination of bugs) I had all samples passing, but program was still giving wrong answer on some obvious cases with n = 2.
The best idea for this task was to start with writing naive solution (implementing what is described in statement), checking that you understand complicated input format correctly, and only then writing the full solution and stressing it with a naive.
I was very lucky for the T-Shirt rank 550.
can anybody tell me how to reduce time complexity of my code for the problem Autocomplete Strikes Back
(http://codeforces.net/gym/100587/submission/9562793)
recur() doesn't modify "vector<int> y", so it should be "const vector<int> &y" to avoid copies. Furthermore, recur() is called repeatedly with same parameters, so you can use memoization.
Also, for your own sake, use an editor with proper automatic indentation, makes the code much easier to read.
diff: http://pastebin.com/6shUwb1f
Can someone enlighten me please; I see the following pattern common amongst many AC solutions submitted for problem #2: all_critical, eg. @ http://attachment.fbsbx.com/hackercup_source.php?sid=369011793270735
sum = 1;1 - notsele[i]?:dp[i] = sum / (1 - notsele[i]);Is this popular approach different from what the editorial note explains @ https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2015-round-2-solutions/1051224511560116 ?
Thanks
Explanation posted as top FB comment to official editorial:
My question:
Forget about 20 for a moment. You have n bars and make 1 step.
Как долго футболки идут из калифорнии в Питер?
Yay! Received my T-Shirt today. =D
(Classy of Facebook to use FedEx delivery by the door. ^^)
Eagerly waiting ! :D Haven't received mine yet. Haven't got any response lately from them either. :/
Just a small clarification in 20 pt problem . In the editorial , we need to calculate upto 20 powers of
pand1-pbut these may become so small thatP(s,i)may become zero which infact is not exactly zero. This leads to allP(s,i)values to become zero. How to overcome this?You scared me dude. Because of your post this blog appeared in the recent actions. After reading "Round is over" I thought I've missed it.
I almost had a micro heart attack.