ZIO solution help

How to solve Q.no 3 and Q.no 4 of ZIO-2017 ,
Please provide me descriptive solution,
with one of the test cases as example.

Link:- https://www.iarcs.org.in/inoi/2017/zio2017/zio2017-question-paper.pdf

I couldnt solve the c part of the ZIO 2017 , P3
Anybody who solved that pls help

Thanks
Sudheera Y S

1 Like

What you wanna do for P3 is to choose the lowest h value person at every step

Yes
For a and b subtask we can write down the whole array everytime as the number of operations we have to do is very less
But for the c subtask , we cant write so many steps so we have to find some pattern here or something
How to do that ?

Thanks a lot!
Sudheera Y S

One lemma you’d wanna use is the number of steps to reduce N equal numbers. Write a couple examples and see how an array of equal numbers reduces. Then use that in part c

Alright
I goit it

So i did that and i found a pattern ,
If there are N copies of x …

To make all of them 0 , we need

x+2 if N <= x
x+1 if N > x

So in the c part , we decrease the value of each and every one by 130 , to make it 0 we need 132 steps and then we are left with minimum number 0 and maximum number 10 so we can make all of them 0 in 10 steps
So the total number of steps is

132 + 10 = 142 and the answer is 145 ?!?

Where am I wrong ?
@imyourayush @druh

Thanks a lot !

What about Q.no 4

Um you don’t need to explicitly find a formula. See what happens when you have N equal numbers of value x and wanna reduce them to value x-N+1 etc

Also your formula doesn’t seem right. What if x = 0 and N = 14?

First let all children with low H[i] seek until everyone needs an equal number of hide turns. In (b) that was (3,2,2,1,0,0,…), so they all needed 1 more hide turn. From then on just distribute the seeks evenly until you are done

1 Like

The algorithm gives the following configuration of seekers:

(9,5,10,2,8,0,3,7,9,3,2,8,5,4,6)+(5,5,5,5,4,4,4,…)=(14,10,15,7,12,4,7,11,13,7,6,12,9,8,10)

which means they hid the following number of times:

(131,135,130,138,133,141,138,134,132,138,139,133,136,137,135)

can some one explain me Q.no 4 with taking one of the test case as an example

What is this ?

How did you get this ?

Sorry , I dont understand :sob::sob:

Thanks a lot !