Round 1 FHC starts in January, 17, at the 18.00 UTC.

Look this and other information here. The top 500 finishers will advance to Round 2, as well as contestant who gets the same number of points as the 500th contestant.

Round 1 will last 24 hours. This is not virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is unusually decision. It is clearly that organizers wants all participants to find the convenient time to solve the problems. I hope the problemset we be completed such a way so how many times does participient 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 large number of participants, much more than 500, but very few people will be able to solve something else.

(I will glad to see the remarks about translation mistakes)

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 1starts in January, 17, at t̶h̶e̶ 18.00 UTC.Seethis and other information here. The top 500 finishers will advance to Round 2, as well asanycontestant who gets the same number of points as the 500th contestant.Round 1 will last 24 hours. This is not

avirtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It isan unusualdecision. It isclearthat organizerswantall participants to findaconvenient time to solve the problems. I hope the problemsetwillbe completedinsuch a waythathowmuch time the participantcan 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 byalarge number of participants, much more than 500, but very few people will be able to solve something else.(I will

beglad 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.

..

I upvoted you for your avatar!

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

beforeconsidering 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

everybodyto 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.

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.

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

`ulimit`

on 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 unlimited`

should 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.

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.

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 havejin nodev.One can prove that in a correct answer

jmust be ≤degree[v] + 1.To calculate it quickly one can precalculate the first and the second minimum among

jfor eachv.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 1`

while we are able to make`1 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] = 1a[x] = 1 + 2 * (a[x- 1] +a[x- 2] + ... +a[2] +a[1])At least 2

vvalues must appear in children. If there is only onev<xvalue, you can swap it with root and you havevin root.So

a[x] = 3^{x - 1}I assumed secondy< = 13. I hope it's enough. (curiosity — When I sety< = 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.com/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.

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.

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 kindsof 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 thej=bcase. :)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.

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.com/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

typicalinternet 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

kcolors are required for any givenk. Just start from 1, and on thek'th step attach lots of constructions fork- 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.com/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.com/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

wastime 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

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.