### Sammarize's blog

By Sammarize, 6 years ago, translation, ,

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.

• +80

 » 6 years ago, # |   -13 I've been wondering — why do we need send output file AND source code? Why not only source code?
•  » » 6 years ago, # ^ |   -7 Probably for finding cheats out.
•  » » » 6 years ago, # ^ |   +14 how can find cheats with outputs :-?
•  » » » » 6 years ago, # ^ |   +13 I meant code for finding cheats out (MOSS) and output because you are free to chose language.
•  » » 6 years ago, # ^ |   +59 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.
•  » » » 6 years ago, # ^ |   +6 So why do we need send source code? o.O
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   +2 what about sending a correct output with source code only print Hello World :D
•  » » » » » » 6 years ago, # ^ |   +8 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.
•  » » » » » » » 6 years ago, # ^ |   0 #pragma comment(linker, "/STACK:134217728") It works for Visual Studio.
 » 6 years ago, # |   +48 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).
•  » » 6 years ago, # ^ |   +16 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.
•  » » 6 years ago, # ^ |   +10 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.
 » 6 years ago, # |   -10 who can hack facebook in this round this is important
•  » » 6 years ago, # ^ |   +3 Whoever succeeds to hack Facebook during round deserves to pass to the next round, right? :D
•  » » » 6 years ago, # ^ |   +2 Not really funny, no.
 » 6 years ago, # | ← Rev. 2 →   +28 (I will glad to see the remarks about translation mistakes) 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)
•  » » 6 years ago, # ^ |   -6 Translation is pretty OK though I'm somewhat puzzled by: 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. 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.
•  » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +7 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?
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 Is it possible to submit the practise questions of old hacker cup contests?
•  » » » » 6 years ago, # ^ |   -13 yes
 » 6 years ago, # |   +18 dis like me pls
 » 6 years ago, # |   -16 Best of luck to everyone participating!!
 » 6 years ago, # |   +11 Is participation in the qualification round required to participate in round 1? I didn't realise it would be held so early!
•  » » 6 years ago, # ^ |   0 Yes, one solved problem in the qualification round is required.
 » 6 years ago, # | ← Rev. 4 →   -45 ..
•  » » 6 years ago, # ^ |   -34 I upvoted you for your avatar!
 » 6 years ago, # |   +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 :( :(
 » 6 years ago, # |   +109 I guess contestants with slow Internet connection already have some special feelings about those 20mb-large input files...
•  » » 6 years ago, # ^ |   +41 My internet downloads 20 mb in 18 minutes, I have a great problem... xD
•  » » 6 years ago, # ^ |   +83 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.
•  » » » 6 years ago, # ^ |   +29 For outputs, jury can just ask to upload some cryptographically secure hash of the output file.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 If the output is (almost) unique.But there still will be problems with different endlines, extra spaces, #'s etc
•  » » » » » 6 years ago, # ^ |   +34 Ask for hash in 6 minutes and for the actual output in unlimited time. All such problems are trivially solvable in cryptography.
•  » » » » » » 6 years ago, # ^ |   0 Nice idea, agreed
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +26 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.
•  » » » » » » » 6 years ago, # ^ |   0 Sure there are such tasks. For example these 4 tasks from my rounds on Codeforces: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.
•  » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   +20 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.
•  » » » 6 years ago, # ^ |   +11 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.
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ |   0 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!
•  » » » » 6 years ago, # ^ |   +9 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.
•  » » » » » 6 years ago, # ^ |   0 Oh. Ok. I understand the situation. Thank u for your answer!
•  » » » » » 6 years ago, # ^ |   -8 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? :/
•  » » » 6 years ago, # ^ |   +32 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?
•  » » » » 6 years ago, # ^ |   0 We have logs showing the download times, and we still require that people submit their source code which we can check manually.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 6 years ago, # ^ |   0 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!
•  » » » 6 years ago, # ^ |   +28 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.
•  » » » » 6 years ago, # ^ |   +46 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.
•  » » » » » 6 years ago, # ^ |   +19 Good. I agree that this is the right thing to do at this point.Any estimate on when the results will be up?
•  » » » » » » 6 years ago, # ^ |   +7 My current estimate is about 6 hours.
•  » » » » » 6 years ago, # ^ |   +3 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).
•  » » » » » » 6 years ago, # ^ |   +16 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.
•  » » » » » » » 6 years ago, # ^ |   -19 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: No more complaints about Stack Overflow issues. No more complaints about manual submissions. Several strong competitors who were finalists in previous year will advance. Stronger competition for T-shirts — if there will be 550 T-shirts and now 731 person advanced, then there's basically no competition for T-shirts at all, right? No competition leads no motivation. Facebook Hacker Cup gets more popularity because so many people will not be annoyed by unfairness. 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.
•  » » » » » » » 5 years ago, # ^ |   +3 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
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 The T-shirt design was finalized yesterday. I'm not sure about the ship date at the moment.
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   -11 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.
•  » » 6 years ago, # ^ |   0 You have 6 minutes to send the solution.
•  » » » 6 years ago, # ^ |   0 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?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +12 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).
•  » » » » 6 years ago, # ^ |   +17 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.
 » 6 years ago, # |   0 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 :(
•  » » 6 years ago, # ^ |   +3 There is a clarification there to contact them in case if you had problems downloading huge input file on slow connection.
 » 6 years ago, # |   +12 Remove all expired time and change 6 min to 15 min ;)
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 tnx but how ?edit: not funny :(
•  » » 6 years ago, # ^ |   0 Why you are so bad? Liar!
 » 6 years ago, # |   +32 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.
•  » » 6 years ago, # ^ |   +8 Actually, in my case, I had to solve at mid night because of downloading the input =))
•  » » 6 years ago, # ^ |   0 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)
 » 6 years ago, # |   -21 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.
 » 6 years ago, # | ← Rev. 3 →   -9 Sorry.
•  » » 6 years ago, # ^ |   -18 Please do not discuss anything regarding content of tasks before the end of the round.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » 6 years ago, # ^ |   +12 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.
•  » » » 6 years ago, # ^ |   +1 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.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   +8 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.
•  » » 6 years ago, # ^ |   -13 My computer couldn't handle the large input files. On BOTH the second and last problems :(.
•  » » » 6 years ago, # ^ |   +10 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.
•  » » » » 6 years ago, # ^ |   +34 Microsoft Notepad))
•  » » » » » 6 years ago, # ^ |   -11 You can't install anything better?
•  » » » » » » 6 years ago, # ^ |   0 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 :\ :(.
•  » » » » » » » 6 years ago, # ^ |   -8 Then why did you say "MS Notepad"? I know it has trouble opening large files, so I assumed it was the problem.
•  » » » » » » » » 6 years ago, # ^ |   0 what?I did not say MS notepad (though i used that to open my file.)
•  » » » » » » » » » 6 years ago, # ^ |   0 Oh wait. It wasn't you I was initially replying to... I didn't notice because your previous post seemed like it was.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 6 years ago, # ^ |   0 To who am i supposed to mail the solution, please clarify??
•  » » » » 6 years ago, # ^ |   0 "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.
•  » » » » » 6 years ago, # ^ |   0 Was anyone lucky to get the response for such "feedback"?
•  » » » » » » 6 years ago, # ^ |   0 Yes I got a response, and sent my solution. Now, waiting for adding the problem before the round ends(as they said).
•  » » » » » » » 6 years ago, # ^ |   0 What? I sent them a response but got none back :\
•  » » » » » » » » 6 years ago, # ^ |   0 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).
•  » » » » » » » » » 6 years ago, # ^ |   0 I think i sent it ~40 minutes before the round ended.
•  » » » 6 years ago, # ^ |   +11 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.
 » 6 years ago, # |   +40 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!
•  » » 6 years ago, # ^ |   +1 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!
•  » » » 6 years ago, # ^ |   +20 ulimit -s unlimited should help
•  » » » » 6 years ago, # ^ |   0 Nice. This actually worked!
•  » » » » 6 years ago, # ^ |   0 That moment when you discover the solution to your problem on codeforces comments
•  » » 6 years ago, # ^ |   +11 What was the fix? I had the same story but with a different ending. :'(
•  » » » 6 years ago, # ^ |   +15 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.
•  » » » » 6 years ago, # ^ |   0 This problem is not really related to the actual programming.. :\It's not really fair to fail people for this reason :|.
•  » » » » » 6 years ago, # ^ |   -11 i have failed because of this and i think i must wait for another year :/
•  » » 6 years ago, # ^ |   +44 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.
•  » » » 6 years ago, # ^ |   -7 true sad story
•  » » » 6 years ago, # ^ |   +27 yes the same for me; my timer expired because I couldn't fix that damned stack overflow error in time! This is completely UNFAIR!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +26 Same for me in D. I managed to rewrite my DFS to be iterative, but it was intense ;)
•  » » 6 years ago, # ^ |   +5 Same here, but with memoization you can do this: for(int i=n-1;i>=0;i-=1024) calc(i,...); print calc(0,...);Or random calls if you still get RTE.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 Will I get WA if I use file input/output?
•  » » 6 years ago, # ^ |   0 No
 » 6 years ago, # |   0 When will see results? Right after round ending?
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   +5 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) :(
•  » » 6 years ago, # ^ |   +6 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 :)
 » 6 years ago, # |   +39 BTW, It would be cool to see in scoreboard problems failed due to time limit to better understand current situation, wouldn't it?
 » 6 years ago, # |   +8 Guys, how did you solve 4th problem?
•  » » 6 years ago, # ^ |   +1 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.
•  » » » 6 years ago, # ^ |   +6 I did the same, but took 50 instead of 10.I think 20 is enough, but took 50 for insurance.
•  » » » 6 years ago, # ^ |   +6 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
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 :\
•  » » » » » 6 years ago, # ^ |   0 If you swap colors, you can use 5 colors or even less — look at my comment above and my submission at Gym
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 6 years ago, # ^ |   +3 my solution crashed on 5th test case))
•  » » » 6 years ago, # ^ |   0 Mine too on local machine, but passed here in Gym. May be stack size? (I am talking about Corporate Gifting)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +19 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.
•  » » » 6 years ago, # ^ |   +2 What if we have 1 in all leaves and minimum excludant from labels of children in other nodes? Is it wrong?
•  » » » » 6 years ago, # ^ |   0 i also guessed it at first. But when I simulated it , it gave more value . So its probably not right way .
•  » » » » 6 years ago, # ^ |   +9 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)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +9 0 1 0 2 2 3 2 4 Your coloring is 3 1 2 1 1 while we are able to make 1 2 2 1 1.
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +55 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: a[1] = 1 a[x] = 1 + a[x-1] + a[x-2] + ... + a[2] + a[1] 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].
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 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).
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   0 oh sorry, now i get it, is the minimum so you need the minimum in each child, thanks
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 6 years ago, # ^ |   +3 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.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +6 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] = 3 x - 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).
•  » » » » 6 years ago, # ^ |   +3 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.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 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!
•  » » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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 ??
•  » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   +5 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.
•  » » » » » 6 years ago, # ^ |   +3 Sorry, my bad .. I have uploaded it here for reference : http://home.iitk.ac.in/~skmanish/p39-kubicka.pdf
•  » » » » » » 6 years ago, # ^ |   +10 I tried to look for the free version of paper for almost 10 hours yesterday.I think you cannot distribute private papers like this.
•  » » » » » » » 6 years ago, # ^ |   +10 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.
 » 6 years ago, # |   0 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.
 » 6 years ago, # | ← Rev. 6 →   0 Irrelevant, I wrongly assumed that large files are the same.
•  » » 6 years ago, # ^ |   +27 Aren't inputs different for every participant?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 6 years ago, # ^ |   +8 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
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » 6 years ago, # ^ |   0 How to simply calculate this hash?
•  » » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   +1 Actually you don't have to; you can find it if you open your submission from the problem page...
•  » » » » 6 years ago, # ^ |   0 Yeah, I was pointing out that there's no need to ask questions that can be answered by a single Google search.
•  » » 6 years ago, # ^ |   +9 A: d0ee7647ad6dd0014a1dd5d197805964 B: 57664116c970da2d8be396e36c872a61 C: 24da720c50105b958cd5ae9129c2653b D: dd04084a224c69ea300931f1fca8ef69Indeed it looks that there are at least two different inputs :)
•  » » » 6 years ago, # ^ |   +25 And here are my inputs (the larger ones are still uploading): https://drive.google.com/folder/d/0B2d37tm1YmE3a0xMLTJFdDZyams/editIf somebody is not lazy enough, please post the MD5s of your outputs on these inputs :)
•  » » » » 6 years ago, # ^ | ← Rev. 6 →   0 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 directlyWould you share your outputs? I get both hashes different:)My outputsHashes with \n as newline ac78b81e3db66c301db1fd4d847543eb autocomplete.txt d1a57df20500e6fcab12d1a9b30f4734 gifting.txt 1a126e2363aa662c1749fe174d3a0b94 homeworks.txt 3e6c597d827ad5779b8df450b3dfd20b winnings.txt 
•  » » » » » 6 years ago, # ^ |   0 Mine have Windows newlines, no extra spaces, and have #s.I'm doing this from a phone, copying outputs would be cumbersome :(
•  » » » » » 6 years ago, # ^ |   0 Got the same output with these 4 inputs.All i need to do next is bless the manual judgement will give the correct answers.....
•  » » » » » 6 years ago, # ^ |   0 all outputs match :)
•  » » » » 6 years ago, # ^ |   0 I got the same hashes for output files (\r\n after every case, including the last one) with your input files for all problems.
•  » » » » 6 years ago, # ^ |   +3 OK, got same hashes with \r\n newlines
•  » » » » 6 years ago, # ^ |   +8 Either we made similar mistakes...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I have the same hashes for A,B,C)) Thanks for sharing!
•  » » 6 years ago, # ^ |   0 All my hashes are different from yours. So let's hope our inputs are different :)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 According to adelnobel they are different. I also forgot about line endings.
•  » » » » 6 years ago, # ^ |   +8
 » 6 years ago, # |   +5 Note to self: 1<<20 is smaller than 1e7.
•  » » 6 years ago, # ^ |   0 Rule of thumb for quickly estimating powers of two: pow(2,10) == 1<<10 == 1024 > 1000 now estimate e.g. 1<<23: pow(2,23) == pow(2,10) * pow(2,10) * 2*2*2 > 8.000.000
 » 6 years ago, # |   0 What is the answer for the 3rd problem's input: 1-0
•  » » 6 years ago, # ^ |   0 1 1?
•  » » 6 years ago, # ^ |   0 1-1
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 it should be 1 1 cause only one way to achieve this
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   0 Thanks, I also think 1-1 is the right answer.
•  » » 6 years ago, # ^ |   0 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!
•  » » 6 years ago, # ^ |   +8 So a victory of 1-0 is stress-free and stressful at the same time?!This makes no sense whatsoever :)
•  » » » 6 years ago, # ^ |   +5 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.
•  » » » » 6 years ago, # ^ |   0 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" :)
•  » » » » » 6 years ago, # ^ |   +5 Well, it's also quite difficult to imagine a match with score 2000-1999, if we want to think this way...
•  » » 6 years ago, # ^ |   0 It can be "1 0" also.
 » 6 years ago, # |   -8 Why thinking bottom-up is so much harder than recursive DP :(
•  » » 6 years ago, # ^ |   0 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..
•  » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 Almost 1000 people answered all four problems.... looks like you can't make any single mistake in order to go to the next round...
•  » » 6 years ago, # ^ |   +9 Last years showed near 50 percent wrong submission and two any problems were enough.
•  » » 6 years ago, # ^ |   +7 Submitted on != answered correctly.
•  » » » 6 years ago, # ^ |   0 I know... but given that there are 1000 people...
•  » » » » 6 years ago, # ^ |   0 If only 499 don't fail on at least one of the 25pt problems, 75 will be enough to go to the next round.
•  » » » » » 6 years ago, # ^ |   0 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%....
•  » » » » » » 6 years ago, # ^ |   +4 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.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I also thought about this testcase. It's both stressful and stressfree, right?
•  » » » » » » » » 6 years ago, # ^ |   +1 Yes.
•  » » » » » » » 6 years ago, # ^ |   +3 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.
•  » » » » » » » » 6 years ago, # ^ |   -18 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.)
•  » » » » » » » » » 6 years ago, # ^ |   +14 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.
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 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).
•  » » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » » » 6 years ago, # ^ |   0 According to you, what should be the correct answer for this testcase should it be 1-1 or 1-0.
•  » » » » » » » » 6 years ago, # ^ |   0 Read the comments above.
•  » » » 6 years ago, # ^ |   +5 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.
•  » » » » 6 years ago, # ^ |   0 (many people will fail on C) Why do think so? what's the deal? :D
•  » » » » » 6 years ago, # ^ |   0 Tests like 1-0 or 1000-0.
•  » » » » » » 6 years ago, # ^ |   0 Correct answer is "1 1" for both, right?
•  » » » » » » » 6 years ago, # ^ |   0 Yes.
•  » » » » » » » » 6 years ago, # ^ |   0 Why do you think there will be many wrong answers with these test?
•  » » » » » » » » » 6 years ago, # ^ |   +3 People first iffing out the j = 0 case, then the j = b case. :)I might be wrong though.
•  » » » » » » » » » 6 years ago, # ^ |   +8 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 .
•  » » » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 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 :)
 » 6 years ago, # |   +1 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?
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   +10 "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.
•  » » » » 6 years ago, # ^ |   +25 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.
•  » » » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 i have sent a clarification due to submit issue in last 10 minutes but no answer tell now?!!
 » 6 years ago, # |   +11 Let's judge our solutions in Facebook Hacker Cup 2015 — round 1: http://codeforces.com/blog/entry/15864
 » 6 years ago, # | ← Rev. 6 →   +48 It will be a long day at Menlo Park. :)
•  » » 6 years ago, # ^ |   +23 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.
•  » » » 6 years ago, # ^ |   0 when you show us the results?
•  » » » » 6 years ago, # ^ |   +3 The tentative results should be announced later this evening.
•  » » » » » 6 years ago, # ^ |   0 Ok, Thx.
•  » » » 6 years ago, # ^ |   0 Now you'll be testing future rounds on a typical internet connection? ;)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Oh yes, yes indeed :)shiplove
 » 6 years ago, # |   +10 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!
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   +8 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).
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   -35 As flashion 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).
•  » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » 6 years ago, # ^ |   -19 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?
•  » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » » » 6 years ago, # ^ |   -28 It looks like number of necessary colors is polylog n.
•  » » » » » » » » 6 years ago, # ^ |   +30 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.
•  » » » » » » » » » 6 years ago, # ^ |   -25 You are right 5 does not have to mean constant. But in practice it is close to log log n which is too little.
•  » » » » » » » » » 6 years ago, # ^ |   +50 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.
•  » » » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » 6 years ago, # ^ |   +9 Let me translate what you said:"As flashion 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.
•  » » » » » » » 6 years ago, # ^ |   0 Here is link to the solutions Link There is no proof tough.
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   +14 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?
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 6 years ago, # ^ |   +8 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)
 » 6 years ago, # |   +65 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.
•  » » 6 years ago, # ^ |   +5 Memory limit exceeded on test 2 (Autocomplete) However it runs fine in my 8G machine :)
•  » » 6 years ago, # ^ |   0 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 .
•  » » 6 years ago, # ^ |   0 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?
•  » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # | ← Rev. 2 →   +28 For problem 4, this paper explains a simple O(n) algorithm — http://www.public.asu.edu/~halla/papers/OCCPWG96.psMy implementation — http://codeforces.com/gym/100579/submission/9468814This problem on uva is pretty similar http://uva.onlinejudge.org/external/113/11307.html
 » 6 years ago, # |   +34 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
 » 6 years ago, # |   0 Solution to problem 4 was dp + dfs.Here is mine accepted solution of it in codeforces gym. http://codeforces.com/gym/100579/submission/9474632
•  » » 6 years ago, # ^ |   +5 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.
•  » » » 6 years ago, # ^ |   +3 Here is the ideone link of the solution http://ideone.com/oGmWhE
•  » » » » 6 years ago, # ^ |   0 Thanks!
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   0 both one
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   +28 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.
•  » » » » 6 years ago, # ^ |   +3 There was no time for what?
•  » » » » » 6 years ago, # ^ |   0 I speak about getting WA on some pretests like codeforces, or on small input like codejam.
 » 6 years ago, # |   0 ... Then, Do you think that 60 points is enough to advance to Round 2?
•  » » 6 years ago, # ^ |   0 I hope yes, but think no
•  » » 6 years ago, # ^ |   0 Definetly NO :) Bloody hell! :@
 » 6 years ago, # |   +9 Guys... ranking has been changing... I hope it's final migration of manual submissions