Answers to: ODDSORT and ANTS on the INOI serverhttps://inoi15.discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server<p>Has anybody solved these two? If so, how?</p>enFri, 09 Jan 2015 22:05:00 +0530Answer by arpanb8https://inoi15.discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server/61126<p>Hey,
I have solved the ODDSORT Problem. Its pretty easy... Here's my C++ Source Code...I got a 100:</p>
<h1>include "iostream"</h1>
<h1>include "algorithm"</h1>
<p>using namespace std;</p>
<p>int main()
{</p>
<pre><code>int n, sum=0;
cin >> n;
int x[n+1], y[n+1];
for (int i = 1; i<=n; i++)
{
cin >> x[i];
y[i]=x[i];
sum+=x[i];
}
sort (y+1, y+n+1);
int mf[n+1][n+1];
for (int j = 0; j<=n; j++)
{
mf[j][0]=0;
mf[0][j]=0;
}
for (int p = 1; p<=n; p++)
for (int q = 1; q<=n; q++)
{
if (x[p]==y[q])
mf[p][q]=x[p]+mf[p-1][q-1];
else
mf[p][q]=max(mf[p-1][q], mf[p][q-1]);
}
sum-=mf[n][n];
cout << sum;
return 0;
</code></pre>
<p>}</p>
<p>I read ANT's prob. statement and I think I can solve that also...Please wait for no more than 3 hours!!! I'll upload the solution...</p>arpanb8Fri, 09 Jan 2015 22:05:00 +0530https://inoi15.discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server/61126Answer by idraumrhttps://inoi15.discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server/61095<p>Hey,</p>
<p>Oddsort is a tricky problem. Note that a certain subsequence of numbers would not be moved at all, and the rest would be moved relative to it. Once you've thought this far, the solution is easy. Two observations --- the subsequence that is fixed has to be in an increasing order. Secondly, the optimal solution is achieved when the sum of this subsequence is maximum. You can also prove this somewhat informally.</p>
<p>Ants is actually a problem from a SRM (446), namely AntsOnGraph. The solution is available at <a href="http://apps.topcoder.com/wiki/display/tc/SRM+446">http://apps.topcoder.com/wiki/display/tc/SRM+446</a>.</p>
<p>Cheers,
Shikhin</p>idraumrFri, 09 Jan 2015 13:51:01 +0530https://inoi15.discuss.codechef.com/questions/61046/oddsort-and-ants-on-the-inoi-server/61095