NPL1701C - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: neeladree
Editorialist: neeladree

DIFFICULTY:

EASY

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

Find the winner in a game, which consists of two players, who are picking integers off an array and splitting an integer into two of its factors and replacing the new integers on the array. The end point is when no move can be made.

QUICK EXPLANATION:

Find the sum of prime factors of all the integers present in the array.

EXPLANATION:

Basically, the number of times an integer from the array can be subdivided is equal to the number of prime factors of the number – 1. So, if we sum this up for all the numbers in the array, we get the total number of moves that can be played in a game and it is fixed for a given array. Depending on whether this number is odd or even, we get the winner of the game.
The number of prime factors of an integer can be calculated offline by making a little modification to the Sieve code - by adding 1 to all the numbers encountered in the inner loop. However, even solutions which calculate the number of prime factors of an integer online in log(n) time will also pass the test cases.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

2

Many thanks for the highlighted problem and for the proposed solution, very useful. The problem is really pretty interesting, I think that it will be good to ask it my colleagues and try to solve it together. Again, a lot of thanks, we will post the solution at this page.