Hey all, Google Code Jam Round 2017 Round 2 will start at MAY 13 14:00 UTC

Just a reminder !!

Top 500 will advance to round 3 !!

Top 1000 will get a T shirt !!

Good luck to all !!

Don't forget to discuss the problems here after the contest !!

GL ! HF !!

**UPDATE** :: 30 mins to goo !!

The solutions and some explanations will be updated here quickly after the test ends... https://github.com/ckcz123/codejam

Good luck, everyone!

Auto comment: topic has been updated by sanket407 (previous revision, new revision, compare).This GCJ round is almost parallel with hockey. Not that I need to watch Slovakia vs Russia to know how it will end.

Was C Subtask solvable with 2-CNF? I almost derived it to this (+ few other checks), but failed to implement in time (and hence lost top 1000 :( )

I don't know about 2-CNF. I solved the subtask by this:

For any two shooters in a row that do not have a wall between them, fix their position as VERTICAL. For any two shooters in a column that do not have a wall between them, fix their position as HORIZONTAL. If their is a conflict, answer is not possible. Now their might be some shooters whose position hasn't been fixed till now. We fix them by simply checking if their is any unmarked cell in that row that doesn't have a beam crossing it from any of the fixed shooters. If there is, then we fix the position as HORIZONTAL, else VERTICAL.

At last, we just need to check if all '.' are covered or not.

yes , both subtasks are solvable by 2sat

I didn't pay attention to R <= 5 and I implemented a -fucking massive don't how it's correct code- .

I managed to solve C with 2 SAT + the simulation of the beams, but it became quite messy and I feel I did an overkill. Is there anything simpler?

There's nothing messy in this approach. Did you know you can do reflections using

`^= 1`

and`^= 3`

on the direction value?Yes, I know, but somehow my solution reached 200 lines: http://ideone.com/rqFefA

Atleast your code isn't buggy and 500 lines... :(

Update: got AC in 581 lines :), Ugliest Code Possible

`bool rektttt`

reminds me of`/wtf`

folders in some Linux source I was compiling.I used rekt first and realized it had been taken so added three extra t's cause adrenaline. Glad I at least got the small dataset accepted before time elapsed XD

I wrote the 2-SAT part, but only without mirrors; too bad I didn't have the ~10 minutes necessary to write the mirror part. I agree with Al.Cash, it's simple already.

My solution was indeed an overkill. Let

Kbe the number of beams. Instead of writing linear SCC, we can useO(K^{3}) Floyd-Warshall to get POSSIBLE/IMPOSSIBLE. We can even repeat thisO(K) times and determine the boolean values one by one (and avoid topological sort). Only Floyd-Warshall, extremely simple.Don't you have prewritten 2sat? Copying is even easier than some Floyd-Warshalls. On contrary I had impression that this was easy to code, made no bugs. Btw we have 2sat in our library that doesn't divide graph into SCC, so there wouldn't have been need for that even if constraints had been larger :D (don't ask me about it).

I have a very poorly written SCC (it's difficult to use, the graph must be named exactly "graph", the number of vertices must be named "N", each time when I use it I have to initialize all related variables, etc). Yes, I know I must improve it.

By the way I think this is the first time I needed pre-written codes in GCJ, except for flows.

One nice thing about SCC algorithms is they find the SCC's in the topological order of the meta graph. It makes pulling out 2SAT answers or running DP on the meta-graph a bit less code.

Can’t

KreachO(RC) = 2500 (e. g. if the grid is a chequerboard of walls and beam shooters), which should makeO(K^{3}), let aloneO(K^{4}), too slow?No, read the constraints properly.

K≤ 100.Oh, right! I did notice that during the contest, but must have forgotten later. And when I went back to check before asking here, I looked at a different problem’s statement… how embarrassing.

I understand how to get POSSIBLE/IMPOSSIBLE with Floyd–Warshall (just check whether any X and ¬X are reachable from each other simultaneously), but how do you determine the Boolean values?

How to solve B? :D

Let's iterate over all prefixes of the seats. The number of rides is sufficient iff

`i * rides >= pref_sum[i]`

for all`i`

, so we can easily find it. We also need to take into account that the number of rides is not less than the maximum number of tickets per customer. After that, we just need to find the sum of`max(seats_count[i] - rides, 0)`

for all`i`

(we greedily keep all the customers we can and move the rest).Note: the

`pref_sum`

is the prefix sums of`seats_count`

, which is the number of tickets for the`i`

-the seat.Thank you :)

How to prove that in B we can forget about the requirement not to put the same person on one ride twice, as long the number of rides is not smaller than the maximum number of tickets a single person have?

couldn't find a counter example for 30 minutes so just submitted it lol

ignore

How do you map this problem to a partially ordered set?

When there's a ticket with the

i-th people and thej-th seat, connect thei-th left vertex and thej-th right vertex, and construct a bipartite graph. We need to prove the following: when the degree of each (both left and right) vertex is at mostK, we can partition the edges into at mostKmatchings. To do this, repeat the following steps: at each step, find a matching that covers all vertices with maximum degree.Such matchings always exist: https://math.stackexchange.com/questions/638598/any-bipartite-graph-has-a-matching-that-covers-each-vertex-of-maximum-degree

You may add a fake tickets and now exactly

Anstickets will be sold for each place and nobody will have more thanAnstickets. Make a bipartite graph. Then you may use Hall's theorem and make a perfect (over places) matching starting from all persons withAnstickets being matched (actually Hall's conditions are enough for default matching algo to never fail a DFS).Upd. Even simpler you can add fake persons for tickets so every ticket will match

Anspersons and then fake seats so every person will haveAnstickets. Now this is a well-known case for decomposition intoAnsperfect matchingsHow to solve D? I guess the max number is the same as in the max matching but we have to cleverly modify and order the matching to satisfy the constraints?

I think you can use min cost matching to help. Ordering the matching can be done with bfs (i.e. find any soldier that can reach their turret safely, and repeat).

Wish I had thought of this during contest :(. Probably slightly different from the editorial solution:

Firstly, let us get an upper bound on how many turrets we can shoot. Suppose all turrets do not fire. Then finding how many turrets can be shot is just a matching problem. It turns out that this number is also correct for the original question. We will proceed to construct it.

From the maximum matching, (wlog every soldier is used) we can match each soldier to a turret. For each soldier, fix a path to the intended turret. Along the way, the soldier also enters the line of sight of other turrets, in some order. If a soldier sees 2 turrets simultaneously, break ties arbitrarily. In other words, each soldier has a sequence of turrets T1, T2, ..., Tn such that he may shoot at turret Ti if everything before has been dealt with.

Now, we let all soldiers fire at their respective T1s. This will cause some turrets to be fired at twice. While this is the case, choose a soldier for whom this turret is not the last turret, and assign him his next turret in the sequence instead.

This procedure has to terminate because there are at most 100 turrets per soldier and at most 100 soldiers. It is correct because whenever two soldiers fire at the same turret, one of them has a next turret to fire at.

Implementation wise, since the important thing about the sequence of turrets T1, ... is that you may fire at Ti if everything before has been cleared, we can actually do a BFS from each soldier and add the turrets in order they are seen. Lastly, to ensure the final order of destroying turrets is correct, simply make sure that for each soldier firing at Tk, all turrets Ti for i<k have been destroyed prior. This is --EDIT: not-- doable using toposort (although there are probably faster methods the bounds are small enough for this to not matter).

Edit: Panic! Solution was 'wrong' -- You can't toposort a cycle. For more security, go read the official solution. I'm sorry and will go hide in a cave for now. =(

More detailed explanation + attempted fix (possibly with more sinister logic bugs): Basically, after constructing the sequences of turrets for each soldier, it reduces to the following problem:

Given some sequences of numbers, such that each sequence ends with a different number, rearrange the sequences such that if, from the first sequence onwards, we pick the first number we have yet to pick, we are able to pick 1 number from each sequence (before the sequence ends).

Example: 1, 2, 3 2, 1 1, 2

If we use this order, then we pick 1 from the first sequence, and 2 from the second sequence. We can't pick anything from the third sequence, so this fails. However, if we rearrange the sequences by placing the first sequence at the back, we get 2, 1, 3, and this works.

In a more useful line of thought, we can think of the question as follows: after rearranging the sequences, pick a prefix for each sequence such that the last elements are unique and every non-last term in each sequence is contained in an earlier sequence. This formulation suggests that in a sense, shorter sequences are easier to work with. So we try to reduce the length of sequences while maintaining the property that all sequences end with unique numbers.

Firstly, wlog, let the sequences end with 1 to n. Then if a number greater than n appears in some sequence, then we can truncate the sequence to end with it, while preserving uniqueness of last numbers in the sequences. Thus we may assume that only numbers 1 to n exist.

Since we are working by the hypothesis that a solution exists as long as every sequence ends in a different number, if some sequences are like as follows:

1, 2 2, 3 3, 1

We can truncate the sequences to form {1}, {2} and {3} respectively, retaining the uniqueness of the last numbers in the sequences. More specifically, we imagine a directed graph, where each number from 1 to n is a node. Then we draw an edge from x to y if the sequence ending with x contains y. If there is a cycle, then we can truncate the sequences as described above. If there is no cycle, then we can now do the toposort to retrieve the solution.

I will try my bestest to actually code it out tomorrow, and once again, I'm sorry to anyone who was led astray by my logic.

finds a cave to hide inWeird thing happened! I solved C at around 5 minutes to end and had 2 Wrong Answers on B previously. I just copied my previous code of B, downloaded the input file and submitted hopelessly. Miraculously it passed, and I'm getting a T-Shirt now :D

Was it just luck and were the testcases weak?

Did you copy the wrong solution and resubmit it ?

I guess so!

From the description it sounds like he did that. Not a surprise though. I discovered that my incorrect submission had in one test case +1 in promotions. Perhaps downloading input few more times will do the job too.

BTW, when will the t-shirt be sent out? And how long will it take? I'm afraid I cannot get it timely...

Thanks!

Last year I got mine in August.

Thank you!

Submitted output of Asmall to Alarge. It's sad that it's not checked in any way. Different number of tests would help

This was discussed already.

Problem B: Suppose we fix the sheet number for each ticket. Then we have edge coloring of a bipartite graph. Then, the minimum number of rides equals to the maximum degree of the bipartite graph due to the fact that the line graph of a bipartite graph is perfect. Then rest is straight-forward.

Thanks for this! A really nice proof for this problem.

For the reference, the graph anta is talking about is the bipartite graph where customer vertices on the left and seat numbers on the right. We can see that colours can represent rides, since one customer can't have two colours (that would mean one person on the same ride) and one seat can't have two colours (that would mean two of the same seat number on the same ride).

My idea for B was to binary search for the answer. Then I iterated through each person, and for each ticket of that person, assign the ticket to the biggest number position possible. I see that this gives the correct minimum days, but fails to optimize the minimum number of promotions. Could anyone explain why this greedy is not correct? My Code-Code

I'm not sure I understood your approach. But if I did, it fails because you assign a ticket to a seat when you promote it. This is wrong. When you promote a ticket, it becomes a flexible ticket, therefore it can't be fixed as you do with not promoted ones. The testcases your code gives incorrect outputs are something like this:

You force customer 1 to seat 3, customer 2 to seat 2, promoting its ticket and customer 3 to seat 1, promoting its ticket aswell. The correct answer would be to let customer 1 and 3 seat in their tickets and promote customer 2 to seat on 1.

Would be nice if small datasets would actually be just smaller inputs, not some trivial special cases of the problem.

But solving only smalls was enough to advance :)

Did anyone in India receive their Tshirts?