So I was solving this problem https://mirror.codeforces.com/gym/105723/problem/F

and wrote this solution https://ideone.com/SNfGJ6

It works fine in my laptop and ideone C++ 14 but when I submitted it in C++17 (GCC 7-32) I got WA on test 1. It did not make sense to me how I got a vastly different result on the test case in my laptop and CF. I suspected some type of RTE but I could not find any. Then I just submitted in C++23 (GCC 14-64, msys2) and got AC even though I did not change anything in the code.

Anyone knows why this happened. I feel like knowing it would kind of help me avoid it in contests. idk -_-

Given n 3D vectors e_i, 1 <= i <= n, and a 3D vector vector v, find the value of the coefficients c_i such that v is described as a linear combination of the n vectors

v = c_0*e_0 + c_1*e_1 + ... + c_n*e_n

but the twist is to calculate c_i such that abs(c_i) <= a_i, where a_i will be given, 1 <= i <= n.

Print the coefficients c_i or print that it's impossible. (If possible print the answer that minimizes the sum of c_i). I have been pondering this question for quite some days and I still have zero idea how to approach this, will it be DP or greedy with some heuristics. I did not add any constraints since I don't really know what the time complexity will be. Any help will be appreciated. Thank you.

Recently i did Leetcode Longest Common Subsequence problem. I used the basic dp approach and solved it in 18 ms using 12 mb space. After that i decided to check the fastest solutions for the problem and got this code

class Solution {
public:
    int longestCommonSubsequence(string X, string Y) {
        if ( X.size() < Y.size() ) swap(X,Y) ;
        int m = X.size() , n = Y.size();
        if (m == 0 || n == 0) return 0;
        int w = (m + 31) >> 5;
        std::uint32_t S[256][w];
        std::memset(S, 0, sizeof(std::uint32_t) * 256 * w);
        std::int32_t set = 1;
        for (int i = 0, j = 0; i < m; ++i) {
            S[X[i]][j] |= set;
            set <<= 1;
            if (!set) set++,j++;
        }
        std::uint32_t L[w];
        std::memset(L, 0, sizeof(std::uint32_t) * w);
        for (int i = 0; i < n; ++i) {
            std::uint32_t b1 = 1;
            std::uint32_t b2 = 0;
            for (int j = 0; j < w; ++j) {
                std::uint32_t U  = L[j] | S[Y[i]][j];
                std::uint32_t c  = L[j] >> 31;
                std::uint32_t V  = U - (L[j] << 1 | b1+b2);
                b1 = c;
                b2 = (V > U);
                L[j] = U & (~V);
            }
        }      
        int res = 0;
        for (int i = 0; i < w; ++i)
            for (; L[i]; ++res)
                L[i] &= L[i] - 1;
        return res;
    }
};

I submitted it and it ran in 4 ms using 7.5 mb space. I tried to deconstruct the algorithm and understand how it was working. I cleaned the code a bit and got it to run in 3 ms, but I still could not understand it.

#include <cstring>

typedef unsigned int uint;

class Solution {
public:
    int lcs(string X, string Y){
        if ( X.size() < Y.size() ) swap(X,Y) ;
        int m = X.size() , n = Y.size();
        if (m == 0 || n == 0) return 0;
        int w = (m + 31) >> 5;
        uint S[256][w];
        memset(S, 0, sizeof(S));
        uint set = 1;
        for (int i = 0, j = 0; i < m; ++i) {
            S[X[i]][j] |= set;
            set <<= 1;
            if (!set) set++,j++;
        }
        uint L[w];
        memset(L, 0, sizeof(L));
        for (int i = 0; i < n; ++i) {
            uint b1 = 1;
            uint b2 = 0;
            for (int j = 0; j < w; ++j) {
                uint U  = L[j] | S[Y[i]][j];
                uint V  = U - (L[j] << 1 | b1+b2);
                b1 = L[j] >> 31;
                b2 = (V > U);
                L[j] = U & (~V);
            }
        }      
        int res = 0;
        for (int i = 0; i < w; ++i)
            res += __builtin_popcount(L[i]);
        return res;
    }

    int longestCommonSubsequence(string text1, string text2) {
        return lcs(text1, text2);
    }
};

I could not find any relevant blogs explaining it. Can anyone help me understand how this works or link any blogs. Thanks.

In the recent CF round 931 for problem B I realized that I could not solve it normally using DP since n was too high. I knew that some coin systems can be solved greedily but it was not the case for this one. During the contest, I solved it like this: https://mirror.codeforces.com/contest/1934/submission/249165174

But later I saw that some people just pre-calculated the answer upto 30 or something and then used some mod tricks to get the answer. I thought they picked 30 since it was the LCM and so I tried to test my hypothesis by solving the CSES Minimizing Coin problem and it actually worked. I thought this was some optimization on the problem that I did not know about before. This was my solution: https://cses.fi/paste/dbb9ee26f083862b8352b1/

However, I soon realized that my method does not work for coin systems like {3, 6, 10, 15}, as my code would give impossible for the value 32, which is obviously wrong as it should really be 4. After that, I thought there had to be some conditions that had to be met for me to use this "lcm" trick (if this is even real or just something that coincidentally worked). But I could not think of any and I could not find any relevant articles, so I want to ask you guys to make me understand.

Thanks in advance. Btw before writing this blog, I thought I'd solve the original CF problem using the "lcm" trick but it did not give the correct answers lol.