Help for Solving ZIO 2014 Question Paper

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.

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

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.

Wait can we write programs in zio?

no we can’t

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

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?

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

Can you explain your approach

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

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

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.

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

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

How to do it using greedy?

Group the words with same starting words and optimize them further

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

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

1 Like

i have only solved a subtask

What was the logic, could you please explain?

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