Farmer John just discovered that he's missing cow treats! He knows that some cows have access to the secret cow treat stash (located in the warehouse), but he's not sure which one stole his treats. :(
However, after having been with his cows for a good 10 or so years, he knows about that his cows are usually very careful, especially when they're committing morally wrong acts. He theorizes that a cow will only steal treats if both conditions are satisfied:
1. They are alone in the warehouse at any given time
2. They never return to the warehouse when there are others present (they may be present with others before the time of the robbery, but they will not be seen in the room with another cow after the robbery)
Based on Farmer John's theory and the security camera footage, which shows when each cow entered and left the building, print out the names of the cows that could have committed this atrocious act.
The first line of the input contains the integer $$$n$$$ representing the number of times a cow enters or exits a barn. ($$$1 \le n \le 10^5$$$)
The next $$$n$$$ lines contain a single integer $$$x$$$ ($$$1 \le x \le 10^5$$$) indicating that if cow $$$x$$$ is already in the barn, it leaves and if it is not in the barn, it enters the barn. The barn starts off initially empty.
Print the numbers assigned to the cows who may have stolen the treats with one integer per line. Print the cows in sorted order.
10 96518 96518 4862 4862 90754 71337 71337 61387 95917 95917
4862 96518
Trotles gave Keys and array with $$$n$$$ integers. However since Keys is very clumsy, he spilled juice over some values of the array. So now, for some of the values of array, Keys only knows a interval of values that it could be.
Given $$$q$$$ queries, where each query gives you a left and right endpoint of a range and a target sum, determine whether Keys can choose a value for each of the uncertain intervals such that the sum of the segment denoted by the left and right endpoints achieve the target sum.
The first line contains $$$n$$$ and $$$q$$$, the length of the array and the number of queries respectively. $$$1 \le n, q \le 10^5$$$.
The next $$$n$$$ lines contain either:
a) $$$1$$$ $$$a$$$ indicating that Keys knows this value of the array and it is equal to $$$a$$$. $$$1 \le a \le 1000$$$
b) $$$2$$$ $$$l$$$ $$$r$$$ indicating that Keys doesn't know this value and it could be anywhere from $$$l$$$ to $$$r$$$ inclusive. $$$1 \le l, r \le 1000$$$
The next $$$q$$$ lines contain 3 space separated numbers, $$$l$$$ $$$r$$$ $$$x$$$, the left endpoint, right endpoint, and target sum respectively. $$$1 \le l, r \le n$$$, $$$1 \le x \le 1000$$$
The output contains $$$q$$$ lines. Each line should contain "yes" if it is possible to choose values of the intervals to reach the target sum or "no" if it is not (without the quotes). It is case insensitive.
10 8 2 4 266 2 5 401 1 202 2 4 101 2 3 179 2 6 210 2 3 373 1 312 2 8 463 1 447 5 9 374 1 4 139 3 6 160 3 5 81 9 10 433 6 6 367 2 10 270 2 3 197
yes no no no no no no no
Bessie has a 1D keyboard with $$$N$$$ keys, with all the keys laid out in a row next to each other. She would like to construct a string, with the string having exactly $$$K$$$ occurrences of each character in the keyboard. However, since Bessie only has hooves, every time she presses a key, she ends up pressing two keys – the $$$i$$$th key and then immediately after, the $$$i + 1$$$th key. She can also choose to press either the first key by itself or the last key it itself as well. Bessie is curious – what is the smallest string lexicographically that she can create?
On the first line, there are space seperated integers $$$N$$$ ($$$1 \lt = N \lt = 26$$$) and $$$K$$$ ($$$1 \lt = K \lt = 10^5$$$). On the second line a string S of length N which contains distinct uppercase letters of the alphabet representing the keyboard.
The lexicographically minimum string that Bessie can create.
7 2 LOSTKEY
EYEYLLOSOSTKTK
Definition of lexicographically minimum: https://en.wikipedia.org/wiki/Lexicographic_order
There are two groups of people in the country of Berland, the Red's and the Blue's. There are also $$$n$$$ cities which are connected by a set of $$$m$$$ roads such that each of the roads have some edge weight cost associated with building them. Both the Red's and the Blue's want to be able to travel between all the cities they have claimed (they can travel through cities claimed by the other party if needed if it is on the path to a city of their own color). What's the minimum cost of roads they must build such that all Red cities and all Blue cities are connected within each color?
The first line contains $$$N$$$ and $$$M$$$. ($$$1 \le N, M \le 2 \cdot 10^5$$$).
The second line contains a string $$$S$$$ of length $$$N$$$. $$$S[i]$$$, $$$i \in [1, n]$$$ is the color of a city, either 'R' or 'B' for red and blue respectively.
The next $$$M$$$ lines contain three integers, $$$u$$$, $$$v$$$, and $$$w$$$ indicating that cities $$$u$$$ and $$$v$$$ have a potential road that can be built between them with cost $$$w$$$.
It is guaranteed that the graph is fully connected.
Print a single integer indicating the minimum cost of building the roads such that all red and all blue cities are connected.
5 5 RBRRB 1 3 1 4 3 1 2 5 2 1 2 4 2 3 4
4
Trotles is on a well deserved vacation. He has 3 whole days where he wants to do activities that will make him as happy as possible. However, because he loves sleep, he must sleep for 8 hours every day, giving him 16 hours per day to do activities.
There is a list of $$$N$$$ activities, the $$$i$$$th taking a certain amount of hours $$$t_i$$$ to do and giving Trotles happiness $$$h_i$$$. Trotles can only do one activity at a time. He also can't do the same activity across multiple days, meaning every activity must be completed the day he starts it.
Find the maximum amount of happiness Trotles is able to achieve if he optimally plans his vacation.
The first line consists of a single integer $$$N$$$ $$$(1 \leq N \leq 1000)$$$, the number of activities.
The next $$$N$$$ lines consists of two integers $$$t$$$ and $$$h$$$, describing an activity that takes $$$t$$$ hours and gives $$$h$$$ happiness. $$$(1 \leq t \leq 16, 1 \leq h \leq 1000)$$$
Output a single integer that is the maximum amount of happiness Trotles can achieve.
6 8 2 8 1 9 1 12 2 16 5 4 10
20
Trotles is given a set of $$$n$$$ nodes and wants to construct a functional graph where the in-degree and out-degree of each node is $$$1$$$. Luckily for him, he is already given the some of the edges. For the rest of the edges he randomly chooses a node with the out-degree $$$0$$$ and a node with in-degree $$$0$$$ (they can be the same node) and draw an edge from the first one to the second one. Calculate the expected number of cycles in the graph modulo $$$10^9 + 7$$$.
The first line contain $$$n$$$ and $$$m$$$, the number of nodes and the number of given edges respectively. $$$1 \le m \le n \le 10^5$$$
The next $$$m$$$ lines contain two numbers $$$a$$$ and $$$b$$$ which means that there is an edge drawn between nodes $$$a$$$ and $$$b$$$. $$$1 \le a, b \le n$$$
It is guaranteed that the in-degree and out-degree of each node given in the test case will be less than or equal to $$$1$$$.
Print a single integer representing the expected number of cycles.
If the number of cycles is $$$\frac{p}{q}$$$ then print $$$p \cdot q^{-1} \pmod {10^9 + 7}$$$.
4 2 2 4 3 1
500000005
9 6 9 4 6 6 7 7 1 8 3 1 8 2
833333343
You are given an array A with N numbers. There are Q queries which give you a number x. Print the index of A where (A[i] - x) * (A[i + 1] - x) is maximized.
First line has N and Q, length of the array and number of queries. $$$1 \le N, Q \le 2 \cdot 10^5$$$
Second line has N space separated integers representing the array A. $$$1 \le A[i] \le 2 \cdot 10^5$$$
Next Q lines have one integer: X. $$$1 \le X \le 2 \cdot 10^5$$$
Print Q lines, the answer for each query.
10 10 102392 37104 59879 14348 157814 183664 -60462 60677 -13277 -179147 -196790 194340 126649 121980 -141990 -18502 111378 51412 59177 75080
5 9 9 9 5 5 9 9 9 9