sanket407's blog

By sanket407, history, 5 months ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +39
  • Vote: I do not like it  

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Good luck, everyone!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sanket407 (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +43 Vote: I do not like it

This GCJ round is almost parallel with hockey. Not that I need to watch Slovakia vs Russia to know how it will end.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +36 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's nothing messy in this approach. Did you know you can do reflections using ^= 1 and ^= 3 on the direction value?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Yes, I know, but somehow my solution reached 200 lines: http://ideone.com/rqFefA

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 4   Vote: I like it +15 Vote: I do not like it

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

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

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          bool rektttt reminds me of /wtf folders in some Linux source I was compiling.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        No, read the constraints properly. K ≤ 100.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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?

»
5 months ago, # |
  Vote: I like it +41 Vote: I do not like it

How to solve B? :D

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -18 Vote: I do not like it

    ignore

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    Such matchings always exist: https://math.stackexchange.com/questions/638598/any-bipartite-graph-has-a-matching-that-covers-each-vertex-of-maximum-degree

  • »
    »
    5 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 in

»
5 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

Was it just luck and were the testcases weak?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you copy the wrong solution and resubmit it ?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess so!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

Thanks!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it +176 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    But solving only smalls was enough to advance :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone in India receive their Tshirts?