r/backtickbot • • Mar 08 '21

https://np.reddit.com/r/programminghorror/comments/m019mq/so_this_is_the_source_code_of_the_official/gq5vr0o/

Tried to pretty it up and add comments

TLDR; Looks like it's reading a file and permuting arrays in the file

#include <bits/stdc++.h>
using namespace std; 
ifstream in_file("permutare.in"); 
ofstream out_file("permutare.out");
cosnt unsigned INFINITY = 2000000001; 
unsigned n,m,c,u,v,p,q,x[2010];
int main() {
    // Initialize matrix for dynamic programming
    unsigned D[1000][1000];
    D[0][0]=1;
    for(int i = 1; i < 1000; i++) {
        D[i][0] = 1; // set first value in each row to 1
        for(int k = 1; k <= i; k++) {
            // every value in DP matrix is either sum of left and above or infinity
            // [0 0 ... 0 0]
            // [1 1 ... 1 1]
            // [1 2 3 4 ...]
            // [1 3 6 10 ...]
            //  ...
            // [1 999 ...]
            D[i][k] = min(D[i=1][k] + D[i][k-1], INFINITY);
        }
    }
    unsigned c;  // command number
    unsigned n;  // half length of array
    while(in_file >> c >> n) {  // Read two numbers first is command second is value
        // Our position in DP
        unsigned u = n;  // Row for DP matrix
        unsigned v = n;  // Col for DP matrix

        // Position in the array
        unsigned p = 1;  // start index into x array
        unsigned q = n + 1;  // Halfway index into x array 
        unsigned m = 2 * n;  // Array length  

        // Which mode are we in?
        if(c == 1) {
            // Modify array according to K
            // file looks like "1 n k" 
            int k_num;
            in_file >> k_num;
            // iterate over array in memory
            // We have two cursors p to the start of the x array and q to the middle
            // We change the x array depending on the special K value
            // if K is < the DP cell above us we set the 
            // at the end we will have a matrix where half the values are overwritten by the index
            // e.g.  [1000 2000 3000 4000 5000 6000 7000 8000] -> [1 3 4 4000 2 5]
            for(int i = 1; i <= m; i++) {
                // Check if input_k is < DP value UP in the matrix
                if(D[u][v-1] >= k_num) {
                    // modify first half of array
                    x[p++]= i;  // overwrite with index
                    v--;  // move up
                } else {
                    // modify second half of array
                    x[q++] = i;  // advance the halfway index and set current x value to index
                    k_num -= D[u--][v-1];  // decrease special value by the UP value in DP matrix then move to DP cell left of us
                }
            }
            // Write out array
            for(int i = 1; i <= m; i++) {
                out_file << x[i] << ' ';
            }
            out_file << '\n';
           // continue;  I replaced this with the else branch to make it clearer
        } else {
            // Calculate K from input array
            // Read in array of unsigned ints
            for(int i = 1; i <= m; i++) {
                in_file >> x[i];
            }
            int k_num_2 = 1;
            for(int i = 1; v > 0; i++) {
                // if index from start == the index
                if(x[p] == i) {
                    v--;  // move up dp cell
                    p++;  // advance p index
                } else {
                    // add above DP cell and then move left
                    k_num_2 += D[--u+1][v-1];
                    q++;  // idk
                }
                out_file << k_num_2 << '\n';
            }
        }
    }
    return 0;
}
12 Upvotes

0 comments sorted by