Basic knowledge of Number theory for Odd and Even integer is needed to solve this problem.

• Sum of any number of even integers is even
• Sum of even number of odd integers is even
• Sum of odd number of odd integers is odd

I tried to solve it by bfs by considering every possible states. That's why I got TLE. Greedy was the intended solution for this problem.

My code that got TLE in contest:

string s;
map<string, int> mp;
struct state
{
      string in;
      int swap;
};

int main(void)
{
    //freopen("1.txt", "r", stdin);
    //freopen("2.txt", "w", stdout);
    char in[20];
    int k;
    int i,j;
    int ind;
    while(cin >> in >> k)
    {
          queue<state> pq;
          //cout << in << " " << k << endl;
          struct state st, temp;
          st.in= in;
          ind = 1;
          st.swap = 0;
          pii pii1 = make_pair(st.in, st.swap);
          pq.push(st);
          mp[st.in] = ind++;
          s = "0000000000000000000";
          while(!pq.empty())
          {
                temp = pq.front();
                pq.pop();
                //if(temp.swap == k)
                //{
                      if(temp.in > s)
                      {
                            s = temp.in;
                            //continue;
                      }
                //}
                int sz = temp.in.size();
                st = temp;
                if(temp.swap == k)
                continue;
                forl(i,0,sz-1)
                {
                      //forl(j,i+1,sz)
                      j = i+1;
                      //{
                            //
                            if(i != j && st.in[j] > st.in[i] && !(i == 0 && st.in[j] == '0'))
                            {
                                  st = temp;
                                  char c = st.in[i];
                                  st.in[i] = st.in[j];
                                  st.in[j] = c;
                                  st.swap = temp.swap+1;
                                  if(mp[st.in]==0)
                                  {
                                        st.swap = temp.swap+1;
                                        mp[st.in] = ind++;
                                        pq.push(st);
                                  }
                            }
                      //}
                }
                
          }
          
          cout << s << endl;
          mp.clear();
    }
    
    return 0;
    
}

Defining proper state was the root challenge in this problem.

State can be defined by dp[a][isFulfilled]

a is current sum and isFulfilled is true/1 if we made at least one single step with length >= d.

Base Cases are:

      if(a == n && isFulfilled == 1)
      {
            return 1;
      }
     
      if(a == n && isFulfilled == 0)
      {
            return 0;
      }
      
      if(a>n)
        return 0;