In the vast and mysterious land of Arabia, the legendary Alibaba discovers a hidden cave filled with treasures beyond imagination. However, the cave holds a strange secret. It stores not only riches but also magical arrays, each locked by a unique pattern. Alibaba, along with his loyal companions, must now figure out how to unlock the secrets of these arrays, using clever tricks and reasoning.
You are given an array $$$A$$$ of $$$n$$$ integers, representing a magic sequence in the cave. Your task is to process $$$Q$$$ queries, which are of two types:
For example, consider the array $$$A = [1, 2, 3, 3]$$$ and two stored arrays $$$M_1$$$ and $$$M_2$$$:
- $$$M_1 = [2, 3, 1, 3]$$$ — This array matches the subarray $$$A[1..4]$$$.
- $$$M_2 = [2, 3, 1, 3, 5]$$$ — This array does not match.
The first line contains two integers $$$n$$$ and $$$Q$$$ $$$(1 \leq n \leq 10^5, 1 \leq Q \leq 2 \times 10^5)$$$ — the size of the array $$$A$$$ and the number of queries, respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array.
The next $$$Q$$$ lines contain queries of one of the following types:
Note:
For each query of type 2, you need to output how many stored arrays match the pattern of occurrences of the subarray $$$A[l..r]$$$.
10 6 5 1 2 4 1 5 2 1 9 7 1 7 4 1 2 5 2 1 1 2 2 8 1 6 2 5 4 5 1 1 2 1 6 1 6 1 2 1 5 5 4 2 1 6
1 1 2
5 4 1 2 3 4 5 1 3 5 3 4 1 2 4 3 2 3 5 2 3 4
1 1
After his seven great voyages and accumulating unimaginable wealth, Sindibad had many servants, from humans to Jinns, some of whom he tricked many times through his past adventures. They serve him well, so Sindibad refuses to free any of them. However, he becomes wary of their potential rebellion against him. So, he swears to free his Jinn servants if they achieve one task. He wants to give them a task that would seem simple but may take them a long time to finish.
Given a grid of length $$$n$$$ and width $$$4$$$, and this specific shape (shown in the image below), his Jinn servants must tile the entire grid using copies of this shape.
The shape can be rotated or flipped in any way but must completely fit within the grid. Each grid cell must be covered exactly once by a shape (no overlaps or empty cells) and every tile must have an adjacent tile to which they form a rectangle.
Determine how many distinct ways this grid can be fully tiled using copies of this shape.
The input contains a single integer $$$n, ( 1 \leq n \leq 40 )$$$ — the length of the grid.
Output a single integer — the number of distinct ways the shape can be placed within the grid.
3
4
In the heart of Agrabah, as the holy month of Ramadan began, the city came alive with the scent of spices, the sound of prayers, and the warmth of community. To celebrate this sacred time, the wise and beloved Sultan decided to create a grand display of lanterns symbolizing unity and harmony.
The Sultan commissioned an $$$n \times n$$$ mystical grid, where each lantern at position $$$(i, j)$$$ carried a special meaning. He explained to his trusted advisor, Aladdin, that the brightness of each lantern depended on the mathematical relationship between its row $$$i$$$ and column $$$j$$$.
The Rule of the Lanterns
Example: $$$n=3$$$
Aladdin, eager to assist, was given the task of calculating the total brightness of all the lanterns in the grid. The Sultan believed that this total brightness would reflect the collective spirit of Agrabah during Ramadan.
To ensure the result remains manageable, the total brightness should be computed modulo $$$10^9 + 7$$$.
Can you help Aladdin solve this challenge and determine the total brightness of the magical lantern grid?
The first line contains the number of test cases t ($$$1\le t \le 10^5$$$). Each test case consists of a single integer $$$n$$$ ($$$1\le n \le 10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$
For each test case, print the total brightness of the magical lantern grid.
2 1 3
1 23
Iceberg House, a trading house, is a highly desirable workplace for young scholars thanks to its renowned reputation throughout the markets. Each year, Yessine receives a vast pool of apprenticeship seekers. In the past, he would select candidates arbitrarily. However, this year, he has learned from travelers along the Silk Road that trading houses with diverse knowledge and skills are more successful in negotiating profitable deals with merchants from distant lands.
To enhance diversity, Yessine has identified a list of $$$n$$$ skills. Each candidate has a proficiency score for each skill, ranging from $$$1$$$ (lowest proficiency) to $$$m$$$ (highest proficiency).
To ensure a diverse selection, Yessine will choose candidates such that no applicant is more skilled than another. However, if two or more candidates are equally skilled, then Yessine will only select one of them.
A candidate $$$A$$$ is more skilled than $$$B$$$ if, for every skill, candidate $$$A$$$ has a proficiency score greater than or equal to candidate $$$B$$$, and for at least one skill, candidate $$$A$$$ has a strictly higher proficiency score. Two candidates are equally skilled if they have exactly the same proficiency scores for all skills.
Yessine wants to maximize the number of young scholars while still adhering to the selection criteria described above.
The applicant pool is very large and contains every possible combination of skill scores. What is the maximum number of candidates Yessine can accept while ensuring no candidate is more skilled than another?
Since the answer can be large, output it modulo $$$M = 998244353$$$.
The single line of the input contains two space separated integers:
Output one integer, representing the desired answer modulo $$$998244353$$$
10 10
432457640
3 20
300
100 100
920143000
200 200
441305744
In Sultan Malik's palace, there are $$$N$$$ antiques, each with a distinct value. Initially, the antiques are arranged randomly in the entrance of his palace.
Sultan Malik, known for his love of perfection, wishes to sort his antiques in ascending order of their values.
The Sultan is looking for a wise advisor, so he makes this task into a game. You can only sort the antiques using swaps. Moreover, there is another restriction: a swap is only allowed if one antique has a value strictly greater than a chosen threshold $$$K$$$, and the other has a value strictly lower than $$$K$$$.
Formally, given an array $$$A$$$ of $$$N$$$ distinct integers, you want to sort it with the following operation:
The Sultan will select the advisor who can find the smallest possible $$$K$$$ that allows the antiques to be sorted in increasing order.
Fankoush, aspiring to be the Sultan's advisor, asked for your help to determine $$$K$$$.
If there exists no such $$$K$$$, you must report $$$-1$$$ to Fankoush.
The first line contains an integer $$$T$$$ denoting the number of test cases ($$$ 1 \le T \le 10^5 $$$). For each test case:
Print the minimum possible $$$K$$$ or $$$-1$$$ if it is not possible.
423 122 131 2 352 4 3 1 5
2 -1 0 3
Each year, Aziz Mansour, a local shopkeeper, lights up lanterns (fawanis) in the streets around his shop to celebrate Ramadan. The lanterns are represented by a string of bits, where $$$1$$$ symbolizes a lit lantern and $$$0$$$ symbolizes an unlit lantern.
To maintain tradition, the fawanis must follow a harmonious pattern: the number of $$$01$$$-substrings (a lit lantern followed by an unlit one) must be equal to the number of $$$10$$$-substrings (an unlit lantern followed by a lit one).
However, this year, Mansour has committed an error and the pattern may have become unbalanced. Your task is to help Mansour restore harmony to the lanterns by making the fewest changes.
In one change, you may flip any bit in the string (change a $$$1$$$ to $$$0$$$ or vice versa) to achieve the balanced pattern.
The first line contains a number $$$N$$$: the length of the string. $$$2\le N \le 10^6$$$
The second line contains a string $$$S$$$, the string modeling the lanterns
Output two lines:
2 10
1 0
3 101
0
This is an interactive problem.
Sultan Shahrayar has $$$n$$$ advisors, numbered from $$$1$$$ to $$$n$$$. One time he was bored, so he arranged them in a line, ordered from the wisest to the least wise. To test your intelligence, he brings you to his castle and challenges you to guess the exact order of the advisors. To help you, he allows you to ask $$$20000$$$ questions. In each question, you can pick a number $$$x$$$ and Shahrayar will tell you whether the number of inversions of the order is more or less or equal to $$$x$$$.
A pair $$$(i, j)$$$ is called an inversion in an array $$$A$$$ of length $$$n$$$ if:
After each question, the order of the advisors is rotated to the right.
For example, if the initial order is $$$[4, 1, 3, 2]$$$, the inversions are $$$(4,1)$$$, $$$(4,3)$$$, $$$(4,2)$$$, and $$$(3,2)$$$, resulting in a total of $$$4$$$ inversions. After one question, the order becomes $$$[2, 4, 1, 3]$$$ and the number of inversions is $$$3$$$.
The interaction starts after reading a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ - the length of the permutation.
To ask a question, print "$$$?$$$ $$$x$$$" $$$(0 \le x \le n^2)$$$, then read the answer.
3 < < > =
? 2 ? 2 ? 2 ? 1 ! 1 3 2
You have to guess the initial order, not the order after the questions.
After printing a query or the answer, do not forget to output an end-of-line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
This is an interactive problem.
Aladdin has found the magical lamp and awakened the Genie inside it. He wished to become the richest man in the kingdom. The Genie agreed to grant Aladdin his wish and said he would do so by granting him $$$n$$$ golden coins. However, there was one condition for the wish to come true, Aladdin must guess the number. The Genie told Aladdin that he has at most $$$29$$$ tries to guess $$$n$$$, and that the number of golden coins is at least $$$1$$$ and at most $$$10^9$$$.
To find the secret number, Aladdin needs to make guesses, where in each guess he proposes a number. After each guess, the Genie will reveal to Aladdin the Hamming distance between the guess and $$$n$$$.
The Hamming distance between $$$2$$$ integers is the number of bits that are different at the same position in both numbers in their binary representation. For example, the Hamming distance between $$$9$$$ and $$$14$$$ is $$$3$$$.
Aladdin really wants to get rich. Can you help him uncover the number of golden coins before all his wishes are gone?
To make a query, you have to print a line "$$$?$$$ $$$x$$$" $$$(0 \le x \le 10^{9})$$$
After each query, read a single integer $$$k$$$ $$$(0 \le k \le 30)$$$ – the Hamming distance between $$$n$$$ and $$$x$$$.
When you find $$$n$$$, print a line "$$$!$$$ $$$n$$$". Printing $$$n$$$ is not counted as one of 29 operations.
3 4 2 0
? 24 ? 55 ? 8 ? 4 ! 4
After printing a query or the answer, do not forget to output an end-of-line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
In the enchanting realm of Alf Layla w Layla, there lies a remote island where rising sea levels, due to melting ice caps, are increasing the water level by $$$1mm$$$ each year.
The island inhabitants, with a knack for a living simply and no known talent for bridge-building, are worried about their island splitting into separate landmasses. They joke that if their island splits, they might need to start a swimming club just to visit neighbors! Thus, they're keen to find out in which year that will happen.
Fortunately, the wise sorceress Zahra has foreseen this calamity. Using her mystical powers, she has devised a way to predict the fate of the island. She has transformed the island's topography into an $$$n \times m$$$ grid, where each cell represents the elevation above sea level in millimeters (cells with $$$0$$$ elevation initially represent sea). Zahra's magic allows her to simulate the rising sea levels year by year, revealing how the island will change over time.
For the purposes of this problem, an island is considered divided if there exists one path of sea ($$$0$$$ elevation) that separates the island into distinct land masses.
Note that two cells are considered part of the same landmass only if they are connected by their sides (up, down, left, or right).
Furthermore, any land that reaches an elevation below $$$0$$$ is considered submerged and thus treated as sea, even if it doesn't have direct contact with the existing sea areas at that point in time.
If no division occurs, the entire island will eventually sink below sea level.
Zahra's prediction depends on this simulation. She tasks you with analyzing the grid, year by year, as the sea level rises, to determine the precise moment when the island first splits into separate landmasses.
Print the year when the island is first divided into two or more landmasses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.
The first line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^3)$$$ respectively the length and width of the map containing the island.
Then a grid of $$$n \times m$$$ numbers will follow representing the current topology of the island.
Each number represents the elevation of that point above the sea level while $$$0$$$ represents points already submerged by the sea ($$$0 \leq elevation(i,j) \leq 10^9$$$).
Print the year when the island is first divided into two or more land masses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.
5 6 0 0 0 0 0 0 0 2 2 1 0 0 0 0 1 1 2 0 0 0 0 2 3 0 0 0 0 0 0 0
1
5 5 0 0 0 0 0 0 0 1 0 0 0 4 2 2 0 0 0 3 0 0 0 0 0 0 0
2
Below is a simulation of the $$$1st$$$ test example
During the holy month of Ramadan, Rami and Yassine have a special tradition. Every night, after breaking their fast at iftar, they head to their favorite coffee place to engage in friendly games while waiting for suhoor. One evening, they decide to play a modified version of Rock-Paper-Scissors as a card game.
There are only three types of cards: Rock, Paper, and Scissors.
The game proceeds in turns as follows:
Now both players play optimally, and fairly:
Given the initial deck compositions $$$R_1, P_1, S_1$$$ for Rami and $$$R_2, P_2, S_2$$$ for Yassine, compute the probability of each player winning the game.
A single line containing six integers $$$1 \leq R_1, P_1, S_1, R_2, P_2, S_2 \leq 18$$$.
It is guaranteed that: $$$$$$ 3 \leq \max(R_1 + P_1 + S_1, R_2 + P_2 + S_2) \leq 20 $$$$$$
Print two floating-point numbers $$$0 \leq p_1, p_2 \leq 1$$$:
1 1 1 1 1 1
0.5 0.5
4 5 6 5 5 5
0.482774 0.517226
The first test case corresponds to a traditional rock paper scissor game. It can be proven that the optimal strategy for each player, is to choose any card, with the same probability.
Fankoush has successfully been recruited as the advisor to Sultan Malik.
In his first day, he faced a new challenge: Sultan Malik has an ancient letter containing an encrypted string $$$S$$$ of $$$N$$$ characters. The letters hold some important content. To restore it, the string must be sorted through a series of swaps.
Again, there is a restriction: characters $$$c_1$$$ and $$$c_2$$$ can only be swapped if a rule $$$(c_1, c_2)$$$ exists. At first, no rules exist, so Fankoush must create them.
Note that the rule $$$(c_1, c_2)$$$ is the same as the rule $$$(c_2, c_1)$$$.
To prove his skill, he must find the minimum number of rules required to sort the string in ascending order.
Fankoush is tired of sorting stuff for Malik, so he asked for your help again.
The first line contains an integer $$$T$$$, the number of test cases $$$( 1 \le T \le 10^5 )$$$. For each test case:
Print the minimum number of rules. It can be proven that a solution always exists.
4 2 ab 2 ba 3 cba 3 cab
0 1 1 2
Annoyed at sorting stuff for Sultan Malik, advisor Fankoush has stolen a powerful treasure and escaped into a deep maze. He will be taking some specific path that will lead him to a point of no return, where he will disappear without a trace.
The maze contains $$$N$$$ rooms. Each room is connected to one or multiple rooms by a passage. There are $$$M$$$ passages in the maze. Passage $$$i$$$ has length $$$w_i$$$.
The sultan's soldiers chase the thief, and each of them starts in some room in the maze. The soldiers know the exact path that Fankoush will take and the distances between the rooms.
Note the following:
The soldiers' mission is to catch Fankoush before he leaves the maze and escapes forever.
Your task is to help them find the number of the first room where they can intercept him. If it's impossible to catch him in time, you should return $$$-1$$$.
Note:
Print a single integer, the number of the first room in Fankoush's path where any soldier can intercept him, or $$$-1$$$ if no interception is possible before the last room.
6 70 2 10 5 31 2 21 3 21 4 21 5 22 3 23 3 1 52 0 211 10
5