Be F(N, K) = 1^k + 2^k + 3^k + ... + n^k.

Given N and K we need to calculate F(N, K) (mod 2^32)

INPUT:

1 <= N, K < 2^32

PS: I think about this question for a few days and didn't get success if you have any idea how to solve it, please share it :D

The problem can be found here to submit (statement in portuguese): http://olimpiada.ic.unicamp.br/pratique/programacao/nivels/2013f3p2_somapot

Hi everyone.

The problem is given 3 strings I, S, F How many moves (it should be minimum) are needed to transform String I to string S and transform string S to string F.

A move on a string S consists of choosing two integers i, j (0 <= i <= j <= | S |) and inverting this substring. For example: S = ABCDE . If i = 1 and j = 4, the string will be DCBAE

Input:

The input consist of 3 strings I, S, F

|I| <= 10 **** |I| = |S| = |F|

Example:

abc cba cab

The output should be 2

I was trying to solve it using a BFS but I think it will get TLE because the worst case will exist N! strings and for every string I need to choose two elements to invert

Anyone have any idea how to solve it ? :D

Hi everyone !

We have a static array of size N and Q queries. Each Query given us two integers i and j.

For each query we need to answer what is the maximum frequency of the values of this range.

For example:

A = {3, 4, 3, 4, 4, 1 }

Query(0, 2) = 2 (The value 3 repeat 2 times)

Query(0, 5) = 3 (The value 4 repeat 3 times)

The problem can be found here : http://www.spoj.com/problems/FREQ2/

1 <= N, Q <= 100000, 0 <= A[i] <= 100000

OBS: I would like to know if this problem is possible to solve "online" and the total complexity O(N*log(N)) __ If you have any idea comment bellow, please :D.

Solution using Mo's algorithm (Offline Queries and O(N*sqrt(N)) :

You need to save the value's frequency in a array.

Freq[i] will determine how many times the value "i" has been appears in our current array

Every times you will need to remove a element, decrease Freq[A[i]] by one and check if your answer should be changed

And for Add a element, increase Freq[A[i]] by one and do: answer = max(answer, freq[A[i]])

Code : http://codepad.org/0D7V5uha

Thank you :) and sorry for my bad english