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

×

Problem solving this array based problem?

given an array Sets S[K] for 0 ≤ K < N are defined as follows: S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }. find the size of the largest set S[K] for this array. The function should return 0 if the array is empty. for [5,4,0,3,1,6,2] ans is 4.

asked 23 Feb '17, 18:03

arpit728's gravatar image

2★arpit728
6831462
accept rate: 10%


I need more details on the question. Whats the time complexity? The constraints? Is it necessary to have an efficient algo or even a brute force will do?

I think the algo steps are simple in 'naïve approach'

  1. Run a Loop from 0 to n-1, with arr[I] begin the element under inspection
  2. now that we have chosen arr[I], we increment answer by 1. Now in another loop (preferable while loop), we check if arr[I] is more than n-1. If its not, then we increment answer by 1 and I = arr[I], else we stop checking and note the value of answer.
  3. Once the while loop ends (i.e. we get a value more than n-1 i.e. out of index) we note it (value of variable ans, which is nothing but how many times did the while loop run) and compare it with maximum value achieved till now. If ans>max, then max = ans.
  4. We set answer to 0 again and iterate similarly through all elements.

This algo will pass ~60-80% of test cases.

WATCH OUT! CORNER CASES

  1. The first corner case is like array = {1,0,3,4}. Here, if we start from index 0, it sends us to 1st index, and if we goto 1st index, it sends us BACK TO 0TH index. This results in infinite loop. We must maintain a check of what indexes we visited. For this, I would make a bool array and set it to true at start of loop. After visiting the index, would change its value to false and use if and break statements to terminate the while loop in case it sends us back to a visited element. Eg, in above, we would set bool[0]=false , then goto index 1. We set bool[1] = false, do the stuff, and when it sends us back to index 0, we find bool[0] is false and hence the while loop stops.

I cant comment more on corner cases due to lack of constraints, but yeah, this is what I feel the naïve solution is. I suspect dp is involved in this Q in some way or the other, but I am no expert in dp so I wont comment.

Get back to me with constraints, like number of queries per test case, range of valued, time limit, any TLE problem etc.

link

answered 23 Feb '17, 18:43

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

edited 23 Feb '17, 19:29

@vijju123 is right, you have to provide the full question or link with relevant constraint and right explanation.

link

answered 23 Feb '17, 19:10

bansal1232's gravatar image

5★bansal1232
2.8k1418
accept rate: 16%

provide full question or link .

link

answered 23 Feb '17, 19:31

raghu3489's gravatar image

0★raghu3489
1
accept rate: 0%

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,642
×833
×228

question asked: 23 Feb '17, 18:03

question was seen: 519 times

last updated: 23 Feb '17, 19:31