I recently solved https://cses.fi/problemset/task/1193/, and I found that using pointers here was a natural way to efficiently keep track of the shortest path. At first I had a vector of type obj, each of which contained a pointer to the type obj, but I soon learned that these objects were not actually returning their own memory location! Instead they seemed to take on the memory location of the front of the queue. To try and fix this, I changed it to be a queue of type obj*, but now I could no longer add things to the queue like this q.push({0,0,"",nullptr}), instead I could only get it to work by adding a constructor to obj, and building objects on the heap. Am I missing a simpler/elegant way of doing this?

The solution in question: https://cses.fi/paste/0c68129b81b0a8252c88f4/

I was looking over this article https://cp-algorithms.com/algebra/fft.html, and I was a bit confused by one of example applications. It says that we can use FFT to efficiently solve for all unique sums a[i] + b[j] given integer arrays a and b in $$$O(n\log(n))$$$. I follow the logic behind how the polynomial representation gives us this solution, but i'm confused by the following example: Say a = [1,2,...,1000] and b = [0,1000,2000,...,1000000], then all possible sums takes $$$O(n^2)$$$ to even store! Am I misunderstanding what $$$n$$$ refers to here?

There are many methods of ensuring that you don't write beyond your arrays bounds, i'm wondering which others have found to be best.

For instance, I just went through a simple problem which was solvable via recursion, and handled bounds like this:

bool inBounds(vector<vector<int>> &G,int i,int j){
    return (i >= 0) && (j >= 0) && (i < G.size()) && (j < G[0].size());
}
 
void fill(vector<vector<int>> &G,int i,int j){
    if(!inBounds(G,i,j) || !G[i][j]) return;
    G[i][j] = 0;
    fill(G,i-1,j); fill(G,i+1,j);
    fill(G,i,j-1); fill(G,i,j+1);
}

Instead of this, I could have handled bounds like this:

void fill(vector<vector<int>> &G,int i,int j){
    if(!G[i][j]) return;
    G[i][j] = 0;
    if(i-1 >= 0) fill(G,i-1,j); 
    if(i+1 < G.size()) fill(G,i+1,j);
    if(j-1 >= 0) fill(G,i,j-1); 
    if(j+1 < G[0].size()) fill(G,i,j+1);
}

but the second approach seems more susceptible to bugs! i.e. it relies on picking the right bound to check, instead of blanket checking every one of them.

There's also a third approach I sometimes use, which here would be to modify G in the following way

void preprocess(vector<vector<int>> &G){
    G.insert(G.begin(),vector<int>(G[0].size()+2,0));
    for(int i=1;i<G.size();i++){
        G[i].insert(G[i].begin(),0);
        G[i].push_back(0);
    }
    G.push_back(vector<int>(G[0].size(),0));
}

void fill(vector<vector<int>> &G,int i,int j){
    if(!G[i][j]) return;
    G[i][j] = 0;
    fill(G,i-1,j); fill(G,i+1,j);
    fill(G,i,j-1); fill(G,i,j+1);
}

Then no bounds checking is needed! As long as we never start at an edge, since our preprocessing adds a boundary of 0's around G, and part of the problem already involved terminating when we hit a 0.

Are there other method/tricks for making this process easier? It's usually not that big of a consideration, but when a bug appears because of it, it can sometimes lead to 30 minutes of fruitless debugging. How do you handle this?

In chess there's a variant called Hand and Brain where each side consists of two players. The first decides which piece to move (the brain), and the second decides where to move it (the hand.) I was thinking whether this is extendable to competitive programming. The brain solves the problem, and the hand has to implement it just from what the brain tells them (must not be too detailed.) How crazy does this sound?

I've found that I frequently engage in the following anti-pattern:

1. I read the problem description and start writing out some details on paper (to better visualize what's happening.)
2. I get the right idea for how to solve the problem and start implementing it before figuring out every detail.
3. I test the program and find it (shockingly) misses some sample cases.
4. I go back to the paper and notice something I missed.
5. return to step 2.

For Div 2 A/B problems, this process tends to be sufficient to get the right answer, but it fails badly beyond that, and it also very quickly eats up huge amounts of time. I know I should write out all of the details, but there's always some details that get left out. I'm really curious to hear what others processes are when solving problems they consider hard. E.g. do you prove every bound beforehand? Do you write out pseducode and then implement it?

I worked through https://cses.fi/problemset/task/2413/, but i'm not too happy with my implementation: https://cses.fi/paste/a16f2727089e9e76291e5a/

It's very complicated, as I went with a route I saw would work, but knew would be hard to implement. Every integer represents one of the 20 possible row states, and dp figures out in the next row how many of type X appear based on the sum of the states that allow for type X to appear next. Looking at others solutions, no such enumeration is necessary, but I can't really understand why the alternative method works. Could someone explain the proper approach here?

I've been building up tools for problem solving, and one that came to mind was a form of meta programming. I've found that often I'll know exactly how to structure the entire program, but there are a few loop bounds where it's not immediately clear (e.g. do we end the loop at n, or n-1, or n+1.) Rather than do this hard work of thinking/debugging, every reasonable bound choice is added as a label, and a higher level program generates program strings that are compiled with every possible combination of bounds, returning all of the program strings which pass all local test cases.

Does anyone actually do this, or similar metaprogramming trickery in practice, or is it a fools errand?

I've spent the past few days thinking over https://cses.fi/problemset/task/1085/ without much progress. Looking for a hint to go in the right direction.

One failed method I implemented was to greedily always split the current max sum subarray in two, keeping track of ranges and sums with a priority queue. If it ever hit a single element, then it was clearly done since we can't do better than that, and otherwise output the final max sum. This failed because for instance [111111111] is best divided as [111|111|111] whereas my method would yield [1111|111|11]. My thinking has been that this method may still kind of work by picking the max, combining it with its neighboring regions, and splitting it into 4 instead of 3 subarrays (or fewer in the case that there were fewer neighbors), but this also feels overly complicated.

Very often when $$$n$$$ and $$$m$$$ are variables in a problem, $$$n$$$ will appear first. Alphabetically $$$m$$$ comes first, so why is this the case? For instance when $$$p$$$ and $$$q$$$ are variables, they always seem to come in the right (alphabetical) order.

My thought is that $$$n$$$ is a very popular variable choice, and no one ever uses $$$o$$$ as a variable (easily confused with 0.) so $$$m$$$ is the next natural choice. $$$m$$$ also looks right after $$$n$$$, since it looks like two $$$n$$$'s together. I'm curious if problem setters have other reasonings.

I'm attempting to solve https://cses.fi/problemset/task/2168, and I believe I have the right idea, but i'm getting TLE for all large test cases. My algorithm is to:

1. Transform inputs so that they're constrained to the range [0,400000]
2. For every interval start, keep track of the smallest and largest interval ending.
3. Build a sparse table to solve Range Minimum Queries on the minimum array.
4. Build simpler (cheaper) array to solve RMQ with L=1 fixed for max array.
5. Finally itterate through all queries and solve (one $$$O(1)$$$ call to the sparse table per query.)

Implementation: https://cses.fi/paste/cec69737a6649398283c56/

My main thought is to use an offline query method instead, but nothing here seems like it should exceed the 1 second time limit.

I'm trying to solve https://cses.fi/problemset/task/2183, and I'm completely baffled since every approach I come up with looks to violate the subset sum problem being NP complete for finding a specific subset that sums to N. I'd appreciate a nudge in the right direction.

My observations so far:

• If $$$1,2,4,...,2^i$$$ are in $$$X$$$, then $$$MEX >= 2^{i+1}$$$

• $$$MEX <= 1 + (x_1 + \ldots + x_n)$$$

• $$$MEX = 1$$$ if $$$\min(X) > 1$$$

None of these observations seem sufficient in general.

I'm a bit stumped at why my optimization to https://cses.fi/problemset/task/1625 is failing. With setting the map on line 73 commented out, the code (slowly) finds the correct answer. It seems conceptually that there shouldn't be an issue with using memoization, but i'm not so used to c++ maps. Can anyone see what's wrong?

#include <bits/stdc++.h>

using namespace std;

bool field[9][9] = {0};

int skip(int x, int y, int xp, int yp){
  int dx = x-xp;
  int dy = y-yp;
  if(field[x+dx][y+dy] && !field[x+dy][y+dx] && !field[x-dy][y-dx]){
    return true;
  }
  return false;
}

long long int getState(){
  long long int x=0;
  long long int ind=0;
  for(int i=1;i<8;i++)
    for(int j=1;j<8;j++){
      if(field[i][j])
        x += ((long long int)1<<(ind));
      ind++;
    }
  return x;
}

int counter = 0;
map<long long int,int> m;
map<long long int,int>::iterator it;

int traverse(int x, int y, string s, int ind, int xp, int yp){
  int t = 0;
  if(field[x][y])
    return 0;
  
  if((ind + abs(x-7) + abs(y-1)) > 48)
    return 0;
  
  if((ind == 48) && (x==7) && (y==1)){
    return 1;
  }
  else if((x==7) && (y==1))
    return 0;
  
  field[x][y] = true;
  
  long long int state = getState();
  it = m.find(state);
  if(it!=m.end()){
    field[x][y] = false;
    return m[state];
  }
  
  if(!skip(x,y,xp,yp)){
    if(s[ind] == 'U')
      t += traverse(x-1,y,s,ind+1,x,y);
    else if(s[ind] == 'D')
      t += traverse(x+1,y,s,ind+1,x,y);
    else if(s[ind] == 'L')
      t += traverse(x,y-1,s,ind+1,x,y);
    else if(s[ind] == 'R')
      t += traverse(x,y+1,s,ind+1,x,y);  
    else{
      t += traverse(x+1,y,s,ind+1,x,y);
      t += traverse(x,y+1,s,ind+1,x,y);
      t += traverse(x-1,y,s,ind+1,x,y);
      t += traverse(x,y-1,s,ind+1,x,y);
    }
  }
  
  if(ind < 10){
    m[state] = t; //comment me out to work
  }
  
  field[x][y] = false;
  
  return t;
}

int main(){
  string s;
  cin >> s;
  
  for(int i=0;i<9;i++){
    field[0][i] = true;
    field[i][0] = true;
    field[8][i] = true;
    field[i][8] = true;
  }
  
  cout << traverse(1,1,s,0,0,1) << endl;
}

I've been compiling locally with c++11, e.g. g++ -Wall -Wextra -Wpedantic -std=c++11 -o "D" "D.cpp", and I've been trying to figure out why I'm getting different results remotely. I submitted the same code to:

GNU C++11 (fails) https://codeforces.net/contest/1493/submission/110434447

GNU C++14 (passes) https://codeforces.net/contest/1493/submission/110479676

Locally my c++11 compilation is not getting the error shown in the submission on problem set 3. My gut feeling is that there's some out of bounds write occurring that i'm missing that just isn't affecting things by luck in the other submission, but if it is I just can't detect it. I would appreciate any insight (or critique of my code.)

I actually really love how this is the unique best answer to this question.

Am I missing something, it seems odd that comments have a structure where it shows depth like this : ">> >> >>", but I can't find any way to minimize a comment and all its children (making it much simpler to navigate). Is this normal, or am I missing something?

Given a real number as an input, and an exponent, what would be the right way to determine exactly how many digits of that number are necessary to retrieve the integer part of the resultant exponent. That is, given $$$r \in \mathbb{R}$$$ and $$$n \in \mathbb{N}$$$, you'd like to find the minimum number of digits necessary to accurately compute $$$\left \lfloor{r^n}\right \rfloor$$$. Binary search of digit usage looks like it would work, but feels very inefficient, and for non-truncated real numbers (e.g. where we have a formula instead of raw digits) requires a guaranteed accurate starting point. I've studied very little numerical analysis, but I believe this falls into that realm of problems.