Maximize it MXM

general
1

#include
#include 

typedef unsigned long ul;
typedef unsigned long long ull;

int main()
{
    int t, n;
    ull k, *a;
    std::cin >> t;
    while(t--)
    {
        std::cin >> n >> k;
        a = new ull[n];
        for(int i = 0; i < n; i++)
        {
            std::cin >> a[i];
        }
        int max_index = 1;
        ull n1, n2;
        n1 = pow(k, a[0]);
        n2 = pow(k, a[1]);
        for(int i = 2; i < n; i++)
        {
            n2 += pow(k, a[i]);
        }
        ull max_product = n1 * n2;
        for(int i = 1; i < n - 1; i++)
        {
            ull x = pow(k, a[i]);
            n1 += x;
            n2 -= x;
            ull product = n1 * n2;
            if(product > max_product)
            {
                max_product = product;
                max_index = i + 1;
            }
        }
        delete[] a;
        std::cout << max_index << "\n";
    }
    return 0;
}


It only passes one test case

I think its because even unsigned long long cannot store such huge values

Or is it the algorithm?

2

It’s due to unsigned long long int. It can store upto 1.8*(10^20) as far as I remember. But it any case, not 1000^1000 can be stored in ull.

In order to get an AC, totally a different algorithm needs to be implemented. I also know only about how to get 30pts.

3

And just an advice,

Try not to use pow() function. Rather define your own Power() Function.

It has double type, and for products of large order it gives wrong answer because of precision errors.

P.S. Not applicable for this problem, just talking in general.

4

Can someone help me by a hint?

5

Thanks @arjitkansal

6

For 30 pts

Only one observation required.

(k-1)(k^0 + k^1 + … + k^a) < k^(a+1)

Try to think in this direction :slight_smile: