×

# Discussion of CHARORNOT .

 2 Initially when I began to read papers on this problem , I found some papers which mentioned algorithms but they were just names and no other details . I found out some papers which mentioned algos like base 3 , base 5 , sphere methods , block algo and KD algo . What I could understand was only base 3 algo and it gave me 0.41 points . I didn't understand a bit of the other algos and therefore couldn't implement them . further I improved by using an exhaustive bad time complexity solution but it couldn't further incorporate the base 3 solution with it . I would like to know what other ideas were implemented by people specially toppers of the problem and also the details if anyone implemented the above algos I have mentioned and how did they take care of time limits if exhaustive algos were involved . asked 18 Jun '13, 13:24 285●10●17●19 accept rate: 5% Can you provide links to the algorithms you mentioned... Since I only wrote the worst case programs for this question.... Due to my xams I was not able to solve much problems this time.... but the links may help for sure.... (18 Jun '13, 13:42) I used base 3 property and brute force the remaining numbers. This gave me double the score of only base-3 numbers. (18 Jun '13, 13:46) jatin_694★ 1 @devanshug : www.cs.umd.edu/~gasarch/ramseycourse/3aplarge.pdf‎ This is probably the best I could manage. (18 Jun '13, 14:19) There is a similar question in the previous contests of Codechef. Its worth reading.. http://www.codechef.com/COOK15/problems/GENARSEQ but this approach gave me only 0.69 points. I am waiting for a better algo... (18 Jun '13, 15:35)

 4 My approach was to use both the base 3 method. And I was first removing all the numbers which are having 0,1,3,4 modulo 6 value. In this way, almost 4/6, 66% of the numbers with good probability of being in AP were considered. Then I used kept on taking the numbers if they did not form the AP with my earlier taken numbers. This is where I could have optimized my program, but I could not :(. One more observation can be made that, most of the numbers of your series will be from the first and last parts of sorted sequences. Middle numbers would be very less. One another idea I had in my mind to convert problem into standard maximum independent set problem. But I could not code this well. answered 18 Jun '13, 15:31 2.5k●53●137●170 accept rate: 20%
 3 The Simplest Approach which gave me 0.69 points beyond which i couldnt think:P: 1)Sort the Nos. 2)Assume first two nos are in ur answer. 3)To check wheather next no is in ur answer:Find AM(Arithmetic Mean) with all Previously selected nos.. and if that no is present Neglect that no..and Proceed for next input no.. If all AM's are not present .Select that No.. I hope this helps.. And Thanx kavishrox for mentioning those methods.. answered 18 Jun '13, 15:11 425●3●7●17 accept rate: 4% i did exactly the same. :) @kutengine: if you read this, please explain your very nice approach ! (18 Jun '13, 23:21)
 2 I got got 0.75 points with a simple method that I didn't optimize much. (Run time = 6 seconds with Go). I think it could potentially reach 0.85 points with some fine tuning. http://www.codechef.com/viewsolution/2243028 I had two helper methods: func hasTwo(num int) bool { for num > 0 { if num % 3 == 2 { return false } num = num/3 } return true } func pValue(nums []int) (float64, int) { max := 0 for _, v := range nums { if v > max { max = v } } p := float64(len(nums))/float64(max) return p, max }  here pValue is P, the probability of taking a number. (i.e. the density of the numbers given). I assumed the numbers were already sorted. First I count how many numbers fall into each of the 1000 buckets. So numbers close together get put into the same bucket. Then each bucket gets given a score. The score is based on collisions with other buckets. If there are three buckets in an arithmetic progression, their score increases depending on how many numbers are in the three buckets. Eventually numbers that are in buckets that have low collision scores are given priority.  pV, max := pValue(ints) num_buckets := 1500 buckets := make([]int, num_buckets) //make gives zero'd int array of length 1500 bucket_scores := make([]int, num_buckets) d := max/num_buckets + 1 for _, v := range nums { buckets[v/d]++ //bucket counts it's values } for i, _ := range buckets { for j, _ := range buckets { d := i - j k := i + d if j >= i || (k >= num_buckets) { break } //should have a better scoring function score := (buckets[i] + buckets[j] + buckets[k])/3 bucket_scores[i] += score bucket_scores[j] += score //increase score of bucket based on collision bucket_scores[k] += score } }  now value v has score bucket_scores[v/d]. Also if hasTwo(v), and if the density p > 0.74, then we increase the score (and hence the priority) of value v. (note any three numbers with hasTwo() cannot collide) Note that some buckets that collide with each other will have the same score, so I don't go through the values in rough order of priority, rather than exact order of priority. Basically each time I add a number x to the solution, I loop through all other added numbers y. Then I insure (x+y)/2 is marked as taken, and y + (y-x) is added and x - (y-x) is added. (or thereabouts). This shows that no number can go there. I go through numbers in rough order of priority, if they can go there, then I add them and mark other related spots as taken for _, v := range bucket_scores { if v < min_score { min_score = v } } min_score += 2 for cap := min_score; cap < min_score + 100; cap += 10 { for _, rej := range rejected { if !taken[rej] && (bucket_scores[rej/d] < cap) { ok := true for _, v := range added { pos1 := 2 * rej - v pos2 := - rej + 2 * v if pos1 >= 0 && pos1 <= 100000 { if taken[pos1] { ok = false break } } if pos2 >= 0 && pos2 <= 100000 { if taken[pos2] { ok = false break } } if (rej - v) % 2 == 0 { pos3 := (rej + v)/2 if taken[pos3] { ok = false break } } } if ok { added = append(added, rej) solution = append(solution, rej) //fmt.Println(rej) taken[rej] = true } } } }  That was it, other things to try are fiddling with how much cap increases by. E.g. once cap > min_score + 100, I might start increasing cap by 200 after that. answered 18 Jun '13, 16:09 148●1●6 accept rate: 0%
 0 jatin_69 is right. I too expanded my selected subset by brute force after using base 3. As an example the base 3 method only selects 7 out the first 20 natural numbers, whereas there are 9 that can be selected. Apart from this many people have used the Stanley sequence. I was able to jump a few ranks by processing the given array in a different order like a[1] a[n] a[2] a[n-1] a[3] and so on. answered 18 Jun '13, 14:25 4★moody 105●5●6●12 accept rate: 0%
 0 There is a similar question in the previous contests of Codechef. Its worth reading.. http://www.codechef.com/COOK15/problems/GENARSEQ but this approach gave me only 0.69 points. I am waiting for a better algo... answered 18 Jun '13, 15:34 551●7●16●26 accept rate: 8%
 0 I used only a brute force approach that was good enough for score of 4.04 Anyways, I am really waiting for the editorials to come out and when do we get to know the approach of the problem setter i.e. @ACRush. It might even be superior to that of @kutengine... !! Who Knows!! answered 19 Jun '13, 04:10 1.1k●13●22●29 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×164
×62

question asked: 18 Jun '13, 13:24

question was seen: 6,489 times

last updated: 20 Jun '13, 04:46