ayush_awasthi's blog

Need Help in a problem on SPOJ.

By ayush_awasthi, history, 9 years ago, In English

I was trying to solve this problem on spoj http://www.spoj.com/problems/BOBERT/ can anybody please help me . Finding 20! arrangements and then a range minimum query would cause TLE so i dont know how to exactly approach the solution? I am looking for an initial approach and not the full solution.

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

»
9 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Edit: Sorry i didn't notice you didn't need full solution. You can use see 'rev' to find the full solution

I can think of a dp solution. Lets start with trivial dp[i][j] where i is position of array you are in and j is the bitmask of all those k sticks. (1 <= i <= n) (0 <= j < (1<<k)). Lets also define function f(x,low,high) which is l[x] * (max(i,j) — min(i,j).

Now some stick has to start from position 1..right? So lets say we try all sticks from pos 1. so recurrence from any position i and set of chosen sticks = mask would be 

for(int x = 0; x < k; x++)
     if((mask & (1<<x)) == 0)
         dp[i][mask] = max(dp[i][mask] , f(x,0,l[x]-1) + dp[i + l[x] - 1][mask | 1<<x])

But complexity would be O(n*2^k) which surely would give us tle. Hopefully we can do better. Try thinking of optimizing or you can use always use 'rev' to see my previous comment :)

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

    link to my solution http://ideone.com/n7PfoO.
    Initially it was giving Runtime Error( seg fault) , but now it is wrong answer , is my approach wrong ? I just increased the stack size using these functions to avoid stack overflow and the runtime error is now resolved.

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

      i don't use c++ much but i see you have used 'long int' everywhere.. can it store 64 bit? if not then you can change it to 'long long' and try again maybe. Also take care about overflow in some intermediate calculation coz that's the only reason i can think you program gives WA. Also you were getting runtime error probably because of assigning to much memory. if n<=1e5 dont assign 1e7 memory! 1e5 + some safe offset is almost always good enough for any good quality problem!

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

I'll give you some ideas for this problem.

  • Try precalculating lengths of all subsets of sticks using bitmasks, so that you don't need to do any extra operations then.
  • After that, do DP with bitmasks and you'll already know which segment you're covering next.
  • You can get the min/max of every segment with RMQ if you have a fast enough data structure, but I'd recommend you precalculate everything. Since there are only 20 possible lengths of segments, precalculate the min/max for every one of them before doing the DP. You can do that with sliding window min/max.

Note: If you want the full solution, check revision 3 of this post.

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

    Basically You are suggesting precomputation such that RMQ bcomes fast. That can be done with Sparse table making query O(1) but will make Computation O(NlogN). Here is the link of my sol : http://ideone.com/Lj6VXf

    Its still giving TLE. can u suggest some chnges.Can u links/ or code for sliding window min/max ?

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

      Precomputation for Sparse Table is O(NlogN), while precomputation for sliding window is O(N * K). Check here to learn about sliding window minimum/maximum: Sliding Window Maximum. That page uses built in deque data type, but I found it's faster if you use your own deque with a standard array and two variables.

      And about your code, why do you do 1 << (mask | (vv))] instead of just mask | vv or mask + vv ??? That will cause overflow, runtime error and all kinds of undefined behaviour.

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

    Thanks it actually worked! I like the approach you suggested

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

So, basically 20! is a very brute approach for this problem, which obviously wont work at all. Just try to think, how to approach the problem with the help of dynamic programming.

Lets say I have a state F(mask) meaning I have used all those sticks whose bits are set in mask. You also dont need to keep track of the length you have covered so far. Your set bits in mask will help you to calculate that. Now, you can try to set any unset bit in the current mask and see which of them fetches you with maximum answer.

if mask == (1<<k)-1
     F(mask) = 0
else
     F(mask) = max(F(mask), F(mask|(1<<i) + cal(len, len + stick_len[i]-1) * stick_len[i] for all in [0,k-1]

return F(mask)

Note: k is the number of sticks cal(a,b) is the difference between maximum and minimum element in the range[a,b] in the given array you wish to cover with given K sticks. Use RMQ to calculate that. Segment tree will time out probably. Atleast I got 1 TLE due to that.

Here is my code for detailed implementation: Link

→ Reply