ADDSQURE - Editorial

editorial
, , ,
103

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

104

Thanks! I’ll try using BigInteger.

1 Like
105

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

106

Its not about TLE.I am getting wrong answer.

107

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
108

@spaanse thanks a lot dude.

109

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

*/
110

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

1 Like
111

Basically revHorizontal gives distance between vertices less than y.

112

After shifting, yes

115

Hey can anyone code this in Python3 please?

116

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

1 Like
117

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;

}

118

@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

119

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.

120

Testcases are weak!
See this solution : Solution: 48845901 | CodeChef
This should fail for this testcase :
7 12 2 4
0 4
4 11 10 12
Correct answer should be 1 not 2
Also, see this solution : Solution: 51720646 | CodeChef
This sol should fail for this testcase :
1 12 2 1
0 1
6
Correct answer should be 1 not 0.