Thanks to everyone who participated!
Cast
Problem A (Product Triplets): Written by Akashdeep Nain and prepared by Satyaki Upadhyay.
Problem B (Combining Classes): Written by and prepared by Jonathan Irvin Gunawan.
Problem C (Cave Escape): Written by Zhang Chen and prepared by Kevin Tran.
Solutions, other problem preparation, reviews and contest monitoring by Akashdeep Nain, Gary Sham, Ian Tullis, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu and Satyaki Upadhyay.
Analysis authors:
Given N integers A1, A2, ..., AN, count the number of triplets (x, y, z) (with 1 ≤ x < y < z ≤ N) such that at least one of the following is true:
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the number of integers in array A. The second line consists of N integers Ai; the i-th of these is the value of the i-th integer, as described above.
For each test case, output one line containing Case #x: y, where x is
the test case number (starting from 1) and y is the number of triplets satisfying the
condition given in the problem statement.
1 ≤ T ≤ 30.
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
0 ≤ Ai ≤ 2 × 105, for all i.
3 ≤ N ≤ 200.
3 ≤ N ≤ 7000.
4 6 5 2 4 6 3 1 6 2 4 8 16 32 64 3 1 1 1 3 200000 200000 200000
Case #1: 1 Case #2: 6 Case #3: 1 Case #4: 0
In Sample Case #1, the only triplet satisfying the condition given in the problem statement is (2, 4, 5). The triplet is valid since the second, fourth, and fifth integers are 2, 6, and 3, and 2 × 3 = 6.
In Sample Case #2, the six triplets satisfying the condition given in the problem statement are: (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6).
In Sample Case #3, make sure you only count the triplet (1, 2, 3) once.
In Sample Case #4, there is no triplet satisfying the condition given in the problem statement since the product of any pair of integers in the array will not be in the array.
Supervin is teaching N classes, which are numbered from 1 to N. After giving his most recent exam, he noticed that in each of his classes, the test scores of his students form a sequence of consecutive integers. Therefore, Supervin can summarize the scores for the i-th class as two integers Li and Ri. This means that the i-th class has Ri - Li + 1 students, and for each x (Li ≤ x ≤ Ri), there is exactly one student with score x.
Supervin would like to combine the scores from the students from all of his classes and sort the scores in non-increasing order. He has Q questions (numbered from 1 to Q) about this list; for the i-th question, he wants to know what the Ki-th highest score is. (If Ki is greater than the number of students, then the answer for the i-th question is 0.)
Can you help Supervin answer all of his questions? Since there may be many answers, instead of outputting all of them, output proof that you have answered them: the sum of (Si × i) for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains four lines. The first line contains two integers N and Q as described above. The next three lines each contain six integers in the following format, respectively:
We define:
For each test case, output one line containing Case #x: y, where x is
the test case number (starting from 1) and y is the sum of (Si × i)
for all 1 ≤ i ≤ Q, where Si is the answer to the i-th question.
1 ≤ T ≤ 100.
Time limit: 180 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 4 × 105.
0 ≤ Ai < Mi, for all i.
0 ≤ Bi < Mi, for all i.
0 ≤ Ci < Mi, for all i.
0 ≤ X1 < M1.
0 ≤ X2 < M1.
0 ≤ Y1 < M2.
0 ≤ Y2 < M2.
0 ≤ Z1 < M3.
0 ≤ Z2 < M3.
1 ≤ Mi ≤ 109, for all i.
Q = 1.
1 ≤ Q ≤ 105.
2 5 1 3 1 4 1 5 9 2 7 1 8 2 9 4 8 15 16 23 42 7 1 2 3 4 5 6 31 1 3 4 5 5 17 2 2 1 3 2 100
Case #1: 7 Case #2: 28
In Sample Case #1, the generated arrays X, Y, Z are:
2 5 5 3 1 4 1 5 9 2 7 1 8 2 9 4 8 15 16 23 42 1 2 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 2
Case #1: 39 Case #2: 1
In Sample Case #1, every parameter is the same as Sample Case #1 except the value of Q. Therefore, the values of L and R, and the students' scores for all classes combined are still the same as Sample Case #1. However, the queries are now K = [5, 9, 40, 23, 12]. The students with the 5th, 9th, and 12th highest scores have scores of 7, 6, and 4, respectively. Since there are only 20 students, the 23rd and 40th students do not exist. Therefore, S = [7, 6, 0, 0, 4] and the answer is 7 × 1 + 6 × 2 + 0 × 3 + 0 × 4 + 4 × 5 = 7 + 12 + 20 = 39.
In Sample Case #2, the generated arrays X, Y, Z are:
Mr. Raven is stuck in a cave represented by a matrix of N rows and M columns, where rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to M from left to right. The cell at the i-th row and the j-th column is denoted by (i, j). Mr. Raven is currently at the cell (SR, SC), and the exit of the cave is located at the cell (TR, TC).
Some cells of the cave may contain obstacles. Mr. Raven cannot step into a cell
that has an obstacle.
Other cells may contain traps. The first time that Mr. Raven enters a cell with a trap, he must
spend a number of energy points equal to the strength of the trap. If he has fewer energy points
than needed, he cannot enter the cell.
Moreover, some other cells may contain potions. The first time that Mr. Raven enters a cell with a
potion, he gains energy points equal to the strength of the potion.
Mr. Raven initially has E energy points. He can move between cells that share an edge (not just a corner). On the exit cell, Mr. Raven can choose not to exit the cave and continue to explore the cave if he wants to. Can you help him find the maximum number of energy points he can have when he exits the cave, if it is possible to do so?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with seven integers N, M, E, SR, SC, TR and TC as described above. The i-th of the next N lines describes the i-th row of the cave. Each line consists of M integers Vij; the j-th of these represents the cell in the j-th column of the i-th row. Each Vij can be one of the following
For each test case, output one line containing Case #x: y, where x is
the test case number (starting from 1) and y is the maximum energy points that Mr.
Raven can have when he reaches the exit of the cave. If it is not possible for Mr. Raven to reach
the exit, output -1.
1 ≤ T ≤ 100.
Time limit: 120 seconds per test set.
Memory limit: 1 GB.
1 ≤ N ≤ 100.
1 ≤ M ≤ 100.
0 ≤ E ≤ 100000.
1 ≤ SR ≤ N.
1 ≤ SC ≤ M.
1 ≤ TR ≤ N.
1 ≤ TC ≤ M.
(SR, SC) ≠ (TR, TC).
-100000 ≤ Vij < 100000, for all i, j.
At most 15 cells have -100000 < Vij < 0. (There are at most 15 traps.)
VSRSC = 0. (Mr. Raven's initial position is an empty cell.)
VTRTC = 0. (The cell with the exit is empty.)
There are no cells that have Vij > 0. (There are no potions in the cave.)
No additional constraints.
2 4 4 100 1 1 4 4 0 0 0 0 0 0 0 0 0 0 0 -100000 0 0 -100000 0 2 2 100 1 1 2 2 0 0 0 0
Case #1: -1 Case #2: 100
In Sample Case #1, it is not possible for Mr. Raven to reach the exit.
In Sample Case #2, there are no traps and no potions, which means Mr. Raven can reach exit and no matter what path he follows his energy will stay unchanged.
1 8 8 250 7 1 1 7 -100000 -100000 -100000 -100000 -100000 -100000 0 -100000 -100000 0 -100000 0 -400 0 0 -100000 -100000 100 -300 0 -100000 -300 -100000 -100000 -100000 0 -100000 500 -100000 250 0 -100000 -100000 -200 -100000 -100000 -100000 -100000 -100 -100000 -100000 0 -100000 0 0 50 50 -100000 0 0 -100 0 -100000 50 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000
Case #1: 250
In Sample Case #1, the cave is as depicted in the following image where
In this case, one of the optimal ways to reach the exit with maximum energy points is to
The Small dataset can be solved by complete search. We can check for each possible triplet (x, y, z) (with 1 ≤ x < y < z ≤ N) and check whether at least either one of Ax, Ay, or Az is the product of the other two. Each time we get a valid triplet, we increment our answer variable by one.
Since N ≤ 200 for this dataset, an O(N3) time solution will run within the time limit.
Let us ignore indices i where Ai = 0 for the time being. In other words, let us assume that Ai > 0 for all i.
We can observe that for any three positive integers a, b, and c, if a × b = c, then a ≤ c and b ≤ c. Therefore, if we sort A in nondecreasing order, for each triplet (x, y, z) (with 1 ≤ x < y < z ≤ N), we only need to check whether Ax × Ay = Az. However, doing this naively will still be an O(N3) time solution.
We can optimize this solution by computing the number of z satisfying y < z and Ax × Ay = Az for each pair (x, y) in constant time. To do this, we can store the number of occurrences of each number in A in a hashmap.
If we design our nested loop such that we have y = {N .. 1} as our outer loop (and x = {y - 1 .. 1} as our inner loop), then we can update our hashmap for Ay just before we decrement the value of y. This is to make sure that our hashmap only contains the elements with indices larger than the current value of y. In other words, the algorithm looks something like:
sort(A)
ans = 0
occurrences = hashmap()
for y : {N .. 1}
for x : {y - 1 .. 1}
ans = ans + occurrences.count(A[x] * A[y])
occurrences.update(A[y], occurrences.get(A[y]) + 1)
We should not forget that our algorithm so far ignores those indices i where Ai = 0. Suppose there are Z such indices (i.e., there are Z zeroes in A). We can make C(Z, 3) triplets using three zeroes, and C(Z, 2) × (N - Z) triplets using two zeroes and one non-zero.
Therefore, we get our final answer by summing the value of ans from our pseudocode,
as well as C(Z, 3) and C(Z, 2) × (N - Z). This solution runs in
O(N2) time.
Let us define a function f(x) as the number of students scoring more than or equal to x. We can compute f(x) in O(N) time by iterating through all classes.
Therefore, we can use binary search to find the largest x that satisfies f(x) ≥ K, which is the score of the K-th highest score. This solution runs in O(Q × N × log(109)) time.
We can solve the Large dataset by compressing the scores first. That is, we map the existing values of Li and Ri onto a range [1, D], where D is the number of distinct values in Li and Ri. After compressing the scores, we can assume that the students' scores are between 1 and 2N.
For each possible score x, let cnt(x) be the number of students with score x. We can compute the values for all cnt(x) in O(N log(N)) using a range-update point-query data structure such as a segment tree. If we compute the suffix sum (similar to prefix sum, but we cumulate the sum backwards) of cnt(x), we will get the number of students scoring more than or equal to x, which is f(x).
Therefore, just as in our solution for the Small dataset, we can use binary search to find the largest x that satisfies f(x) ≥ K. However, note that the answer is not exactly x, since we compressed the scores earlier. The exact details of the implementation are left as an exercise.
This solution runs in O((N + Q) log N) time.
Since there are no available potions in this dataset, we cannot increase our energy points and hence we are looking for a path with the smallest sum of traps which leads us to the exit. We can consider the cells of the grid as the vertices of our graph and moves between adjacent cells as the edges, with the weight of an edge being the absolute value of the destination cell. Running Dijkstra's algorithm on this graph gives us the path with the smallest sum of traps to reach the exit in O(NM * log(NM)) time.
We can observe that whenever are potions that we can take without going through traps, we should always take them all before going through a trap. After that, we have two recursive choices :
Let CT be the count of traps in our test case. A naive recursive solution based on the above would be of the order of O(NM * CT!).
Observe that for a chosen subset of traps, all orderings of this subset have the same energy points (after going through all the traps), the same set of reachable unvisited traps and the same reachability of the exit cell. We can precompute these values by doing a graph search (BFS / DFS) on all 2CT subsets. To find the order of visiting the traps, we can use dynamic programming along with bitmasks. For every mask of traps, we can choose to go to the next unvisited reachable trap if its cost is not greater than our current energy points, or go to the exit cell if it is reachable and take the choice that maximizes our answer.
The time complexity for precomputation is O(NM * 2CT) and the time complexity of finding the ordering using dynamic programming is O(2CT * CT).
for every subset i in 2CT subsets precompute :
Ei := Energy points left after visiting traps in subset i
Ri := Reachable unvisited traps after visiting traps in subset i
Exiti := Denotes if exit cell is reachable from given subset of visited traps
def MaxEnergy(mask) {
ret := -1
// Go to exit if it is reachable
if Exitmask = True :
ret := Emask
// Go to an unvisited reachable trap
for i in Rmask :
if TrapCosti ≤ Emask :
ret := max(ret, MaxEnergy(mask | 2i))
return ret
}