There are many ways of solving this problem. We will introduce one of them.

First, let \(X\) be the sum of beauty, taste, and popularity, and for each integer from \(3\) through \(3N\) (inclusive), let us find the number of cakes where \(X = k\).
This number corresponds to the number of ways of choosing an integer from \(\{1,2, \dots , N\}\) three times whose sum is \(k\).
This problem can be solved by the DP (Dynamic Programming) where dp[the number of integers chosen][their sum]=[the number of such choices]. A naive implementation will need a total of \(O(N^2)\) time, but since the destination of a transition from \(dp[i][j]\) is a segment of \(dp[i+1][j+1],dp[i+1][j+2], \dots dp[i+1][j+N]\), so one can speed this up to \(O(N)\) with cumulative sums.

Now we figured out the value \(X\) of the \(K\)-th cake from the left. Then, the problem can be solved in an \(O(N)\) loop, iterating each “beauty” of the cake.
Specifically, once we know the “beauty” and the value \(X\) of a cake, the possible range of “taste” forms a single segment, so each iteration of the loop will find such segment. For more details, refer to the sample code as well.

Therefore, the problem has been solved in a total of \(O(N)\) time.

Sample code in C++:

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  long long k;
  cin >> n >> k;
  long long dp[4][3000005]={0};
  dp[0][0]=1;
  for(int i=0;i<3;i++){
    for(int j=0;j<=i*n;j++){
      dp[i+1][j+1]+=dp[i][j];
      dp[i+1][j+n+1]-=dp[i][j];
    }
    for(int j=1;j<=(i+1)*n;j++){
      dp[i+1][j]+=dp[i+1][j-1];
    }
  }
  
  int x;
  for(int i=3;i<=3*n;i++){
    if(k<=dp[3][i]){x=i;break;}
    else{k-=dp[3][i];}
  }
  for(int i=1;i<=n;i++){
    int jmi=max(1,x-i-n);
    int jma=min(n,x-i-1);
    if(jmi>jma){continue;}
    if(k>(jma-jmi+1)){k-=(jma-jmi+1);continue;}
    int y=jmi+k-1;
    int z=x-i-y;
    cout << i << ' ' << y << ' ' << z << '\n';
    return 0;
  }
}

BONUS! This problem can be solved for little more large constraints, and the problem with many queries of cakes can also be solved. Do consider many ways to solve!