CodeChef Starters 157 Solutions

CodeChef Starters 157 Solutions –

Glass Prices

Chef is buying spectacles, and is now deciding on which frame to purchase.

Chef has narrowed his options down to two choices: a plastic frame that costs $X$ rupees, and a metal frame that costs $Y$ rupees.

Chef will buy the metal frame if and only if it costs at most twice the price of the plastic frame – otherwise he will buy the plastic frame.

Can you decide which frame Chef will buy?

Input Format

The first and only line of input will contain two integers $X$ and $Y$ – the price of the plastic frame and the metal frame, respectively.

Output Format

For each test case, output on a new line the answer: the type of frame Chef will purchase.
This is either the string "PLASTIC" or the string "METAL" (without quotes) depending on the outcome.

Each letter of the output may be printed in either uppercase or lowercase – for example, the strings METAL, MeTaL, metal, and mEtAL will all be treated as equivalent.

Constraints

$1 \leq X \leq 2000$
$1 \leq Y \leq 2000$

Sample 1:

Input 499 999

Output PLASTIC

Explanation:

The plastic frame costs $499$ rupees, and the metal one costs $999$ rupees.

$2 \times 499 = 998$ is less than $999$ , so Chef will prefer the plastic frame.

Sample 2:

Input 499 998

Output METAL

Explanation:

The plastic frame costs $499$ rupees, and the metal one costs $998$ rupees.

$2 \times 499 = 998$ is equal to $998$ , so Chef will prefer the metal frame.

Sample 3:

Input 698 1099

Output METAL

Explanation:

The plastic frame costs $698$ rupees, and the metal one costs $1099$ rupees.

$2 \times 698 = 1396$ is greater than $1099$ , so Chef will prefer the metal frame.

Solution in C

#include <stdio.h>

int main() {

int X, Y;

scanf(“%d %d”, &X, &Y);

if (Y <= 2 * X) {

printf(“METAL\n”);

} else {

printf(“PLASTIC\n”);

}

return 0;

}

Non-matching Name

Alice and Bob invented a brand-new algorithm – but they can’t decide what to name it!

Alice suggested the name $S_{A}$ , and Bob suggested the name $S_{B}$ . ( $S_{A}$ and $S_{B}$ are both strings of lowercase English letters.)

However, Alice thinks Bob’s naming sense is really bad – she’ll only be happy if the name given to the algorithm is not close to $S_{B}$ at all.
More specifically, Alice will be happy if and only if the algorithm’s name does not share any characters with $S_{B}$ .

Similarly, Bob thinks Alice’s naming sense is really bad, and will only be happy if the algorithm’s name doesn’t share any characters with $S_{A}$ .

Is there a way to name the algorithm (using only lowercase English letters) so that both Alice and Bob are happy?

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of three lines of input.
- The first line of each test case contains two space-separated integers $N$ and $M$ — the length of $S_{A}$ and the length of $S_{B}$ , respectively.
- The second line contains the string $S_{A}$ .
- The third line contains the string $S_{B}$ .

Output Format

For each test case, output on a new line the answer: "YES" if a valid name exists for the algorithm, and "NO" otherwise.

Each letter of the output may be printed in either uppercase or lowercase, i.e, the strings NO, No, nO, and no will all be treated as equivalent.

Constraints

$1 \leq T \leq 1000$
$1 \leq N \leq 50$
$1 \leq M \leq 50$
$S_{A}$ and $S_{B}$ contain only lowercase English letters, i.e, the characters 'a' through 'z'.

Sample 1:

Input

Output

3
8 7
dijkstra
blossom
24 19
fastquicklazypropagation
westmajixhoverboard
34 45
supercalifragilisticexpialidocious
pneumonoultramicroscopicsilicovolcanoconiosis

Yes
No
Yes

Explanation:

Test case $1$ : We have $S_{A} = dijkstra$ and $S_{B} = blossom$ .
They can name the algorithm $queen$ for example – you may verify that it shares no characters with both $S_{A}$ and $S_{B}$ .
Many other names are possible too – some examples are $puff, yen, new$ .

Test case $2$ : It can be shown that no matter what the algorithm is named, either Alice or Bob will be unhappy.

Test case $3$ : One valid name for the algorithm is $zzz$ .

Solution in C++

#include <bits/stdc++.h>

using namespace std;

void solve() {

int t;

cin >> t;

while (t–) {

int n,m;

cin >> n >>m ;

string s1, s2;

cin >> s1 >> s2;

int arr1[26] = {0};

int arr2[26] = {0};

for (auto ch : s1) {

arr1[ch – ‘a’] = 1;

}

for (auto ch : s2) {

arr2[ch – ‘a’] = 1;

}

bool hasCommon = false;

for (int i = 0; i < 26; ++i) {

if (arr1[i] == 0 && arr2[i] == 0) {

hasCommon = true;

break;

}

if (hasCommon) {

cout << “YES” << endl;

} else {

cout << “NO” << endl;

}

int main() {

solve();

return 0;

}

Not-too-far Replacement

You are given an array $A$ of length $N + 1$ , denoted $[A_{1}, A_{2}, \dots, A_{N + 1}]$ .

You can perform the following operation on the array $A$ :

Choose an index $i$ ( $1 \leq i \leq N$ ) such that $A_{i} \leq 2 \cdot A_{N + 1}$ .
Then, swap the values of $A_{i}$ and $A_{N + 1}$ .

That is, you can swap the element at index $N + 1$ with some element of the array that’s at most twice as large as it.

You may perform this operation as many times as you like (even zero times).
Find the minimum possible sum of the first $N$ elements of $A$ after the operations, i.e, the minimum possible value of

A_{1} + A_{2} + \dots + A_{N}

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of each test case contains a single integer $N$ — meaning the length of the array is $N + 1$ .
- The second line contains $N + 1$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}, A_{N + 1}$ , the initial values of the array.

Output Format

For each test case, output on a new line the minimum possible sum of $A$ after performing some replacement operations.

Constraints

$1 \leq T \leq 200$
$1 \leq N \leq 200$
$1 \leq A_{i} \leq 1000$

Sample 1:

Input

Output

4
4
5 2 1 2 3
3
3 10 30 1
4
16 4 8 2 1
4
20 100 30 49 15

Explanation:

Test case $1$ : Initially, $A = [5, 2, 1, 2, 3]$ .
Perform one operation with $i = 1$ , which is allowed since $5 = A_{1} \leq 2 \cdot A_{N + 1} = 6$ .
After the swap, $A = [3, 2, 1, 2, 5]$ .

The sum of the first $N$ elements is $8$ , which is the minimum possible.

Test case $2$ : Initially, $A = [3, 10, 30, 1]$ . $A_{N + 1}$ cannot be swapped with anything since it’s too small. So, the answer is just the sum of the first $N$ elements, which is $3 + 10 + 30 = 43$ .

Test case $3$ : Initially, $A = [16, 4, 8, 2, 1]$ . Consider the following sequence of operations:

Choose $i = 4$ , which is valid since $2 \leq 2 \cdot 1$ . Now, $A = [16, 4, 8, 1, 2]$ .
Choose $i = 2$ , which is valid since $4 \leq 2 \cdot 2$ . Now, $A = [16, 2, 8, 1, 4]$ .
Choose $i = 3$ , which is valid since $8 \leq 2 \cdot 4$ . Now, $A = [16, 2, 4, 1, 8]$ .
Choose $i = 1$ , which is valid since $16 \leq 2 \cdot 8$ . Now, $A = [8, 2, 4, 1, 16]$ .

The sum of the first $N$ elements is $15$ which is the best we can do.

Small, Smaller, Smallest

You are given a binary string $S$ of length $N$ .
You can perform the following two-step operation on it:

Choose a non-empty contiguous substring of $S$ .
If the substring contains an odd number of ones, delete every $0$ in it.
If it instead contains an even number of ones, delete every $1$ in it.

For example, suppose $S = 1010001$ ,

If you choose the substring $101$ from indices $1$ to $3$ , it has two ones, which is an even number.
So, delete every $1$ in the substring, turning the string into $S = 00001$ .
If you instead choose the substring $1000$ from indices $3$ to $6$ , the number of ones is $1$ , which is odd.
So, you’d delete every $0$ in the substring, turning the string into $S = 1011$ .

You can perform this two-step operation as many times as you like.
Find the minimum possible length of the final string.

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of each test case contains a single integer $N$ — the length of the binary string.
- The second line contains the binary string $S$ of length $N$ .

Output Format

For each test case, output on a new line the minimum possible length of $S$ after performing several operations.

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 3 \cdot 1 0^{5}$
$S_{i} \in {0, 1}$
The sum of $N$ over all test cases won’t exceed $3 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

0
1
1

Explanation:

Test case $1$ : Choose the substring $11$ , which is the entire string.
It has two ones, which is even – so we delete every occurrence of $1$ . The string becomes empty.

Test case $2$ : One optimal sequence of operations is as follows:

Choose the substring $10$ from index $2$ to index $3$ . It has one $1$ , which is an odd number – so every occurrence of $0$ gets deleted. The string is now $01$ .
Choose the entire string, which is $01$ . The $0$ gets deleted again, making the string $1$ .

This is optimal.

Normal is Good (Easy)

This is the easy version of the problem. The only difference is the constraint on $A_{i}$ — in this version, $1 \leq A_{i} \leq 2$ .

An array $B$ of length $M$ is said to normal if its mean equals its median.

The mean of $B$ is defined to be

M B ^{1} + B ^{2} + \dots + B ^{M}

For example, the mean of $[1, 2]$ is $2 3 = 1.5$ , and the mean of $[2, 2, 3, 1, 3]$ is $5 11 = 2.2$ .

The median of $B$ is defined to be the element at index $⌈ 2 M ⌉$ when the elements of $B$ are sorted in ascending order.
That is, the median of an odd-length array is the middle element after sorting, and the median of an even-length array is the left of the two middle elements after sorting.

For example, the median of $[2, 1, 2]$ is $2$ (sorted order is $[1, 2, 2]$ ), and the median of $[3, 1, 2, 2, 1, 1]$ is $1$ (sorted order is $[1, 1, 1, 2, 2, 3]$ , take the left of the two middle elements which is $1$ .)

You’re given an array $A$ containing $N$ integers, each of which lies between $1$ and $2$ .
Count the number of contiguous subarrays of $A$ that are normal.

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of each test case contains a single integer $N$ — the length of the array $A$ .
- The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

For each test case, output on a new line the number of normal subarrays of $A$ .

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 3 \cdot 1 0^{5}$
$1 \leq A_{i} \leq 2$
The sum of $N$ over all test cases won’t exceed $3 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

6
4
7

Explanation:

Test case $1$ : Every subarray contains only twos, so the mean and median are always $2$ .
Every subarray is normal, so the answer is the count of subarrays, which is $6$ .

Test case $2$ : The only normal subarrays are those with length $1$ .

Unmedian

You are given an array $A$ of length $N$ .

You can perform the following operation on it:

Choose any contiguous subarray of $A$ such that its length is greater than $1$ and odd.
Then, delete the median $^{†}$ of this subarray from it.
If there are multiple occurrences of the median within the subarray, delete the leftmost one.

Note that the length of the array decreases by $1$ after the operation.

For example, if the array is $A = [1, 3, 1, 4, 1, 5]$ and you choose the subarray $[1, 4, 1]$ from indices $3$ to $5$ , the median is $1$ .
The leftmost occurrence of $1$ within the subarray is at index $3$ , so it will be deleted and the array becomes $[1, 3, 4, 1, 5]$ .

Is it possible to perform this operation several times (possibly, zero) so that the final array $A$ is sorted in non-descending order?
If it is possible, also find any valid sequence of operations.

Note that you do not need to minimize the number of operations: you only need to find any valid sequence.

$^{†}$ The median of an odd-length array is the middle element when the array is written in sorted order.
For example, if $A = [3, 1, 4, 1, 5]$ , the median is $3$ since the sorted array is $[1, 1, 3, 4, 5]$ .

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of input contains a single integer $N$ , the length of the array $A$ .
- The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

For each test case,

If it is not possible to obtain a sorted array no matter what, print a single line containing the integer $- 1$ .
Otherwise,
- First, print a single line containing one integer $K$ : the number of operations you wish to perform.
- The next $K$ lines should describe the operations you perform.
  On the $i$ -th of these $K$ lines, print two space-separated integers $L_{i}$ and $R_{i}$ , meaning that the operation is performed on the subarray $[A_{L i}, A_{L i + 1}, \dots, A_{R i}]$ of the current array $A$ .

These integers should satisfy $1 \leq L_{i} < R_{i} \leq N - i + 1$ , and also $R_{i} - L_{i} + 1$ should be odd.

Constraints

$1 \leq T \leq 5000$
$3 \leq N \leq 5000$
$1 \leq A_{i} \leq 1 0^{9}$
The sum of $N$ over all test cases won’t exceed $5000$ .

Sample 1:

Input

Output

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

Explanation:

Test case $1$ : Consider the following sequence of operations:

Choose the subarray $[4, 1, 4]$ , from indices $2$ to $4$ . The median is $4$ , deleting its leftmost occurrence results in $A = [3, 1, 4, 5]$ .
Choose the subarray $[3, 1, 4]$ from indices $1$ to $3$ . The median is $3$ , deleting it results in
$A = [1, 4, 5]$ which is sorted.

Test case $2$ : $A$ cannot be sorted by performing the given operation.

Normal is Good

An array $B$ of length $M$ is said to normal if its mean equals its median.

The mean of $B$ is defined to be

M B ^{1} + B ^{2} + \dots + B ^{M}

For example, the mean of $[1, 2]$ is $2 3 = 1.5$ , and the mean of $[2, 2, 3, 1, 3]$ is $5 11 = 2.2$ .

You’re given an array $A$ containing $N$ integers, each of which lies between $1$ and $3$ .
Count the number of contiguous subarrays of $A$ that are normal.

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of each test case contains a single integer $N$ — the length of the array $A$ .
- The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

For each test case, output on a new line the number of normal subarrays of $A$ .

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 3 \cdot 1 0^{5}$
$1 \leq A_{i} \leq 3$
The sum of $N$ over all test cases won’t exceed $3 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

4
4
8

Explanation:

Test case $1$ : Looking at every subarray of $A$ :

$[3]$ has both mean and median $3$ , so it is normal.
$[1]$ has both mean and median $1$ , so it is normal.
$[2]$ has both mean and median $2$ , so it is normal.
$[3, 1]$ has mean $2$ and median $1$ , so it is not normal.
$[1, 2]$ has mean $1.5$ and median $1$ , so it is not normal.
$[3, 1, 2]$ has mean and median both equal to $2$ , so it is normal.

Test case $2$ : The only normal subarrays are those with length $1$ .

MEXtreme Divisibility

The div-MEX of an array is defined to be the smallest positive integer that doesn’t divide any element of the array.
For example, the div-MEX of $[4, 10, 1, 9, 21]$ is $6$ , because every integer from $1$ to $5$ divides at least one element of the array, but $6$ doesn’t divide any of them.

You’re given an array $A$ of length $N$ , and an integer $M$ . The elements of $A$ all lie between $1$ and $M$ .

At most once, you can choose an index $i$ ( $1 \leq i \leq N$ ) and an integer $x$ ( $1 \leq x \leq M$ ), and replace $A_{i}$ with $x$ .

Find the maximum possible div-MEX of the final array $A$ .

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of two lines of input.
- The first line of each test case contains two space-separated integers $N$ and $M$ — the length of the array and the maximum allowed value, respectively.
- The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ — the elements of array $A$ .

Output Format

For each test case, output on a new line the maximum possible div-MEX of array $A$ after making at most one replacement.

Constraints

$1 \leq T \leq 2 \cdot 1 0^{5}$
$1 \leq N, M \leq 5 \cdot 1 0^{5}$
$1 \leq A_{i} \leq M$
The sum of $N$ and the sum of $M$ over all test cases both won’t exceed $5 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

4
4 1
1 1 1 1
5 5
1 3 4 2 2
4 5
2 1 5 2
7 20
15 20 13 2 17 20 12

Explanation:

Test case $1$ : Since $M = 1$ , all the elements of $A$ must be $1$ no matter what.
The div-MEX is thus $2$ .

Test case $2$ : Replace $A_{4} = 2$ with $5$ , to obtain the array $[1, 3, 4, 5, 2]$ .
Every number from $1$ to $5$ is present in $A$ , while $6$ doesn’t divide anything in $A$ .

Test case $3$ : Replace $A_{2} = 1$ with $3$ , to obtain $[2, 3, 5, 2]$ .
$1, 2, 3$ all have multiples in the array, but $4$ does not.
This is optimal.

Saturated Subarrays

For an array $B$ of length $M$ , let $f (B)$ denote its maximum subarray sum.
Note that in this problem, the empty subarray with a sum of $0$ is considered to be a subarray of $B$ .

We say the array $B$ is saturated if $f (B) = \sum_{i = 1 M} B_{i}$ , that is, if the maximum subarray sum of $B$ equals the sum of $B$ .

You’re given an array $A$ of length $N$ . Answer $Q$ queries on it of the following form:

Given $L$ and $R$ ( $1 \leq L \leq R \leq N$ ), count the number of pairs $(l, r)$ such that:
- $L \leq l \leq r \leq R$ , and
- The array $[A_{l}, A_{l + 1}, \dots, A_{r}]$ is saturated.

That is, given $L$ and $R$ , count the number of saturated subarrays of the array $[A_{L}, A_{L + 1}, \dots, A_{R}]$ .

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers $N$ and $Q$ — the length of $A$ and the number of queries, respectively.
- The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .
- The next $Q$ lines describe the queries. The $i$ -th of these lines contains space-separated integers $L_{i}$ and $R_{i}$ , denoting the bounds for the $i$ -th query.

Output Format

For each query, output the answer on a new line.

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N, Q \leq 2 \cdot 1 0^{5}$
$- 1 0^{9} \leq A_{i} \leq 1 0^{9}$
The sum of $N$ and the sum of $Q$ over all test cases both won’t exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

2
4 3
17 -15 3 18
2 3
1 4
2 4
10 3
8 5 7 20 -18 12 -13 -3 -6 -16
5 7
3 8
1 10

Explanation:

Test case $1$ : Let’s go over all the queries.

Query $1$ : The subarray is $[- 15, 3]$ . The only saturated subarray is $[3]$ .
Query $2$ : The subarray is $[17, - 15, 3, 18]$ . The saturated subarrays are:
- $[17]$
- $[3]$
- $[18]$
- $[3, 18]$
- $[17, - 15, 3, 18]$
Query $3$ : The subarray is $[- 15, 3, 18]$ . the saturated subarrays are the same as the previous query, but excluding $[17]$ and the full array.

CodeChef Starters 157 Solutions