CHAORNOT TLE problem

general
, , ,
1

Hi,

The june contest was my first programming competition ever. This CHAORNOT problem was the first problem I tried to solve,but it kept on giving TLE.

the code from my submission is
http://www.codechef.com/viewsolution/2200280

The general pattern that I followed was, remove the Arithmetic mean for every pair of numbers in the given sequence, and then the ones that would be left would not be in AP when the process finished. I tested it for small input sizes, and it seemed to work.

Any feedback would be greatly appreciated and since I am very new,please forgive any naive mistakes I might have done.

(PS- I think my input method is pretty stupid , would highly appreciate if someone could show how to handle very large datasets)

Thanks.

2

@mightymosquito :, i followed a slightly different procedure.
maintain an array ans[] which will finally contain the list of numbers to be displayed.
add the first and the second element i.e B[0] and B1 to the array ans[].
now, for every element B[i],(i>=2):
consider pairs of B[i] and ans[j](j >= 0):
if arithmetic mean of B[i] and ans[j] is present ,dont add B[i] to ans[].

also, maintain a kind of hashmap to find which elements are already present in the ans[].
This solution fetched me 0.691 pts.here’s my solution

3

@mightymosquito Reason that you got TLE is your algorithm complexity is not good enough to get AC within TL.

As you mentioned in the question that you are removing arithmetic mean for every pair of numbers. That is every time you are selecting 2 numbers out of M, C(M,2), which is equal to

C(M,2) = (M * (M - 1)) / 2

So your algorithm have time complexity order of M^2, now with M = 100000 you will certainly get TLE.
You need a better algorithm. I suggest you read editorial for the same problem admins posts it.

EDIT:

Follow this question for algorithms to solve this problem.

And as far knowing when do you need new algorithm to solve a particular problem is concerned, I suggest practice as many as problems you can, then you will know which complexity algorithm would pass given question just by reading the question.

1 Like
4

I tried making this algorithm faster,but was unable to do so.Can it be made faster and if yes ,then what should be my approach, moreover when should I start thinking about a new algorithm when such problems arise when solving problems??-thanks

5

hey i think you can check mine solution for that :

http://www.codechef.com/viewsolution/2270572

I worked on same approach and got TLE initially but then optimised my code by taking following things into considiration :

  1. AM of a even number and a odd number isnt to be checked as it will be not in out input for sure. So we can save half of searches.

  2. Implied quick sort.

  3. Used binary search.

And finally it got accepted with 0.69 point… :slight_smile:

Hope this might help…

1 Like
6

Thanks.This is exactly what I wanted.

7

@mightymosquito Even i had a sort of exhaustive checking algorithm that wasnt very efficient so i put a condition that if number of input elements is greater than around 40,000, then i process upto there only and neglect other numbers. By processing only a maximum of 40k inputs.
in short:

if(num_ of_ inputs>40000) :
{ limit=40000 }

i was able to score around 0.68 points with that.

you can check my link:solution