damn_me's blog

By damn_me, 9 years ago, In English

Hello All,

I am very new to the concept of dp with bitmasking. So, was going through some basic problems like this. My code's link is this: http://ideone.com/kerT7s . I have precalculated the distance between every restaurant location and the solitairs location. Then because we have the constraint of limited number of restaurants (n), my lowest number with n bits set is (1<<n)-1 . The next number will be the one with same number of set bits. Then corresponding to every set bit (which denotes the location of the restaurant), I am checking the distances of each solitiare if it lies within the permissible radius range.

But the above gives TLE. I have no clue why, someone please give some hint or point out the flaw. Will be really helpful. Thanks :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By damn_me, 10 years ago, In English

I was trying solving the problem George and job of contest 467C. And my solution is : http://ideone.com/2cC2Fb I am using dp and finding out dp[k][i] i.e. the maximum sum of k subsets of the size m from 1 to i in the given array input. Thus, that sum is computed as :

dp[k][j]= max(dp[k-1][j-size]+sum[j],dp[k][j-1]);

I.e for a given K, i'll get the maximum of the addition of sum (k-1) subset which ends at j-size, size here is m +sum[j] which is basically the subset [j-size,j]. Either I am including this or I am not including thi, the deciding factor is the maximum sum. I am getting WA on 22nd test case. I thought it's exceeding the range, and so made it unsigned long long int also, but then it gives Memory limit exceeded. I went across one of the solution, I only saw the memory used by the arrays and it was the same as of my code. Then, why such error?

Full text and comments »

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

By damn_me, 10 years ago, In English

I was trying solving this problem http://codeforces.me/problemset/problem/489/C. Thinkinh in dp manner, I thought i'll need a table that can tell me the number of i digits that sum to particular j. Then if I want to calculate dp[i][j], then my subproblems will be dp[i-1][sum-j] and so on. However, I am unable to implement this idea.

Please help with this. Also, I coded the brute force way: http://ideone.com/83pdfJ but this gives TLE. Where to optimize in it?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By damn_me, 10 years ago, In English

I was trying out this problem: http://codeforces.me/contest/469/problem/D Although I thought this is a question of matching in graph. I tried doing it other way round. What I have done till now in this is: distribute elements in set A and check whether rest can be in set B or not. If not then change the above, i.e. distribute in B and then go for A. In each I will also check in the end if every element is now there in some set or not.

I know I am making mistake here and missing some test cases like the cases in which some elements can be there in either of the set and answer may be YES by distributing some elements in B which I initially kept in A. But I am unable to figure out how I should start thinking with the matching? What should be the approach for that? Not only for this question, for any other question if one could answer, that will be really helpful.

Full text and comments »

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

By damn_me, 10 years ago, In English

I know how qsort works using the function compare. But I am not getting how many times that compare is called. i.e. how is qsort functioning using compare. I read that it takes the elements pairwise. Does that mean if the array is int a[]={10,9,8,7,6,5};

then it will first take 10,9 and then 8,7 and so on. What exactly is happening. I did this to figure out but could not.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By damn_me, 10 years ago, In English

Why is the following code giving TLE for the PROBLEM

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By damn_me, 10 years ago, In English

Can someone provide me the code for solving this spoj problem spo.com/problems/FREQUENT . What I am basically trying to do is :

Using segment trees, declare the tree as such pair<int,int> tree[4*max][3] where tree[node][0] = (maximum occuring element, count of its occurence in the range's left part) tree[node][2] = (maximum occuring element, count of its occurence in the range's right part) tree[node][1] = (maximum occurencing element, count of its ocuurence in the whole range comparing it with left and right parts)

The leaf nodes will have [(0,0), (a[i],1), (0,0)] where i is the case where l==r in the construct function of the segment tree. For the rest, tree[node][1] can be easily found. For tree[node][1], we'll compare tree[2*node][1] and tree[2*node+1][0] and similarly for tree[node][2] we'll compare tree[2*node+1][1] and tree[2*node][2].

I have just started solving problems based on segment trees but unable to code this. However, i coded but that seems to be a bad one. Can someone please help!!!

Stuck on this!! Please..

Full text and comments »

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

By damn_me, 10 years ago, In English

Can someone please explain how to multiply two polynomials using fft using an example, I have read the theory of the same and possibly understood but lacking somewhere in its implementation. It'll become much clear if I get the working of its code using an example.

Full text and comments »

Tags fft
  • Vote: I like it
  • +3
  • Vote: I do not like it

By damn_me, 10 years ago, In English

Can someone provide some hint for solving this prbolem of spoj www.spoj.com/problems/LIS2/. The approach I am trying is very similar to the LIS dp solution(O(Nlogn)). But my solution doesnot give correct answer for all cases I am testing upon.

Here is the rough idea of what I am doing : http://ideone.com/kyIJMf

Full text and comments »

Tags spoj, dp
  • Vote: I like it
  • +3
  • Vote: I do not like it