RGPC '18 P4 - Higgs - Olympiads Online Judge

RGPC '18 P4 - Higgs

Points: 15 (partial)

Time limit: 1.4s

Memory limit: 128M

Author:

Problem type

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

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

Rin defines the cost of stopping the experiment at tick $t_p$ ~t_p~ to be $C_p = pE_p$ ~C_p = pE_p~, where $p$ ~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$ ~N~ and $T$ ~T~. The next line will contain $N$ ~N~ space-separated integers, indicating the spins $S_i$ ~S_i~ of the $i$ ~i~th particle. $T$ ~T~ lines follow, each containing three space-separated integers $a$ ~a~, $b$ ~b~, and $k$ ~k~.

Constraints

For all subtasks:

$0 \le S_i \le 1\,000$ ~0 \le S_i \le 1\,000~

$1 \le a, b \le N$ ~1 \le a, b \le N~

$-1\,000 \le k \le 1\,000$ ~-1\,000 \le k \le 1\,000~

Subtask 1 [20%]

$1 \le N \le 10\,000$ ~1 \le N \le 10\,000~

$2 \le T \le 20\,000$ ~2 \le T \le 20\,000~

Subtask 2 [80%]

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

$2 \le T \le 10^5$ ~2 \le T \le 10^5~

Output Specification

Output a single integer, the minimum cost of the experiment $\min_{p \le N} pE_p$ ~\min_{p \le N} pE_p~, for a prime $p$ ~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

Explanation

Rin achieves the minimum cost by stopping the experiment after the 2nd tick, when the inefficiency is $1\,538$ ~1\,538~.

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

Comments

-20

eric574 commented on Aug. 1, 2018, 9:35 p.m. ← edited →

Nvm.

This comment is hidden due to too much negative feedback. Show it anyway.

37

CopyPastePolice commented on Oct. 19, 2018, 1:47 a.m. ← edit 2 →

YOU'RE UNDER ARREST

It has come to our attention that you've been copying and pasting solutions on DMOJ as well as cheating on contests. This does not show good sportsmanship and is unfair to DMOJistan. Blindly copying and pasting code and cheating on contests does not improve your own abilities and breaks DMOJ's rules.

Proof:

Contest Cheating:

Example 1: https://dmoj.ca/problem/ddrp3

eric574's submission: https://dmoj.ca/src/931485

Alternate accounts's submission: https://dmoj.ca/src/931158

Both joined contest at different windows.

Example 2: https://dmoj.ca/problem/ppwindsor18p7

eric574's submission: https://dmoj.ca/src/1054225

Alternate accounts's submission: https://dmoj.ca/src/1054223

Both joined contest at different windows.

Example 3: https://dmoj.ca/contest/dmopc17c2/ranking/

Note that eric574 solved the first problem in 37 seconds and the second one 1 minute 40 seconds, which wasn't achieved by IOI contestants and multiple others.

Example 4: https://dmoj.ca/contest/tle17c2/ranking/

Note that eric574 solved the first problem in 21 seconds, which is only possible if he had read the problem beforehand.

The above has happened on multiple other occasions.

Proof of Alternate Accounts

Example 1: https://dmoj.ca/problem/dmopc18c2p3

Account 1's submission: https://dmoj.ca/src/1039154

Account 2's submission: https://dmoj.ca/src/1039335

Both joined contest at different windows, and were unrated for this contest, as they were confirmed to be the same person.

Example 2: https://dmoj.ca/problem/mmcc14p3

Account 1's submission: https://dmoj.ca/src/819744

Account 2's submission: https://dmoj.ca/src/806968

From this (although there are multiple other examples), we know that eric574 is both reeee and _____.

In both contests mentioned, there was a previous entry of either reeee or _____ (this happens on almost all his contests).

Code Copying:

Example 1: https://dmoj.ca/problem/pacnw16j

Copied C++ Submission: https://dmoj.ca/src/1034737

Copied Python Solution: https://dmoj.ca/src/1029724

Source: https://speedyguy17.info/icpc/data/pacnw/2016/recap/Shopping/

Example 2: https://dmoj.ca/problem/ccc10s5

Copied Solution: https://dmoj.ca/src/274408

Source: https://mmhs.ca/ccc/2010/S52010VLv2.txt

Again, there are multiple other examples, but I won't list them all.

Please refrain from doing this again.

Note: His other submissions are generally edits of either wleung_bvg's code or kevinwen's code. This applies to anyone with a GitHub account.

35

Darcy___Liu commented on Jan. 18, 2020, 6:08 a.m. ← edit 5 →

CopyPastePolice, YOU'RE UNDER ARREST

It has come to our attention that you've been copying and pasting solutions on DMOJ. This does not show good sportsmanship and is unfair to DMOJistan. Blindly copying and pasting code does not improve your own abilities and breaks DMOJ's rules.

Proof:

Example 1: Hello world - https://dmoj.ca/problem/helloworld

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/1454324

Example 2: Hello world - https://dmoj.ca/problem/helloworldhard

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/279082

Example 3: Hello world - https://dmoj.ca/problem/vmss7wc16c3p3

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/submission/1595568

Example 4: Hello world - https://dmoj.ca/problem/tle18p1

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/1732316

RGPC '18 P4 - Higgs

Input Specification

Constraints

Subtask 1 [20%]

Subtask 2 [80%]

Output Specification

Sample Input 1

Sample Output 1

Explanation

Sample Input 2

Sample Output 2

Comments

Proof:

Contest Cheating:

Example 1: https://dmoj.ca/problem/ddrp3

Example 2: https://dmoj.ca/problem/ppwindsor18p7

Example 3: https://dmoj.ca/contest/dmopc17c2/ranking/

Example 4: https://dmoj.ca/contest/tle17c2/ranking/

Proof of Alternate Accounts

Example 1: https://dmoj.ca/problem/dmopc18c2p3

Example 2: https://dmoj.ca/problem/mmcc14p3

Code Copying:

Example 1: https://dmoj.ca/problem/pacnw16j

Example 2: https://dmoj.ca/problem/ccc10s5

Note: His other submissions are generally edits of either wleung_bvg's code or kevinwen's code. This applies to anyone with a GitHub account.

Proof:

Example 1: Hello world - https://dmoj.ca/problem/helloworld

Example 2: Hello world - https://dmoj.ca/problem/helloworldhard

Example 3: Hello world - https://dmoj.ca/problem/vmss7wc16c3p3

Example 4: Hello world - https://dmoj.ca/problem/tle18p1