Question discussion : Ansys hiring challenge (Contest already over)

help
1

31%20PM
Screenshot 2019-10-12 at 11.23.31 PM.png1044×812 89.3 KB

Can I ask for the approach for this, This was asked in hiring challenge but I couldn’t,t solve it.
Contest ended yesterday.

I’ll be highly obliged for the discussion.
@ssrivastava990 @vijju123 @aryanc403 @anon55659401

2

Am I missing anything? If A_0 is given then doesn’t the array become fixed?

What is the minimum sum stuff?

Regarding rest of the solution-

1 Like
3

For given link, “Sorry, you are not allowed to access this contest as it is restricted.” is popping up.

And yes, once A0 is provided odd element becomes A[I-1]*3+1. I am able to track the values in array but after that I tried subset sum and subset sum using bitset but nothing worked.

4

As per link, Archive of question can be retrieved from here but no question matches the requirement https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=738

5

Check updated link. I think the solution will help.

6

Can you mention the constraints?
I think it can be solved in O(Q*log(10^18) with base 3)
Since the size of the array will be log X with base 3 you can easily traverse each element of the array from right to left and keep subtracting the array element from X if a[i]<=X. If it perfectly subtracts X, it can be obtained. It is so because subset sum obtained from a set of consecutive numbers will anyway be less than the succeeding number.
One more thing, you can just skip the numbers greater than 10^18 as they won’t be of any use.

3 Likes
7

it was easy just some observations
this is what I do to get AC.

vector<int> solve (int A0, vector<long long> X, int N, int Q) {
   // Write your code here
   // Return a vector arr of size Q, such that arr[i]=1 if ith query evalutes to true otherwise 0.
   
   ll maxX = *max_element(X.begin(), X.end());
   
   vector<ll> a;
   a.push_back(A0);
   
   for(int i = 1; i < N; i++)
   {
       ll temp = 0;
       if(i&1)
       {
            temp = 3*a[i-1] + 1;
            if(temp > 1e18)
                break;
            a.push_back(temp);
       }
       else
       {
            temp = 2*a[i-1] + 3*a[i-2];
            if(temp > 1e18)
                break;
            a.push_back(temp);
       }
   }
   
    vector<int> ans;
    for(int i = 0; i < Q; i++)
    {
        ll x = X[i];
        for(int j = a.size()-1; j >= 0; j--)
        {
            if(a[j] <= x)
                x -= a[j];
        }
        if(x == 0)
            ans.push_back(1);
        else
            ans.push_back(0);
    }
    
    return ans;
}
3 Likes
8

I don’t have constraint but yes, It was similar to the ICPC mirror constraints.
Thanks for heads up for O(Q*log(10^18) with base 3)

1 Like
9

Nice observation.i was unable to solve it at that time.

1 Like
10

Exactly what I was saying

12

I missed this, which might have resulted in overflow.

13

I think this can be done using bitmasking and divide and conquer method as well.
If you observe then for any given A0, sequence exceeds 10^18 after 40 numbers only.
So, run bitmask on first 20 and map their sum. After that, again run bitmask on remaining 20 and check if X - sum is already mapped or not.
I haven’t tested it but I think it should work.

1 Like
15

I did almost same…but got segment error…why…

16

My this solution got passed for full marks but this is an overkill here. Instead we can sort the array (which is of 40 size) and traverse from back greedily picking largest number from our array which is smaller than required number and subtract this number from required number, then go to smaller numbers. If we come to any number which is greater than required number we ignore it. This can be easily proven that this will give correct result because in sorted array we can prove that sum of all previous numbers is lesser than current number.

3 Likes
17

Thanks for the post. I too couldn’t solve though I had ample of time left. :frowning:

18

This question can be solved using greedy approach…because any element a[i] will be greater than the sum of all the previous elements.

19

exactly what I did but I didn’t break the loop at the moment it exceeded the limit. I used assert() to realize that the array I was forming had elements <0.

1 Like
21

Can you explain the proof in detail? And regarding to above statement, will it hold for array A = [6,7,8], here sum of 6 + 7 = 13 > 8 which violates what you just said, sum of all previous numbers is lesser than current number(considering 8 as current number)

22

Yes…neeraj…and almost same type of question was asked in Infosys infytq round 2…I applied your method iteration from last and same in this q. But got segm . Error

23

[6,7,8] is not a valid array.Every A[i+1] is at least 3 times A[i](which makes it 3*A[i] +1) or (2 times A[i] and 3 times A[i-1] ) as given in the problem statement