RGPC '18 P4 - Higgs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Rin is conducting an experiment with some particles. Her particles are numbered from 1 to N, and each has a spin value S_i. She observes her system of particles for T time "ticks", and numbers the first tick t_1. For each tick, she decides on three integers a, b, and k, which she then uses to advance her experiment in one of two ways:

  1. If the tick is prime-numbered (i.e. t_i, where i is prime), she finds the sum of the spins values between particles a and b inclusive, and then adds k to that sum. She then calls the resulting number the inefficiency E_i of the system at tick t_i.
  2. Otherwise, she increases the spins of each particle from a to b inclusive by k.

Rin defines a cost of stopping the experiment at tick t_p to be C_p = pE_p, where p is prime (i.e., the cost is a tradeoff between the final inefficiency of the system and how many ticks it takes to get there). Help her find the minimum cost.

Note: to recall, a prime number is any natural number greater than 1 that has exactly two distinct factors.

Input Specification

The first line of input consists of two space-separated integers N and T. The next line will contain N space-separated integers, indicating the spins S_i of the ith particle. T lines follow, each containing three space-separated integers a, b, and k.


For all subtasks,

  • 0 \le S_i \le 1\,000
  • 1 \le a, b \le N
  • -1\,000 \le k \le 1\,000
Subtask 1 [20%]
  • 1 \le N \le 10\,000
  • 2 \le T \le 20\,000
Subtask 2 [80%]
  • 1 \le N \le 10^6
  • 2 \le T \le 10^5

Output Specification

Output a single integer, the minimum cost of the experiment \underset{p \le N}{\text{min}}\,\,pE_p, for a prime p.

Sample Input 1

6 4
162 840 327 543 957 582
5 5 329
3 5 -618
5 5 -242
2 5 -173

Sample Output 1



Rin achieves the minimum cost by stopping the experiment after the 2nd tick, when the inefficiency is 1538.

Sample Input 2

7 5
478 186 954 257 126 420 492
2 4 104
6 7 -63
5 6 619
1 5 -704
7 7 818

Sample Output 2