All Tracks Math Number Theory Basic Number Theory-2 Problem

Finite or infinite
Tag(s):

Algorithms, Math, Number Theory, Number theory

Problem
Editorial
Analytics

You are given the following:

  • A set \(S\) of size \(n\)
  • A class of functions called \(\mathbb{FUNC}\) \(f: \mathbb{C} \to \mathbb{C}\) such that \(\forall\ k \in S, f^k(x) = x \) holds \(\forall\ x\)
  • A set \(G\) that is defined based on the natural numbers such that a number \(l \in G\) if and only if \(f^l(x) = x \forall x\) holds \(\forall f \in \mathbb{FUNC}\)

Your task is to construct the complement set of \(G\) based on the natural numbers, which implies that a number \(l \in G' \) if and only if \(l \notin G\)

If the cardinality of \(G'\) is finite, then print \(FINITE\). Otherwise, print \(INFINITE\). There are multiple test cases.

Mathematics note

  • \(f: \mathbb{C} \to \mathbb{C}\) is a notation that is used to describe a function \(f\) that considers a complex number, \(a+ib\), as an input and provides another complex number, \(c+id\), as the output.
  • \(\forall \) is read as for all, particularly if \(f^l(x) = x \forall x\) which implies that \(​​f^l(x) = x\) is true for all \(x \) in the domain of the function. Here, domain is a complex number.
  • \(f^l(x) = f(f(f(..f(x)))\) where \(f\) is repeated \(l\) times which means that \(f^2(x) = f(f(x)), f^3(x) = f(f(f(x)))\).
  • \(\in\) is used to denote a set that is a subset of another set.
  • Cardinality is used to denote the size of a set.

Input format

  • First line: \(t\) denoting the number of test cases
  • For each test case:
    • First line: \(n\) denoting the size of the set \(S\) 
    • Second line: \(n\) elements of set \(S\)

Output format

For each test case, print the string \(FINITE\) or \(INFINITE\) in a single line.

Constraints

\(1\leq\) sum of \(n\) over all the test cases \(\leq 100000\)

If \(k \in S\), then \(1 \leq k \leq 100000\)

SAMPLE INPUT
2
3
2 4 1
1
2
SAMPLE OUTPUT
FINITE
INFINITE
Explanation

The sample has two test cases.

In first testcase, we have the information that \(f(x) = x, f^2(x) = x, f^4(x) = x\), Note that, from \(f(x) = x\) we can show that \(f^m(x) = x\), \(\forall m \in \mathbb{N}\). First, let us prove that \(f^3(x) = x\) holds. \(f(f(f(x))) = f(f(x)) = f(x) = x \implies f^3(x) = x\), where we used the fact \(f(x) = x\) repeatedly. In a similar manner, we can prove the claim that \(f^m(x) = x \forall m \in \mathbb{N}\). Hence, we get that for all \(m \in \mathbb{N}\), \(m \in G\). Thus, \(G'\) is an empty set, and the answer is FINITE.

 

In the second testcase, we will prove that the set \(G\) is exactly all the even positive numbers, i.e. \(f^{2m}(x) = x\). We can get this claim from a similar inductive argument as above. Now, all we need to prove is that odd numbers are not part of \(G\). Consider the simple function \(f(x) = 1-x\), which satisfies the condition for all even positive integers (hence it belongs to class \(\mathbb{FUNC}\)), but it does not satisfy \(f^{2m-1}(x) = x\) for any positive integer \(m\). Hence, \(G'\), the complement of \(G\) is exactly the set of odd numbers, and thus the answer is INFINITE.

 

Updated problem name

Finite or infinite sets

Updated problem statement

You are given the following:

  • A set \(S\) of size \(n\)
  • A class of functions called \(\mathbb{FUNC}\) \(f: \mathbb{C} \to \mathbb{C}\) such that \(\forall\ k \in S, f^k(x) = x \) holds \(\forall\ x\)
  • A set \(G\) that is defined based on the natural numbers such that a number \(l \in G\) if and only if \(f^l(x) = x \forall x\) holds \(\forall f \in \mathbb{FUNC}\)

Your task is to construct the complement set of \(G\) based on the natural numbers, which implies that a number \(l \in G' \) if and only if \(l \notin G\)

If the cardinality of \(G'\) is finite, then print \(FINITE\). Otherwise, print \(INFINITE\). There are multiple test cases.

Mathematics note

  • \(f: \mathbb{C} \to \mathbb{C}\) is a notation that is used to describe a function \(f\) that considers a complex number, \(a+ib\), as an input and provides another complex number, \(c+id\), as the output.
  • \(\forall \) is read as for all, particularly if \(f^l(x) = x \forall x\) which implies that \(​​f^l(x) = x\) is true for all \(x \) in the domain of the function. Here, domain is a complex number.
  • \(f^l(x) = f(f(f(..f(x)))\) where \(f\) is repeated \(l\) times which means that \(f^2(x) = f(f(x)), f^3(x) = f(f(f(x)))\).
  • \(\in\) is used to denote a set that is a subset of another set.
  • Cardinality is used to denote the size of a set.

Input format

  • First line: \(t\) denoting the number of test cases
  • For each test case:
    • First line: \(n\) denoting the size of the set \(S\) 
    • Second line: \(n\) elements of set \(S\)

Output format

For each test case, print the string \(FINITE\) or \(FINITE\) in a single line.

Constraints

\(1\leq\) sum of \(n\) over all test cases \(\leq 100000\)

If \(k \in S\), then \(1 \leq k \leq 100000\)

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?