Algorithmic problem

[Mhd45]

John and Alex like to watch cars passing by on the street. When the car drives past, both boys write down the types of cars in their notebooks. John is older and can write down all the cars flawlessly. Alex is younger and may not notice some cars. So, in Alex's list, some cars may be left out. The boys analyze their records and ponder which cars Alex might have noted and which he sure couldn't.

Input: The first line of input contains three integers n, m and k (1 ≤ n, m, k ≤ 300,000), denoting successively the length of the John list (equal to the number of cars), the length of the Alex's list, and the number of different types of cars. In the second line there is a sequence of length n composed of integers from the interval [1, k], denoting more types of cars on John's list. In the third line there is a sequence of length m in the same format - Alex's list. You can assume that Alex may have omitted some of the cars from John's list, but didn't add anything "extra". In other words, the input data is chosen such that it is possible to erase a certain number of cars (possibly zero) from the list John and get Alex's list.

Output: The output should contain n integers separated by single spaces: the i-th of these numbers shall be equal to 1 if the i-th car could have been noted by Alex, or 0 if it certainly could not be noted down

Example1:

12 6 6

6 1 1 3 3 6 2 5 4 1 1 3

6 1 1 3 2 5

1 1 1 1 1 0 1 1 0 0 0 0 # Answer/Output

Example2:

16 9 4

1 1 1 4 3 1 1 2 4 1 1 2 2 1 3 1

1 1 1 4 1 2 2 1 3

1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 # Answer/Output


Can you help me write code for that problem?

[Yoriz]

Thank you for posting your homework question.

Homework and No Effort Questions

This forum is focused on education. It exists to help people learn Python. We don’t exist to solve others’ problems, although that tends to be a happy byproduct of education. You should keep this in mind when writing replies.

Learning is most effective when the learner is making mental effort (see Make It Stick by Mark A. McDaniel and Peter C. Brown or this Youtube video for more about this). Since we are focused on education (learning) it is essential to make sure that the question asker has made some reasonable effort. This pertains to every question asked on the forum, not just homework questions. Ideally, they provide a “Minimal, Reproducible Example” to quote Stackoverflow. It’s reasonable to point them toward that or other links (e.g. Lifehack or catb) which talk about how to ask questions well.

Please read the full details from the link above, also see the links in my signature for details of what to post and how to post code.

[deanhystad]

The first thing you need to do is solve the problem. With pencil and paper write out John and Alex's observations and a list of zeros as long as John's list.

Output:
Alex   : 6 1 1 3 2 5
John   : 6 1 1 3 3 6 2 5 4 1 1 3
Match? : 0 0 0 0 0 0 0 0 0 0 0 0

Now fill out all the blanks if a car in Alex's list could match the corresponding car in John's list. This is of course the tricky part. Both John and Alex have a single "5" in their list, that has to be a match.

Output:
Alex   : 6 1 1 3 2 5
John   : 6 1 1 3 3 6 2 5 4 1 1 3
Match? : 0 0 0 0 0 0 0 1 0 0 0 0

Both lists start with a 6, so that is probably a match.

Output:
Alex   : 6 1 1 3 2 5
John   : 6 1 1 3 3 6 2 5 4 1 1 3
Match? : 1 0 0 0 0 0 0 1 0 0 0 0

I also see that both lists have a single 2, so that has to be a match.

Output:
Alex   : 6 1 1 3 2 5
John   : 6 1 1 3 3 6 2 5 4 1 1 3
Match? : 1 0 0 0 0 0 1 1 0 0 0 0

And both lists also have two 1's

Output:
Alex   : 6 1 1 3 2 5
John   : 6 1 1 3 3 6 2 5 4 1 1 3
Match? : 1 1 1 0 0 0 1 1 0 0 0 0

From Alex's list we have not matched anything to 3
In John's list we have not matched anything to _ _ _ 3 3 6 _ _ 4 1 1 3

Alex doesn't have a 4 in his list, so we know there is no match to the 4 in John's list. That will be a 0 in Match? But what about the 3 3 6 1 1 3 that are currently unmatched, but are cars that appear in Alex's list? Which of those could be matches?

You work on the problem until you have a process you can describe as a sequence of steps. Test your process against both test cases. Write down you process and have somebody else apply it to the test case. If the process can be successfully applied by you and others, it is likely defined well enough to be an algorithm; a series of well defined steps that can be applied to finding the solution to a particular problem.

Once the algorithm is defined, translate to Python. This last step is usually the easiest. If you have a hard time translating your algorithm to Python it might be that some of the steps are not all that well defined. Intuition and flashes of insight are difficult to program. Re-evaluate your algorithm looking for steps that can be simplified. Repeat the translation process. You might have to loop through this cycle of coding/re-evaluating multiple times.

[deanhystad]

This is a fun problem. I ended up with a recursive solution. I modified the Alex list for brevity

Find where Alex[0] matches John

Output:
 John 6 1 1 3 3 6 2 5 4 1 1 3
      |
Alex  6 3 2 5
Match 1 0 0 0 0 0 0 0 0 0 0 0

Now find the first match for Alex[1:] and John[1:]

Output:
 John 1 1 3 3 6 2 5 4 1 1 3
          |
Alex      3 2 5
Match 1 0 0 1 0 0 0 0 0 0 0 0

And then find the first match for Alex[2:] and John[4:]

Output:
John  3 6 2 5 4 1 1 3
          |
Alex      2 5
Match 1 0 0 1 0 0 1 0 0 0 0 0

This is repeated until the Alex list is empty. When the Alex list is empty you unwind the recursion and find the next match.

The trickiest part is you cannot place a tick mark in the match list if the Alex list is not an ordered sub-list of the John list. In addition to an empty Alex list, this signals a break in the recursion.