anuraganand's blog

Invitation for Bitwise 2016
By anuraganand, history, 9 years ago, In English

The much awaited Bitwise is finally here. Prizes worth 1000 USD are up for grabs.
To register follow the following:

  1. This is a team contest with each team having a maximum of two members.
  2. This is a 5 hour long contest and will start at this time.
  3. Teams will be ranked as per the number of problems solved. Ties will be broken by the total time for each team in ascending order of time.
  4. All the team members should register themselves on HackerEarth. The link to register is: https://goo.gl/wbaPvW .
  5. The contest link is: https://www.hackerearth.com/bitwise-2016/
  6. All teams should register themselves for the prizes by filling up this google form: https://goo.gl/GpzbeK

For more information please check the Bitwise website: http://www.codeclub-iitkgp.in/

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1) What should I do if I don't have an account on hackerearth (using Facebook/Google to login)?

2) How you will count time? You say that you will count time separately for each participant. It is strange.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Are you not able to submit ?
    2. The post has been updated. Time will be counted for a team.
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I was curious what should I write in the field 'Hackerearth username' in the google form.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why are the submissions not made public after contest ? will there be any editorials?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No t-shirts? :(

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve this problem : https://www.hackerearth.com/bitwise-2016/algorithm/fibonacci-coffecients/

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    Recall that for M = [[1, 1], [1, 0]], MN is [[FN + 1, FN], [FN, FN - 1]].

    Then we make an array of A[i] * Mi and build a segment tree on top of that. Also we precompute powers of the inverse of M (the inverse is M - 1 = [[0, 1], [1,  - 1]]).

    In the segment tree for combining two intervals we just sum the respective matrices.

    Modifying a single element is straightforward.

    If we are queried fibsum(l, r), then we query the tree on this interval and get res = A[l] * Ml + A[l + 1] * Ml + 1 + .... We then multiply by M - l + 1. Because of linearity, we will get res * M - l + 1 = A[l] * M + A[l + 1] * M2 + .... The answer is in res[0][1].

    In short, instead of working with Fibonacci numbers, we work with the matrices. This allows us to easily shift the Fibonacci sequences in any direction.

    PS: Fenwick Tree would also work.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve https://www.hackerearth.com/bitwise-2016/algorithm/lcs-1/

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

    Let S1, S2, ..., Sn be the set S. Define P = S1#S2#S3#...#Sn. Now we want to check if string T is a substring of P. We can build suffix automaton for string P and then proccess query in O(|T|) time.

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

      Thnks .Also could you give an idea how to solve RELATIVES.

      https://www.hackerearth.com/bitwise-2016/algorithm/relatives/

      Thnks in advance.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        We can solve it using dynamic programming. For each state (i, j, k), we maintain (minimum number of boxes required, weight of active box) for all A's packages having index  ≤ i, B's packages having index  ≤ j and C's packages having index  ≤ k. From this state, we can move to states (i + 1, j, k), (i, j + 1, k) or (i, j, k + 1) and try to fit corresponding box. If it does not fit, we need to start a new box. We update the weight of active box accordingly. Our aim is to minimize the number of boxes required, and in case of tie, minimize the weight of active box.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      can we solve it using suffix array or rabin karp (i donot know suffix automation)

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve this https://www.hackerearth.com/bitwise-2016/algorithm/othello/ ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +63 Vote: I do not like it

    If you choose row i and col j and flip a "cross of tiles" with a center (x,y) for every pair (x,y) such that x=i or y=j, every tile except (i,j) will be flipped an even amount of times, while the tile (i,j) will be flipped n+m-1 times which is odd. So doing this will flip only one tile (i,j). This means that any state of tiles could be reached from any other.

    Now let's point out the order of flips doesn't matter and there is no point of flipping the same cross more than once, so there are at most 2mn different positions (mn is the number of different crosses) which can be obtained from the starting one. Also there are exactly 2mn positions total. That means that for every position there is exactly one way of getting to it (not counting the order) without flipping the same cross twice.

    Now we only have to find it. So we will get to all white tiles and then remove all pairs of repeating flips of the same crosses. This can easily be done in O(mn) doing the combo-flip from the first paragraph and storing for each row and col the number of times each cross from it have to be flipped.

    Final algorithm: 

    for each black tile (i,j)
    rowFlipCount[i]++
    colFlipCount[j]++
    tileFlipCount[i][j]++

ans = 0
for each tile (x,y)
    if (rowFlipCount[x] + colFlipCount[y] + tileFlipCount[x][y]) is odd
        ans++
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Nice solution! Here's an alternate proof for this being the minimum number of flips.

      Let H(i, j) denote the number of black tiles in the row i and column j. If H(i, j) is odd, we plan to flip the tile (i, j) as described in the algorithm above. Now, note that the parity of H(i, j) can only be changed by flipping (i, j). Flipping any other tile on the board maintains the same parity of H(i, j). We know that in the final configuration (all tiles white), H(i, j) = 0 (an even number) for all (i, j). Thus, in order to reach the final configuration, we must flip at least all the tiles for whom H(i, j) is odd. Thus, no set of flipped tiles can be smaller than the set generated by the algorithm described above by Vercingetorix.

      → Reply