PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy
PREREQUISITES:
Basic Primality Test
PROBLEM:
Given an integer N, check whether it is a Prime Number or not. Print Divesh if it is a Prime, else print Tanya.
QUICK EXPLANATION:
Tanya always wins for composite N, and hence Divesh wins on primes.
EXPLANATION:
Let’s first understand the game. We are provided with an integer N (N \ge 2) and, in each move, a player has to choose an integer K \{(2 \leq K \leq N) \space \wedge \space (N \bmod K \equiv 0)\} and set N = \frac{N}{K}. This means we need to choose an integer K (K \neq 1) which divides N. The player who cannot choose any K other than K = N loses, because this move will set N to 1 and then no other legal move can be made (because we will be unable to choose any valid K).
This game is somewhat similar to the Nim Game, but in a very different sense. Here we are talking about striking out factors of N.
Now, let’s just try to simplify things here. First of all, it is very important to note that Tanya makes the first move, which is a great advantage for a player. So, if the integer N is a prime number, then there’s no possible K other than K = N and hence she will lose in such a case.
Surprisingly, this is the only case when Divesh wins, and it can also be proved that this game won’t last for more than 2 moves given that both players play optimally (also, in such a case Divesh will never have any control on the game, it’s just Tanya’s move (the first move of the game) which will decide everything).
Now let’s take the case when N is a composite number, that is, N has more than 1 prime factors (or a single prime factor with multiplicity more than 1).
Formally,
N = p_{1}^{e_{1}}.p_{2}^{e_{2}} \dots p_{\alpha}^{e_{\alpha}} \space \Big( that is, N = \prod\limits_{i = 1}^{\alpha}p_{i}^{e_{i}} \space \Big),
where p_{i} (1 \leq i \leq \alpha) is a unique prime and \sum\limits_{i = 1}^{\alpha}{e_{i}} \geq 2.
In this case, Tanya (playing optimally) can easily choose a K which will always leave Divesh with a prime number and hence he loses (this also sufficiently proves that the game will never have more than 2 moves). One such valid K which Tanya can choose is:
K = \bigg(\prod\limits_{i = 1}^{\alpha - 1}{p_{i}^{e_{i}}}\bigg).p_{\alpha}^{(e_{\alpha} - 1)} \space = \space \frac{N}{p_{\alpha}} \space \space \big(\text{if } \alpha = 1, \text{then} \prod\limits_{i = 1}^{\alpha - 1}{p_{i}^{e_{i}}} = 1\big)
\therefore \space In this case, Divesh is left with N = p_{\alpha}, which is a prime number. So, the only valid K he can choose is K = N = p_{\alpha}.
This leads us to the final conclusion, that if N is a prime Divesh wins, else Tanya wins.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
inline bool is_prime(int n) {
for (int i = 2; i * i <= n; i++) {
if (!(n % i)) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
if (is_prime(n)) {
cout << "Divesh\n";
} else {
cout << "Tanya\n";
}
}
return 0;
}
ALTERNATE SOLUTIONS:
Though the above mentioned solution is sufficient to pass both the test sets, but here is another implementation which treats both the test sets (the first and second sub-tasks) separately.
Warning: This is just an overkill with a heavier implementation just to pass the first sub-task faster using a pre-processed sieve implementation. And remember, Competitive Programming is not about squeezing your solution to be faster than others’. You just have to be correct with your approach, implementation and time complexity, that’s it.
Both of them use O(n) (n \leq 10^{6}) auxiliary space. And pre-processing time for sieve implementation is O(n \log{\log{n}}) (n \leq 10^{6}).
Also, the primality test (for the second sub-task here) runs in O(\sqrt{N}) time per test.
(Same implementation as the main solution mentioned above)
Alternate Solution 1
#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
inline void pre_processing() {
constexpr int N = 1'000'001;
vector<bool> p(N, true);
for (int i = 2; i * i < N; i++) {
if (p[i]) {
for (int j = i * i; j < N; j += i) {
p[j] = false;
}
}
}
for (int i = 2; i < N; i++) {
if (p[i]) {
prime.push_back(i);
}
}
}
inline bool is_prime(int n) {
for (int i = 2; i * i <= n; i++) {
if (!(n % i)) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pre_processing();
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
if (n < 1'000'001) {
if (binary_search(prime.begin(), prime.end(), n)) {
cout << "Divesh\n";
} else {
cout << "Tanya\n";
}
continue;
}
if (is_prime(n)) {
cout << "Divesh\n";
} else {
cout << "Tanya\n";
}
}
return 0;
}
Here binary search is really a bigger overkill. For the first sub-task this one takes O(\log_{2}{n}) (n \leq 10^{6}) time per test, and for the second sub-task it takes O(\sqrt{N}) time per test.
Alternate Solution 2
#include <bits/stdc++.h>
using namespace std;
vector<bool> prime;
inline void pre_processing() {
constexpr int N = 1'000'001;
prime.assign(N, true);
for (int i = 2; i * i < N; i++) {
if (prime[i]) {
for (int j = i * i; j < N; j += i) {
prime[j] = false;
}
}
}
}
inline bool is_prime(int n) {
for (int i = 2; i * i <= n; i++) {
if (!(n % i)) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pre_processing();
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
if (n < 1'000'001) {
if (prime[n]) {
cout << "Divesh\n";
} else {
cout << "Tanya\n";
}
continue;
}
if (is_prime(n)) {
cout << "Divesh\n";
} else {
cout << "Tanya\n";
}
}
return 0;
}
This one is simpler and without binary search, and hence faster. For the first sub-task this one takes O(1) time per test, and for the second sub-task it takes O(\sqrt{N}) time per test.
It’s just that these solutions pass the first sub-task faster. They’re mentioned here for educational purpose only. You don’t necessarily need them to get an AC for this problem.
COMPLEXITY:
Time complexity: O(\sqrt{N}) per test
Space Complexity: O(1) auxiliary space per test
Feel free to share your approach. If you have any queries, they are always welcome.