Let's say we have a polynomial $$$P(x)$$$ in the field modulo $$$(10^9+7)$$$

For $$$n=10^5$$$ obviously we can't generate the whole polynomial explicitly. But I think maybe we can solve the following problems

• Find the coefficient of $$$x^k$$$ in $$$P(x)$$$
• Find the polynomial $$$P(x)\%x^k$$$

I don't how to solve them efficiently. That's why I am asking you guys. How efficiently can you solve the problems for some $$$k$$$?

There's a string $$$S$$$ of length $$$N$$$ containing $$$1s$$$ and $$$0s$$$ only, you don't know the string but you know $$$N (N \lt =1000)$$$. You can ask at most $$$1024$$$ questions: is $$$P$$$ a substring of $$$S$$$? $$$P$$$ can be of any length. Then you have to know the string $$$S$$$.

This comment claims that this problem has a deterministic solution as well as a nice randomization solution. But I am thinking of the solution for a pretty long time and nothing popped out of my tiny brain. Can you help me?

Note: I am interested in the randomized solution more. But any solution will quench my thirst!

I am stuck on this following problem for a pretty long time.

It will be really helpful if you can provide me with a solution.

I am stuck on this following problem for a pretty long time.

Given a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges and the capacity of each edge is $$$1$$$. $$$maxFlow(u, v)$$$ defines the maximum flow from node $$$u$$$ to node $$$v$$$. You have to find out how many pair of nodes $$$(u, v)$$$ are there where $$$u \lt v$$$ and $$$maxFlow(u, v) = 2$$$ .You can assume that the graph won’t have any self loop.

$$$Constraints: 1 \lt =n \lt =10^5, n-1 \lt =m \lt =7*10^5$$$

You can find the problem here. It will be really helpful if you can provide me with a solution.

The following problem popped into my mind all of a sudden and I have no idea how to solve it.

You are given a weighted rooted tree with $$$n$$$ nodes. You need to find the number of unordered pairs of nodes $$$(u,v)$$$ such that

$$$Constraints: 1 \lt =n \lt = 10^5, -10^6 \lt =edge\,weights \lt =10^6$$$

It will be really helpful if you can provide me with a solution.

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.

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.

Constraints:

1<=n<=100000

Example:

Input:

aabaa

Output:

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.

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.

Constraints:

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.

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.

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.

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.