Seems like everybody related to the event already knows, but anyway I'll remind.

Facebook Hacker Cup Round 3 is happening today at 1:00 PM PT. Top-25 coolhackers will continue to Final Round.

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 176 |

6 | maroonrk | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Seems like everybody related to the event already knows, but anyway I'll remind.

Facebook Hacker Cup Round 3 is happening today at 1:00 PM PT. Top-25 coolhackers will continue to Final Round.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 00:04:14 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Man, that was... definitely harder problems than last year. No AC on the 2nd problem...

I solved the 1st problem with

O(K^{2}C) dynamic programming, taking (number of processed families, number of gifts added between them) as a state;Cis some large constant here, if we consider the size of a family to be constant — and small.I realize that if the 2nd problem looks really easy, costs that many points, and is in the last round, it will be something really hardcore, so I never even tried to code anything on it :D

I spent most of the time on the 3rd problem, and managed to prove that the graph must be bipartite, planar (there's no solution for

K_{3, 3}) and got to the assumption that is must be reducible to a single edge by the operation "find 2 connected vertices of degree 2 and delete them". Is it good or completely off-topic? :DStill, top 50 is good enough...

How have you proven that graph must be planar?

I proved that satisfying the main condition for

K_{3, 3}(as a subgraph) leads to a contradiction.I'll assume you know the trivial rules for vertices at distance 1.

Firstly, a lemma about

K_{2, 2}: let's say that one partition of a subgraphK_{2, 2}contains vertices (1,2) and the other (3,4); w.l.o.g., associate vertex 1 with a subsetS_{1}of chains, such that no other vertex is associated with a smaller set. Then, for vertices 3 and 4, we haveS_{3}=S_{1}+aandS_{4}=S_{1}+b(a,bare also chains, anda≠b), and thenS_{2}=S_{1}+a+b, because ifS_{2}didn't contain (w.l.o.g.)a, thenS_{2}=S_{1}, which is impossible.I just realized there's a stroger version, working on any subgraph

K_{2, 3}. Let's use the same notation as above (partitions (1,2) and (3,4,5));S_{3}=S_{1}+a,S_{4}=S_{1}+b,S_{5}=S_{1}+c. There are 2 possible cases: |S_{1}| is the smallest or |S_{3}| is the smallest (w.l.o.g.). If it'sS_{1}, then by the lemma onK_{2, 2}(1,2,3,4) and (1,2,3,5), we haveS_{2}=S_{1}+a+b=S_{1}+a+c; otherwise, by the lemma on (1,2,3,4) and (1,2,3,5), we haveS_{4}=S_{3}+a+b=S_{5}; both are contradictions. QED.My mistake, it doesn't imply planarity.

K_{3, 3}can be a subgraph of a minor, it just can't be a direct subgraph.Edge contraction affects the solution, so its off-topic.

It's not edge contraction, though. It's edge deletion. I don't merge the endpoints of an edge, I delete them both.

And just to make this clear: leaves are trivial, so I only consider graphs without leaves.

The fact the graph should be planar isn't true. 5-dimensional binary cube (vertices are numbers from 0 to 31, edges between pair of integers if they differ in exactly one bit) isn't planar, but is easily colorable.

Yeah, my mistake. I just confused the rules of planarity a bit. Still, the planarity was just a peculiar note, not anything important :D, what I was proving back then was non-existence of

K_{3, 3}.Could you elaborate on the first problem. I don't see how your state in dynamic programming is sufficient. My understanding is that it's also important how the other gifts (those that were not added between the processed families) are distributed.

Yes, it is important. It's all hidden in the large constant.

Let's say that we're processing family

i, and there arejpeople so far that haven't given/received (those 2 numbers are equal) any gifts. Out ofn_{i}people of this family,xcan give gifts to processed people, andycan get gifts from the processed people, moving to a state (i,j+n_{i}-x-y).Now, combinatorics ensues. Let's assume that the conditions of at least 1 way existing (

x,y≤j,n_{i}etc.) are satisfied. There are ways to choose thexpeople, ways to chooseyand those 2 groups are independent. There arej(j- 1)..(j-x+ 1) ways to choose which people of thejwill get gifts from ourx, andj(j- 1)..(j-y+ 1) ways to choose the same for those giving gifts to they. Those are just small products and can be enumerated with modular arithmetic inO(n_{i}) =O(1) time.So even if there are many ways, those are compressed to the combination-variation product; in the dp state, they're viewed as equivalent and they're differentiated only when picking some few of them.

Funny that C appeared on team competition in Poland 2 weeks ago :P (problem M here http://www.mwpz.poznan.pl/zadania.php). In slightly different version, but main idea was exactly the same. Nobody solved it during the contest, but few guys successfully googled it :P.

Also, Wikipedia had the answer to the problem.

http://en.wikipedia.org/wiki/Partial_cube

Here's a solution to Pizza Baking (the second problem).

Let S_i be the total number of pizzas that need to be in an oven at time i. Then the key lemma to this problem is that the number of ovens needed to satisfy the requirements is always max(ceil(S_i / C_i)). While it's an obvious lower bound I still don't have a clean proof of its correctness.

Given this lemma, we first calculate the number of required ovens, call it M. Then we'll add a virtual pizza at every time so that S_i = C_i * M at all times. Therefore it will be necessary to fill every oven to maximum capacity at all times.

We can find such an assignment that fills the oven to capacity using max flow. To do so we will have K + 1 nodes for each time. Then for each pizza we'll connect its start time to its end time (where the times are in [s, e) form instead of the [s, e] form given in input). Now imagine that there are capacities from the source to the time nodes and from the time nodes to the sink node. Then we can compute the number of pizzas selected by the flow at time i as sum[j<=i] flow[source][j] — flow[j][sink]! Therefore we just need to setup the capacities from the source and sink nodes to time nodes so that in a maximal flow the oven is at capacity at all times.

Therefore we should set cap[source][i] = max(0, C[i] — C[i — 1]) and cap[i][sink] = max(0, C[i — 1] — C[i]).

Now we use this flow concept and try forcing pizzas to be used and verifying that a feasible solution still exists. If we reuse old flow networks this can lead to a rather efficient solution.

Code: https://gist.github.com/msg555/8078816

It was pointed out to me that the max flow construction itself is a proof. We can always saturate the network with fractional flows because S_i is a multiple of C_i and therefore there is an integer solution as well.

Is there any link to the problems too?

T-Shirts are coming! Got mine today.

Anybody knows, it is OK that i have not received my t-shirt yet?

Yeah, sending t-shirts always takes a lot of time for some reason.