# PROBLEM LINK:

Contest

**Author:** Akshay Padte

**Tester:** Rushang Gajjal

**Editorialist:** Rushang Gajjal

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

String manipulation

# PROBLEM:

Given a music sequence and malicious sequence, the integral multiples of the malicious sequence present in the music sequence have to be removed and the number of such sequences removed has to be printed.

**Note** : An Integral Multiple of a malicious sequence is obtained by multiplying the amplitudes of each tone by the same integer leaving the frequencies i.e. letters are left unchanged.

# EXPLANATION:

We can separate the music and the malicious sequences into amplitudes and frequencies arrays.

**n** : Length of music sequence

**m** : Length of malicious sequence

**freq** : Frequency Array for music sequence

**amp** : Amplitude Array for music sequence

**freqm** : Frequency Array for malicious sequence

**ampm** : Amplitude Array for malicious sequence

The amplitudes are present at odd positions and the frequecies are present at even positions.We iterate from **1 to 2n** to input the entire sequence because there are n tones and each tone has a frequency and amplitude.

```
for i from 1 to 2*n:
if i%2=0:
amp.append(input())
else:
freq.append(input())
```

Similarly input the malicious sequence in **freqm** and **ampm**.

We have to perform an algorithm similar to string matching.
First Iterate over the entire music sequence and maliciuos sequence and find the part of the music sequence which has the same frequencies in the same order as malicious sequence.

```
for i from 1 to len(amps)-m:
for j from 1 to m:
if(freq[i+j]!=freqm[j]):
break
```

We iterate till **len(amps)-m** because we have to match sequence of size **m**.Now if the for loop runs without break for a certain pair of **i** and **j** we have to check whether the amplitudes of the matched sequences are same or integral multiples of each other. If all conditions are satisfied count is incremented.

```
ratio = 0
for j from 1 to m:
if amp[i+j]%ampm[j]!=0:
break
if j==0:
ratio = amp[i+j]/ampm[j]
else:
if(amp[i+j]/ampm[j]!=ratio):
break
else:
count++
```

In the above code first we initialize the value of ratio to the ratio of amplitudes of the **i**-th tone of music sequence and **1-st** tone of malicious sequence.Then check whether the ratios of the following amplitudes of the tones are same as **ratio**.If the entire malicious sequence is iterated satisfying the ratios of amplitudes, increment the **count** variable.

# Time Complexity:

**O(n*m)** per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

asked
**09 Sep '18, 13:57**

4★rusherrg

1●3

accept rate:
0%