Update No. N+1
So, I’ve been competing in Codechef’s September 2016 programming challenge. Actually I have just started with the Competitive Coding. Good thing I solved 3 questions successfully (after 2-3 attempts :p ).
Now I’m stucked with a problem from past four days. Rest of the problems are out of my league :p. Well this problem is DIVMAC and it seems very simple at first. Anyone with intermediate knowledge of coding can code it using the Naive Approach. It’ll definitely work on your IDE (I’m using Code::Blocks in Ubuntu 16.04 LTS ) if your code is correct. But there’s a poop known as Constraints(Time Limits, variable limits and hidden test cases). Your solution won’t be accepted when you use the Naive Approach. It showed TLE (Time Limit Exceed) error.
After a Little research and consulting my friends I came to know about an Algorithm : Sieve of Eratosthenes. This algorithm basically generates an array of Prime Numbers with complexity of O(log n). That’s okay. I used it in my code, submitted my code, and again TLE !! I then thought of more ideas. But I’m just a beginner so I’ll learn more about optimization and implementation of algorithms.
Update 1 :
The approach I tried earlier was partially correct. But yesterday I came to know about the Data Structure named Segment Trees or SegTrees on which this problem is based upon.
This Data Structure uses a Tree in form of a single dimension array. It uses two operations update and query. This algorithm apply these operations in a given segment (Left L to Right R) of an Array.
Normally these operations can be done using brute force but it will take the complexity of O(n). By this Algorithm it will implement the tree and it’s complexity will result to O(log n)
Will study more about it and it’s implementation and fill solve it. I will also try to post the solutions after the contest. Till then, to practice the SegTrees, you can solve SPOJ’s GSS1 and GSS3 problem.