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

×

Little Elephant and Divisors - LEDIV

Problem link : LEDIV

My code : LEDIV

Can't figure out the error in my code. Please help.

asked 18 Sep '13, 19:58

gautam94's gravatar image

3★gautam94
474142646
accept rate: 11%

edited 19 Sep '13, 14:07

Updated my code.

(19 Sep '13, 14:07) gautam943★

My algorithm is incorrect. It fails for n = 1 because the for loop staarts from j = 2 and the inner loop terminates when a[i] % j != 0 and directly compares the value of ans and n. This will cause the output to be -1 for all sequences which contain an odd number.

(19 Sep '13, 18:21) gautam943★

Have you understood the problem clearly? Have you read the editorial?

Your program is printing only one output for 2 test inputs.

link

answered 18 Sep '13, 20:59

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

Your code at IdeOne is wrong, isn't it? T = 5, but there are 4 results in output...

link

answered 19 Sep '13, 18:42

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

@betlista Yes that code is incorrect and no I now the reason it fails, so I am trying some other method.

(19 Sep '13, 18:48) gautam943★

This solution is getting TLE.

link

answered 19 Sep '13, 19:36

gautam94's gravatar image

3★gautam94
474142646
accept rate: 11%

1

First observation, why are you using sort to get min, when sort is O(n log n) but array traversal is O(n)...

(19 Sep '13, 19:38) betlista ♦♦3★

@betlista Still getting TLE. Should I use getchar_unlocked ?

(19 Sep '13, 19:52) gautam943★

Such optimizations are not needed when algorithm is ok ;-)

Your code runs in O(min(a[i]) * n), so for 100.000 * 100.000 it requires 10^10 operations.

(19 Sep '13, 19:53) betlista ♦♦3★

And what is the limit for Codechef judge?

(19 Sep '13, 20:23) gautam943★

I do not know for sure, but I guess something like 10^8 for second.

(19 Sep '13, 20:35) betlista ♦♦3★
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:

×1,917

question asked: 18 Sep '13, 19:58

question was seen: 817 times

last updated: 19 Sep '13, 20:35