ADDSQURE - Editorial

Nice problem. Great explanation, got to learn about bitset, thanks!

Thanks! I’ll try using BigInteger.

1 Like

Every insertion and find operation in set is causing you O(log n) time. Use unordered_set instead and it should pass for the first subtask

Its not about TLE.I am getting wrong answer.

You don’t remove the newly added lines again when you start to consider the next line, so the differences from the new line y=5 are still in set2 when you start to consider y=6

1 Like

@spaanse thanks a lot dude.

My code is giving WA for the last testcase of partial marks. Can anyone tell me what is wrong with the code ? I used the same approach as in the editorial for partial marks.
code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl "\n"
#define INT_MAX 2147483647
#define M 1000000

bool HorDiff[100001];
bool VerDiff[100001];


void solve(){ // testcases
    int w,h,n,m;
    scanf("%d%d%d%d",&w,&h,&n,&m);
    int vertical[n],horizontal[m];
    // scanf("%d%d%d%d",&w,&h,&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&vertical[i]);
    for(int i=0;i<m;i++) scanf("%d",&horizontal[i]);

    int maxVerdiffvalue=0;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            VerDiff[abs(vertical[i]- vertical[j])]= true;
            maxVerdiffvalue=max(maxVerdiffvalue,abs(vertical[i]-vertical[j]));
        }
    }
    maxVerdiffvalue++;
    int maxHordiffvalue=0;

    for(int i=0;i<m;i++){
        for(int j=i;j<m;j++){
            HorDiff[abs(horizontal[i]-horizontal[j])]= true;
            maxHordiffvalue=max(maxHordiffvalue,abs(horizontal[i]-horizontal[j]));
        }
    }
    maxHordiffvalue++;

    int cnt,maxi=0;
    for(int k=0;k<100001;k++){
        bool NewHorDiff[100001]={false};
        for(int i=0;i<m;i++) NewHorDiff[abs(k-horizontal[i])]=true ;
        cnt=0;
        bool mp[100001]={false};
        for(int i=1;i<max(maxHordiffvalue,maxVerdiffvalue);i++){
            if((NewHorDiff[i] or HorDiff[i]) and VerDiff[i]){
                if(mp[i]==false){
                    mp[i]=true;
                    cnt++;
                }
            }
        }

        maxi=max(cnt,maxi);
    }

    printf("%d\n",maxi);
    return;
}
int main(){
    int testcase=1,z=1;
    while(z<=testcase){
        solve(); z++;
    }
    return 0;
}
/*

10 10 3 3
3 6 8
1 6 10

*/

k<100001 should become k\leq h in the for loop

1 Like

Basically revHorizontal gives distance between vertices less than y.

After shifting, yes

Hey can anyone code this in Python3 please?

Nice Problem. Taught me the concept of bitset.
Still wondering, how come i have not learnt bitset earlier. :slight_smile:

1 Like

i am writing the code in brute force first but it is giving wrong answer .can anyone point out the mistake ?thanks. i tried too many times :cold_sweat:

#include<bits/stdc++.h>
using namespace std;
using lli=long long int;
#define maxn 1E5+42

int main()
{
lli t,w,h,n,m,ans,input;
// cout<<“t:\n”;
cin>>t;
while(t–)
{
ans=0;
// cout<<“w,h,n,m:\n”;
cin>>w>>h>>n>>m;
vector horizontal(maxn) ;vector vertical(maxn);

   // cout<<"vertical:\n";

    for(int i=0;i<n;i++)
    {
        cin>>input;
        vertical[input]=true;
    }

 //   cout<<"horizontal:\n";
    for(int i=0;i<m;i++)
    {
        cin>>input;
        horizontal[input]=true;
    }

    vector<bool> verdiff(maxn);
    for(int i=0;i<=w;i++)
    {
        if(vertical[i])
        {
            for(int j=i+1;j<=w;j++)
            {
                if(vertical[j])
                    verdiff[abs(i-j)]=true;
            }
        }
    }

    vector<bool> hordiff(maxn);

    for(int i=0;i<=h;i++)
    {
        if(horizontal[i])
        {
            for(int j=i+1;j<=h;j++)
            {
                if(horizontal[j])
                    hordiff[abs(i-j)]=true;
            }
        }
    }

    for(int k=0;k<=h;k++)
    {
        vector<bool> newhordiff(maxn);
        for(int i=0;i<=h;i++)
        {
            if(horizontal[i])
                newhordiff[abs(i-k)]=true;
        }
        lli nsq=0;

        for(int i=0;i<=h;i++)
        {
            if(verdiff[i]&&(hordiff[i]||newhordiff[i]))
            {
                nsq++;
            }
        }
        ans=max(ans,nsq);
    }
    cout<<ans<<endl;
}
return 0;

}

@spaanse can you please check this code and tell what am i doing wrong ,i m stuck on this for almost 2 days,i m first trying to do the brute force approach but it is showing wrong ans and tle even for sub-task.
following is the link to the problem.

https://www.codechef.com/viewsolution/39082927

https://www.codechef.com/viewsolution/39082927

There is only one testcase, so you shouldn’t read in t. This means that your program keeps waiting for input when all input was already given, leading to TLE.