HOMO - Homo or Hetero


Consider a list of numbers with two operations:

  • insert number — adds the specified number to the end of the list.
  • delete number — removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number 4 to the list [1, 2, 1] is the list [1, 2, 1, 4]. If we delete the number 1 from this list, we get the list [2, 1, 4], but if we delete the number 3 from the list [1, 2, 1, 4], the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list [2, 2] is homogeneous, the list [2, 1, 4] is heterogeneous, the list [1, 2, 1, 4] is both, and the empty list is neither homogeneous nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list’s homogeneity and heterogeneity after each operation.

Input

The first line of the input file contains an integer number n — the number of operations to handle (1 ≤ n ≤ 100 000).

Following n lines contain one operation description each. The operation description consists of a word “insert” or “delete”, followed by an integer number k — the operation argument (−10^9 ≤ k ≤ 10^9 ).

Output

For each operation output a line, containing a single word, describing the state of the list after the operation:

  • both” — if the list is both homogeneous and heterogeneous.
  • homo” — if the list is homogeneous, but not heterogeneous.
  • hetero” — if the list is heterogeneous, but not homogeneous.
  • neither” — if the list is neither homogeneous nor heterogeneous.

Example

Input:
11
insert 1
insert 2
insert 1
insert 4
delete 1
delete 3
delete 2
delete 1
insert 4
delete 4
delete 4

Output:
neither
hetero
both
both
hetero
hetero
hetero
neither
homo
neither
neither

hide comments
madhur4127: 2017-10-03 19:42:29

hashing->speed

nadstratosfer: 2017-09-18 12:07:03

Finally AC after countless TLEs in Python. Lesson: want efficient data structures to behave as such, use them correctly.

kmkhan_014: 2017-08-24 23:01:45

used map container in c++(stl).passed all test cases in 0.65s any suggestions on how to improve run time of the code.

sas1905: 2017-07-04 16:02:44

No CPP14..:(

imsaral: 2017-06-21 18:19:57

3
delete 2
insert 2
insert 2

shouldn't the output be "homo"
but spoj toolkit output is "neither"
and also the code whose output is "neither" is getting AC
Problem Setter should check this.

ayushgupta1997: 2017-06-02 09:56:58

0.15... nice problm :) used multiset

anurag_tangri: 2017-05-31 12:05:27

(set + Hashmap==AC:)

kshubham02: 2017-03-28 07:36:00

AC 0.78 :/
How to get better time?
I used map STL.

vengatesh15: 2017-01-23 16:46:36

AC in 1 go :-)

hpabhi: 2016-07-28 16:47:14

GOOD QUESTION..but weak test cases guys...my wrong solution got accepted..do verify it with other codes

Last edit: 2016-07-28 16:47:55

Added by:Daniel Ampuero
Date:2010-10-27
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:ACM ICPC 2009–2010, NEERC, Northern Subregional Contest