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

• +3

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;

}



• -6

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;