### YouKn0wWho's blog

By YouKn0wWho, 4 months ago, ,

Well, one can count the number of primes less than or equal to n in (correct me if I am wrong) using Prime-counting function. You can solve this beautiful problem using the idea.

But recently I have come across following two (this and this) SPOJ problems with tag and have no idea how to solve them.

So If anyone can give me any idea about how to solve them, anyone will be appreciated respectfully. Thanks.

• +38

By YouKn0wWho, 7 months ago, ,

I am stuck on this following problem:

### Statement:

Given a string of size n, for each i from 1 to n you need to find if the string can be split into i non-empty non-intersecting palindromes. Output YES/NO.

1<=n<=100000

### Example:

aabaa

YES

NO

YES

YES

YES

#### Explanation

aabaa(1 palindrome), aa|b|aa(3 palindromes), a|b|a|aa(4 palindromes), a|b|a|a|a(5 palindromes)

Notice that you can not split the string into 2 palindromes.

### Trivia:

Thanks for reading the problem. It will be really helpful if you can provide me with a solution.

• +12

By YouKn0wWho, 7 months ago, ,

I am stuck on this following problem:

#### Statement:

Given an undirected connected simple graph of n nodes and m edges, for each node i from 1 to n you need to find if this node was not present in this graph how many connected components the graph would have.

1<=n,m<=100000

#### Example:

Input:

4 4 //4 nodes and 4 edges

1 2

2 3

2 4

3 4

Output:

1 2 1 1

#### Note:

A node is not present means erasing the node and its edges

#### Trivia:

Thanks for reading the problem. It will be really helpful if you can give me a solution.

• +15

By YouKn0wWho, history, 7 months ago, ,

I am stuck on this following problem:

#### Statement:

Given a string of size n and q queries of type (l,r) you need to find how many palindromes are there in the substring of range [l...r].

#### Constraints:

1<=n,q<=100000

1<=l<=r<=n

Thanks for reading the problem. It will be really helpful if you can give me a solution.

• +15

By YouKn0wWho, history, 7 months ago, ,

I need to solve this following problem as a subproblem of another problem:

Statement:

You are given n sets S[1], S[2], S[3], ..., S[n] each having some distinct elements (Note that 2 different sets have common elements but each set have distinct elements).

Given q queries of type (i,j) you need to find if there is any common element in set S[i] and S[j]. Output YES/NO.

Constraints:

1<= n,size of S[i],elements of S[i],q <=100000

1<= sum of sizes of all sets <=100000

Thanks for reading the problem. It will be great if you can give me a solution.

• +9

By YouKn0wWho, 8 months ago, ,

I need to solve the following task as a subtask of another problem. So I need your HELP.

I need a Data Structure that can do the following operations:

1. Add a pair of integers (x,y) in the Data Structure.

2. For a given pair (a,b) it will give me the count of the number of pairs (x,y) such that x<=a and y<=b.

Note: Maximum Time Complexity for both of the operations can be at most O(log n).

Trivia: (not for this problem) I am interested if there is a solution with erase operation.