2015
09-18

# Min-max-multiply

MMM is solving a problem on an online judge, but her solution got TLE (Time limit exceeded). Here is her submitted Java solution:

private static Scanner cin;
private static int n;
private static char[] command;
private static long[] arr;
private static long minValue, maxValue;
n = cin.nextInt();
minValue = cin.nextLong();
maxValue = cin.nextLong();
command = new char[n];
arr = new long[n];
cin.nextLine();
String[] tokens = cin.nextLine().split(" ");
for (int i = 0; i < n; i++) {
command[i] = tokens[i].charAt(0);
arr[i] = Long.valueOf(tokens[i].substring(1));
}
}

public static void go() {
int numQuery = cin.nextInt();
long ans = 0;
long y, y0;
for (int i = 0; i < numQuery; i++) {
y0 = cin.nextLong();
y = y0;
for (int j = 0; j < n; ++j) {
switch (command[j]) {
case ‘+’:
y += arr[j];
break;
case ‘-’:
y -= arr[j];
break;
case ‘*’:
y *= arr[j];
break;
case ‘@’:
y += y0 * arr[j];
}
y = Math.min(maxValue, y);
y = Math.max(minValue, y);
}
ans += y;
}
System.out.println(ans);
}

public static void main(String argv[]) throws IOException {
cin = new Scanner(System.in);
int numTest = cin.nextInt();
while (numTest– > 0) {
go();
}
}
}

She thought that maybe this is due to the slowness of Java compared to C++. So she changed her program into C++, however, she got TLE again:

const int kMaxN = 1000000;
char command[kMaxN];
long long arr[kMaxN];
int main() {
int num_case = 0;
scanf("%d", &num_case);
assert(1 <= num_case && num_case <= 10);
for (int icase = 0; icase < num_case; ++icase) {
int n;
long long min_value, max_value;
scanf("%d%lld%lld", &n, &min_value, &max_value);
assert(1 <= n && n <= 1000000);
assert(1 <= min_value && min_value <= max_value);
assert(max_value <= 10000000000LL); // 10^10
for (int i = 0; i < n; ++i) {
scanf(" %c%lld", command + i, arr + i);
assert(1 <= arr[i] && arr[i] <= 10000000000LL); // 10^10
if (command[i] == ‘*’ || command[i] == ‘@’) {
assert(arr[i] <= 100000); // 10^5
}
}
int num_query;
scanf("%d", &num_query);
assert(num_query <= 1000000);
long long ans = 0;
for (int iquery = 0; iquery < num_query; ++iquery) {
long long start_value;
scanf("%lld", &start_value);
assert(1 <= start_value && start_value <= 10000000000LL); // 10^10
long long sum = start_value;
for (int i = 0; i < n; ++i) {
switch(command[i]) {
case ‘+’:
sum += arr[i];
break;
case ‘-’:
sum -= arr[i];
break;
case ‘@’:
sum += start_value * arr[i];
break;
default:
assert(command[i] == ‘*’);
sum *= arr[i];
}
sum = min(sum, max_value);
sum = max(sum, min_value);
}
ans += sum;
}
printf("%lld\n", ans);
}
return 0;
}

MMM was so desperate that she asked the judge for help. The judge found out that both programs produce the correct output; however, they cannot finish execution within the time limit. Could you, our talented contestant, help her optimize the algorithm and got AC?

The first line of input is an integer T (0 < T ≤ 100) indicating the number of test cases.

For each case, there are 3 integers n, min_value, max_value in the first line, which denote the number of operations, the minimum and maximum value after each operation, respectively (1 ≤ n ≤ 10^6, 1 ≤ min_value ≤ max_value ≤ 10^10).

Then there are n operations in the next line. Each operation is an operator, ‘+’, ‘-’, ‘@’ or ‘*’, followed by a positive integer, without any spaces between them.

For operations of format +x and -x, you can assume 1 ≤ x ≤ 10^10.

And for operations of format *x and @x, you can assume 1 ≤ x ≤ 10^5.

After the line of operations, there would be an integer num_query indicating the number of queries (1 ≤ num_query ≤ 10^6).

Then num_query integers x_i follows, each of them is of range 1 ≤ x_i ≤ 10^10

The first line of input is an integer T (0 < T ≤ 100) indicating the number of test cases.

For each case, there are 3 integers n, min_value, max_value in the first line, which denote the number of operations, the minimum and maximum value after each operation, respectively (1 ≤ n ≤ 10^6, 1 ≤ min_value ≤ max_value ≤ 10^10).

Then there are n operations in the next line. Each operation is an operator, ‘+’, ‘-’, ‘@’ or ‘*’, followed by a positive integer, without any spaces between them.

For operations of format +x and -x, you can assume 1 ≤ x ≤ 10^10.

And for operations of format *x and @x, you can assume 1 ≤ x ≤ 10^5.

After the line of operations, there would be an integer num_query indicating the number of queries (1 ≤ num_query ≤ 10^6).

Then num_query integers x_i follows, each of them is of range 1 ≤ x_i ≤ 10^10

3

9 1 10
-6 +1 +2 +3 -4 *3 -5 @1 -5
10
1
2
3
4
5
6
7
8
9
10

6 1 10
-6 +1 +2 +3 -4 *3
10
1
2
3
4
5
6
7
8
9
10

2 20 25
+20 -1
1
3

36
93
22
HintDon't submit your code until you believe that significant optimization over MMM's solution has been achieved.
MMM's solution would run for an hour on our test data but we expect your solution to finish within seconds. 

1. “中餐的不健康性”这个字眼是值得商榷的，中国菜或每个中国菜系中高糖高脂的能有多少？相比之下一年四季烹饪方法和食材雷打不动的、“逆天”的西式快餐由于其高盐、高糖、高脂，是引发糖尿病、高血压、高血脂、肥胖病、营养失衡的罪魁祸首。《食品公司》“Food, in

2. “中餐的不健康性”这个字眼是值得商榷的，中国菜或每个中国菜系中高糖高脂的能有多少？相比之下一年四季烹饪方法和食材雷打不动的、“逆天”的西式快餐由于其高盐、高糖、高脂，是引发糖尿病、高血压、高血脂、肥胖病、营养失衡的罪魁祸首。《食品公司》“Food, in

3. “中餐的不健康性”这个字眼是值得商榷的，中国菜或每个中国菜系中高糖高脂的能有多少？相比之下一年四季烹饪方法和食材雷打不动的、“逆天”的西式快餐由于其高盐、高糖、高脂，是引发糖尿病、高血压、高血脂、肥胖病、营养失衡的罪魁祸首。《食品公司》“Food, in

4. “中餐的不健康性”这个字眼是值得商榷的，中国菜或每个中国菜系中高糖高脂的能有多少？相比之下一年四季烹饪方法和食材雷打不动的、“逆天”的西式快餐由于其高盐、高糖、高脂，是引发糖尿病、高血压、高血脂、肥胖病、营养失衡的罪魁祸首。《食品公司》“Food, in

5. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

6. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

7. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

8. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

9. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

10. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

11. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

12. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

13. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

14. 年少时莫名地喜欢一个人，喜欢到无以复加，然后万劫不复。为了他的一个动作、一个微笑、一段简短而微妙的陪伴而窃喜好久甚至不知疲倦地回味着，多纯真多难得。我们甚至不会想到要把他据为己有。有些人，一辈子注定不会在一起，但感情却能藏在心里，守一辈子。

15. 这视频想说的其实应该是；‘抵抗’不会使‘被抵抗物事’变得更强、更难！只是会使‘被抵抗物事’更充分地显现暴露，当问题完全地被重视、被充分呈现时，只是看起来似乎更显强大困难了！其实反是更清晰，从而更能让人全面应对了！！！ 抵抗、冲突是世事发展变化的必然，是

16. 这视频想说的其实应该是；‘抵抗’不会使‘被抵抗物事’变得更强、更难！只是会使‘被抵抗物事’更充分地显现暴露，当问题完全地被重视、被充分呈现时，只是看起来似乎更显强大困难了！其实反是更清晰，从而更能让人全面应对了！！！ 抵抗、冲突是世事发展变化的必然，是

17. 这视频想说的其实应该是；‘抵抗’不会使‘被抵抗物事’变得更强、更难！只是会使‘被抵抗物事’更充分地显现暴露，当问题完全地被重视、被充分呈现时，只是看起来似乎更显强大困难了！其实反是更清晰，从而更能让人全面应对了！！！ 抵抗、冲突是世事发展变化的必然，是

18. 这视频想说的其实应该是；‘抵抗’不会使‘被抵抗物事’变得更强、更难！只是会使‘被抵抗物事’更充分地显现暴露，当问题完全地被重视、被充分呈现时，只是看起来似乎更显强大困难了！其实反是更清晰，从而更能让人全面应对了！！！ 抵抗、冲突是世事发展变化的必然，是

19. 这视频想说的其实应该是；‘抵抗’不会使‘被抵抗物事’变得更强、更难！只是会使‘被抵抗物事’更充分地显现暴露，当问题完全地被重视、被充分呈现时，只是看起来似乎更显强大困难了！其实反是更清晰，从而更能让人全面应对了！！！ 抵抗、冲突是世事发展变化的必然，是