Snackdown PreElimination Round Problem Code: SNTEMPLE

What is the problem with this code ?
I implemented dp here.
Can anyone tell any testcase where it fails ?

    /*
Hey , this one is mine ..
make a new one for yourself
             ---->>AKASH KANDPAL
             */
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
using namespace std;
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
const ll INF = ll(1e18);
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

#define fi first
#define se second
#define pb push_back
#define po pop_back
#define mp make_pair
#define st string
#define vi vector<int>

int mod =1e6;
void add(int &x, int y) {

  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int power(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

const int MOD = (int)1e9 + 7;
const int N = 6066061 ;

/*vector<int> g[1000006];
bool vis[1000006],has[1000006];
stack<int> s;
void dfs(int z){
	vis[z]=1;
	s.push(z);
	while(!s.empty()){
		z=s.top();
		s.pop();
		for(int i=0;i<g[z].size();i++)
			if(!vis[g[z][i]]){
				vis[g[z][i]]=1;
				s.push(g[z][i]);
			}
	}
	return;
}
*/

int fa[1000005];
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}

int func()
{

}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    //cout << (fixed) << setprecision(10);
    //bitset<2001> dp[2];
ll t,r,mini=1e10,maxi=-1e9;
ll z=1,n1,mid=0,d=0,u,num=0,n,q,i=0,x,y,l,e,f=0,j=0,m,p,pa,ans=0,k,sum=0,c1=0,c2=0,a[201201],b[201210],c[201201],sn=1,a1,b1;
string s1,s2;
ll maxi1=-1e9,maxi2=-1e9;
//bool vis[N];
//st s1[2]={"Bob","Alice"};
//vi v;
//map<int, int> mp;
//getline(cin,s);
//memset(dp , -1 , sizeof(dp));
//sort(s.begin(),s.end(),f);
//fill(dp+1,dp+4005,-1e9);
cin>>t;
while(t--){
    cin>>n;
    for(i=0;i<n;i++){cin>>a[i];sum+=a[i];}
    z=0;
   maxi1=-1e9;
   if(n==2){
       cout<<a[0]+a[1]-1<<endl;
   }
   else
   {
    for(i=0;i<n;i++)
    {
        if(a[i]>z){
            z++;
           b[i]=z;
        }
        else
        {
            z=1;
            b[i]=z;
        }
//        cout<<b[i]<<" ";
    }
    z=0;maxi2=-1e9;
  //   cout<<endl;
    for(i=n-1;i>=0;i--)
    {
        if(a[i]>z){
            z++;
            c[i]=z;
        }
        else
        {
            z=1;
        c[i]=z;
        }
 //    cout<<c[i]<<" ";
    }
    maxi=-1e9;
 //    cout<<endl;
   for(i=0;i<n;i++){
    if(b[i]>c[i]){
    maxi=max(maxi,c[i]+1);//cout<<"hi"<<" ";
    }
    else{
    maxi=max(maxi,min(b[i],c[i]));
    }
    }
    if(maxi*2>n+1)maxi--;
  //  cout<<sum<<" "<<maxi<<" ";
    sum-=(maxi*maxi);
    cout<<sum<<endl;
sum=0;maxi=-1e9;z=0;
}}
return 0;

}

Please can anyone suggest some test cases where it fails ?
Thanks in advance .
Accepted Solution ::Code Link

This test case gives the wrong result:

1
6
1 2 2 3 2 1

Please clean up your code a little bit, before you post the next time.

6 Likes

See this
1
10
1 2 3 4 4 1 1 3 1 1
correct output : 12
ur output : 5.

2 Likes

What was the correct approach to solve this problem?

1
5
3 1 7 9 10

Your output:21
Answer:26

Answer is for this final configration: 0 1 2 1 0

2 Likes

this test case :
1
5
2 1 1 1 2
your answer- 3
correct answer - 6

1 Like

make the arrays so they can follow these constrain A[i] < A[i+1] then ( A[i] = A[i+1] + 1 ) and A[i] > A[i+1] then A[i] + 1 = A[i+1] so…after that by simply observation find the answer the maximum height of temple that can be formed after that compute answer in O(1)

2 Likes

A[i] + 1 = A[i+1] is it even a valid assignment?or did you mean
A[i+1]= A[i]+1 ?

This was probably the hardest problem for me, or maybe the second hardest, after consecutive snakes. I saw that many people have solved it but i just couldn’t figure it out. Then it clicked :).

The idea is this:

Go from left to right and try to ‘grow’ the longest possible temple side. For example if the array is [1,3,3,4,5,4…] you can build
[0,1,2,3,4,X…]. This new array tells you for each index, if you build a temple at that index what is the largest left side you can get. For example the 4 in the new array means that if i build an array at that index my temple might look like:

----*
---*
--*
-*
*

I say might, because i am still not sure for the right side.

As you can see i put an ‘X’ in one place in the array. This is because i cant keep increasing that side. This means that the value at that index in the original array is lower than the what it needs to be to grow the previous castle. The largest value for X is the value of the original array -1. So with X resolved, the new array would look like:

[0,1,2,3,4,3…].

Now we countinue counting from 3.

We do the same but going right to left this time to find out for each index, the largest right side of temple possible.

After that we iterate all possible positions for a temple and take the minimum of the left and right sides. That is the size of our temple.

3 Likes

I am getting a very basic idea of what you are trying to do but the terminology you have used is very confusing.I bet you are very active on Codeforces. Looks very similar to the editorials and comments i’ve seen there .All super human beings there who can understand anything and everything however complex either the answer or solution is :slight_smile:

1 Like

@aditya730: Create left and right arrays,

left[i] = min(left[i-1] +1, arr[i])
    
right[i] = min(right[i+1]+1, arr[i])

Then find maxtemp => maxtemp = max(maxtemp,min(left[i],right[i]) for all i from 1 to n. Answer is totalsum - (maxt^2)

2 Likes

How are you dealing with cases where two temples have same length? Meaning you find two spots where temple can be constructed, both with same maximum side?

easy to understand   : code link

1 Like

I am getting right answer for all testcases. Can anyone tell in my cod eany testcase where it fails ?

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define inf 1e18
#define PI 3.14159265
#define mset(A,num,n); memset(A,num,n);
#define nl cout << endl
const int MOD = 1e9+7;
const int N = 1e6+5;

typedef long long int ll;

ll POWER[65];
void precompute() {
POWER[0]=1;
for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;
}
int main()
{
ll T;
cin>>T;
//string str[4],str1[4];
ll cnt;
while(T–)
{
ll n;
cin>>n;
ll A[n];
for (int i=0;i<n;i++)
cin>>A[i];

    ll left,right,i,j;
    left =0;right =n-1;
    i=0;j=n-1;cnt=1;
    while(left<right)
    {

        if(A[i]>=cnt&&A[j]>=cnt)
        {
            cnt++;
            i++;
            j--;
            //continue;
            //cout<<334;

        }
        else if(A[i]<cnt&&A[j]<cnt)
        {
            if(A[i]>=A[j])
            {
                 right=j+A[j]-1;
                i=left;
                j=right;
                cnt=1;

            }
            else
            {
                 left=i-A[i]+1;
                i=left;
                j=right;
                cnt=1;


            }
        }

        else if(A[i]<cnt)
        {
            left=i-A[i]+1;
            i=left;
            j=right;
            cnt=1;

        }
        else if(A[j]<cnt)
        {
            right=j+A[j]-1;
            i=left;
            j=right;
            cnt=1;

        }
      //  cout<<343;
        if(i>j)
        {

            break;
        }
    }
    //cout<<cnt<<endl;
    ll sum1=0,sum=0;
    sum1=2*((cnt*(cnt-1))/2);
    //sum=sum+1;
    sum1=sum1-(cnt-1);
    for (ll i=0;i<n;i++)
        sum=sum+A[i];
    //cout<<cnt-1<<endl;//<<sum1<<endl<<sum-sum1<<endl;

    cout<<sum-sum1<<endl;


}

}

@adlitya730 :slight_smile: you made me laugh :). No i do not compete on codeforces and sorry for confusing you.

Have a look at my code, it is pretty clear: https://www.codechef.com/viewsolution/13835044

Draw the array on paper and try to simulate what i explained. You will see what i mean.

1 Like

@vijju123 You choose any of the maximal temples to build. The point is to use as many ‘land’ as you can which is the same as deleting the least ‘land’.

add some extra new lines, it might help :slight_smile:

i am taking about idea…yes I mean A[i+1] = A[i] + 1

Thanks got it . Marked as accepted :slight_smile:

Yeah fixed :slight_smile:
Ok will keep in mind .