cauchyk's blog

Facebook Hacker Cup 1A
By cauchyk, 14 years ago, In English
Can anyone explain how to solve the second question i.e, diversity numbers??
and, can the last question i.e, turn on the lights be solved in any better way than O((2^c)*r*c)  where c=no.of columns, r=no.of rows??


thanks in advance. 
  • Vote: I like it
  • +2
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Turn on the Lights
It can be solved in O(R3C3) by solving a system of linear equations with Gauss method.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even though it did appear to me that gauss works, I've chosen to do 2^n*n*m anyway. Since it seems to be much easier..

    Also interedted in how to solve problem B.

     

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      B problem. I have only the basic idea and can't understand some points in it.
      First, if we understand, what the answer is, we can see, that there is some sub - sequence a1, a2, ... an  and in sorted way this array looks like a1, an, a2, ... Then the answer is a1 * ( a2 - 1 ) * ( a3 - 2 ) * ... Also we can see that this subsequence can be separate to 2: a1 <= a2 <= a3 ... and an <= an-1 <= ...
      Let's construct such dpi,j,k which means - i-th number is the index in A such that number is the last number of the first part of subseq, j-th number is the same but for the second part ( we construct the subsequence from its ends ), k - is the length of each part. To calculate the transition in linear time we can add the 4th parametr l - what part we are adding (0 - left part, 1 - right part).
      Also in transition we should be careful with the equal numbers (I used set).
      This is my idea. Maybe it's wrong but I hope there are some right points
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        > k - is the length of each part
        But the parts may have different lengths.

        >         Also in transition we should be careful with the equal numbers (I used set).
        Can you explain the details? For example, how do you make sure that in the sequence (1,3,2,1,3,2) the subsequence (1,3,2) is counted only once?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          we have 2 variants of K in dp - both parts are equal ( L = 0 ) and left part is K+1 and right part is K ( L = 1 ). We can assume in dp that in second case both part are K (it's no matter, because we are looking for the addind of the right part by 1 ).

          In (1,3,2,1,3,2) at first we are look for the left part - at first we take 1, then 3, then 2 and after that we won't take anything. Then we look for the adding for the right part - it's 2, 3, 1, and again - nothing after these. We don't need to take the number, because we took it before) Smth like that.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            How does it handle case when left part is much longer than the right part?

            1 2 3 4 5 6 7 8 9 10 3 for instance?

            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Maybe I didn't understand the statements but " if first K elements are non-decreasing sequence and last N-K+1 elements are non-increasing sequence" - I think that first K elements ans second K elements
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Marked it as bold for you :o)

                 

                if first K elements are non-decreasing sequence and last N-K+1 elements are non-increasing sequence

                → Reply
      • 14 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        First of all,

        a1 * ( a2 - 1 ) * ( a3 - 2 )

        During the contest, believing that two sequences which elements are the same, but indices are different, are different (which is wrong) I coded the following solution:

        Meaning of i and j is the same as yours,

        k is sum of lengths of left and right parts

        z (z is from 0 to 1) is whether we ever moved right pointer or not. Since when left and right pointer meet, I cound solution if and only if either left pointer points to number strictly greater than the one right pointer points to, or if right pointer was never moved.

        It gives answer=19 instead of 17 on the fourth sample, since it counts some 1 2 and 1 twice.

        Have no idea how to handle equal sequences yet.

        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I had the same line of reasoning. Would love to know the solution…
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          We can handle this trouble like that: let's just take the first element a[l] that was not before (after i) in current segment i .. j. For right side we can do the same. 
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    can you please explain the procedure in a bit more in detailed manner. 
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Make n*m equations. Each equation consist of 5 or few variables: x(i)(j) + x(i-1)(j)+x(i+1)(j)+x(i)(j-1)+x(i)(j+1) = y. y = 0, if lamp is lighting and 1 otherwise. Solve these equations and sum all numbers from solution. Sum is the answer.
      → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it
    Why is it correct?

    Gauss method may be used, if there are unique solution (determinant != 0). In another case, there are multiple solution (maybe, no solution). How are you choose the minimal answer?

    In my opinion, you're wrong.

    So, I think bruteforce is correct way to solve.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have compared my answer to the answer of the person who used gauss, and it was the same.

      I used 2^n*n*m solution.

      May be it can be proven that answer is alweys unique. Or facebook is lame enough to prepare only tests which have unique solution.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Can you explain your solution?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Fix what lamps are switched in the first row (2^m), iterate over all the rows starting from second (n), for each row for each lamp (m) switch it if and only if lamp above is off.

          Complexity is 2^m*m*n.

          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Nice =)
            → Reply
          • 14 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it
            I used the same approach :) it took around 1 min to answer the input file... i thought for a second that it would time out :P... but is brute force the only way??
            → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It is not: for "1 2 XX" there are 2 solutions.
        → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      I can't be confident in my solution before official results
      But, here in my input: http://pastebin.com/cxrkze5X
      And output: http://pastebin.com/smP02J0Q

      Upd.
      Because of Facebook is not very fast to publish results, here my answers for problem A
      It's interesting to compare them
      Input:
      20
      30 7
      14 1
      97 86
      83 4
      34 27
      23 11
      51 43
      32 7
      4 2
      86 2
      24 3
      62 39
      15 8
      82 59
      75 1
      1 1
      73 9
      66 46
      19 4
      66 19

      Output:
      948425733
      405146859
      229148997
      552088028
      875219463
      268080562
      253211239
      402231981
      7
      299325777
      654845005
      80187174
      13402248
      390562784
      862630060
      1
      141282623
      596669446
      380563847
      488623143

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        yes i think your answer is right for the above input (it matched with mine) :)
        → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
1) It is clear thar order of switching lights doen't matter
2) You can switch 0 or 1times, because if you switch 3 times for example it will be equal to switch once

Now xi, j  = {0, 1} - "switcher state" - variables of the system of equations

Every point on the grid can also be in state {0, 1}, so
yi, j = {0, 1} - right column of the system of equations

Now consider point on the grid with neiborhoods
xi, j + xi - 1, j + xi + 1, j + xi, j - 1 + xi, j + 1 = 1 - yi, j, where '+' is taken by modulo 2

^This is the system to solve
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

(wrong place)

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Facebook published results of Round 1A.
"Facebook Hacker Cup
Hey everyone, the final results for round 1A are up on the scoreboard. Since we had fewer than 1000 competitors, everyone who successfully solved at least one problem advances to round 2 and can no longer participate in round 1 subrounds. Everyone else still has two more shots at advancing round 2.
Email notifications will go out shortly."

There are only 646 hackers advanced to Round 2 =) I think what to win Facebook T-shirt will be easier than GCJ T-shirt.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    It appears that jury solution for 3rd problem is incorrect (or they have some mistakes in judging). So let's wait for rejudge.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi,

Can someone please tell me what the problems are? I clicked on the links provided but it seems that the problem statements cannot be found :(
→ Reply