Primera subtarea: Primero veamos como resolver el problema para un k fijo: Podemos tomar los unos como su posicion y meterlos para un vector, por ejemplo el caso 1 0 0 1 1 0 1 se convierte en { 1 , 4 , 5 , 7 }, llamemos m al tamagno de este vector. Entonces tenemos que partir este vector en pedazos de k, y para cada uno de los m / k pedazos, hacer que todos los elementos sean iguales, la operacion permitida es equivalente a sumar 1 o restar uno a un elemento. Esto es un problema clasico que aqui se conoce como el greedy de la mediana(lo cual spoilea la solucion). Imaginemos que queremos llevar al arreglo { 1 , 4 , 5 , 7 } a que todos sean iguales, si queremos llevarlo a un numero x, la solucion es la suma para cada i de abs( a[i] - x ), esta solucion es como multiplicar la diferencia por la cantidad de elementos que pasan por ahi, por ejemplo si lo llevamos a 4, por el tramo de 1 a 4 pasa el 1, por el de 4 a 5 pasan el 5 y el 7, y por el tramo entre el 5 y el 7 pasa el 7. Entonces el largo del tramo i es a[i] - a[i-1], y la cantidad de gente que pasa por el es i si x >= a[i] o n - i + 1 de lo contrario, por simplicidad veamos que pasa cuando todos los tramos tienen largo 1, en este caso para un x fijo la solucion es 1 + 2 + 3 + ... + x + ( n - x ) + ( n - x - 1 ) + ... + 1, por ejemplo para n = 5 y x = 4 es 1+2+3+1, para n = 5 y x = 3, es 1+2+2+1, lo cual es optimo, no es dificil darse cuenta que para un n, el mejor x siempre va a ser (n+1)/2, ya que sino tendriamos que recorrer cada cacho con igual o mas elementos que con aquel x. Cuando cada tramo tiene un largo especifico este greedy sigue funcionando igual, la prueba la dejo como ejercicio al lector, este greedy es muy comun en problemas de CP. Con esto, ya podemos resolver el problema para un k fijo, cogemos para cada uno de los pedazos de k, y sumamos abs(a[i]-mediana_del_pedazo) para cada uno de sus elementos. Como puede notar esto solo es posible si k es un divisor de m, asi que podemos probar todos los divisores de m y calcular la solucion y quedarnos con lo mejor. La complejidad total es O(n*div(n)) donde div(n) es aproximadamente n^(1/3).

Segunda subtarea: Para esta subtarea tenemos que mejorar nuestra solucion anterior, ahora no podemos representar el vector, ya que si lo hariamos m puede ser hasta la suma total, que es 10^12 en el peor caso. Para reslover esto lo que vamos a hacer es, llevar la suma de los menores que la mediana( que son k / 2 ), y la de los mayores que la mediana, entonces vamos de 1 a n, y tratamos de completar nuestro pedacito de k, cuando lo hacemos, lo que queda de a[i], lo convertimos en a[i] % k, ya que estos pedazos tienen costo 0, con esto podemos evaluar la solucion para un k, en O(n). Si probamos todos los divisores, la complejidad seria demasiado grande para 10^6, pero teniendo en cuenta que para picar en pedazos de k, si hay un numero p, que es un divisor de k, la solucion de p sera en el peor caso igual que la de k, por lo que solo es necesario probar con los factores primos de la suma, lo cual nos deja una solucion lo suficientemente rapida como para dar AC.

Hay una solucion alternativa, que es mucho mas corta y orz. Analicemos lo que pasa si sustituimos a[i] por s[i], donde s[i] es la suma de todos los a[j] de 1 a j, o sea, la suma de prefijos. Si movemos uno a la derecha es equivalente a restar 1 a s[i], y si movemos uno a la izquierda es equivalente a sumar 1 a s[i-1]. Ademas si todos los s[i] son divisibles por k, tambien lo seran todos los a[i]. Entonces el problema se reduce a: tenemos un arreglo, y queremos hacer que todos los elementos sean divisibles por k y la operacion es sumar 1 o restar 1, asi que la solucion para un k es simplemente la suma para cada i de min( s[i] % k , k - s[i] % k ). NOTA: En muchos problemas es util, debido a ciertas caracteristicas, mirar como se afctan otros arreglos, como son la suma de prefijos o el difference array, y finalmente un tip random, hacer un arreglo A creciente es lo mismo que hacer el arreglo B no decreciente definiendo B[i] como A[i] - i, y viceversa.