### sanket407's blog

By sanket407, history, 16 months ago, ,

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

•
• +39
•

 » 16 months ago, # |   0 The solutions and some explanations will be updated here quickly after the test ends... https://github.com/ckcz123/codejamGood luck, everyone!
 » 16 months ago, # |   0 Auto comment: topic has been updated by sanket407 (previous revision, new revision, compare).
 » 16 months ago, # |   +43 This GCJ round is almost parallel with hockey. Not that I need to watch Slovakia vs Russia to know how it will end.
 » 16 months ago, # |   0 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 :( )
•  » » 16 months ago, # ^ |   +10 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.
•  » » 16 months ago, # ^ |   +5 yes , both subtasks are solvable by 2satI didn't pay attention to R <= 5 and I implemented a -fucking massive don't how it's correct code- .
 » 16 months ago, # |   +36 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?
•  » » 16 months ago, # ^ |   0 There's nothing messy in this approach. Did you know you can do reflections using ^= 1 and ^= 3 on the direction value?
•  » » » 16 months ago, # ^ |   +10 Yes, I know, but somehow my solution reached 200 lines: http://ideone.com/rqFefA
•  » » » » 16 months ago, # ^ | ← Rev. 4 →   +15 Atleast your code isn't buggy and 500 lines... :(Update: got AC in 581 lines :), Ugliest Code Possible
•  » » » » » 16 months ago, # ^ |   +5 bool rektttt reminds me of /wtf folders in some Linux source I was compiling.
•  » » » » » » 16 months ago, # ^ |   0 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
•  » » 16 months ago, # ^ |   0 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.
•  » » 16 months ago, # ^ |   +5 My solution was indeed an overkill. Let K be the number of beams. Instead of writing linear SCC, we can use O(K3) Floyd-Warshall to get POSSIBLE/IMPOSSIBLE. We can even repeat this O(K) times and determine the boolean values one by one (and avoid topological sort). Only Floyd-Warshall, extremely simple.
•  » » » 16 months ago, # ^ |   +10 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).
•  » » » » 16 months ago, # ^ |   +10 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.
•  » » » 16 months ago, # ^ |   0 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.
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Can’t K reach O(RC) = 2500 (e. g. if the grid is a chequerboard of walls and beam shooters), which should make O(K3), let alone O(K4), too slow?
•  » » » » 16 months ago, # ^ |   +10 No, read the constraints properly. K ≤ 100.
•  » » » » » 16 months ago, # ^ |   0 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.
•  » » » 16 months ago, # ^ | ← Rev. 3 →   0 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?
 » 16 months ago, # |   +41 How to solve B? :D
•  » » 16 months ago, # ^ | ← Rev. 4 →   +11 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.
•  » » » 16 months ago, # ^ |   0 Thank you :)
 » 16 months ago, # |   +18 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?
•  » » 16 months ago, # ^ |   +32 couldn't find a counter example for 30 minutes so just submitted it lol
•  » » 16 months ago, # ^ | ← Rev. 2 →   -18 ignore
•  » » » 16 months ago, # ^ |   0 How do you map this problem to a partially ordered set?
•  » » 16 months ago, # ^ |   +15 When there's a ticket with the i-th people and the j-th seat, connect the i-th left vertex and the j-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 most K, we can partition the edges into at most K matchings. To do this, repeat the following steps: at each step, find a matching that covers all vertices with maximum degree.
•  » » 16 months ago, # ^ | ← Rev. 5 →   0 You may add a fake tickets and now exactly Ans tickets will be sold for each place and nobody will have more than Ans tickets. Make a bipartite graph. Then you may use Hall's theorem and make a perfect (over places) matching starting from all persons with Ans tickets 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 Ans persons and then fake seats so every person will have Ans tickets. Now this is a well-known case for decomposition into Ans perfect matchings
 » 16 months ago, # |   0 How 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?
•  » » 16 months ago, # ^ |   +10 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).
•  » » 16 months ago, # ^ | ← Rev. 2 →   +8 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
 » 16 months ago, # | ← Rev. 2 →   +5 Weird 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 :DWas it just luck and were the testcases weak?
•  » » 16 months ago, # ^ |   0 Did you copy the wrong solution and resubmit it ?
•  » » » 16 months ago, # ^ |   0 I guess so!
•  » » » 16 months ago, # ^ |   0 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.
 » 16 months ago, # |   +8 BTW, when will the t-shirt be sent out? And how long will it take? I'm afraid I cannot get it timely...Thanks!
•  » » 16 months ago, # ^ |   +6 Last year I got mine in August.
•  » » » 16 months ago, # ^ |   0 Thank you!
 » 16 months ago, # |   0 Submitted output of Asmall to Alarge. It's sad that it's not checked in any way. Different number of tests would help
•  » » 16 months ago, # ^ |   0 This was discussed already.
 » 16 months ago, # |   +10 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.
•  » » 16 months ago, # ^ |   +2 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).
 » 16 months ago, # | ← Rev. 2 →   +8 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
•  » » 16 months ago, # ^ |   +5 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: 3 3 3 3 1 3 2 2 3 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.
 » 16 months ago, # |   +176 Would be nice if small datasets would actually be just smaller inputs, not some trivial special cases of the problem.
•  » » 16 months ago, # ^ |   +60 But solving only smalls was enough to advance :)
 » 12 months ago, # |   0 Did anyone in India receive their Tshirts?