The problem setting team tries to keep weekly meetings to discuss progress etc. Generally, the person who arrives last has to do meeting minutes. Unfortunately, recently regardless of who arrives last, Elijah does the meeting minutes (even if he does not show up to the meeting himself!).
You will be given a list of $$$n$$$, $$$(1 \leq n \leq 100)$$$ names in the order that they arrived to the meeting. Each person's name will be $$$20$$$ characters or less.
You will have to output the person who will do the meeting minutes.
The first line will contain an integer $$$n$$$, $$$(1 \leq n \leq 100)$$$, the number of people who showed up to the meeting. The following $$$n$$$ lines will each contain one name per line, $$$(1 \leq |name| \leq 20)$$$ denoting the name of the person in the order they showed up to the meeting. All names will consist of only of ASCII characters.
You will have to output the person who does the meeting minutes (Elijah!). The output is case sensitive.
7 Elijah chessbot bossologist chessbot MantleMoose NullAwe SPark
Elijah
Elijah arrives first.
Chessbot shows up second.
Then Bossologist arrives.
Afterwards, chessbot's clone joins the meeting.
MantleMoose arrives after that.
A little after, nullawe who is not in the problem setting team joins.
Finally, SPark dials in.
As per tradition, Elijah has to do the meeting minutes.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Novice 1, Intermediate 1, Advanced 1
Bossologist is brushing up on his arithmetic skills, and has found an interesting way to practice by doing $$$P$$$ ($$$1 \leq P \leq 10^5$$$) problems of a certain format. For the $$$p$$$th problem, he first picks two numbers $$$A_p$$$ and $$$B_p$$$. He will then use the four operations $$$+, -, *, \div$$$ to combine $$$A_p$$$ and $$$B_p$$$ in any way (i.e. Bossologist finds $$$A_p+B_p$$$, $$$A_p-B_p$$$, $$$B_p+A_p$$$, etc.). For each of $$$P$$$ problems determine the number of distinct answers Bossologist gets.
The first line of input will be $$$P$$$.
The next $$$P$$$ lines will each contain the two numbers $$$A_p$$$ and $$$B_p$$$ ($$$1 \leq A_p, B_p \leq 10^4$$$) he picks for the $$$p$$$th problem.
Note that test case $$$0$$$ is the sample case, which is not worth any points.
Output $$$P$$$ lines where the $$$p$$$th line gives the number of distinct answers Bossologist gets for problem $$$p$$$.
4 2 19 3 5 4 3 6 6
6 6 6 4
For the first problem, the possible answers are $$$2 + 19 = 21$$$, $$$2 - 19 = -17$$$, $$$19 - 2 = 17$$$, $$$19 \cdot 2 = 38$$$, $$$19 \div 2 = 9.5$$$, and $$$2 \div 19 \approx 0.105$$$, for a total of $$$6$$$ distinct answers.
$$$---------------------------------------------$$$
Problem Idea: Bossologist
Problem Preparation: Bossolgist
Occurrences: Novice 2
This is the easy version of the problem. In this version, Takagi only has to follow one rule.
Nishikata and Takagi are standing in front of an infinitely long fence. Fenceposts are numbered from $$$1$$$ to $$$\infty$$$ and fencepost $$$i$$$ costs $$$i$$$ units of paint to paint. They both also have an infinite amount of paint. The game for today will consist of painting a bit of that fence.
To try and make it fair, Nishikata has planned a few rules.
Nishikata's rules are as follows:
1. When painting, the two of them will only ever paint a contiguous interval of fenceposts.
2. He will pick a fencepost $$$n$$$, and he gets to paint that fencepost no matter what.
3. To minimize teasing, he will pick a segment of fenceposts that are disjoint from the fenceposts Takagi picks. In other words, he and Takagi will not ever paint the same fencepost.
As Takagi plays the game, she won't tell Nishikata, but she will follow these rules:
1. She will make the game end in a draw by making sure she and Nishikata will paint the same amount.
Takagi already knows how the game will end up, but you do not. So given the integer $$$n$$$ that Nishikata picks in rule $$$2$$$, find any two intervals $$$[a, b]$$$ that Nishikata paints and $$$[c, d]$$$ that Takagi paints that does not break either of their rules.
You will answer $$$T$$$ testcases $$$(1 \leq T \leq 10^4)$$$. Each testcase contains an integer $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ corresponding to the fencepost Nishikata picks in rule $$$2$$$.
Output four integers $$$a, b, c, d$$$ where $$$[a, b]$$$ denotes the fenceposts Nishikata paints and $$$[c, d]$$$ denotes the fenceposts Takagi paints. It can be proven an answer always exists and it satisfies $$$(1 \leq a, b, c, d \lt 2^{31})$$$.
These two intervals must be disjoint and sum of $$$[a ... b]$$$ should be equal to sum of $$$[c ... d]$$$. Also $$$(a \leq n \leq b)$$$ must hold.
If there are multiple solutions, output any.
2 1 9
1 3 6 6 9 9 4 5
Note that $$$1, 2, 3, 3$$$ is also a valid output for the first sample while $$$1, 5, 4, 6$$$ is not.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Novice 4
You are given two strings of equal length, $$$A$$$ and $$$B$$$. Two strings are considered $$$\small \textit{alike}$$$ if they contain the same count of each letter they possess. Note that two strings can be $$$\small \textit{alike}$$$ even if they are not exactly equal. Your goal is to find the minimum number of letters that need to be changed in $$$A$$$ in order for the two strings to be considered $$$\small \textit{alike}$$$.
The first line of input will be an integer $$$N$$$ ($$$1 \leq N \leq 10^4$$$), denoting the length of both of the strings.
Then the next two lines will contain two lowercase space-separated strings $$$A$$$ and $$$B$$$.
The output should be an integer representing the minimum number of letters needing to be changed in $$$A$$$ for the two strings to be considered $$$\small \textit{alike}$$$.
5 abced abcdf
1
The string $$$\text{abced}$$$ and $$$\text{abcdf}$$$ have one character they don't have in common, which is $$$\text{e}$$$. Therefore, only one change is necessary for $$$\text{abced}$$$ and $$$\text{abcdf}$$$ to be considered $$$\small \textit{alike}$$$: change $$$\text{e}$$$ to an $$$\text{f}$$$.
$$$---------------------------------------------$$$
Problem Idea: Spark
Problem Preparation: Spark
Occurrences: Novice 3
Misaka had an $$$n$$$ by $$$m$$$ grid of kangaroos. She also had a string $$$s$$$ of instructions which were all L, R, D, or U.
If the current instruction was L, a kangaroo on spot $$$x, y$$$ would move to $$$\max(1, x-1), y$$$
If the current instruction was R, a kangaroo on spot $$$x, y$$$ would move to $$$\min(n, x+1), y$$$
If the current instruction was D, a kangaroo on spot $$$x, y$$$ would move to $$$x, \max(1, y-1)$$$
If the current instruction was U, a kangaroo on spot $$$x, y$$$ would move to $$$x, \min(m, y+1)$$$
A given instruction will be followed by all kangaroos on the board. If two kangaroos end up on the same spot, they will move together for all of the following instructions.
Initially there is a kangaroo on every cell $$$x, y$$$ such that $$$(1 \leq x \leq n), (1, \leq y, \leq m)$$$. After the instruction string $$$s$$$ was executed, every kangaroo was gathered on the same cell.
Unfortunately, Misaka has forgotted the original size of the grid $$$n$$$ and $$$m$$$! Luckily, she still remembers the instruction string $$$s$$$ and would like you to find the maximum area of the original grid.
The first line will be one integer $$$T$$$ denoting the number of testcases $$$(1 \leq T \leq 100)$$$. Each of the following $$$T$$$ lines will contain an integer $$$n$$$ denoting the length of the instruction string followed by a string $$$s$$$ denoted the instruction string $$$(1 \leq n \leq 10^6)$$$. It is guaranteed that the sum of $$$n$$$ over all testcases is less than $$$10^6$$$.
You will output $$$T$$$ lines. Each line will contain one integer denoting the maximum area of a grid that guarantees after the instruction string $$$s$$$ is executed all the kangaroos are on the same spot.
4 1 L 3 LDL 8 RLDULULU 4 LRUD
2 6 16 4
In the first sample, the kangaroos on (1, 1) will all move to (1, 2) on a 1x2 board. It can be proven no better area exists.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Novice 5, Intermediate 2
Allie is given a list of $$$n$$$ numbers, $$$a_1, a_2, \ldots, a_n$$$. She is given $$$m$$$ conditions, $$$b_1, b_2, \ldots, b_m$$$, denoting that the list should be modified to contain $$$b_i$$$ occurrences of the number $$$i$$$. Allie can add or subtract $$$1$$$ from an element in the list, both operations having $$$1$$$ cost. Help her find the minimum cost needed to modify the list to satisfy the conditions.
The first line contains two integers, $$$n$$$ ($$$1 \leq n \leq 10^5$$$), and $$$m$$$ ($$$1 \leq m \leq 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).
The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq n$$$).
It is guaranteed that $$$\sum b_i = n$$$.
Output a single integer, the minimum cost needed to modify the list to satisfy the conditions.
5 3 2 2 1 2 2 2 2 1
2
One solution is to subtract $$$1$$$ from the $$$1$$$st element and add $$$1$$$ to the $$$2$$$nd element, with a total of $$$2$$$ cost. The resulting sequence is $$$1$$$ $$$3$$$ $$$1$$$ $$$2$$$ $$$2$$$, which contains $$$2$$$ $$$1$$$'s, $$$2$$$ $$$2$$$'s, and $$$1$$$ $$$3$$$, satisfying all the conditions. There is no way to fulfill the conditions with less cost, so the answer is $$$2$$$.
$$$---------------------------------------------$$$
Problem Idea: Mantlemoose
Problem Preparation: Mantlemoose
Occurrences: Novice 7
You've just challenged Soma to a shokugeki (food war)! The winner gets to hold hands with their favorite waifu!
In order to win, you need to craft the tastiest meal using $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ ingredients. The umami of the $$$i$$$th ingredient is $$$U_i$$$ and the sweetness of the $$$i$$$th ingredient is $$$S_i$$$ $$$(1 \leq U_i,\, S_i \leq 10^9)$$$.
To make the tastiest meal, the ratio of umami and sweetness is important. More specifically, for each ingredient, you need to make $$$U_i = K \cdot S_i$$$ $$$(1 \leq K \leq 10^4)$$$. In one second, you can choose either the umami or sweetness of a single ingredient and either increase or decrease it by $$$1$$$.
Find the minimum amount of time you need to make the tastiest meal.
The first line contains $$$2$$$ integers, $$$N,\, K$$$.
The next $$$N$$$ lines describe the ingredients. The $$$i$$$th of which contains $$$2$$$ integers, $$$U_i,\, S_i$$$.
Print the minimum amount of time you need to make the tastiest meal.
2 5 5 1 9 3
2
For the $$$1$$$st ingredient of the example, you don't change the umami or sweetness. Now, $$$U_1 = 5$$$ and $$$K \cdot S_1 = 5 \cdot 1 = 5$$$, so $$$U_1 = K \cdot S_1$$$. You spent $$$0$$$ seconds changing the umami and sweetness of the $$$1$$$st ingredient.
For the $$$2$$$nd ingredient of the example, you can spend a second increasing $$$U_2$$$ from $$$9$$$ to $$$10$$$. Then, you can spend another second decreasing $$$S_2$$$ from $$$3$$$ to $$$2$$$. Now, $$$U_2 = 10$$$ and $$$K \cdot S_2 = 5 \cdot 2 = 10$$$, so $$$U_2 = K \cdot S_2$$$. You spent $$$2$$$ seconds changing the umami and sweetness of the $$$2$$$nd ingredient.
In total, you spent $$$0 + 2 = 2$$$ seconds making the tastiest meal, which is the minimum.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Novice 6, Intermediate 3, Advanced 2
There is an ocean in a cartesian plane ranging from ($$$0, 0$$$) to ($$$M, N$$$). On some of the integer coordinates of this cartesian plane there are islands. All the islands are owned by either Alex, Bossologist, or Codicon. Alex wants to build as many different ziplines from any of his islands to any of Bossologist's islands as possible. Here are the conditions for making a zipline:
A zipline must be a straight line, starting from one of Alex's islands and ending at one of Bossologist's islands. It must not cross any of Codicon's islands. A zipline can pass through any of Alex or Bossologist's other islands. A zipline is considered different from another if either the starting point or the ending point is different.
There will be two space-separated integers $$$1 \leq M \leq 120$$$ and $$$1 \leq N \leq 120$$$. The cartesian plane will range from $$$(0, 0)$$$ to $$$(M, N)$$$. Thus, there will be $$$M+1$$$ lines of $$$N+1$$$ space-separated characters, which will be either $$$A$$$, $$$B$$$, $$$C$$$, or $$$W$$$. $$$A$$$ represents Alex-owned islands, $$$B$$$ represents Bossologist-owned islands, $$$C$$$ represents Codicon-owned islands, and $$$W$$$ represents the water (ocean).
The output will be an integer showing the number of different ziplines that can be created satisfying the conditions.
2 2 A A A C C W B B B
5
There are $$$5$$$ different ziplines. For the first $$$A$$$ island located at ($$$0, 0$$$), there is one $$$B$$$ island it can reach, ($$$2, 1$$$). For the second $$$A$$$ island located at ($$$0, 1$$$), there are two $$$B$$$ islands, ($$$2, 0$$$) and ($$$2, 2$$$). For the final $$$A$$$ island located at ($$$0, 2$$$), there are also two ziplines that can reach an island $$$B$$$, ($$$2, 1$$$) and ($$$2, 2$$$). Thus the answer is $$$1 + 2 + 2 = 5$$$.
$$$---------------------------------------------$$$
Problem Idea: Spark
Problem Preparation: Spark/Codicon
Occurrences: Novice 8, Advanced 3
As a student of U.A., it's important for you to conduct villain threat analysis. So, your sadistic teacher, Midnight, assigned you a painful homework assignment.
She gives you an $$$N$$$ by $$$M$$$ $$$(1\leq N \leq 500,$$$ $$$1 \leq M \leq 500)$$$ city $$$A$$$ describing villains. The danger of the villain in the $$$i$$$th row and $$$j$$$th column is given by $$$A_{ij}$$$ $$$(1 \leq A_{ij} \leq 10^9)$$$.
The threat level of $$$k$$$ villains with danger $$$d_1, d_2, \dots, d_k$$$ is $$$d_1 \mid d_2 \mid \dots \mid d_k$$$, where $$$\mid$$$ is the bitwise OR operator.
Your late (Mid)night assignment is to answer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ questions of the form $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$ $$$(1 \leq X_1 \leq X_2 \leq N,\, 1 \leq Y_1 \leq Y_2 \leq M)$$$. For each question, find the threat level of the villains in the rectangular region of the city with top left corner at row $$$X_1$$$ and column $$$Y_1$$$ and bottom right corner at row $$$X_2$$$ and column $$$Y_2$$$.
The first line contains $$$3$$$ integers, $$$N$$$, $$$M$$$, $$$Q$$$.
The next $$$N$$$ lines describe the rows of the city. The $$$i$$$th of which contains $$$M$$$ integers, $$$A_{i1}, A_{i2}, \dots, A_{iM}$$$.
The next $$$Q$$$ lines describe the questions. The $$$i$$$th of which contains $$$4$$$ integers, $$$X_{1i}$$$, $$$Y_{1i}$$$, $$$X_{2i}$$$, $$$Y_{2i}$$$.
For each question, print the threat level on a separate line.
2 2 2 1 2 3 4 1 1 1 2 1 1 2 2
3 7
For the first question of the example, the threat level is $$$1 \mid 3 = 3$$$.
For the second question of the example, the threat level is $$$1 \mid 2 \mid 3 \mid 4 = 7$$$.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Novice 10, Intermediate 5
After chessbot bugged PurpleCrayon for too long to share the proof for P=NP, PurpleCrayon decided to leave the team! Now he has to find good and original problem ideas and flavor text...
However, it seems that most participants from the last contest found $$$P=NP$$$ to be too easy, so chessbot has buffed the problem to be harder!
Define $$$F(x, y)$$$ as the total number of pairs $$$n, p$$$ $$$(0 \leq n \leq x, 0 \leq p \leq y)$$$ such that $$$p = n \cdot p$$$.
Chessbot wants you to find $$$\prod_{i = 1}^{N} \prod_{j = 1}^{P} F(i, j)$$$ for a given $$$N, P$$$. Since this number may be very large, please find it modulo $$$10^9 +7$$$.
The first line containers an integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$. Each of the next $$$T$$$ lines contains two integers $$$N, P$$$ $$$(1 \leq N, P \leq 3 \cdot 10^5)$$$ corresponding product chessbot wants you to compute. It is guaranteed that the sum of $$$N$$$ does not exceed $$$3 \cdot 10^5$$$ and that the sum of $$$P$$$ does not exceed $$$3 \cdot 10^5$$$.
Output $$$T$$$ lines, one integer per line, denoting the desired product modulo $$$10^9 +7$$$.
3 1 1 2 2 33 66
3 240 387366933
$$$F(1, 1) = 3$$$ for pairs $$$(0, 0), (1, 0), (1, 1)$$$. So the answer for the first testcase is $$$3$$$.
$$$F(1, 1) = 3, F(2, 1) = 4, F(1, 2) = 4, F(2, 2) = 5$$$. The product for those $$$4$$$ numbers is $$$240$$$ which is the answer.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Novice 9, Intermediate 4
Goma has asked Peach to play a little game. Goma has put $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) face up cards in a circle labeled $$$1$$$ to $$$N$$$ clockwise where the $$$i$$$th card has the number $$$a_i$$$ on it ($$$1 \leq a_i \leq 10^9$$$). Goma simply tells Peach to pick a number $$$k$$$ from $$$1$$$ to $$$N$$$ inclusive, and to take a sum of the cards in the following fashion: To begin, flip the first card face down. Then go $$$k$$$ cards clockwise and if the card is face up, flip it face down and continue the process, otherwise stop. Then take the sum of all the face down cards. Peach is curious and would like to know what sum they would get for each $$$k$$$ from $$$1$$$ to $$$N$$$.
The first line contains $$$N$$$.
The next line contains $$$N$$$ integers denoting $$$a_1, a_2,...,a_N$$$.
Test case 1 is the sample and will not be worth points.
Test case 2-4: $$$N \leq 1000$$$
Test cases 5-21: No further constraints
Output $$$N$$$ lines, where the $$$i$$$th line is the resulting sum when Goma chooses $$$k = i$$$.
5 1 2 3 4 5
15 15 15 15 1
If $$$k = 2$$$, and $$$N = 5$$$, Peach would flip the 1st card face down, then the 3rd, then the 5th, then the 2nd, then the 4th, then stop since the 1st card is already face down. Since all the cards are face down the sum we get is $$$1 + 2 + 3 + 4 + 5 = 15$$$.
$$$---------------------------------------------$$$
Problem Idea: Bossologist
Problem Preparation: Bossologist
Occurrences: Intermediate 8, Advanced 6
Codicon has gotten into gambling (uh oh!). He plays a game containing $$$3 \leq N \leq 2 \cdot 10^5$$$ players (including himself) seated in a circle in positions $$$1$$$ to $$$N$$$ going clockwise, where Codicon is in the first position. At the beginning of the game, each player is assigned a number, and during each of $$$1 \leq R \leq 2 \cdot 10^5$$$ rounds two selected players (that are not Codicon) switch spots. Codicon then bets a certain amount of money $$$b$$$ in each round that his number is below at least half of the other people who are at most $$$K$$$ seats away from him ($$$1 \leq K \lt \left\lceil \frac{N}{2} \right\rceil$$$). If he wins the bet he gets $$$b$$$ $$$(1 \leq b \leq 10^6)$$$ dollars, otherwise he loses $$$b$$$ dollars.
In addition, since Codicon is the person that is betting, in each round his number changes before he bets. Given that he starts with $$$M$$$ $$$(1 \leq M \leq 10^9)$$$ dollars output the amount of money he ends up with after all $$$R$$$ rounds, if he loses all his money or goes into debt, output "BANKRUPT" and the round number in which he lost his money (i.e. If Codicon goes bankrupt on the third round output BANKRUPT 3).
The first line contains $$$N, R, M, K$$$ in that order.
The next line has $$$N$$$ integers, corresponding to the assigned number $$$a_i$$$ $$$(1 \leq a_i \leq N)$$$ each player gets.
The last $$$R$$$ lines each have $$$s_r, t_r, n_{r}, b_r$$$, where in the $$$r$$$th round, the players in spots $$$s_r$$$ and $$$t_r$$$ $$$(s_r \neq t_r$$$ and $$$s_r, t_r \neq 1)$$$ are swapped, Codicon is assigned the number $$$n_{r}$$$ $$$(1 \leq n_{r} \leq N)$$$, and he bets $$$b_r$$$ dollars for that round.
Test case 1 is the sample and will not be worth points.
Test cases 2-4: $$$N \leq 1000$$$
Test cases 5-21: No further restrictions
A single integer that shows how much money Codicon ended up with after he finished all the rounds, or if he loses all his money output "BANKRUPT" and the round number in which he lost all his money (i.e. BANKRUPT 3).
5 3 200 1 2 3 1 4 4 2 3 5 10 4 2 2 40 4 5 3 30
260
Note that since $$$K = 1$$$, Codicon looks to the people sitting next to him to see if he won the bet. For the first round, players in position $$$2$$$ and $$$3$$$ switch places and Codicon's number switches to $$$5$$$, which is greater than the number of both people sitting next to him ($$$4$$$ and $$$1$$$), so he loses $$$10$$$ dollars. He then wins the next two rounds, so he ends up with $$$260$$$ dollars.
$$$---------------------------------------------$$$
Problem Idea: Bossologist
Problem Preparation: Bossologist
Occurrences: Intermediate 9, Advanced 5
Thomas has been caught game (again)! Instead of playing on a 2d grid, he is now playing on a multidimensional space that has no regard to fundamental axioms of geometry, more commonly known as a graph. Thomas is on a graph of $$$n$$$ nodes completely full with an undirected edge between all $$$u$$$ and $$$v$$$ such that $$$(1 \leq u \lt v \leq n)$$$. Teacher is trying to catch Thomas and has already blocked off $$$m$$$ of these edges.
Thomas is trying to run out of the graph before Teacher comes and catches him. Thomas is able to escape from a node if it has degree at most $$$1$$$ or there is at most $$$1$$$ edge out of it.
As it turns out, Teacher still has not used his secret weapon yet. Teacher has a powerful device that is able to delete $$$2$$$ nodes. When a node is deleted, all of the edges that go out of that node are removed from the graph.
Thomas now wants your help to help check if escaping from Teacher's grasp is possible. Thomas will ask you $$$q$$$ queries, where each query is two integers $$$a$$$ $$$b$$$. Thomas wants you to answer the total number of escapable nodes in the graph if Teacher deletes the nodes $$$a$$$ and $$$b$$$ with his machine.
The first line containers three integers $$$n$$$ $$$m$$$ $$$k$$$ $$$(2 \leq n \leq 2 \cdot 10^5), (1 \leq q \leq 2 \cdot 10^5), (0 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \cdot 10^5))$$$. The next $$$m$$$ lines contain two integers each $$$u$$$ $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$. It is guaranteed no edge will appear twice in the input. The following $$$q$$$ lines contain two integers each $$$a$$$ $$$b$$$ $$$(1 \leq a, b \leq n, a \neq b)$$$ denoting a query of Teacher deleting the nodes $$$a$$$ and $$$b$$$. All queries are independant, meaning Teacher does not actually delete any nodes, but rather we are considering the case if he hypothetically did.
You will output $$$q$$$ lines, the $$$i$$$'th line denoting the answer to the $$$i'th$$$ query.
5 3 2 1 2 2 4 4 5 1 2 4 1
2 0
In the first query, the escapable nodes are $$$4$$$ and $$$5$$$.
In the second query, there are no escapable nodes.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Intermediate 7, Advanced 7
Megumin is a small adventurer going on an expedition! Her world has $$$N+1$$$ ($$$N = 2^k-1, \, 0 \leq k \leq 30$$$) cities labeled from $$$0 \,...\, N$$$. There is a bidirectional road between every pair of cities. If Megumin wants to travel from city $$$i$$$ to city $$$j$$$, it takes her $$$i \oplus j \oplus N$$$ days because she needs to explode the enemies on the road. Here, $$$\oplus$$$ is the bitwise XOR operator. Megumin starts at city $$$A$$$ and wants to go to city $$$B$$$ ($$$0 \leq A, \, B \leq N$$$).
For a path $$$p$$$, define $$$\text{explosion}(p)$$$ to be the maximum of $$$p_i \oplus p_{i+1} \oplus N$$$ over all roads $$$p_i \rightarrow p_{i+1}$$$ on the path. If there are no roads on $$$p$$$, $$$\text{explosion}(p) = 0$$$. Find the minimum value of $$$\text{explosion}(p)$$$ amongst all paths $$$p$$$ from city $$$A$$$ to city $$$B$$$.
The first line contains one integer, $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. Then $$$T$$$ test cases follow.
The first and only line of each test case contains $$$3$$$ integers, $$$N, \, A, \, B$$$.
For each test case, print the minimum value of $$$\text{explosion}(p)$$$ amongst all paths $$$p$$$ from city $$$A$$$ to city $$$B$$$ on a separate line.
3 0 0 0 1 0 1 3 1 2
0 0 0
In the first test case of the example, Megumin starts at her finish city, so she does not traverse any roads. Hence the maximum is $$$0$$$.
In the second test case of the example, Megumin can travel directly from city $$$0$$$ to city $$$1$$$. For $$$p = 0 \rightarrow 1$$$, $$$\text{explosion}(p) = \max(0 \oplus 1 \oplus 1) = \max(0) = 0$$$.
In the third test case of the example, Megumin can travel directly from city $$$1$$$ to city $$$2$$$. For $$$p = 1 \rightarrow 2$$$, $$$\text{explosion}(p) = \max(1 \oplus 2 \oplus 3) = \max(0) = 0$$$. Note that Megumin could also take the path $$$q = 1 \rightarrow 3 \rightarrow 2$$$. However, $$$\text{explosion}(q)$$$ $$$= \max(1 \oplus 3 \oplus 3,\, 3 \oplus 2 \oplus 3)$$$ $$$= \max(1,\, 2) = 2$$$. This is not the minimum for a path from city $$$1$$$ to city $$$2$$$ because $$$\text{explosion}(p) = 0 \leq 2 = \text{explosion}(q)$$$.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Novice 11, Intermediate 6, Advanced 4
This is the hard version of the problem, the main difference is that Takagi has another rule she will follow.
Nishikata and Takagi are standing in front of an infinitely long fence. Fenceposts are numbered from $$$1$$$ to $$$\infty$$$ and fencepost $$$i$$$ costs $$$i$$$ units of paint to paint. They both also have an infinite amount of paint. The game for today will consist of painting a bit of that fence.
To try and make it fair, Nishikata has planned a few rules.
Nishikata's rules are as follows:
1. When painting, the two of them will only ever paint a contiguous interval of fenceposts.
2. He will pick a fencepost $$$n$$$, and he gets to paint that fencepost no matter what.
3. To minimize teasing, he will pick a segment of fenceposts that are disjoint from the fenceposts Takagi picks. In other words, he and Takagi will not ever paint the same fencepost.
As Takagi plays the game, she won't tell Nishikata, but she will follow these rules:
1. She will make the game end in a draw by making sure she and Nishikata will paint the same amount.
2. To still be able to tease Nishikata, she will minimize the minimum distance between their intervals.
Takagi already knows how the game will end up, but you do not. So given the integer $$$n$$$ that Nishikata picks in rule $$$2$$$, find any two intervals $$$[a, b]$$$ that Nishikata paints and $$$[c, d]$$$ that Takagi paints that does not break either of their rules.
You will answer $$$T$$$ testcases $$$(1 \leq T \leq 10^4)$$$. Each testcase contains an integer $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ corresponding to the fencepost Nishikata picks in rule $$$2$$$.
In the subtask descriptions, tests are numbered $$$1$$$ to $$$20$$$ with the sample skipped.
Test $$$1$$$ will be every number from $$$1$$$ to $$$10^4$$$.
Tests $$$2 - 10$$$ will satisfy that $$$n \leq 10^6$$$.
Output four integers $$$a, b, c, d$$$ where $$$[a, b]$$$ denotes the fenceposts Nishikata paints and $$$[c, d]$$$ denotes the fenceposts Takagi paints. It can be proven an answer always exists and it satisfies $$$(1 \leq a, b, c, d \lt 2^{31})$$$.
These two intervals must be disjoint and sum of $$$[a ... b]$$$ should be equal to sum of $$$[c ... d]$$$. Also $$$(a \leq n \leq b)$$$ must hold.
Since this is the hard version $$$\min(|b - c|, |a - d|)$$$ must be minimized. Your solution will be considered correct if the code's minimum distance between the two intervals is no more than what the judger has as the minimum distance between the two intervals.
2 1 9
1 2 3 3 9 12 13 15
For the second testcase, $$$9, 9, 4, 5$$$ would have worked except the minimum distance then is $$$4$$$ whereas for $$$9, 12, 13, 15$$$ the minimum distance is $$$1$$$. Since the two intervals must be disjoint, it is impossible to do better than $$$1$$$ as the minimum distance between the two intervals.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Intermediate 10, Advanced 8
I Couldn't Solve The USACO Bronze Problems My Teacher Gave Me, So I Got Reincarnated As A Lazy 3D Self-Balancing Persistent Segment Tree!
The new world you have been isekai'ed into has no shortage of red pandas that like to munch on apples, turnips, or potatoes. There are cows that go "moo.", and within 3366 STEps of every town square, someone is selling lunchboxes of crayons and skittles. There are happy dacs and cosy blobs living in Farmer Johns $$$10^5$$$ fields.
To get into the most prestigious school of all, "Everule Classes", you must demonstrate your capabilities.
There is an array with $$$n$$$ elements initially all set to $$$0$$$. You have to support the following two operations:
Operation of type $$$1$$$: set the values in the range $$$[l, r]$$$ to be $$$x$$$
Operation of type $$$2$$$: roll back the array to be what it was after the $$$k$$$'th update. if $$$k = 0$$$, restore the array to the initial state of all $$$0$$$'s.
After each update, you are given an integer $$$d$$$ and you have to print $$$$$$ \sum_{i = 1}^{n} a[i]^d $$$$$$ Since this value may be very large, please find it modulo $$$10^9 +7$$$.
The first line contains two integers $$$n, q$$$ $$$(1 \leq n \leq 10^6, 1\ \leq q \leq 10^5)$$$.
The next $$$q$$$ lines contain $$$q$$$ queries in the format of $$$1$$$ $$$d$$$ $$$l$$$ $$$r$$$ $$$x$$$ if it is operation $$$1$$$ or $$$2$$$ $$$d$$$ $$$k$$$ if it is operation $$$2$$$.
For all operation $$$1$$$'s: $$$(1 \leq l \leq r \leq n, 1 \leq x \leq 10^9)$$$.
For all operation $$$2$$$'s: $$$(0 \leq k \lt i)$$$ if it is the $$$i$$$'th query. queries are indexed starting from $$$1$$$.
For all operations $$$(1 \leq d \leq 10)$$$.
Note that all of the types of operation of the query, the interval of an operation type 1, and the version restored to of an operation type 2 are all randomly generated. The only dependent variables are $$$n$$$, $$$q$$$, the maximum value of $$$d$$$, the maximum value of $$$x$$$, and the total number of operations type 2.
If you do not trust me on this, the (poorly written) generator is linked here.
For subtasks, tests are numbered from $$$1$$$ to $$$20$$$ with the sample skipped.
Tests $$$1 - 3$$$ will have no rollback operations.
Tests $$$4 - 6$$$ will have $$$d = 1$$$ in all operations.
Output $$$q$$$ lines, the sum of $$$d$$$'th powers of the entire array.
5 5 1 2 1 3 2 1 2 3 3 1 2 1 1 1 2 4 4 1 2 1 3
12 9 6 13 6
There is initially an array of $$$[0, 0, 0, 0, 0]$$$.
After the first operation, the array becomes $$$[2, 2, 2, 0, 0]$$$ and the sum of squares is $$$2^2 + 2^2 + 2^2 + 0^2 + 0^2$$$ or $$$12$$$.
After the second operation, the array becomes $$$[2, 2, 1, 0, 0]$$$ and the sum of squares is $$$9$$$.
After the third operation, the array is restored to what it was after operation one, so it is $$$[2, 2, 2, 0, 0]$$$. $$$2^1 + 2^1 + 2^1 + 0^1 + 0^1$$$ is $$$6$$$.
After the fourth operation, the array becomes $$$[2, 2, 2, 1, 0]$$$ and the sum of squares is $$$13$$$.
After the fifth operation, the array is restored to what it was after the third operation, so it is $$$[2, 2, 2, 0, 0]$$$ and the sum of $$$6$$$.
$$$---------------------------------------------$$$
Problem idea: 3366
Problem preparation: 3366
Occurrences: Intermediate 12, Advanced 10
The year is 2022, and the virtual reality massively multiplayer online role-playing game called Sword Art Online has just been released. This next generation world of the metaverse is nearly indistinguishable from reality.
Kirito just had a blast gamin in the world. However, when he tries to logout, he realizes he forgot his password! Luckily, Kirito knows his password has some peculiar properties:
- His password consists of $$$N$$$ $$$(1 \leq N \leq 10^7)$$$ numbers in a row.
- Each number is an integer from $$$0$$$ to $$$M$$$ inclusive $$$(1 \leq M \leq 10^6)$$$.
- The password contains at least $$$1$$$ non-zero number.
- There are at least $$$K$$$ $$$(1 \leq K \leq 10)$$$ zeros between any pair of non-zero numbers.
- The $$$\gcd$$$ of all non-zero numbers is $$$1$$$.
Kirito wants you to find how many passwords could be his. Of course, Kirito hasn't touched grass in quite a while, so he also doesn't know this number can be quite large. Thus, find the number$$$\mod 10^9 + 7$$$.
The first and only line contains $$$3$$$ integers, $$$N$$$, $$$M$$$, $$$K$$$.
Print the number of passwords that could be Kirito's$$$\mod 10^9 + 7$$$.
3 2 1
6
For the example, $$$6$$$ passwords could be Kirito's: $$$(1,\; 0,\; 0)$$$, $$$(0,\; 1,\; 0)$$$, $$$(0,\; 0,\; 1)$$$, $$$(1,\; 0,\; 1)$$$, $$$(2,\; 0,\; 1)$$$, or $$$(1,\; 0,\; 2)$$$.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Advanced 11
Codicon has been hired as an assistant at a quantum physics research lab! The lab consists of $$$n$$$ rooms connected by $$$n - 1$$$ bidirectional passageways, so that every room is reachable from any other room. That is, the lab is a tree.
Codicon wants to place quantum particle generators in some rooms and then find out how much energy can be detected in other rooms. The lab is initially empty with no generators in any room. Each quantum generator emits particles that travel through the passageways such that exactly one particle reaches every other room. Quantum particles start off with no energy and gain $$$1$$$ unit of energy for every passageway they go through, but they also follow a curious rule. Due to quantum fluctuations, a particle will only be detected if it is an even distance away from the generator that created the particle.
Codicon conducts $$$m$$$ operations of two types. The $$$1$$$st type is adding $$$x_m$$$ quantum particle generators to a room $$$a_m$$$. The $$$2$$$nd type is a query, asking for the amount of energy detected in the room $$$a_m$$$.
The first line contains two numbers $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$ and $$$m$$$ $$$(1 \leq m \leq 5 \cdot 10^5)$$$.
The next $$$n - 1$$$ lines each contain two numbers, $$$a$$$ and $$$b$$$ describing a bidirectional passageway between rooms $$$a$$$ and $$$b$$$. $$$(1 \leq a, b \leq n)$$$
The next $$$m$$$ lines denote the operations. The first number of each line denotes the type of operation.
If the number is $$$1$$$, it is followed by two numbers $$$a$$$ and $$$x$$$, denoting that $$$x$$$ generators are added to room $$$a$$$. $$$(1 \leq a \leq n, 1 \leq x \leq 10^6)$$$
If the number is $$$2$$$, it is followed by a number $$$a$$$, representing a query for the amount of energy that will be detected in room $$$a$$$. $$$(1 \leq a \leq n)$$$
For $$$25\%$$$ of cases that count for points $$$(1 \leq n, m \leq 5000)$$$
For each operation of the $$$2$$$nd type, output a single number denoting the amount of energy detected in the queried room.
5 4 1 2 1 3 2 4 2 5 1 1 2 1 2 2 2 4 2 3
4 4
The $$$1$$$st operation adds $$$2$$$ generators to room $$$1$$$.
The $$$2$$$nd operation adds $$$2$$$ generators to room $$$2$$$.
For the $$$3$$$rd operation, room $$$4$$$ is distance $$$2$$$ away from room $$$1$$$, so each particle from room $$$1$$$ has energy $$$2$$$ when it reaches room $$$4$$$. Since there are $$$2$$$ generators in room $$$1$$$, there is $$$4$$$ energy detected total. Room $$$4$$$ is distance $$$1$$$ from room $$$2$$$, so the particles emitted from the generators in room $$$2$$$ aren't detected and don't add to the energy.
For the $$$4$$$th operation, room $$$3$$$ is distance $$$2$$$ away from room $$$2$$$, so the particles from the generators in room $$$2$$$ each have $$$2$$$ energy when they reach $$$3$$$, for a total of $$$4$$$ energy. Room $$$1$$$ is $$$1$$$ away so the particles from it aren't detected.
$$$---------------------------------------------$$$
Problem Idea: Mantlemoose
Problem Preparation: Mantlemoose
Occurrences: Advanced 12
At Gin-chan's Odd Jobs, Gintoki and his crew will do any job! Whether it be finding lost giant alien pets for aliens, tiling roofs, or running a hair salon, they do it all.
The city of Edo is represented as a $$$3 \cdot 10^6 \times 3 \cdot 10^6$$$ square grid initially containing no jobs. There are $$$N$$$ $$$(1 \leq N \leq 700)$$$ Amanto (space aliens) who are paying for jobs in Edo. The $$$i$$$th Amanto goes through each location $$$(r, c)$$$ such that $$$X_{1,\,i} \leq r \leq X_{2,\,i}$$$ and $$$Y_{1,\,i} \leq c \leq Y_{2,\,i}$$$ $$$(1 \leq X_{1,\,i} \leq X_{2,\,i} \leq 3 \cdot 10^6$$$ and $$$1 \leq Y_{1,\,i} \leq Y_{2,\,i} \leq 3 \cdot 10^6)$$$. If there is not a job at $$$(r,c)$$$, she posts one worth $$$A_i$$$ $$$(1 \leq A_i \leq 1000)$$$ yen. Otherwise, she still wants the job done, so she increases the job's worth by $$$A_i$$$ yen.
To complete the jobs, Gintoki and his crew, $$$M$$$ $$$(1 \leq M \leq 10^6)$$$ people in total, are each assigned a region. The $$$i$$$th person is assigned all locations $$$(r, c)$$$ such that $$$X_{1,\,B_i} \leq r \leq X_{1,\,D_i}$$$ and $$$Y_{1,\,C_i} \leq c \leq Y_{1,\,E_i}$$$ $$$(1 \leq B_i, C_i, D_i, E_i \leq N$$$, $$$X_{1,\,B_i} \leq X_{1,\,D_i}$$$, and $$$Y_{1,\,C_i} \leq Y_{1,\,E_i})$$$.
Let a team be composed of at least $$$1$$$ person. This team goes to each location such that the people assigned to the location are exactly equal to the people on the team. For each location, if there is a job, they do it. The team earns $$$v$$$ yen after completing a job worth $$$v$$$ yen.
Over all possible teams that complete at least $$$1$$$ job, Gintoki wants to find the team with the highest average job worth. If there are multiple, he wants any amongst these teams which earned the most yen. Then, he wants to know how much yen this team earned so he can force them to pay for his Shonen Jump and strawberry milk. However, that's not his job, it's yours!
The first line contains $$$2$$$ integers, $$$N$$$, $$$M$$$.
The next $$$N$$$ lines describe the Amanto. The $$$i$$$th of which contains $$$5$$$ integers, $$$X_{1,\,i}$$$, $$$Y_{1,\,i}$$$, $$$X_{2,\,i}$$$, $$$Y_{2,\,i}$$$, $$$A_i$$$.
The final $$$M$$$ lines describe Gintoki and his crew. The $$$i$$$th of which contains $$$4$$$ integers, $$$B_i$$$, $$$C_i$$$, $$$D_i$$$, $$$E_i$$$.
Print how much yen the team with the highest average job worth earned.
3 2 1 2 2 4 3 1 4 1 4 1 1 1 1 2 2 1 1 3 2 3 3 2 1
5
Example Explanation:
$$$---------------------------------------------$$$
Person $$$1$$$ is assigned locations $$$(r,c)$$$ such that $$$X_{1,\,1} \leq r \leq X_{1,\,3}$$$ and $$$Y_{1,\,1} \leq c \leq Y_{1,\,2}$$$ $$$=$$$ $$$(1,2)$$$, $$$(1,3)$$$, and $$$(1,4)$$$.
Person $$$2$$$ is assigned locations $$$(r,c)$$$ such that $$$X_{1,\,3} \leq r \leq X_{1,\,2}$$$ and $$$Y_{1,\,3} \leq c \leq Y_{1,\,1}$$$ $$$=$$$ $$$(1,1)$$$ and $$$(1,2)$$$.
$$$---------------------------------------------$$$
Denote $$$\{a,b,\dots,c\}$$$ as the team with person $$$a$$$, person $$$b$$$, ... person $$$c$$$.
Team $$$\{1\}$$$ completed the jobs at locations $$$(1, 3)$$$ and $$$(1,4)$$$. Thus, the team earned $$$3 + 4 = 7$$$ yen and completed $$$2$$$ jobs. Team $$$\{1\}$$$ has an average job worth of $$$\frac{7}{2} = 3.5$$$ yen.
Team $$$\{2\}$$$ completed the job at location $$$(1,1)$$$. Thus, the team earned $$$2$$$ yen and completed $$$1$$$ job. Team $$$\{2\}$$$ has an average job worth of $$$\frac{2}{1} = 2$$$ yen.
Team $$$\{1,2\}$$$ completed the job at location $$$(1,2)$$$. Thus, the team earned $$$5$$$ yen and completed $$$1$$$ job. Team $$$\{1,2\}$$$ has an average job worth of $$$\frac{5}{1} = 5$$$ yen.
Team $$$\{1,2\}$$$ has the highest average job worth at $$$5$$$ yen. Since no other team has the same average, the answer is the amount of yen team $$$\{1,2\}$$$ made, $$$5$$$.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Advanced 9, Intermediate 11
Like most members of the JoJo bloodline, you've been bestowed a unique, miraculous ability. Your ability allows you to revert your enemy's actions to zero! You're currently battling a tough enemy.
Your enemy can be represented by a directed graph. Nodes represent actions and each action has an effect. The effect of the $$$i$$$th action is $$$E_i$$$ $$$(1 \leq E_i \leq 10^5)$$$. There is an edge from action $$$u$$$ to action $$$v$$$ if $$$u$$$ influences $$$v$$$. At first, your enemy has $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ actions labeled from $$$1 \dots N$$$. Action $$$1$$$ influences actions $$$2 \dots N$$$.
Actions $$$2 \dots N$$$ are called foundational actions. Denote $$$foundation(x)$$$ as the set of foundational actions such there exists a path from each action to $$$x$$$. In particular, $$$foundation(1) = \{\}$$$ (the empty set) and $$$foundation(i) = \{i\}$$$ for all $$$i$$$ such that $$$2 \leq i \leq N$$$.
During your fight, $$$M$$$ $$$(1 \leq M \leq 10^5)$$$ events of $$$2$$$ types occur. The type of the $$$i$$$th event is $$$T_i$$$.
If $$$T_i = 1$$$, your enemy creates a new action $$$a_i$$$, where $$$a_i$$$ is the number of actions after creating $$$a_i$$$. $$$a_i$$$ is influenced by $$$K_i$$$ distinct actions, $$$B_{1,\, i}, B_{2,\, i}, \dots B_{K_i,\, i}$$$ $$$(1 \leq B_{j,\, i} \lt a_i)$$$. The sum of $$$K_i$$$ over all $$$i$$$ is $$$\leq 10^6$$$. It's guaranteed that $$$foundation(j) \neq foundation(a_i)$$$ for any action $$$j \neq a_i$$$. It's also guaranteed that for any proper subset $$$s$$$ of $$$foundation(a_i)$$$ (including the empty set), $$$s = foundation(B_{j,\, i})$$$ for some $$$j$$$ . Finally, it's also guaranteed that for any $$$j$$$, $$$foundation(B_{j,\, i}) = s$$$ for some proper subset $$$s$$$ of $$$foundation(a_i)$$$.
If $$$T_i = 2$$$, your enemy changes the effect of action $$$1$$$ to $$$C_i$$$ $$$(1 \leq C_i \leq 10^5)$$$. Then, you need to figure out the minimum total effort needed to revert your enemy's actions to zero (make $$$E_j = 0$$$ for all $$$j$$$). To use your ability, select an action $$$j$$$ that you have not selected before and an integer $$$x$$$ ($$$x$$$ can be negative). Then, add $$$x$$$ to the effect of $$$j$$$ and the effects of all actions $$$j$$$ influences. This takes $$$3 \cdot x^3 + 2 \cdot x^2 + x$$$ effort. You may use your ability any number of times. Your total effort is the sum of each effort. Note that you only find the minimum total effort and do not change any $$$E_j$$$.
The first line contains $$$2$$$ integers, $$$N$$$, $$$M$$$.
The second line contains $$$N$$$ integers, $$$E_1, E_2, \dots, E_N$$$.
The next $$$M$$$ lines describe the events, one event per line. The first integer of the $$$i$$$th line is $$$T_i$$$. If $$$T_i = 1$$$, then $$$E_{A_i}$$$, $$$K_i$$$, and $$$B_{1,\, i}, B_{2,\, i}, \dots, B_{K_i,\, i}$$$ follow. If $$$T_i = 2$$$, then $$$C_i$$$ follows.
For each event of type $$$2$$$, print the minimum total effort needed to revert your enemy's actions to zero$$$\mod 10^9 + 7$$$ on a separate line.
3 2 3 1 2 1 1 3 1 3 2 2 1
2
For the example, your enemy starts with $$$3$$$ actions and there are $$$2$$$ events. Action $$$1$$$ has effect $$$3$$$, action $$$2$$$ has effect $$$1$$$, and action $$$3$$$ has effect $$$2$$$. Action $$$1$$$ influences actions $$$2$$$ and $$$3$$$, which are foundational actions.
$$$---------------------------------------------$$$
Since the $$$1$$$st event is of type $$$1$$$, your enemy creates an action. Action $$$4$$$ is created with effect $$$1$$$, and it is influenced by actions $$$1$$$, $$$3$$$, and $$$2$$$. $$$foundation(4) = \{2, 3\}$$$, $$$foundation(B_{1,\, 1}) = foundation(1) = \{\}$$$, $$$foundation(B_{2,\, 1}) = foundation(3) = {3}$$$, and $$$foundation(B_{3,\, 1}) = foundation(2) = \{2\}$$$.
Thus, for any proper subset $$$s$$$ of $$$foundation(4) =$$$ $$$\{\}$$$, $$$\{2\}$$$, or $$$\{3\}$$$, $$$s = foundation(B_{j,\, 1})$$$ for some $$$j =$$$ $$$1$$$, $$$2$$$, or $$$3$$$. Furthermore, for any $$$j =$$$ $$$1$$$, $$$2$$$, or $$$3$$$, $$$foundation(B_{j,\, 1}) = s$$$ for some proper subset $$$s$$$ of $$$foundation(4) =$$$ $$$\{\}$$$, $$$\{2\}$$$, or $$$\{3\}$$$.
$$$---------------------------------------------$$$
Since the $$$2$$$nd event is of type $$$2$$$, you need to find the minimum total effort needed to revert your enemy's actions to zero. Your enemy changes the effect of action $$$1$$$ to $$$1$$$. Here's one way to achieve the minimum effort:
Right now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[1,\, 1,\, 2,\, 1]$$$.
Use your ability on action $$$3$$$ and choose $$$x = -1$$$. This takes $$$3\cdot{(-1)}^3 + 2\cdot{(-1)}^2 -1 = -2$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[1,\, 1,\, 1,\, 0]$$$.
Then, use your ability on action $$$1$$$ and choose $$$x = -1$$$. This takes $$$3\cdot{(-1)}^3 + 2\cdot{(-1)}^2 -1 = -2$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[0,\, 0,\, 0,\, -1]$$$.
Finally, use your ability on action $$$4$$$ and choose $$$x = 1$$$. This takes $$$3\cdot1^3 + 2\cdot1^2 + 1 = 6$$$ effort. Now, $$$[E_1,\, E_2,\, E_3,\, E_4] =$$$ $$$[0,\, 0,\, 0,\, 0]$$$, so you've successfully reverted your enemy's actions to zero.
$$$---------------------------------------------$$$
In total, you took $$$-2 -2 + 6 = 2$$$ effort.
$$$---------------------------------------------$$$
Problem Idea: codicon
Problem Preparation: codicon
Occurrences: Advanced 13