Desafío Ryckeboer #5: "Sereja y Comandos"

Problemas
#1

Antes de enunciar el próximo desafío, les recuerdo que todavía nadie posteó una solución en el foro al Desafío Ryckeboer #4: “Indiana”

Desafío Ryckeboer #5: “Sereja y Comandos”

Enunciado

Sereja tiene un arreglo A que consiste de n enteros. Inicialmente, todos los elementos del arreglo tienen el valor 0 (cero).

Sereja escribió m comandos en una hoja de papel. Estos comandos se enumeran de 1 a m, y pueden ser de dos tipos:

  • Tipo 1: Dados l y r (1 \leq l \leq r \leq n): Incrementar en una unidad todos los elementos del arreglo cuyos índices están entre l y r (inclusive).
  • Tipo 2: Dados l y r (1 \leq l \leq r \leq m) Ejecutar todos los comandos cuyos índices están entre l y r (inclusive). En este caso, está garantizado que el valor de r es estrictamente menor que el índice del comando actual en la enumeración de los comandos que escribió Sereja en la hoja de papel.

¿Puedes ayudar a Sereja a ejecutar todos los comandos que escribió en la hoja de papel?

Entrada

La primera línea de la entrada contiene un entero T que denota la cantidad total de casos a resolver. A continuación, viene la descripción de los T casos.

La primera línea de cada caso contiene dos enteros, n y m.

Las siguientes m líneas contienen los comandos que escribió Sereja en la hoja de papel, de la forma: t,l,r cumpliendo las condiciones descritas en el enunciado. En particular en la i-ésima de las siguientes m líneas (con 1 \leq i \leq m):

  • t \in \{1,2\} (según el Tipo de comando)
  • 1 \leq l \leq r \leq n, (si t = 1)
  • 1 \leq l \leq r < i \leq m (si t = 2)

Cotas

  • 1 \leq T \leq 3

Subtarea 1:

  • 1 \leq n \leq 10
  • 1 \leq m \leq 10

Subtarea 2:

  • 1 \leq n \leq 10^3
  • 1 \leq m \leq 10^3

Subtarea 3:

  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 10^5

Salida

Para cada caso se te pide que escribas una línea con el arreglo A resultante luego de ejecutar todas las acciones descritas por los comandos de la lista de Sereja. Los números de cada arreglo deben estar separados por espacios. Como los números pueden ser grandes, se te pide que cada número del arreglo lo escribas módulo 10^9+7 (Es decir, si el número final es x, debemos imprimir el resto al dividir a x por 10^9+7)

Link

En el siguiente link pueden crearse un usuario y realizar sus envíos del problema para resolver cualquiera de las subtareas. (También vienen un par de instancias de ejemplo)

Link al problema original (CodeChef)

Problema similar (más fácil)

Como comentó IvoP más abajo, puede ser aconsejable pensar y resolver primero este otro problema.

Problema (CodeForces)

Pista (SPOILER)

Bueno, no sé si arruina tanto al problema la pista que voy a dar como para poner SPOIOLER, pero al menos quema el tema.

Pista (ahora de verdad)

Charla sobre Fenwick Tree

1 me gusta
COMPETENCIA 11 de Febrero : Lista de problemas - CodeForces
#2

No puedo submitear el codigo, es algo del problema en particular o me pasa a mi nomas?

#3

Probá ahora (siguiendo el link que puse, es uno “nuevo”)

Lo que cambié es que ahora lo linkeo desde la lista de problemas en vez de hacerlo desde el link del contest.

Desde el link que puse ahora pude hacer un envío al problema.

Si sigue sin funcionar avisá por acá (y si funciona avisá diciendo que funciona)

2 Me gusta
#4

Submiteo este codigo, pero ni idea porque anda solo en algunos casos, si me pueden decir que esta mal:

Codigo 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <tuple>
using namespace std;

#define mt make_tuple
typedef long long tint;
tint MOD = 10e9 + 7;
int sum(tint k,vector <tint> &b) {
	int s = 0;
	while (k >= 1) {
		s += b[k];
		k -= k&-k;
	}
	return (s%MOD);
}
void add(tint k, tint x, vector <tint> &b) {
	while (k <= 100003) {
		b[k] += x;
		k += k&-k;
	}
}
int main() {
	tint a;
	cin >> a;
	for (int i = 0; i < a; i++) {
		tint n, m,p,q,ot;
		cin >> n >> m;
		vector <tint> list(100003,0);
		vector <tint> comands(100003,0);
		vector <tuple<tint, tint,tint>> tuples;
		for (int j = 0; j < m; j++) {
			cin >> ot >> p >> q;
			tuples.push_back(mt(ot, p, q));
		}
		for (int j = m; j >= 1; j--) {
			if (get<0>(tuples[j-1])== 2) {
				add(j, 1, comands);
				add(j + 1, -1, comands);
				p = sum(j, comands);
				add(get<1>(tuples[j-1]), p, comands);
				add(get<2>(tuples[j-1])+1,-p, comands);
				
			}
			else {
				add(j, 1, comands);
				add(j + 1, -1, comands);
				p = sum(j, comands);
				add(get<1>(tuples[j-1]), p, list);
				add(get<2>(tuples[j-1])+1, -p, list);

			}
			
		}
		for (int i = 1; i <= n; i++) {
			cout << sum(i, list) << " ";
		}
		cout << endl;
	}
	return 0;

}
1 me gusta
#5

¡Excelente! :slight_smile:

Otra vez, la idea está perfecta, lo que está fallando es la implementación.

Comentarios
  • Fijate que 10e9+7 tiene un cero de más, seguramente querés 1e9+7
  • Ese 100003 que se arrastra en el código es propenso a errores. Es mejor definir al principio const tint MAXN = 100003 (De la misma forma que hacés con MOD, al cual estaría bueno ponerle el const delante, dado que es una constante que no va a variar a lo largo del código).
  • Estás tomando módulo solo al final, en estos casos es conveniente hacerlo a cada paso (en las funciones sum y add del Fenwick Tree).
  • Fijate que el primer for depende de “i” y adentro tenés al final un for que también itera sobre “i”. Eso se ve muuuuuuy raro. Siempre está bueno activar -Wshadow para que nos avise de estas cosas el compilador. La información sobre cómo hacer eso está en este post de la wiki.
  • Probablemente lo más grave en cuanto a la implementación del problema en sí, es estar teniendo en cuenta qué pasa cuando tomamos módulo de un número negativo (que tranquilamente puede haber por cómo resolvemos el problema). En C++ al hacer % MOD a un número nos da el entero más cercano a cero que tiene el mismo signo y misma congruencia módulo MOD que el número que ingresamos. Por ejemplo (-4) % 3 nos devuelve -1.

Una forma usual de arreglar esto es definirnos una función que haga lo siguiente:


tint mod (tint n)
{
	return ((n % MOD) + MOD) % MOD;
}

De esa forma, nos aseguramos que la respuesta esté siempre entre 0 y MOD-1.

Otro comentario ya que estoy es que con un solo Fenwick también se puede resolver el problema, porque el otro lo podés reemplazar por un arreglo común y corriente, acumulando al final una vez que hacés el truquito para hacer el update en un rango (onda tablita aditiva).

Por si te interesa te dejo el link a mi envío en el problema.
link al envío (CodeChef)

1 me gusta
#6

Gracias por lo comentarios :smiley:
Ahi me dio AC, al principio hice como vos comentaste de usar el MOD en todos los pasos pero no me daba, yo pensaba que en c++ si hacias -4%3 te daba 2, pero bueno.
Tambien me sorprendi por el for que usaba i, ni me di cuenta.
Cuando estaba codeando me di cuenta que este problema es similiar a este:
http://codeforces.com/problemset/problem/816/B por si alguien quiere hacerlo antes de este que me parece un poco mas light y en la editorial comentan otras ideas sin el Fenwick.

3 Me gusta
#7

Concuerdo totalmente en que ese problema está lindo y ayuda claramente a resolver este problema, buen ojo :grinning:

Sobre el problema que linkeás

Claro, es un muy buen problema para usar el truquito para hacer actualizaciones a un rango y después acumular para obtener el arreglo final, sin usar Fenwick en ningún lado, solo tablita aditiva.

Lo prometido es deuda, acá está la merecida :medal_military: Insignia Ryckeboer :medal_military: por el AC en el problema (te doy una nueva porque esta es tu segunda, pero hay un límite :stuck_out_tongue: )

InsigniaRyckeboer2