Duda problema Codeforces

Problemas
#1

Buenas! Estoy intentando resolver el siguiente problema:
https://codeforces.com/problemset/problem/281/B
y me tira WA en el caso 17708 35362 1558 pero no logro encontrar el error de mi código, alguien podría darme una mano?

Creo que el problema se me rompe al comparar algunas fracciones con la operación <, ya que creo que la multiplicación se me va a la miércoles. De ser ese el problema, intenté solucionarlo trabajando con unsigned long long pero no funcionó bien mi código.

   #include <bits/stdc++.h>
#define pb push_back
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforr(i, a, b) for(int i = (int)(b-1); i >= (a); i--)
#define dforn(i, n) dforr(i, 0, n)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct frac {
ll num;
ll den;
};
bool operator <(frac a, frac b){
    if(a.num*b.den < b.num*a.den){
        return true;
    }else{
        return false;
    }
}
ll mcd(ll a, ll b){
    if(b==0){
        return a;
    }else{
        return mcd(b, a%b);
    }
}
frac resta (frac a, frac b)
{
    frac x;
    x.num=a.num*b.den-a.den*b.num;
    x.den=a.den*b.den;
    if(x.num==0) x.den=1;
    return x;
}
int main()
{ FIN;
    frac a;
    ll n;
    cin >> a.num >> a.den >> n;
    frac cadauno[n];
    ll d=mcd(a.num, a.den);
    a.num=a.num/d;
    a.den=a.den/d;

    if(a.den<=n)
    {
        cout << a.num << "/" <<a.den << "\n";
        return 0;
    }
    else
    {
        forr(i, 1, n)
        {
            frac b, c;
            c.den=i;
            b.den=i;
            ll x=0, y=a.num, med=(x+y)/2;
            while(y-x>1)
            {
                med=(x+y)/2;
                b.num=med;
                if(a<b) y=med;
                else x=med;
            }
            b.num=med;
            c.num=med+1;
            if(resta(a,b)< resta(c,a)) cadauno[i]=b;
            else cadauno[i]=c;
        }
        cadauno[0].num=0, cadauno[0].den=1;
        frac aux, mejor;
        forn(i, n)
        {
                frac rest;
                aux=a;
                if(cadauno[i]<a) rest=resta(a, cadauno[i]);
                else rest=resta(cadauno[i], a);
                if (rest<aux)
                {
                    aux=rest;
                    mejor=cadauno[i];
                }
                // cout << cadauno[i].num << "/" << cadauno[i].den << " " << rest.num << "/" << rest.den << "\n";
        }
        if(n==1)
        {
            ll q=a.num/a.den;
            cout << q << "/" << 1 << "\n";
            return 0;
        }
        d=mcd(mejor.num, mejor.den);
        cout << mejor.num/d << "/" << mejor.den/d << "\n";
    }


    return 0;
}
1 me gusta
#2

Hola, vengo a darte una mano, fijate un par de cosas :face_with_monocle:

  • Entiendo que la idea es probar todos los denominadores posibles. Al usar \texttt{forr}, no estás probando con el denominador n, que podría ser necesario.
  • No creo que estés modelando correctamente esta parte del enunciado (no alcanza con simplificar la fracción)

If there are multiple “nearest” fractions, choose the one with the minimum denominator. If there are multiple “nearest” fractions with the minimum denominator, choose the one with the minimum numerator."

  • No lo testeé, pero usando \texttt{long long} no creo que vayas a tener problemas con el overflow. Entiendo que la cuenta más grande se da al hacer \texttt{rest < aux}, pero si no entiendo mal ahí hay cosas del orden de 10^{15}, así que no habría problemas por ahí.
  • Fijado el denominador n, estás usando una binary para encontrar la fracción de la forma \frac{med}{n} más grande a \frac{x}{y} (los del enunciado) que todavía es menor a \frac{x}{y}. Podés ahorrarte la binary despejando de la cuenta, de forma similar al comparar fracciones.

Fijate de hacer bien el caso x = 13, y = 10, n = 7. Debería dar \frac{9}{7}.

Te dejo link a mi envío, que quizá aclara un poco las cosas. Quizá no.

2 Me gusta
#3

Hola, una consulta con respecto al mismo problema.
Mi idea es la siguiente.
Voy probando para cada denominador posible entre 1 y n, y hallo el “numerador correspondiente”. El numerador correspondiente es tal que vale lo siguiente: (a*d-c*b)/(b*d) < mcd(a, b) (donde a y b son mi numerador y denominador iniciales respectivamente y c es el numerador correspondiente y d es el denominador que estoy probando). Despejando todo en función de c queda c > (a*d-mcd(a, b)/(d*b))/b. Tengo entendido que este numerador correspondiente va a ser tal que se minimiza la diferencia entre a/b-c/d, pero por ahí estoy equivocado.
Estoy sacando WA en el TC 7.
Mi código:

código 
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for(tint i=s;i<=n;i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()
 
typedef long long tint;
 
const int INF = 1e5+5;
 
int main() {
	int x, y, n; cin >> x >> y >> n;
	int mcd = __gcd(x, y);
	int bestNum = 0, bestDem = 1;
	double mini = INF;
	forsn(i, 1, n){
		double ans = (x*i-((mcd/i)*y))/y;
		int num = ceil(ans);
		if(num < 0) continue;
		double uv = double((x*i-y*num))/double((y*i));
		if(uv < mini){
			mini = uv;
			bestDem = i; bestNum = num;
		}
	}
	if(x == 1 && y == 1 && n == 1) bestDem=1, bestNum=1;
	cout << bestNum << '/' << bestDem << endl;
}
#4

Primero, ojo que no hay que minimizar \frac{x}{y} - \frac{a}{b} con una fracción más chica, sino minimizar la diferencia en valor absoluto \left | \frac{x}{y} - \frac{a}{b} \right |, para lo cual una fracción que se pasa por un poquito también te sirve.

Voy a responder, pero la verdad es que no me puse a seguir tus cuentas con detalle. En particular, con solo mirar la fórmula no veo por qué “el numerador correspondiente” sería el que cumple esa relación. De todas formas, me imagino que hace referencia al numerador más grande tal que la fracción generada es más chica que \frac{x}{y}. Pero entonces fijate que quizá te sirva usar la fracción más chica que se pasa de \frac{x}{y}, que sería sumarle uno a ese numerador.

Respecto del código, puede que haya problemas de precisión al usar \texttt{double}. A veces alcanza con utilizar \texttt{long double}, pero en realidad habría que mirar la cuenta con cuidado para ver si puede o no haber errores de precisión. En este problema es evitable usar números de punto flotante, en general siempre que se pueden evitar sin mucho trabajo extra es conveniente evitarlo.

2 Me gusta
#5

Gracias por la respuesta!
Sigo intentándolo y cualquier cosa vuelvo a consultar

1 me gusta
#6

+1 , el punto flotante no es exacto y puede generar errores, 0.1 * 10 != 1.0. Si se puede hacer en enteros, que son exactos, siempre es mejor hacerlo en enteros. De regalo, casi seguro ejecuta más rápido pues el punto flotante es bastante más lento.

Acá explica muy bien por qué los problemas que usan punto flotante se evitan a toda costa en las competencias de nivel secundario, y este texto es un clásico excelente que deja claro que hacer las cosas bien con punto flotante no es para nada sencillo en general.

2 Me gusta