[SOLVED] Csc3100  programming assignment 2 1 queue (40% of this assignment) 1.1 description given an n-length list, the value ai

1.1 Description
Given an n-length list, the value ai
in the list satisfies that ai ∈ {1, …, n} and i = 1, …, n. Then,
numbering each element ai
in the list as bi
, bi = i.

Please find the minimum number of elements that should be deleted so that the list of remaining
elements has the same elements as the list of their corresponding numbers.

For example, given a list A = {2, 1, 2, 2, 4}, and its number list N = {1, 2, 3, 4, 5}. We need to delete
the 3-rd and 5-th elements from lists A and N because numbers 3 and 5 are not in the list A. Then, the
list A = {2, 1, 2} and its number N = {1, 2, 4}. However, since 4 is not in the list A, we need to delete
the 3-rd element from lists A and N. Finally, we get the list A = {2, 1} and its number list N = {1, 2},
where the list A = {2, 1} has the same elements as its number list N = {1, 2}. Conclusively, we delete
3 elements from the list A.

1.2 Input
• The first line contains a positive integer n.
• The second line contains the n-length list.
1.3 Output
• The minimum number of deleted elements.
Sample Input 1
5
2 1 2 2 4
Sample Output 1
3
Sample Input 2
5
1 3 4 2 5
Sample Output 2
0
For a list A = {1, 3, 4, 2, 5}, its number list is N = {1, 2, 3, 4, 5}. We do not need to delete any element
from lists A and N since the list A has the same elements as its number list N.
4
Sample Input 3
See attached sample . in
Sample Output 3
See attached sample . out

Problem Scale & Subtasks
For 100% of the test cases, 1 ≤ n ≤ 2 ∗ 105
.
Test Case No. Constraints
1-6 n ≤ 10
7-8 n ≤ 100
9-10 n ≤ 2 ∗ 105
Hint
Hint1 : You can use a queue to store elements that are not in a given list but are in its list of numbers.

2.1 Description
John is learning a new programming language called A++. Having just mastered loops, he is excitedly
writing many programs that contain only loop structures. However, he does not know how to compute
the time complexity of his programs. So he turns to you for help. What you need to do is to write a
program to calculate the time complexity for each program that John writes.

The loop structure in A++ is as follows:
F i x y
… // code block to be executed
E
Here ”F i x y” indicates creating a variable i initialized as x, then compare i with y, and enter the
loop if and only if i is smaller or equal to y. Each time the execution of the code block inside the loop
ends, i will be changed to i + 1. Then i will be compared with y to determine whether to enter the
loop again. The loop ends when i becomes larger than y.

Both x and y can be positive integers or the variable n. n represents the size of the data and must
be retained during time complexity calculations. It cannot be treated as a constant. The value of n is
much greater than 100. x is guaranteed to be smaller or equal to y.

”E” indicates the end of the loop. When the loop ends, any variables created within that loop are also
destroyed.
Note: For the sake of convenience in writing, the uppercase letter O is used to represent the standard
notion of Θ when describing time complexity in this problem.

2.2 Input
The first line contains a positive integer t, indicating that John writes t (1 ≤ t ≤ 10) programs in total
(the programs contain only loop structures). Note that the loop structures are allowed to be nested.
The following lines describe the t programs in order.

For each program, the first line contains a positive integer L (1 ≤ L ≤ 20000), indicating the number
of lines in this program. The next L lines describe the program in detail: each line is either in the form
of ”F i x y” or ”E”, where i is a lowercase letter (it is guaranteed that i will not be letter ”n”), x and

y are either variable n or positive integers smaller than 100, and x is guaranteed to be smaller or equal
to y. Since John has mastered loops quite well, there will be no syntax errors in his programs. i.e. F
and E are guaranteed to match each other and he will not use variables that haven’t been destroyed
in a loop.

2.3 Output
Output t lines, each indicating the time complexity of a program, in the order of the input. In this
problem, time complexity is either in the form of O(1) or O(nˆw), where w is a positive integer smaller
than 20000. O(1) means constant time complexity and O(nˆw) means that the time complexity is
O(n
w)
Sample Input 1
6
2
F i 1 1
E
2
F x 1 n
E
4
F x 5 n
F y 10 n
E
E
4
F x 9 n
E
F y 2 n
E
4
F x 9 n
F y n n
E
E
4
F y 1 99
F x n n
E
E
Sample Output 1
O (1)
O(n ^1)
O(n ^2)
O(n ^1)
O(n ^1)
O (1)

Problem Scale & Subtasks
Test Case No. Constraints Properties
1-3 L ≤ 10 A
4-6 L ≤ 500
7-10 L ≤ 20000
A: For each program, the first L/2 lines are in the form of ”F i x y”, and the lines from L/2 + 1 to L
are in the form of ”E”.