likecs's blog

Some Doubts
By likecs, history, 8 years ago, In English

Hello All,

I have some questions as doubts:

1) How can we solve problem E (The secret code) in http://codeforces.com/gym/100371 Any hints?

2) I am given an sorted array of 1000 elements, where each element can be in the range [0, 20000]. We need to consider all subsequences on the array. For every subsequence, it's power is defined as the sum of all the elements in it. We are given 1000 queries of the form "x" where i need to print the xth smallest value of the power of any subsequence of the array. Here "x" is in the range of [1, min(2^n, 10000)].

For example: Let the array be [1, 2, 100]. Then the power of subsequences sorted order are [0, 1, 2, 3, 100, 101, 102, 103]. If the query is x = 3, I need to print 2.

3) How can we solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2334

My approach to this problem- First of all if the graph contains a directed cycle, then the answer is 0, as a trivial case. Otherwise, consider all the cases where we can partition the groups into 2 equal halves. For this I use of mask (till 2^(2m)) and if it contains number of set bits as "m" I continue the loop. Then I consider the partition if it is valid or not i.e. if in partition 1 or 2, whether there exits a person "i" who has a dependency on person "j" but is not present in the same set. In such a case, I just add nothing. In rest of the cases, I try to find the number of topological sorts on graph in set 1 and 2 and multiply their results and finally add it to the final result. (For number of topological sorts, I used this method http://cs.stackexchange.com/questions/12713/find-the-number-of-topological-sorts-in-a-tree )

Here is a link to my code according to the above implementation https://textb.org/r/doubt-likecs/

4) How can we efficiently find the points of intersection of a line and polygon, where the polygon is not necessarily convex polygon (but the polygon is simple)?

Please help in the above problems. If possible please post the code as well.

Thanks in advance.

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

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

2) There's a good D&C solution for finding the smallest K sums: solve it for two halves of the array and you just need to find the K smallest sums of pairs. Then, you can binsearch the largest sum or use a priority queue to find them in ; that makes the total complexity . (I'm assuming different subsequences with equal powers aren't counted as one value, since there can be less than 2^n possible values otherwise and it would take .)

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it 
// Dynamic Programming based solution for Problem 2.
#include<bits/stdc++.h> 
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false)
#define MAX 400000
using namespace std;
int ar[1009];
int dpl[1000000]; // for dp[i-1][]
int dph[1000000]; // for dp[i][]
int h[1000000];
int main()
{
	//ios;
	// dp[i][sum] denotes the number of subsequences ending at index i and having sum = sum.
	// recurrence relation for dp:  dp[i][sum]=dp[i-1][sum-ar[i]]+dp[i-1][sum+ar[i-1]-ar[i]]
	// Space optimization: clearly, dp[i][] depends only on dp[i-1][], and hence, we don't need to make entire 2D dp[i][sum], just 2 dp arrays: dpl[] and dph[]
	// Note that always, sum<MAX. The proof is simple. Sum is maximum when n=log2(10000) (got by solving for n: 2^n=10000). Thus, for n==log2(10000), if all ar[i]==20000, then sum<= n*20000, taking n=20 (> log2(10000)), sum<400000. If n==1000, then sum<= 2*max(ar),
	// because nC2>10000.
	// h[j] stores min(number of subsequences having sum=j,10000).
	int n,q;
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++) scanf("%d",&ar[i]);
	dpl[ar[0]]=1; // base case
	h[ar[0]]++;
	for(i=1;i<n;i++)
	{
		for(j=0;j<=MAX;j++)
		{
			if(j-ar[i]>=0)dph[j]=min(10001,dpl[j-ar[i]]+dpl[j+ar[i-1]-ar[i]]);
			else dph[j]=0;
		}
		for(j=0;j<=MAX;j++) 
		{
			dpl[j]=dph[j];
			h[j]=min(10001,h[j]+dph[j]);
		}
	}
	vector<int> v; // stores the smallest min(2^n,10000) subsequence sums.
	v.pb(0); // for null subsequence
	int idx=0;
	while(v.size()<10009&&idx<=MAX)
	{
		for(i=0;i<h[idx]&&v.size()<10009;i++) v.pb(idx);
		idx++;
	}
	//for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
	// Answer Queries.
	scanf("%d",&q);
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",v[x-1]);
	}
	return 0;
}
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In above solution, I have assumed that 2 or more subsequences having the same sum are counted more than once.

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

      Your solution is OK but it is a bit slow. For computing the DP, complexity is Max_n * Max_sum = 1000 * 400000 = 4 * 10^8, which is around 4 seconds. I thinks the solution proposed by Xellos is quite good for practical purposes as it doesn't impose any limits on value of A[i] as well.

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

        I know. Just wanted to give an alternative approach. :P

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

A faster solution for (2).

Let K be the maximum value of the queries (in this case K ≤ 10000). Consider a DAG. For each 0 ≤ i < N, we have two multi-edges i -> i+1 of costs 0 and (i+1)^th element of the array. The paths from 0 to N correspond to subsequences and vice versa. Now, we need to calculate all K-best shortest paths of this graph.

This problem can be solved by Eppstein's algorithm (paper). Because the graph is DAG, Eppstein's algorithm can run in O(N + K) time. For practical purpose, we can omit Frederickson's algorithm and get simpler algorithm.

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

    Does a similar solution exists for the problem "1" where i want the k largest products but each number is selected from different array?

    BTW, thanks for the links.

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

      Yes. We can solve the problem in a similar fashion.

      The DAG now have M multi-edges for each 0 ≤ i < N. It corresponds to the M ways of selecting positions.

      Products can be converted to sums by taking logarithm. I think Eppstein's algorithm can be implemented robustly in a sense that floating-point number will work well. Total runtime is O(NM + K) (theoretically).

      → Reply