AlgoChief Sprint Round 3
A. Max Xor Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay gives you two integers $$$N$$$ and $$$X$$$, find the maximum Bitwise Xor value of a pair of integers in the range $$$[1, N]$$$. However, the chosen pair must not include the integer $$$X$$$.

You need to determine the maximum Bitwise Xor value achievable by choosing two distinct numbers $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq N, a \neq X , b \neq X, a \neq b)$$$

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains two integers $$$N$$$ and $$$X$$$ $$$(3 \leq N \leq 10^9, 1 \leq X \leq 10^9)$$$.
Output
  • For each test case, print a single integer — the maximum Bitwise Xor value satisfying the given conditions.
Example
Input
2
6 1
6 2
Output
7
7
Note
  • For test case $$$1$$$, the pair $$$(2,5)$$$ achieves the maximum Bitwise Xor value of $$$7$$$.
  • For test case $$$2$$$, the pair $$$(1,6)$$$ achieves the maximum Bitwise Xor value of $$$7$$$.

B. Segment Trees ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay gives you a sequence of $$$n$$$ integers is given $$$a_1$$$, $$$a_2$$$, .. $$$a_n$$$. You need to process $$$q$$$ queries of two types.

The sequence supports the following two types of operations:

  • $$$1$$$ $$$x$$$ $$$p$$$ — Set $$$a_x$$$ to $$$p$$$.
  • $$$2$$$ $$$v$$$ — Set $$$a_i$$$=$$$max$$$($$$a_i$$$,$$$v$$$) for all $$$i$$$ $$$\in$$$ ($$$1$$$,$$$n$$$). Where $$$max$$$($$$a$$$,$$$b$$$) denotes maximum of $$$a$$$ and $$$b$$$
Your task is to determine the final values of the array after processing all queries.
Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
    • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the elements of the array.
    • The third line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
    • Then $$$q$$$ lines follow. The $$$i$$$-th line contains the $$$i$$$-th query is given either as
      • $$$1$$$ $$$x$$$ $$$p$$$ $$$(1 \leq x \leq n, 1 \leq p \leq 10^9)$$$
      • $$$2$$$ $$$v$$$ $$$(1 \leq v \leq 10^9)$$$
  • The sum of $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$10^5$$$.
Output
  • For each test case, print $$$n$$$ space-separated integers — the final values of the array after processing all queries.
Example
Input
1
8
1 2 3 4 5 6 7 8
8
2 10
1 1 6
1 2 6
2 10
1 1 5
1 2 6
1 3 7
1 4 1
Output
5 6 7 1 10 10 10 10
Note

$$$[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8]$$$ $$$\xrightarrow[]{1}$$$ $$$[10 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{2}$$$ $$$[6 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{3}$$$ $$$[6 ,6 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{4}$$$ $$$[10 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{5}$$$ $$$[5 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{6}$$$ $$$[5 ,6 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{7}$$$ $$$[5 ,6 ,7 ,10 ,10 ,10 ,10 ,10]$$$ ,$$$\xrightarrow[]{8}$$$ $$$[5 ,6 ,7 ,1 ,10 ,10 ,10 ,10]$$$

C. Farthest Apart
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay is focusing on proposing questions. He wants to ensure that he and his soulmate are as far apart as possible on a 1D line. He needs your help to solve this problem optimally.

On a 1D line, two people are at Sanjay $$$(x_1)$$$ and his soulmate $$$(x_2)$$$ with $$$x_1 \lt x_2$$$.

Initially you have $$$n$$$ pairs $$$(l, r)$$$ such that $$$l \leq r$$$, $$$l \leq x_2$$$, and $$$x_1 \leq r$$$.

For each pair, you can perform:

  1. $$$x_1 = \max(x_1, l)$$$,
  2. $$$x_2 = \min(x_2, r)$$$.

Additionally, exactly once, you must perform both operations (1) and (2) on the same pair. For the remaining pairs, you must choose to perform either operation (1) or (2).

Your task is to find the maximum possible value of $$$x_2 - x_1$$$ after performing the operations optimally, ensuring that Sanjay and his soulmate are as far apart as possible.

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of pairs.
    • The second line contains two integers $$$x_1$$$ and $$$x_2$$$ $$$(0 \leq x_1 \lt x_2 \leq 10^9)$$$ — the initial positions of Sanjay and his soulmate.
    • The next $$$n$$$ lines each contain two integers $$$l$$$ and $$$r$$$ $$$(0 \leq l \leq r \leq 10^9, l \leq x_2, x_1 \leq r)$$$ — the ranges of the pairs.
The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
Output
  • For each test case, print a single integer — the maximum possible value of $$$x_2 - x_1$$$.
Example
Input
2
2
2 9
1 8
3 7
3
10 60
11 58
12 59
13 59
Output
5
47
Note
  • For Test Case $$$1$$$: The maximum possible value of $$$x_2$$$ - $$$x_1$$$ is achieved by applying both operations $$$1$$$ and $$$2$$$ on $$$(1, 8)$$$ , choosing operation $$$1$$$ for the remaining all pairs, resulting in maximum value $$$x_2$$$ - $$$x_1$$$ = $$$5$$$.

D. Simple Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay has an undirected tree with $$$n$$$ nodes, where each node is labeled from $$$1$$$ to $$$n$$$. Each node $$$u$$$ also has an associated integer value $$$val_u$$$. For each node $$$u$$$, determine the shortest distance to a node $$$v$$$ $$$(v \neq u)$$$ such that:$$$ \implies $$$ ($$$val_u$$$ $$$\&$$$ $$$val_v$$$) $$$ \neq $$$ $$$max(val_u , val_v)$$$.

___________________________________________________________

  • $$$\&$$$ represents the bitwise AND operation between two values.
  • $$$\max(a, b)$$$ represents the maximum of $$$a$$$ and $$$b$$$.
  • distance between two nodes is the number of edges in the shortest path between them in the tree.

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of nodes in the tree.
    • The second line contains $$$n$$$ integers $$$val_1, val_2, \dots, val_n$$$ $$$(1 \leq val_i \leq 10^9)$$$ — the integer values assigned to each node.
    • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$, representing an undirected edge in the tree.
  • The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$
Output
  • For each node $$$1$$$ to $$$n$$$ ,print the shortest distance to the node that satisfies the given condition. If no such node exists, print $$$-1$$$ for that node.
Example
Input
2
6
3 7 2 5 8 1
1 2
2 3
3 4
4 5
5 6
5
2 2 2 2 2
5 3
4 3
2 5
1 2
Output
1 1 1 1 1 1 
-1 -1 -1 -1 -1
Note
  • For Test Case $$$1$$$: For every node it's adjacent node satisfies the required condition.
  • For Test Case $$$2$$$: For each node there is no other node which satisfies the given condition.