Probably for finding cheats out.

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.

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.

Whoever succeeds to hack Facebook during round deserves to pass to the next round, right? :D

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.

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.

Yes, one solved problem in the qualification round is required.

I upvoted you for your avatar!

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.

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.

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.

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.

You have 6 minutes to send the solution.

There is a clarification there to contact them in case if you had problems downloading huge input file on slow connection.

tnx but how ?

edit: not funny :(

Why you are so bad? Liar!

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)

Please do not discuss anything regarding content of tasks before the end of the round.

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.

My computer couldn't handle the large input files. On BOTH the second and last problems :(.

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.

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!

What was the fix? I had the same story but with a different ending. :'(

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.

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:

for(int i=n-1;i>=0;i-=1024)
   calc(i,...);

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.

No

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.

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 :)

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.

my solution crashed on 5th test case))

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.

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:

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

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 ??

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.