Soluciones de Regionales

Alguien sabe si hay alguna pagina que tenga hints, o soluciones de regionales: europeos. de estados unidos o de cualquier lugar???

Entrenamientos de este semestre

Este lunes nos reunimos para acordar el horario de trabajo, el cual sera:
Lunes de 5-7 salon 203 Yelizcalli y sabados de 11-3 en el primer piso del P, tentativamente el P106, no parece haber clase en el los sabados.

Non-negative Partial Sums: Regional 2011 soutwestern Europa

You are given a sequence of n numbers a₀,..., a_n-1. A cyclic shift by k positions ( 0kn - 1) results in the following sequence: a_k, a_k+1,..., a_n-1, a₀, a₁,..., a_k-1. How many of the n cyclic shifts satisfy the condition that the sum of the first i numbers is greater than or equal to zero for all i with 1in?

Input 

Each test case consists of two lines. The first contains the number n ( 1n10⁶), the number of integers in the sequence. The second contains n integers a₀,..., a_n-1 ( -1000a_i1000) representing the sequence of numbers. The input will finish with a line containing 0.

Output 

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.

Sample Input 

3
2 2 1
3
-1 1 1
1
-1
0

Sample Output 

3
2
0

Andrew and Strings-Codechef

http://www.codechef.com/problems/AMSTRING

Andrew likes strings very much.
He has two strings A and B of N lower alphabet letters. We denote S[i, j] as the substring from i^th to j^th characters of string S.
Andrew is interested in the number of such fours of integers (L_A, R_A, L_B, R_B), where 1 ≤ L_A ≤ R_A ≤ N, 1 ≤ L_B ≤ R_B ≤ N, and R_A − L_A = R_B − L_B, such that the Hamming distance between substrings A[L_A, R_A] and B[L_B, R_B] is not greater than K. Here the Hamming distance between two strings of the same length is the number of unequal characters on the same positions of strings.
Help him and find this number.

Input

The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and K. The second line contains string A, and the third line contains string B.

Output

For each test case, output an integer, denoting the number of fours (L_A, R_A, L_B, R_B) satisfying the conditions described in the problem statements.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ N
• Both A and B are contain only N lower alphabet letters

Example

Input:
3
3 2
aba
abb
3 2
abc
def
1 1
a
a

Output:
14
13
1

Explanation

Example case 1: There are 14 fours as following:
(1, 1, 1, 1) : dist(A[1, 1], B[1, 1]) = dist(a, a) = 0 ≤ 2
(1, 1, 2, 2) : dist(A[1, 1], B[2, 2]) = dist(a, b) = 1 ≤ 2
(1, 1, 3, 3) : dist(A[1, 1], B[3, 3]) = dist(a, b) = 1 ≤ 2
(2, 2, 1, 1) : dist(A[2, 2], B[1, 1]) = dist(b, a) = 1 ≤ 2
(2, 2, 2, 2) : dist(A[2, 2], B[2, 2]) = dist(b, b) = 0 ≤ 2
(2, 2, 3, 3) : dist(A[2, 2], B[3, 3]) = dist(b, b) = 0 ≤ 2
(3, 3, 1, 1) : dist(A[3, 3], B[1, 1]) = dist(a, a) = 0 ≤ 2
(3, 3, 2, 2) : dist(A[3, 3], B[2, 2]) = dist(a, b) = 1 ≤ 2
(3, 3, 3, 3) : dist(A[3, 3], B[3, 3]) = dist(a, b) = 1 ≤ 2
(1, 2, 1, 2) : dist(A[1, 2], B[1, 2]) = dist(ab, ab) = 0 ≤ 2
(1, 2, 2, 3) : dist(A[1, 2], B[2, 3]) = dist(ab, bb) = 1 ≤ 2
(2, 3, 1, 2) : dist(A[2, 3], B[1, 2]) = dist(ba, ab) = 2 ≤ 2
(2, 3, 2, 3) : dist(A[2, 3], B[2, 3]) = dist(ba, bb) = 1 ≤ 2
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(aba, abb) = 1 ≤ 2
Example case 2: The four (1, 3, 1, 3) no longer satisfies the conditions, because
(1, 3, 1, 3) : dist(A[1, 3], B[1, 3]) = dist(abc, def) = 3 > 2

V concurso anual de programacion (ESCOM)

Al parecer sera el 24 de mayo con un costo de $350 por equipo

http://juniocarl.com.mx/wordpress/?p=181#more-181

La Escuela Superior de Cómputo del Instituto Politécnico Nacional convoca a estudiantes de nivel medio-superior y superior a participar en el V Concurso Anual de Programación en el marco de la XVIII ExpoESCOM y el XX Aniversario de esta Unidad Académica.
Este concurso estará basado en las competencias de programación del ACM ICPC. Los estudiantes pondrán a prueba sus habilidades para resolver problemas a través de programas C, C++ o Java, donde requerirán habilidades de programación, matemáticas, trabajo en equipo y de lógica.