12836 - Gain Battle Power

[@li_kuet]

I used LIS and LDS for calculating the power of a Death Eater.
Then i used a greedy technique to split the sequence.

getting WA

Is my method wrong ?

Give me some hint please ...

Code: Select all

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
const double pi=acos(-1.0);
int inf=1000000007;
#define ri(N) scanf("%d",&N)
#define rll(N) cin>>N
#define Reverse(x) reverse(x.begin(),x.end())
#define all(X)  X.begin(),X.end()
#define UNIQUE(X)  X.resize(unique(all(X))-X.begin())
#define tr(container,it)  for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
//////////////////////////////////////////////////////////////////////
vector<int>v;
vector<int>comul;
int findInd(int left,int right)
{
    int sum=comul[right]-comul[left-1];
    int mid=sum/2;
    int val=comul[left-1]+mid;
    int ind=upper_bound(all(comul),val)-comul.begin();
    if(ind==left)
      ind++;
    else
    {
        int sub1=abs((comul[ind-1]-comul[left-1])-(comul[right]-comul[ind-1]));
        int sub2=abs((comul[ind]-comul[left-1])-(comul[right]-comul[ind]));
        if(sub1>sub2)
          ind++;
    }
    return ind;
}
ll solve(int left,int right)
{
    if(left>=right)
      return 0;
    int ind=findInd(left,right);
    ll total=comul[right]-comul[left-1];
    total+=solve(left,ind-1)+solve(ind,right);
    return total;
}
int main()
{
    //freopen("E:/in.txt","r",stdin);
    //freopen("E:/out.txt","w",stdout);
    int i,j,k,l,m,n,t,kase=1;
    ri(t);
    while(t--)
    {
        ri(n);
        v.clear();
        for(i=0;i<n;i++)
        {
            ri(k);
            v.push_back(k);
        }
        vector<int>len1,len2;
        vector<int>M(n+1,inf);
        M[0]=-inf;
        for(i=0;i<n;i++)
        {
            int ind=lower_bound(all(M),v[i])-M.begin();
            M[ind]=v[i];
            len1.push_back(ind);
        }
        Reverse(v);
        vector<int>M1(n+1,inf);
        M1[0]=-inf;
        for(i=0;i<n;i++)
        {
            int ind=lower_bound(all(M1),v[i])-M1.begin();
            M1[ind]=v[i];
            len2.push_back(ind);
        }
        Reverse(len2);
        vector<int>power;
        for(i=0;i<n;i++)
          power.push_back(len1[i]+len2[i]-1);
        comul.clear();
        comul.push_back(0);
        for(i=0;i<n;i++)
          comul.push_back(power[i]+comul[i]);
        printf("Case %d: %lld\n",kase++,solve(1,n));
    }
return 0;
}

[Masum]

I think this is a dp problem. Though the straight-forward dp is n^3, it requires a n^2 version to get accepted. I haven't got accepted yet, though. But greedy should be incorrect. I don't have any cases right now, may be someone else will post some.

[@li_kuet]

May be you are right Masum
Let me know if you find any way (y)

[Masum]

Yes, now I know for sure, this is not greedy. And to optimize the dp complexity, you need Knuth optimization(may be quadrangle inequality)