Errores y consejos más críticos en la programación competitiva

En el momento en que un principiante escucha esta palabra, aparece una imagen en su mente donde los estudiantes están sentados en una sala llena de computadoras y codificando algunas cosas fuera del mundo. Seremos honestos, no es nada difícil de entender, así que seremos proponiendo consejos que ayuden a un programador a subir de nivel más rápido. Entonces, comencemos con los puntos más subestimados en cada tema donde incluso los programadores competitivos avanzados se equivocan.

Entonces, el concepto de desbordamiento se puede ver mucho en la codificación competitiva, el peor problema de no entenderlo es escribir un código completamente perfecto pero aún obtener la respuesta incorrecta, esto se debe a que, en rangos de entrada más altos, el compilador reduce el resultado. según el tamaño de los datos, por lo tanto, es importante recordar los rangos básicos de tipos de datos.

Int => [-109  To 109]
Long Int / long => [-1012,1012]
Long Long Int / long long => [-1018,10^18]

Ejemplo:

// C++ Program, to Illustrate General Tips In Competitive
// Programming
 
// Importing all C++ libraries
#include <bits/stdc++.h>
 
using namespace std;
 
// Main method
int main()
{
 
    // Case: Stack Overflow
    int a = 100000, b = 100000;
    // Expected answer ? 10^10 but
    // no the answer you get is 1410065408, error in
    // precision.
    int c = a * b;
    long long int d = a * b;
 
    // Note: Still error will be generated bacause
    // calculation was done on two ints which were later
    // converted into long long ie they already
    // lost their data before converting
 
    // Print and display on console
    cout << c << " " << d << endl;
 
    // Now if we store a value more than its capacity then
    // what happens is the number line of range of value
    // bacomes a number
    // Example: Circle, If min val is 1 and max is 9, so if
    // we add 1 to 9 it will result in 1, it looped back to
    // starting, this is overflow
 
    int p = INT_MAX;
 
    // An example of overflow
    cout << "An example of overflow " << p + 1 << endl;
 
    // Long long is way better than double,
    // double although can store more than long long but
    // in exchange it will cost you your precision.
    // We can simply use the below command as follows:
    // cout<<fixed(no scientific
    // notation)<<setprecision(0){removes decimal}<<variable
    // to give value same form as long long
 
    // Question where the answer came wrong coz of
    // overflow!!
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
 
        // Here, before i used int and got wrong answer,
        // then made it long long
        long long pdt = 1, temp;
 
        for (int i = 0; i < n; i++) {
            cin >> temp;
            pdt *= temp;
        }
 
        if (pdt % 10 == 2 || pdt % 10 == 3 || pdt % 10 == 5)
            cout << "YES" << endl;
 
        else
            cout << "NO" << endl;
    }
}

1410065408 1410065408
An example of overflow -2147483648

Consejos para estructuras de datos

Sugerencia 1: en la programación competitiva, siempre declare la array globalmente cuando necesite tener una función junto con la función principal, las arrays declaradas globalmente pueden tener un tamaño de 10^7, ya que se almacenan en segmentos de datos .

Sugerencia 2: cada vez que declare una función en la que necesite devolver varios elementos, o incluso en general donde su objetivo sea devolver una array después de algunas modificaciones, siempre elija Pasar por referencia ( p. ej., void swap(int &a, int &b ) ) , lo ayuda de dos maneras, una, al reducir el tiempo para hacer una copia de los datos y luego procesarlos y, en segundo lugar, como está trabajando directamente en los datos principales, puede modificar tantos valores como desee sin tener que hacerlo. preocuparse por devolver los valores y tratar con ellos.

• El límite del tamaño de una array declarada dentro del método principal es 10 ^ 5, porque está almacenado en la memoria de pila con un límite de memoria de alrededor de 8 MB, si el tamaño es mayor que esto, se produce un desbordamiento de pila .
• A veces ocurre un error muy peculiar cuando toma varias strings como entrada después de una entrada cin. en lugar de tomar las entradas requeridas, automáticamente toma espacio como entrada y luego toma las dos strings restantes, para resolver esto use cin.ignore() antes de usar getline() para tomar la string como entrada.
• mientras se forma una nueva string a partir de otra string, en lugar de usar una sintaxis como str = str + str2[I], es decir, agregar un carácter para obtener una string, la complejidad de tiempo de este método es O (tamaño (string)) , por lo tanto, se incluye la adición de caracteres a una string que usamos push_back (carácter) cuya complejidad de tiempo es O (n).

Consejos sobre STL

Como ya sabemos de lejos, STL significa Biblioteca de plantillas estándar en C++, que es una bendición para los programadores competitivos, que contiene estructuras de datos y algoritmos especiales incorporados que reducen y optimizan su código como loco. RECUERDE los siguientes consejos sobre estructuras de datos STL enumerados a continuación:

Sugerencia 1: siempre que necesitemos ordenar datos en una pregunta y eliminar duplicados, la mejor práctica es almacenarlos en un Conjunto, automáticamente ordena los datos y según la propiedad de Conjunto , solo almacena valores únicos.

Sugerencia 2: en las preguntas en las que necesitamos encontrar la frecuencia de todos los valores, la mejor práctica es usar un Mapa. ​​La propiedad de Mapa hace que automáticamente organice los datos en orden lexicográfico, y solo con un pequeño truco, tendrá la solución más eficiente.

Ejemplo

// C++ Program to Illustrate STL Algorithms Tips
 
// Importing all C++ libraries
// Standard command
#include <bits/stdc++.h>
 
using namespace std;
 
// Main method
// From here the code starts executing
int main()
{
 
    // Creating vector and initializing objects
    // by passing custom integer numbers
    vector<int> v
        = { 1, 4, 2, 5, 6, 3, 9, 0, 10, 3, 15, 17, 3 };
 
    // Operation 1
    // Finding the minimum element in the array,
 
    // Note: It returns the pointer/iterator
    auto min = min_element(v.begin(), v.end());
 
    // Print and display elements on console
    cout << "Min element: " << *min << endl;
 
    // Operation 2
    // // Finding the maximum  element in the array
    auto max = max_element(v.begin(), v.end());
    cout << "Max Element: " << *max << endl;
 
    // Operation 3
    // Sum of all elements, the third parameter tells us
    // initial sum ki value kya hai.
    auto sum = accumulate(v.begin(), v.end(), 0);
    cout << "The sum of all elements: " << sum << endl;
 
    // Operation 4
    // Count the frequency of an element in the array/vector
    auto cnt = count(v.begin(), v.end(), 3);
    cout << "Frequency Of 3 is: " << cnt << endl;
 
    // Operation 5
    // Finds an element and returns its pointer
    auto elem = find(v.begin(), v.end(), 3);
 
    if (elem != v.end())
        cout << "the element is at posn: " << *elem << endl;
    else
        cout << "Element not found" << endl;
 
    // Operation 6
    // Reversing a string or array/vector
    // using reverse method
    reverse(v.begin(), v.end());
 
    cout << "Reversed Vector: ";
 
    for (auto val : v) {
        cout << val << " ";
    }
 
    // New line for better readability
    cout << endl;
 
    // Operation 7
    // Sort array/vector using sort() method
    sort(v.begin(), v.end());
    cout << "Sorted Vector: ";
    for (auto val : v) {
        cout << val << " ";
    }
}

Min element: 0
Max Element: 17
The sum of all elements: 78
Frequency Of 3 is: 3
the element is at posn: 3
Reversed Vector: 3 17 15 3 10 0 9 3 6 5 2 4 1 
Sorted Vector: 0 1 2 3 3 3 4 5 6 9 10 15 17 

Nota: Estos son algunos algoritmos populares que pueden facilitarle la vida. Todos tienen el mismo patrón de uso, es decir, el nombre de la función.

(límite inferior, límite superior+1)