Sunday, February 26, 2012

knocked down qudrant query and changing bits

Made several stupid mistakes in changing bits but got it eventually. O(sqrt(N)) per query is fast enough. Now I got 24/29 solved.

Solved Problems

String Reduction: greedy with reducing max cnt char

Permutation game: easy bit

Task Scheduling: segment tree

Circle Summation: matrix mult

Quadrant Queries: segment tree

K Difference: easy

String Transmission

EQUATIONS: factor

Lego Blocks: dp with a wall to cut

Grid Walking: dp with precalculation

String Similarity

Substring Diff

Vertical Sticks: indepdently calculate each stick

FIND STRINGS

ARITHMETIC PROGRESSIONS: ans is q!*d^q1*d^q2..., when q is more than MOD, then ans is 0

Meeting Point: axis transformation to get L1 norm

Changing Bits: blocks of sqrt(N)

Save Humanity: overlap two prefix match (forward and reverse) to obtain a match with 1 error

Stone Piles: Grundy number and sum of games, very tricky

Billboards: minimize throw away, sliding window

Kingdom Connectivity: topological sort with cycle detection

Square Subsequences: try all split and find common substr

Fairy Chess: moving diamond and edges

Connect the country: simulation
Posted by at

23 comments:

  1. siva krishnaFebruary 27, 2012 at 6:57 AM

    hi..please see my comment on your posts.

    ReplyDelete
  2. techie.rsMarch 29, 2012 at 4:48 AM

    Hi...m looking into the problem permutation game....but get stuck....looking for some hint that how to proceed

    ReplyDelete
    Replies
    1. Li YanMarch 30, 2012 at 4:37 PM

      this is a standard combinatorial game problem. Just use DP with memorization to check each state being win or lose,

      a state is win if it can reach a lose state
      a state is lose if all its next state is win

      Delete
  3. ananthaApril 5, 2012 at 11:23 PM

    Hello,

    Can you give me clue for Vertical Sticks problem.

    ReplyDelete
  4. Li YanApril 6, 2012 at 10:49 PM

    calculate each stick individually

    ReplyDelete
  5. Piyush KapoorApril 9, 2012 at 11:09 AM

    Hi,Can you explain a bit more on using a sliding window for BillBoards,i am stuck with DP of complexity O(nk)...

    ReplyDelete
    Replies
    1. RedApril 21, 2012 at 4:08 AM

      Use a MaxHeap to deal with the K elements you need to deal with in the n loop

      Delete
  6. UnknownApril 18, 2012 at 10:57 AM

    how can segment tree apply to task scheduling problem?

    ReplyDelete
    Replies
    1. Li YanApril 23, 2012 at 10:41 AM

      basically it is shortest job first but you need to do a lot of updates, use lazy updates to be within time limit. The use of segment tree is a bit hard to explain, I need to look at my code since it has been a while

      Delete
    2. darklingDecember 5, 2012 at 9:20 PM

      can you tell what the segments represent, i mean is it the Task numbers, Deadlines, Time Remaining, Overshoot ?

      Like the segment [3-4] represents what?

      Thanx

      Delete
  7. RedApril 18, 2012 at 10:08 PM

    You are so smart....

    ReplyDelete
  8. MswoApril 27, 2012 at 3:13 PM

    Hello,

    Can you help me with quadrant queries?
    I have tried with segment tree storing the number of X-queries and Y-queries, but when i try to compute C-queries it's still linear because I have to consider all points.

    I don't see how to use the in a different way.
    Thanks for your help

    ReplyDelete
  9. Li YanMay 2, 2012 at 8:38 PM

    You only need the number of points in each quadrant, not the actual points. And you need the idea of lazy propagation, e.g. if you apply X query on range [i,j], the children under [i,j] are not updated until you have to split into the children range.

    ReplyDelete
  10. vrath87May 14, 2012 at 8:34 AM

    hey Li Yan,
    for the GRID WALKING problem in interviewstreet, could you paste you output for this input...
    1
    4 4
    5 5 5 5
    9 9 9 9

    ReplyDelete
  11. AnubhavMay 19, 2012 at 4:00 AM

    This comment has been removed by the author.

    ReplyDelete
  12. AnubhavMay 19, 2012 at 4:02 AM

    PROBLEM PLEASE HELP...
    i was able to solve this problem by two ways..
    i am facing problem when the input is like...

    1
    10 300
    2 2 2 2 2 2 2 2 2 2
    10 10 10 10 10 10 10 10 10 10

    what should i do please help.....

    ReplyDelete
    Replies
    1. vrath87May 19, 2012 at 12:04 PM

      Hello Anubhav,

      Thanks for your reply. I solved it.
      And for the testcase you asked, the answer is

      292695773

      Thanks again
      Cheers,

      Delete
    2. AnubhavJune 10, 2012 at 1:06 AM

      hi

      could you please help me with the memory issue...(OUTOFMEMORY)
      my code goes out of memory when solving such a large problem in java.(see problem above)

      Delete
  13. AnubhavguptaJune 19, 2012 at 7:36 AM

    hi Li Yan,

    I am facing the same problem in Quadrant Queries like you before, I am able to solve it till 10/11 test case,but in 11th test case it's crossing time limit.
    Please give a clue what should i do.

    Thank you,
    Anubhav

    ReplyDelete
    Replies
    1. AnubhavguptaJuly 3, 2012 at 9:57 PM

      finally able to solve that problem by myself

      now i am getting 11/11 test cases passed.

      i was doing a silly mistake in query part....

      Anubhav

      Delete
  14. AnandJuly 23, 2012 at 7:46 PM

    Hi Li Yan,

    I tried solving Kingdom connectivity using DFS which also detects the loop in graph but only able to get through 2 test cases. Can you please guide.

    ReplyDelete
  15. UnknownAugust 24, 2012 at 4:41 AM

    Some help on Changing Bits, Except the fact that we need to compute only the bit which is being referred in the get_c command

    ReplyDelete

Subscribe to: Post Comments (Atom)