Karl is the chief of meat at the local eclair factory. Each day he arrives at the factory (next door to his house) and pulls out his trusty telescope to ensure the quality of every eclair in the Food Machine$$$^{\text{TM}}$$$. Using his telescope, he measures the weight of each eclair (it obviously has a built-in scale) and checks for anomalies. An anomaly is present if the weight of an eclair is exactly equal to the sum of its proper divisors (a proper divisor is a positive integer less than the weight which divides the weight). In that case, Karl will declare the eclair a robot and have it taken away for further inspection. Given a list of eclair weights, can you utilize Karl's telescope to find out which of them are actually robots in disguise?
The input will begin with a line containing a single integer, $$$n\ (1 \leq n \leq 10^4)$$$, the number of eclairs that Karl must inspect. The next line will consist of $$$n$$$ space-separated integers, the $$$i$$$th of which denotes the weight, $$$w_i\ (1 \leq w_i \leq 500)$$$, of the $$$i$$$th eclair (or robot in disguise).
The output should consist of a single integer, the number of eclairs which are detected as anomalies by Karl's telescope, also known as the number of eclairs which are actually robots in disguise.
2 6 28
2
3 496 100 499
1
EGaDS has designed a new game, themed around a barbershop called Hardcore Haircuts.
In the game, Harry the Hairy Hairball wants a new haircut! The question, of course, is which one?
Harry has $$$N$$$ hairs and although he knows he wants one of them to be cut, he has forgotten which one. Now, Harry has entered your hair salon and is feeling quite harried, since he doesn't know what to ask for. He does, however have a sorted list of the planned lengths of each hair after the haircut, $$$v_i$$$.
Luckily, you can see Harry's head and observe the lengths of his current hairs. You've also written this down as a sorted list of lengths, given by $$$u_i$$$.
Given the desired lengths of his hairs $$$v_i$$$ and the current lengths, $$$u_i$$$ please determine which hair should be cut. Please hurry to help Harry determine which hair should be harvested!
Line 1 is a single integer, $$$1 \leq N \leq 10^4$$$, representing the number of hairs Harry has.
Line 2 has $$$N$$$ sorted values $$$0 \leq v_i \leq 1000$$$, representing the desired lengths of his hairs.
Line 3 has $$$N$$$ sorted values $$$0 \leq u_i \leq 1000$$$, representing the current lengths of his hairs.
Note that exactly one hair will be cut.
Two integers, denoting the initial and new lengths of the hair.
3 1 2 3 1 3 4
4 2
ACM 4 Change is hosting a series of ethical debates, and they have brought a panel of $$$N$$$ speakers who are experts on a variety of ethical topics to open the floor. Each speaker is distinguished by a unique ID $$$i$$$ ($$$1 \leq i \leq N$$$) and specializes in a particular area denoted by an integer $$$a_i$$$. After lining up all the speakers in a row in increasing order of ID, the officers for ACM need to select some number of speakers to kickstart debates during the meeting. They want exactly $$$K$$$ distinct areas of expertise to be represented by the minimum possible number of speakers, but require all the picked speakers to be part of a contiguous sequence in the row (e.g. if speakers with IDs $$$a$$$ and $$$b$$$ are picked with $$$a \leq b$$$, any speaker with ID $$$x$$$ with $$$a \leq x \leq b$$$ must also be selected). What is the minimum number of panel members that must be chosen to speak?
The first line of input contains two space separated-integers $$$N$$$ and $$$K$$$ ($$$1 \leq N, K \leq 10^5$$$), representing the number of panel speakers and the exact number of distinct topics A4C would like debaters to go over, respectively. The second line of input contains $$$N$$$ space-separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^5$$$) that represent the topic of expertise of the $$$i$$$-th speaker. Two speakers with IDs $$$i$$$ and $$$j$$$ have the same area of expertise if and only if $$$a_i = a_j$$$.
Output the minimum number of panel speakers necessary to meet the requirements of having exactly $$$K$$$ distinct topics covered. If this is not possible with the given speakers, output $$$-1$$$ instead.
4 2 1 2 2 3
2
5 1337 1 22 333 4444 55555
-1
In the first sample case, the first two speakers or the last two speakers can be selected.
In the second sample case, there are not enough distinct topics covered by the panel speakers.
Freetail Hackers is an organization focused on bringing students who are passionate about technology together to build cool tech, learn new skills, and become involved in the hackathon and tech communities. We put on HackTX, an annual hackathon that brings students from all over the country to build new technology. Learn more about Freetail Hackers
For their field day event, Freetail Hackers has decided to play one of their favorite bat-related games, Bat-shoes. Bat-shoes is played similarly to Horseshoes, but with multiple pegs and some special rules.
There are $$$N$$$ pegs in a row and $$$N$$$ people on a team facing the pegs. The goal of the game is to toss bat-shoes onto the pegs, where each person tosses bat-shoes onto the peg directly in front of them.
Each person starts out with a different number of bat-shoes, given by $$$a_1,...,a_N$$$. Players then toss in the order given (i.e. $$$1...N$$$). Players can score extra points by forming an increasing sequence – that is, if player $$$i$$$ tosses $$$x_i$$$ bat-shoes onto their peg, then player $$$i+1$$$ tosses $$$x_{i+1} \gt x_i$$$ bat-shoes onto their peg, player $$$i+2$$$ tosses $$$x_{i+2} \gt x_{i+1}$$$ bat-shoes onto their peg, and so on ($$$0 \lt x_i \le a_i$$$ for all $$$i$$$).
Your team wants to know: what's the maximum length increasing sequence your team can create, if you play optimally?
The first line contains one integer $$$N$$$ ($$$1 \le N \le 10^6$$$), the number of pegs and the number of people on your team.
The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^6$$$), representing the number of batshoes the players start out with.
Output an integer representing the maximum length increasing sequence your team can create if everyone plays optimally.
6 2 5 6 2 7 9
4
In the example, your team can create an increasing sequence of length 4 if player 3 tosses 1 batshoe onto their peg, player 4 tosses 2 batshoes, player 5 tosses 7 batshoes, and player 6 tosses 9 batshoes ($$$1 \lt 2 \lt 7 \lt 9$$$). It can be shown that this is the maximum length increasing sequence you can obtain.
Larry Longsleeves is reknown for having the finest collection of long shirts and long pants in the world. After winning the International Longsleeve Showdown five years in a row, he's confident that he's uncovered the secrets of stylish outfits. To maximize on his discovery, he's decided to start his own clothing company, with the help of Convergent!
In his pitch, Larry plans to reveal that each outfit, consisting of just one shirt and one pair of pants, can be reduced to a style score $$$s$$$! Even better, there's a formula to compute it, based solely on $$$a$$$, the length of the shirt sleeves, and $$$b$$$, the length of the pant sleeves: $$$s = |a^2-b^2|$$$. But while a higher value of $$$s$$$ is preferred, an outfit can only truly be stylish if $$$s$$$ is prime. This insight, as Larry claims, will allow his brand to suggest the best outfit combinations for the customers and beat out his competition.
However, the members of Convergent aren't convinced. After all, while Larry has won the International Longsleeve Showdown many times, he also has the most extensive wardrobe in the world — perhaps he just got lucky when selecting the winning outfits?
In any case, it is your job to help out Larry. He needs a stylish outfit, and fast. As his second in command, personal butler, and best friend, can you look through his wardrobe and find Larry Longsleeves an outfit to win Convergent over?
The first line of input contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^4$$$), representing the number of shirts and pants Larry has, respectively.
The second line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$), representing the sleeve length of each shirt that Larry has.
The third line contains $$$m$$$ integers, $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^6$$$), representing the sleeve length of each pair of pants that Larry has.
Output the highest style score achievable of any of Larry's stylish outfits, or $$$-1$$$ if no combination of Larry's shirts and pants yields a stylish outfit.
2 3 2 4 1 3 5
7
1 3 2 4 6 8
-1
After a mostly peaceful week, UT Austin's CS week has devolved into an all-out turf war.
UT Austin can be seen as a $$$N \times N$$$ grid with $$$K$$$ clubs located at various (distinct) points.
Clubs patrol their turf by walking between edges in the $$$4$$$ cardinal directions. A club controls a cell of this grid if its path to that cell is shorter than all other clubs. In the case of ties, the club with the lowest index wins.
UTPC hasn't joined in yet, but rather than fight over land, we seek only to develop a rivalry with another club by positioning ourselves to take their land. Given that we're the last club to join, we won't win any tiebreakers.
Given the grid size and clubs, determine how much of that club's turf UTPC could take for each club.
Three numbers, $$$1 \leq N \leq 750$$$ and $$$1 \leq K \leq min(10^4,\frac{N^2}{2})$$$.
The next $$$K$$$ lines are a list of the $$$K$$$ club locations.
It is guaranteed that there will not be more than one club or building per cell.
$$$K$$$ lines, for each club, the amount of its turf UTPC could take.
4 3 1 2 2 3 3 2
2 4 2
We're a student org created by transfer students, for transfer students. We know firsthand how tough it can be to find your way and your people after transferring into the CS major or into UT more generally. If you're an internal transfer, external transfer, or ATP student we hope to see you!
The CS Transfer Society is hosting a scavenger hunt in the GDC! At the time of writing this I have no idea what the objectives are, so I'll assume that the goal is to collect as many moldy sandwiches as possible!
The GDC can be (grossly) represented by an $$$N$$$ by $$$N$$$ grid. The CS Transfer Society has placed $$$M$$$ moldy sandwiches inside the GDC, marked by '#'. All other locations are marked as '.'.
You are participating on behalf of your CS week organization and, of course, are looking to win! However, time is running out. You know that with $$$K$$$ time you can explore any $$$K$$$ by $$$K$$$ square and collect all the moldy sandwiches in that square. (All squares have sides parallel to the sides of the original square).
You would like to know: for each $$$1 \le i \le M$$$, what value of $$$K$$$ is required to collect $$$i$$$ sandwiches, if you choose to explore the optimal $$$K$$$ by $$$K$$$ square?
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^3$$$), the side length of the square representing the GDC.
The next $$$N$$$ lines of $$$N$$$ characters each represent the current layout of the GDC, where '#' marks a moldy sandwich and '.' is filled in otherwise. It is guaranteed that the number of moldy sandwiches $$$M$$$ will be at least $$$1$$$ and will not exceed $$$100$$$.
Print out $$$M$$$ integers in a single line: the minimum time needed to collect $$$i$$$ sandwiches for all $$$1 \le i \le M$$$.
4 ..#. .#.. ...# ....
1 2 3
UT's Quantum Collective is hosting their annual qubit selection party! Each year, the members come together to select their very favorite qubits to showcase to the rest of the university. Each qubit, $$$|\varphi\rangle$$$ can be written in the form $$$|\varphi\rangle = \alpha|0\rangle + \beta|1\rangle$$$ for integers (for some reason, the collective banned complex numbers many years ago) numbers $$$\alpha, \beta$$$. This is analogous to saying that every qubit has some "$$$|0\rangle$$$" component and some "$$$|1\rangle$$$" component. Sometimes this can be expressed shorthand by $$$|\varphi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$$$ (a column vector) where $$$|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$$ and $$$|1\rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$$$.
The Quantum Collective did an initial pruning, and now they are down to the top $$$n$$$ qubits in the world. Now all that is left to do is rank them! The members of the quantum collective will select a ranking for each qubit, starting with the very best and ending with the very worst (the $$$n$$$th place qubit).
However, every possible ranking that can be assigned to the qubits has a score associated with it. The score of a ranking is calculated at each step of the ranking. First off, the first qubit, $$$|\varphi_1\rangle$$$ contributes $$$\alpha_1 + n \cdot \beta_1$$$ to the score. Then, the following recurrence relation applies: assuming that $$$k$$$ qubits have been selected so far (for $$$1 \leq k \lt n$$$), the $$$k + 1$$$th qubit contributes $$$\sum_{i=1}^k{\alpha_i \cdot \alpha_{k+1} \cdot k + \beta_i \cdot \beta_{k+1} \cdot (n - k)}$$$ to the score (where each of the $$$k$$$ previously chosen qubits is denoted by its column vector coefficients).
Based on the formula for score calculation, can you determine the highest score that the collective can achieve by choosing their ranking of qubits optimally?
The input will begin with a line containing a single integer, $$$n \ (1 \leq n \leq 20)$$$, the number of qubits that must be ranked. The next $$$n$$$ lines will each consist of two space-separated integers, $$$\alpha$$$ and $$$\beta\ (1 \leq \alpha, \beta, \leq 1000)$$$, respectively, denoting the state of each qubit.
The output should consist of a single integer denoting the highest score that the collective can possibly achieve by choosing the optimal ranking of qubits.
3 1 1 2 2 3 3
45
6 1 2 6 7 3 8 4 2 9 9 1 1
1850
UTCS Roadshow has created a brand new custom track for their Mario Kart Tournament! Banana Split is a very technical track - except for the straightaway with $$$10^9$$$ item box spawn points in a row (a driver could theoretically hit a billion consecutive item boxes without veering off course). The item box spawn points can be viewed as a row from a trackside view, and the points can be numbered from $$$1$$$ to $$$10^9$$$, inclusive, from left to right.
At the beginning of a race, none of the item box spawn points have any active item boxes. During the race, however, the internals of the Mario Kart operating system must respond to $$$Q$$$ queries about the changing state of the giant row of spawn points. There are two types of queries $$$C$$$ and $$$S$$$, that correspond to IDs $$$1$$$ and $$$2$$$, respectively.
- Type $$$C$$$: Output the number of item boxes a kart hits between spawn points $$$x$$$ and $$$y$$$, inclusive, assuming that sufficient time has passed for all previously hit boxes to respawn.
- Type $$$S$$$: Force all the item boxes between spawn points $$$x$$$ and $$$y$$$, inclusive, to start spawning in repeatedly for karts to encounter. If an item box spawn point is already active, it will continue to spawn item boxes.
Can you help answer all queries of type $$$C$$$ to make Banana Split run smoothly?
The first line of input contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of queries to be responded to. The next $$$Q$$$ lines of input each contain three space-separated integers $$$t$$$ ($$$t = 1, 2$$$), $$$x$$$, and $$$y$$$ ($$$1 \leq x \leq y \leq 10^9$$$) representing the query type, $$$x$$$, and $$$y$$$, respectively, as described above.
For each query of type $$$C$$$, output the answer as a single non-negative integer on its own line.
10 2 7 12 2 10 11 1 10 12 2 8 13 1 10 11 2 11 15 1 10 10 2 8 11 2 7 9 2 3 4
3 2 1