October Long Challenge 2019 Div 2: Maximum Star Value (MSV)

help
1

I wrote the following solution to solve the problem during the contest, but I am getting TLE in 2 cases.
Source-Code: CodeChef: Practical coding for everyone

The algorithm which I designed is basically based on this article https://www.geeksforgeeks.org/queries-counts-multiples-array/ on GeekforGeeks but rather than updating the freq_data[] at once I will first check how many multiples of the arr[i] is present in the freq_data[] and after finding all the multiples, I will keep track of maximum multiples for a number I found out till now.

Then when I traversed the whole array, I will print the value stored in the variable max_star_val and that will be the answer.

2

Bruh how did you pass last two but not 2nd and 3rd?!
Look at this

I think majority people got AC in first three.

3

@rude009 Well I guess my logic was good for the last two cases, I have been trying different ideas for passing the 2 other cases, none of them worked out.

You can look at the this articles https://www.geeksforgeeks.org/queries-counts-multiples-array/ . I used ideas from this article.

Can you elaborate on what ideas you used in order to solve the problem?

2 Likes
4

I did this:

  1. Traversed from the end and stopped when pointer was less or equal to max count.
  2. Skipped 1’s.
  3. Skipped repeated elements.
5

@rude009 So…let’s wait for the editorial for the problem, in the mean time, if I get any ideas, will post here, thanks for sharing the approach :slight_smile:

6
1 Like