Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

coding_is_fun's blog

How to add image in a blog or comment ?

By coding_is_fun, 7 years ago, In English

Apologize to everyone for off topic

Hello evryone i tried many times to add image in a blog post or comment . When i click ctrl+p codeforces want a url of the image which i want to upload , but how can i upload an image from my desktop folder ?

Full text and comments »

-2

coding_is_fun
7 years ago
18

Segment Game

By coding_is_fun, 7 years ago, In English

UPDATE : I got a Qlog2(N) solution

Given a number N . then N lines follows some segment L[i] R[i] , where L[i] = left side of segment , R[i]= right side of segment

L1 R1

L2 R2

. . . . . .

LN RN

Then Given Q queries . Then Q lines as follows .

X3 .

For each query you have to answer how many Segment are including the value Xi ( X >= L[i] && X <= R[i] )

Constraint :

1<=N<=10^5

0<=Li , Ri <= 10^9

1<=Q<=10^5

0<=Xi<=10^9

Sample input:

1 6

3 7

5 9

6 9

Sample output:

Explanation : 3rd segment 5-9 , 4th segment 6-9 both including 8 . Because : 8>=5 && 8<=9 , 8>=6 && 8<=9 . So ans is 2 .

How to solve it efficiently ?

My binary search solution

#include<bits/stdc++.h>

using namespace std;

int n,q,xi,ans;

pair<int,int> ar[200000];

int main() {

while(cin>>n)
{

      for(int i=1;i<=n;i++)
        scanf("%d %d",&ar[i].first,&ar[i].second);

    sort(ar+1,ar+n+1);

    cin>>q;

    unordered_map<int,int> val;

    while(q--)
    {
        scanf("%d",&xi);

        if(val.count(xi))
        {
            printf("%d\n",val[xi]);
            continue;
        }

        ans=0;
        int low=0,high=n+1;
        while(high-low>1)
        {
            int mid=(high+low)>>1;
            if(ar[mid].first>xi)
                high=mid;
            else
              low=mid;
        }

        for(int i=1;i<high;i++)
            if(ar[i].second >= xi)
             ans++;

        printf("%d\n",ans);
        val[xi]=ans;

    }

}


return 0;

}

My O( Qlog(N) ) solution

#include<bits/stdc++.h>

using namespace std;

#define debug(...) printf( VA_ARGS )

//#define debug(...) /****nothing****/

#define pb push_back

#define mp make_pair

#define LL long long

int n,q,xi,ans;

pair<int,int> ar[200000];

int main()

{

while(cin>>n)
{

    vector<pair<int,int> > vct;

    for(int i=1;i<=n;i++)
      {
        scanf("%d %d",&ar[i].first,&ar[i].second) ;
       vct.push_back(make_pair(ar[i].first,1)) ;
       vct.push_back(make_pair(ar[i].second+1,-1)) ;
      }

    sort(vct.begin(),vct.end());
    int cnt=0;

    map<int,int> val;

    for(int i=0;i<vct.size();i++)
    {
        cnt+=vct[i].second;
        val[vct[i].first]=cnt;
    }

    cin>>q;

    while(q--)
    {
        scanf("%d",&xi);

        map<int,int>::iterator it=val.upper_bound(xi);
        it--;

        printf("%d\n",it->second);
    }
}


return 0;

}

I used the technique which has been used in this problem ( Two Tv's http://mirror.codeforces.com/problemset/problem/845/C )

Full text and comments »

-8

coding_is_fun
7 years ago
11

Counting Triplets

By coding_is_fun, 7 years ago, In English

I found a similar type of problem as last csacademy problem Sum of Triplets but slightly different :

Here they said find triplets such as A[i] + A[j] = A[k] where i<j<k . 1 <= Array size is <= 10^5 . 1 <= Array values < 2^16 .

Time limit : 12 second .

problem link : https://toph.co/p/counting-triplets

How to solve this problem without n^2 loop ? I am getting TLE .

My solution :

here

#include<bits/stdc++.h>

using namespace std;

int tc,n,ar[123456],i,j,k,cas;

int main()

{

cin>>tc;

 for(cas=1; cas<=tc; cas++)
 {

    unordered_map<int,int> mxindex;

    scanf("%d",&n);

    for(i=1; i<=n; i++)
        scanf("%d",&ar[i]);

    for(j=n; j>=1; j--)
        if(mxindex.count(ar[j])==0)
            mxindex[ar[j]]=j;

    long long ans=0;

    for(i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(mxindex.count(ar[i]+ar[j]))
            {
                if(j+1<=mxindex[ar[i]+ar[j]])
                    ans++;
            }

    cout<<ans<<'\n';

 }


return 0;

}

Since they said "A[i] + A[j] = A[k] where i<j<k " so i can not sort the data . I have to work as the given input .

At first I declare a map<int,int> mxIndex ; Then i store the maximum index of each data in this map .

Then I run a n^2 loop for every A[i] + A[j] , i search this sum in map . If found then i check the maximum index of A[i] + A[j] . If that index >= j+1 . That means found a triplet i < j < k so , ans++ . I know i will get WA . But i am getting TLE for n^2 loop . How can i do it efficiently ?

Full text and comments »

time limit exceeded, help

coding_is_fun
7 years ago
4

CSACADEMY : Sum of triplets

By coding_is_fun, 7 years ago, In English

I am getting Wrong answer . Please help .

code

#include<bits/stdc++.h>

using namespace std;

//#define debug(...) printf( VA_ARGS )

#define debug(...) /****nothing****/

#define pb push_back

#define mp make_pair

#define mem(ar,val) memset(ar,val,sizeof(ar))

int ar[5007],frq[10007][5007],n;

int main() {

while(cin>>n)
{

    mem(frq,0);

   for(int i=1; i<=n; i++)
   {

   scanf("%d",&ar[i]);

   frq[ar[i]][i]=1;

   }

    for(int i=0; i<=10000; i++)
        for(int j=1; j<=n; j++)
            frq[i][j]+=frq[i][j-1];

    sort(ar+1,ar+n+1);

    long long ans=0;

    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            int sum=ar[i]+ar[j];
            ans+=frq[sum][n]-frq[sum][j];
        }

    cout<<ans<<endl;
}

return 0;

}

My logic is :

first sort the array , then run a n^2 for loop . For every ar[i]+ar[j] , i find out the frequency of ar[i]+ar[j] from index j+1 to n in array ar[] . Then i add this frequency to the answer .

To evaluate "frequency of ar[i]+ar[j] from index j+1 to n in array ar[] " i precalculated frq[X][Y] = "frequency of value X , from index 1 to Y " . For instance frq[5][2] means frequency of 5 from index 1 to 2 in arayy ar[] . I did it as like as partial sum technique .

So for every ar[i] + ar[j] I add this => sum=ar[i]+ar[j] ; ans += frq[sum][n] — frq[sum][j] ;

frq[sum][n] — frq[sum][j] means frequency from (j+1) to n = frequency(from 1 to n ) — frequency(from 1 to j ) ;

whats wrong in my logic or code ?

Problem link : https://csacademy.com/contest/archive/task/sum-triplets/

Full text and comments »

coding_is_fun
7 years ago
4