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

×

My approach for SMRSTR(November Lunchtime)

Problem:- SMRSTR

It says that we have to optimize the code snippet given in the problem. We can observe that for every value in the X array we do the same thing by dividing it repeatedly by all the elements in the D array i.e we just divide every value in the X array by the product of all elements in the D array. So, we can proceed by finding this product only once. But according to the constraints the product results in a very big number. But we can observe that if product is greater than the largest element in X array, then answer becomes zero for all of them. So, we stop calculating the product when it crosses the largest element in X array. Since, largest element in the X array satisfies our constraints, we can ensure that our product doesn't overflow. If the product does not exceed the largest element of X array we simply find it and divide it with all the elements of the X array and print the result. This gives us a runtime of O(n) which is enough for this question.

If there is a better approach, please do comment it. Here is a link to my solution:- Click Here

If anyone did solve the second problem L-R queries, please explain me. Thanks.

asked 26 Nov '17, 00:33

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 26 Nov '17, 08:50

admin's gravatar image

0★admin ♦♦
19.7k350498541

Thanks bro!!!

(26 Nov '17, 01:06) ramini2★

How about this(https://www.codechef.com/viewsolution/16361399) approach, It looks easier.

link

answered 26 Nov '17, 16:15

krishankantray's gravatar image

2★krishankantray
163
accept rate: 20%

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:

×145
×98
×16
×4

question asked: 26 Nov '17, 00:33

question was seen: 551 times

last updated: 26 Nov '17, 16:15