Help for Solving ZIO 2014 Question Paper

help
, , ,
1

Link to 2014 ZIO Question Paper:- https://www.iarcs.org.in/inoi/2014/zio2014/zio2014-qpaper.pdf

I have been trying hard but could only solve question 2 completely. I would be grateful if you could give your insights and ways to solve the rest of the question. Link to any tutorial for the required algorithms is equally appreciated.

2

Draw a trie for p1 and count number of nodes in trie

3

In the 3rd Question, Basic recursion could do the job. For reference search for “N Queen Problem”, go for the algo which is solved for the total number of possible positions of queens.

Basic insights:

  1. Make a isValid() to check the scope of adjacent indexes you will be visiting.
  2. In each recursive call pass the current length of password obtained.
  3. Base case will be when CurrLength == GivenLength , Increment the count in this If-statement and include return statement.
4

Wait can we write programs in zio?

5

no we can’t

6

Hello @utkarsh1729 ,

To solve the q3 , we need to find something interesting here , i.e

The number of passwords starting with 2 and having length k is equal to number of passwords starting with 4 and having length k is equal to the number of passwords starting with 6 and having length k is equal to the number of passwords starting with 8 and having length k

The number of passwords starting with 1 and having length k is equal to number of passwords starting with 3 and having length k is equal to the number of passwords starting with 7 and having length k is equal to the number of passwords starting with 9 and having length k

Having this , you can continue to get the answer
Hope you understood

7

How should we approach ZIO problems? Is there any general rule or method to come up with the appropriate strategy to solve the question in the given time? What topics or algorithms should be focused on?

8

Greedy method , dynamic programming , graphs , combinatorics , brute force are the main topics in zio

9

Can you explain your approach

10

Can you suggest some sources that contain easy-to-understand-and-implement tutorials on dynamic programming and combinatorics?

11

Are you sure it is answer for the first question of zio 2014 question paper ?

12

Yeah not exactly but making the trie is the first step. Then you can define states for each node. Btw I leave out the operations for printing the word as it’s easier to add these ops in the end.

Dp(node, 0) = min number of moves to traverse this subtree and come back to this node.

Dp(node, 1) = min number of moves to traverse this subtree completely.

Try to get the transitions. Also this isn’t the normal dfs traversal. Rather it’s moving along the path. And then retracing back - like that.

13

It can be solved easily using greedy method
But this dp method is good

Thanks a lot ! ( will see how to do it ) @anon95832944

14

How to do it using greedy?

15

Group the words with same starting words and optimize them further

16

It’s actually 2*(nodes in the trie) + number of words - length of the longest word

17

Yeah, thats how I did the first question in the paper. Can anyone tell me how to do the 4th question?

1 Like
18

i have only solved a subtask

19

What was the logic, could you please explain?

20

You just have to avoid overcount and you will get the answer