coding_is_fun's blog

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 »

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

N

L1 R1

L2 R2

. . . . . .

LN RN

Then Given Q queries . Then Q lines as follows .

Q

X1

X2

X3 .

.

XQ

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:

4

1 6

3 7

5 9

6 9

1

8

Sample output:

2

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
My O( Qlog(N) ) solution

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

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

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 »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By coding_is_fun, 7 years ago, In English

I am getting Wrong answer . Please help .

code

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 »

  • Vote: I like it
  • +9
  • Vote: I do not like it