i_love_emilia_clarke's blog

By i_love_emilia_clarke, history, 8 years ago, In English

Given an array A of N integers answer Q queries of type (L, R). Answer to a query (L, R) is the sum of distinct integers in the range A[L...R]

Constraints: N, Q <= 100000

0 <= L <= R < N

abs(A[i]) <= 1 000 000 000

I read somewhere that this can be done using persistence segment tree.

So, it would be helpful if one can explain that approach.

Other approach are welcome too.

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Hi, i was wondering how would we carry out these operation on an array using segment tree.

Formal statement of the problem.

Given an array if N positive integers, and Q queries perform these operations.

1 L R X. Decrease every element in the range [L...R] by by value X

2 L R. Return how many element in the range[L...R] are strictly greater than 0

N, Q <= 10^5

0 <= X <= 10000

Initial values of array can be as large as 1 000 000 000 What information would i have to store in each node ?

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Hi there, i was looking to get some insight on the following problem.

Question — What is the probability of n randomly drawn lines intersecting at a point in 2-D space. ? Stated in a different way, what is the probability that a randomly chosen system of n equation in 2 variables yields a result.

Follow up — does this probability equals the probability of n random planes intersecting at a point in 3-D space ? more generally, does this equal to the probability of n random N-dimension hyperplanes intersecting at a point in N-D space ?

I did googled things, but i found this question stacked with some constraint on space, for example, in THIS the space is constrained to a circle and in THIS the spaces is a 3-D grid. these made me thing whether there exist something for general case or not. Please Help. Feel free to ask for any further clarification about the setting of the problem ?

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Hi, i was trying to solve this PROBLEM, i am familiar with segment tree and lazy propagation stuff, what i could not see how to perform update operation.

I feel that we need to store the fibonacci sum of segment at each node, or do we need to store something else ? elaborative explanation will be highly appreciated. Thanks in advance.

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Hi there, i am stuck at the problem Codeforces Eductional Round 6 I read the tutorial and tried implementing the same, here is my Code. I think the problem is with the lazy propagation, please try to find the mistake.

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Problem statement is here and i am getting TLE for this solution. Looks O(31*N) to me, any idea(s) how to improve??

Full text and comments »

By i_love_emilia_clarke, history, 8 years ago, In English

Hi all, i am trying to implement FFT in Python(2.6) and i think i am facing precision issues. I checked the DFT of the coefficient vector at n complex nth roots of unity in a separate program and the values differ just only in precison, but still my FFT program is giving me wrong answer. Do anyone how to circumvent this issue ?. Here is my FFT Program, and here is the checker LINK

Full text and comments »

By i_love_emilia_clarke, history, 9 years ago, In English

Hi, Codeforces folks, i am stuck at this problem LINK, The problem seems to be quite simple, you just have to make a string palindrome adding minimum number of characters at the end, so basically we need to find the longest suffix palindrome and then add the remaining character at the end. My solution implements the same here is the [LINK]

Full text and comments »

By i_love_emilia_clarke, history, 9 years ago, In English

Here is the link to the problem LINK. This is a simple string matching problem. I got AC verdict even with the brute force solution but i am getting TLE when using Z-algorithms in Python. Can anyone figure out why i am getting TLE for THIS solution.Thanks in advance

Full text and comments »

By i_love_emilia_clarke, history, 9 years ago, In English

Hi Codeforces folks, i was wondering whether python has alternative for Bitset(in C++) to use it as flag in sieve, i thought of using a string but it is immutable, so do we have an alternative for bitset in python or are we compelled to make a list?

Full text and comments »

By i_love_emilia_clarke, history, 9 years ago, In English

Hi, I am trying to solve this www.spoj.com/problems/DIVSUM2 but getting TLE . I have pre-calculated primes up-to 10**7 and then for each test-cases i factorize it using O(sqrt(n)) method and then run GP formula for each of the prime factor of the given integer. Here is my solution... http://ideone.com/ZcDbYN... Please Help...

Full text and comments »