Author Archives: admin

Finish the quote: “Never let the fear of striking out keep you from…”?

Finish the quote: “Never let the fear of striking out keep you from reaching for your dreams. No matter how many times you try and fail, never give up. You will eventually find success if you keep pushing forward and never give up.

Finish the quote: “Never let the fear of striking out keep you from…”?

Playing the game
Winning the trophy
Losing your cool
Skipping

The correct answer is Playing the game.

Finish the quote: “Never let the fear of striking out keep you from…”?

Yankees slugger George Herman “Babe” Ruth certainly had no fear of striking out: The “Sultan of Swat” hit a total of 714 home runs during his career, including 60 home runs in the 1927 season alone (not to mention 59 homers in 1921 and 54 in 1920). He was one of the first five players inducted into the Baseball Hall of Fame.

Also read: Shakespeare’s Polonius advised, “This above all: to thine own self” what?

Shakespeare’s Polonius advised, “This above all: to thine own self” what?

Leave a reply

Shakespeare’s Polonius advised, “This above all: to thine own self” what? – And it must follow, as the night the day, Thou canst not then be false to any man.

Shakespeare’s Polonius advised, “This above all: to thine own self” what?

Give the spoils
Be true
Return
Send a letter

The correct answer is Be true.

Shakespeare’s Polonius advised, “This above all: to thine own self” what?

William Shakespeare’s tragedy “Hamlet” was first printed in 1603 and performed at the Globe Theatre in London. This line comes from a scene in which the king’s adviser gives his son Laertes some well-meaning but long-winded council before his trip to Paris. In the end, both characters die at the hands of Hamlet, who decides to be true not to himself but to the vengeful demands of his father’s ghost.

Maximum Xor Sum solution codechef

Leave a reply

Maximum Xor Sum solution codechef – You are given arrays $A$ and $B$ with $N$ non-negative integers each.

Maximum Xor Sum solution codechef

An array $X$ of length $N$ is called good, if:

All elements of the array $X$ are non-negative;
$X_{1}$ $∣$ $X_{2}$ $∣$ $\dots$ $∣$ $X_{i} = A_{i}$ for all $(1 \leq i \leq N)$ ;
$X_{i}$ $&$ $X_{(i + 1)}$ $&$ $\dots$ $&$ $X_{N} = B_{i}$ for all $(1 \leq i \leq N)$ .

Find the maximum bitwise XOR of all elements over all good arrays $X$ .
More formally, find the maximum value of $X_{1} \oplus X_{2} \oplus \dots X_{N}$ , over all good arrays $X$ .
It is guaranteed that at least one such array $X$ exists.

Note that $∣, &,$ and $\oplus$ denote the bitwise or, and, and xor operations respectively.

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 one integer $N$ — the size of the array.
- The next line contains $N$ space-separated integers describing the elements of the array $A$ .
- The next line contains $N$ space-separated integers describing the elements of the array $B$ .

Maximum Xor Sum solution codechef

For each test case, output on a new line, the maximum bitwise XOR of all elements over all good arrays $X$ .

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$0 \leq A_{i} < 2^{30}$
$0 \leq B_{i} < 2^{30}$
It is guaranteed that at least one such array $X$ exists.
Sum of $N$ over all test cases is less than $3 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

1
3

Maximum Xor Sum solution codechef

Test case $1$ : An optimal good array is $X = [0, 3, 2]$ .

For $i = 1$ : $A_{1} = X_{1} = 0$ and $B_{1} = X_{1}$ $&$ $X_{2}$ $&$ $X_{3} = 0$ .
For $i = 2$ : $A_{2} = X_{1}$ $∣$ $X_{2} = 3$ and $B_{2} = X_{2}$ $&$ $X_{3} = 2$ .
For $i = 3$ : $A_{3} = X_{1}$ $∣$ $X_{2}$ $∣$ $X_{3} = 3$ and $B_{3} = X_{3} = 2$ .

The XOR of all elements of $X$ is $0 \oplus 3 \oplus 2 = 1$ . It can be proven that this is the maximum XOR value for any $X$ .

Test case $2$ : An optimal good array is $X = [2, 1]$ .

For $i = 1$ : $A_{1} = X_{1} = 2$ and $B_{1} = X_{1}$ $&$ $X_{2} = 0$ .
For $i = 2$ : $A_{2} = X_{1}$ $∣$ $X_{2} = 3$ and $B_{2} = X_{2} = 1$ .

The XOR of all elements of $X$ is $2 \oplus 1 = 3$ . It can be proven that this is the maximum XOR value for any $X$ .

Minimal Inversions solution codechef

Leave a reply

Minimal Inversions solution codechef – Initially, Chef had an array $A$ of length $N$ . Chef performs the following operation on $A$ at most once:

Select $L$ and $R$ such that $1 \leq L \leq R \leq N$ and set $A_{i} := A_{i} + 1$ for all $L \leq i \leq R$ .

Minimal Inversions solution codechef

Determine the maximum number of inversions Chef can decrease from the array $A$ by applying the operation at most once.
More formally, let the final array obtained after applying the operation at most once be $B$ . You need to determine the maximum value of $in v (A) - in v (B)$ (where $in v (X)$ denotes the number of inversions in array $X$ ).

Note: The number of inversions in an array $X$ is the number of pairs $(i, j)$ such that $1 \leq i < j \leq N$ and $X_{i} > X_{j}$ .

Input Format

The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first line of each test case contains an integer $N$ — the size of the array $A$ .
The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ denoting the array $A$ .

Minimal Inversions solution codechef

For each test case, output the maximum value of $in v (A) - in v (B)$ which can be obtained after applying at most one operation.

Constraints

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$1 \leq A_{i} \leq N$
Sum of $N$ over all test cases does not exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

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

2
0
3

Minimal Inversions solution codechef

Test case $1$ : The initial array $A$ is $[4, 2, 3, 1, 5]$ which has $5$ inversions. We can perform operation on $L = 3, R = 4$ . The resultant array will be $[4, 2, 4, 2, 5]$ which has $3$ inversions. Therefore we reduce the number of inversion by $2$ which is the maximum decrement possible.

Test case $2$ : The initial array $A$ is $[1, 2, 3, 4, 5, 6]$ which has $0$ inversions. In this case, we do not need to apply any operation and the final array $B$ will be same as the initial array $A$ . Therefore the maximum possible decrement in inversions is $0$ .

Test case $3$ : The initial array $A$ is $[2, 1, 1, 1]$ which has $3$ inversions. We can perform operation on $L = 2, R = 4$ . The resultant array will be $[2, 2, 2, 2]$ which has $0$ inversions. Therefore we reduce the number of inversion by $3$ which is the maximum decrement possible.

Distinct Values solution codechef

Leave a reply

Distinct Values solution codechef – The beauty value of an array is defined as the difference between the largest and second largest elements of the array. Note that the largest and second largest elements can have the same value in case of duplicates.

Distinct Values solution codechef

For example, beauty value of $[2, 5, 3, 1] = 5 - 3 = 2$ and beauty value of $[7, 6, 7] = 7 - 7 = 0$

You are given an array $A$ of length $N$ . Your task is to find the total number of distinct beauty values among all subarrays of $A$ having length greater than $1$ .

Note that, a subarray is obtained by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.

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 size of the array.
- The second line contains $N$ space-separated numbers – $A_{1}, A_{2}, \dots, A_{N}$ , the elements of the array.

Output Format

For each test case, output a single line, the total number of distinct beauty among all subarrays of $A$ having length greater than $1$ .

Distinct Values solution codechef

$1 \leq T \leq 1 0^{4}$
$2 \leq N \leq 2 \cdot 1 0^{5}$
$1 \leq A_{i} \leq 1 0^{9}$
Sum of $N$ over all test cases does not exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

Distinct Values solution codechef

Test case $1$ : The only subarray is $[1, 1]$ whose beauty is $0$ . Thus, there is only $1$ distinct value of beauty.

Test case $2$ : The subarrays are $[4, 2], [2, 1],$ and $[4, 2, 1]$ having beauty $2, 1,$ and $2$ respectively. There are $2$ distinct values of beauty.

Test case $3$ : The unique values of beauty are $7, 1, 6,$ and $5$ .

Test case $4$ : The unique values of beauty are $3, 5, 2,$ and $1$ .

Lcm hates Gcd solution codechef

Leave a reply

Lcm hates Gcd solution codechef – Chef has two integers $A$ and $B$ .
Chef wants to find the minimum value of $lcm (A, X) - gcd (B, X)$ where $X$ is any positive integer.

Lcm hates Gcd solution codechef

Help him determine this value.

Note: $gcd (P, Q)$ denotes the greatest common divisor of $P$ and $Q$ and $lcm (P, Q)$ denotes the least common multiple of $P$ and $Q$ .

Input Format

The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first and only line of each test case contains two space-separated integers $A$ and $B$ — the integers mentioned in the statement.

Output Format

For each test case, output the minimum value of $lcm (A, X) - gcd (B, X)$ .

Lcm hates Gcd solution codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq A, B \leq 1 0^{9}$

Sample 1:

Input

Output

9
0
8

Lcm hates Gcd solution codechef Explanation:

Test case $1$ : For $X = 6$ : $lcm (12, 6) - gcd (15, 6) = 12 - 3 = 9$ which is the minimum value required.

Test case $2$ : For $X = 50$ : $lcm (5, 50) - gcd (50, 50) = 50 - 50 = 0$ which is the minimum value required.

Test case $3$ : For $X = 1$ : $lcm (9, 1) - gcd (11, 1) = 9 - 1 = 8$ which is the minimum value required.

Chef And Babla solution codechef

Leave a reply

Chef And Babla solution codechef – Chef gives an array $A$ with $N$ elements to Babla. Babla’s task is to find the maximum non-negative integer $X$ such that:

No element in the array belongs to the range $[- X, X]$ . In other words, for all $(1 \leq i \leq N)$ , either $A_{i} < - X$ or $A_{i} > X$ .

Chef And Babla solution codechef

Help Babla to find the maximum non-negative integer $X$ for which the given condition is satisfied or determine if no such $X$ exists.

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 an integer $N$ — the number of elements in the array.
- The second line of each test case contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ representing the array $A$ .

Output Format

For each test case, output on a new line, the maximum non-negative integer $X$ , satisfying the above condition.
If no such $X$ exists, output $- 1$ instead.

Chef And Babla solution codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$- 1 0^{9} \leq A_{i} \leq 1 0^{9}$
Sum of $N$ over all test cases does not exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

3
5
8 4 2 5 2
6
7 9 -10 8 12 17
4
0 -3 -1 -10

1
6
-1

Chef And Babla solution codechef Explanation:

Test case $1$ : The maximum value of $X$ such that no element of the array belongs to the range $[- X, X]$ is $1$ . All elements of the array are strictly greater than $1$ .

Test case $2$ : The maximum value of $X$ such that no element of the array belongs to the range $[- X, X]$ is $6$ . All positive elements of the array are strictly greater than $6$ and negative elements are strictly less than $- 6$ .

Test case $3$ : It is not possible to choose an element $X$ that satisfies the given condition.

Odd Even Binary String solution codechef

Leave a reply

Odd Even Binary String solution codechef – Chef had an array $A$ of length $N$ such that $1 \leq A_{i} \leq N$ for all $1 \leq i \leq N$ .

Odd Even Binary String solution codechef

Chef constructed another binary array $B$ of length $N$ in the following manner:

$B_{i} = 1$ if the frequency of element $i$ in $A$ is odd.
$B_{i} = 0$ if the frequency of element $i$ in $A$ is even.

Such an array $B$ is called the parity encoding array of $A$ .

For example, if $A = [1, 1, 2, 3]$ , then $B = [0, 1, 1, 0]$ .

Unfortunately, Chef completely forgot the array $A$ and vaguely remembers the parity encoding array $B$ . He is now wondering whether there exists any valid array $A$ for which the parity encoding array is $B$ . Can you help Chef?

Odd Even Binary String solution codechef

The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first line of each test case contains an integer $N$ — the size of the arrays $A$ and $B$ .
The second line of each test case contains $N$ space-separated integers $B_{1}, B_{2}, \dots, B_{N}$ denoting the parity encoding array $B$ .

Output Format

For each test case, output YES if there exists any valid array $A$ for which the parity encoding array is $B$ . Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

Odd Even Binary String solution codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq N \leq 1 0^{5}$
$B_{i} \in {0, 1}$
Sum of $N$ over all test cases does not exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

3
4
0 1 0 1
5
1 1 1 1 0
6
1 1 1 1 1 1

YES
NO
YES

Odd Even Binary String solution codechef

Test case $1$ : $A = [2, 4, 3, 3]$ is a valid array for the given array $B$ .

Test case $2$ : It can be proven that there does not exist any array $A$ for the given parity encoding array $B$ .

Test case $3$ : $A = [1, 2, 3, 4, 5, 6]$ is a valid array for the given array $B$ .

Mana Points solution codechef

Leave a reply

Mana Points solution codechef – Chef is playing a mobile game. In the game, Chef’s character Chefario can perform special attacks. However, one special attack costs $X$ mana points to Chefario.

Mana Points solution codechef

If Chefario currently has $Y$ mana points, determine the maximum number of special attacks he can perform.

Input Format

The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
The first and only line of each test case contains two space-separated integers $X$ and $Y$ — the cost of one special attack and the number of mana points Chefario has initially.

Output Format

For each test case, output the maximum number of special attacks Chefario can perform.

Mana Points solution codechef

$1 \leq T \leq 1 0^{5}$
$1 \leq X \leq 100$
$1 \leq Y \leq 1000$

Sample 1:

Input

Output

3
6
0

Mana Points solution codechef Explanation:

Test case $1$ : Chefario can perform a maximum of $3$ special attacks which will cost him $30$ mana points.

Test case $2$ : Chefario can perform a maximum of $6$ special attacks which will cost him $36$ mana points. Note that Chefario can not perform $7$ special attacks as these will cost him $42$ mana points while he has only $41$ mana points.

Test case $3$ : Chefario will not be able to perform any special attacks in this case.

Wonderful Jump solution codeforces

Leave a reply

Wonderful Jump solution codeforces – You are given an array of positive integers $a_{1}, a_{2}, \dots, a_{n}$ of length $n$ .

Wonderful Jump solution codeforces

In one operation you can jump from index $i$ to index $j$ ( $1 \leq i \leq j \leq n$ ) by paying $min (a_{i}, a_{i + 1}, \dots, a_{j}) \cdot (j - i)^{2}$ eris.

For all $k$ from $1$ to $n$ , find the minimum number of eris needed to get from index $1$ to index $k$ .

Input

The first line contains a single integer $n$ ( $2 \leq n \leq 4 \cdot 10^{5}$ ).

The second line contains $n$ integers $a_{1}, a_{2}, \dots a_{n}$ ( $1 \leq a_{i} \leq n$ ).

Output

Output $n$ integers — the $k$ -th integer is the minimum number of eris needed to reach index $k$ if you start from index $1$ .

Wonderful Jump solution codeforces

input

Copy

3
2 1 3

output

Copy

0 1 2

Wonderful Jump solution codeforces

Copy

6
1 4 1 6 3 2

output

Copy

0 1 2 3 6 8

input

Copy

2
1 2

output

Copy

0 1

input

Copy

4
1 4 4 4

output

Copy

0 1 4 8

Wonderful Jump solution codeforces

In the first example:

From $1$ to $1$ : the cost is $0$ ,
From $1$ to $2$ : $1 \to 2$ — the cost is $min (2, 1) \cdot (2 - 1)^{2} = 1$ ,
From $1$ to $3$ : $1 \to 2 \to 3$ — the cost is $min (2, 1) \cdot (2 - 1)^{2} + min (1, 3) \cdot (3 - 2)^{2} = 1 + 1 = 2$ .

In the fourth example from $1$ to $4$ : $1 \to 3 \to 4$ — the cost is $min (1, 4, 4) \cdot (3 - 1)^{2} + min (4, 4) \cdot (4 - 3)^{2} = 4 + 4 = 8$ .

Also read: Partial Sorting solution codeforces