You are not logged in. Please login at www.codechef.com to post your questions!

×

ODDSORT and ANTS on the INOI server

1
1

Has anybody solved these two? If so, how?

asked 08 Jan '15, 21:58

superty's gravatar image

3★superty
3647
accept rate: 31%


Hey,

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.

Ants is actually a problem from a SRM (446), namely AntsOnGraph. The solution is available at http://apps.topcoder.com/wiki/display/tc/SRM+446.

Cheers, Shikhin

link

answered 09 Jan '15, 13:51

idraumr's gravatar image

0★idraumr
2463
accept rate: 45%

Thanks for your help. The topcoder link doesn't seem to work though. I logged in but the server failed with a null pointer exception... If it works for you, could you take a screenshot/ paste the text somewhere? Edit: nevermind, I got it, nice problem with an interesting solution.

(09 Jan '15, 14:28) superty3★

Indeed. In fact, after solving that, I found a few more interesting problems that relied on fun uses of the exponentiation by squaring idea for efficient solutions. Cheers!

(09 Jan '15, 15:41) idraumr0★

Care to share them?

(09 Jan '15, 16:06) superty3★

It seems that huge numbers are a giveaway for this sort of thing.

(09 Jan '15, 17:01) superty3★

A repeated operation to be performed for a specific large number of times seems to be the "gist" of it.

(09 Jan '15, 22:20) idraumr0★

@idraumr @superty although a complexity of O(N^2) is enough for the ODDSORT problem, do you know an algorithm with an O(NlogN) or O(N) complexity?

(12 Jan '15, 22:42) sandy9993★

Yes. http://paste.ubuntu.com/9720318/ We can augment that code with segment trees.

(13 Jan '15, 01:14) superty3★

Here's the accepted NlogN code: http://paste.ubuntu.com/9720712/

(13 Jan '15, 02:19) superty3★
showing 5 of 9 show all

Hey, I have solved the ODDSORT Problem. Its pretty easy... Here's my C++ Source Code...I got a 100:

include "iostream"

include "algorithm"

using namespace std;

int main() {

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;

}

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...

link

answered 09 Jan '15, 22:05

arpanb8's gravatar image

3★arpanb8
120310
accept rate: 13%

No worries (or hurry), as you can see I've already got the solution from idraumr. (got both accepted as well)

(09 Jan '15, 22:13) superty3★
2

ok @superty!!! I was jst about to upload my source code...

and u dont hv to stress on the word HURRY every time!!!

(09 Jan '15, 22:58) arpanb83★

@superty...pls provide ur soln. to ants...mine is not working for only one testcase?!?!?!

(20 Jan '15, 21:25) arpanb83★

There is an official solution available. Click on statement and download the attached .cpp file.

(20 Jan '15, 21:44) superty3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3
×3

question asked: 08 Jan '15, 21:58

question was seen: 1,748 times

last updated: 20 Jan '15, 21:44

Related questions