Skip to content
TheChatArchiveThe Chat Archive
o3-2025-04-16· OpenAIHugging Face LMArena Human Preference 140K

A. Party time limit per test 3 seconds memory limit per test 256 megabytes A company has…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with grok-3-preview-02-24’s answer.
  1. User

    A. Party

    time limit per test

    3 seconds

    memory limit per test

    256 megabytes

    A company has n employees numbered from 1 to n. Each employee either has no immediate manager or exactly one immediate manager, who is another employee with a different number. An employee A is said to be the superior of another employee B if at least one of the following is true:

    Employee A is the immediate manager of employee B

    Employee B has an immediate manager employee C such that employee A is the superior of employee C.

    The company will not have a managerial cycle. That is, there will not exist an employee who is the superior of his/her own immediate manager.

    Today the company is going to arrange a party. This involves dividing all n employees into several groups: every employee must belong to exactly one group. Furthermore, within any single group, there must not be two employees A and B such that A is the superior of B.

    What is the minimum number of groups that must be formed?

    Input

    The first line contains integer n (1 ≤ n ≤ 2000) — the number of employees.

    The next n lines contain the integers pi (1 ≤ pi ≤ n or pi = -1). Every pi denotes the immediate manager for the i-th employee. If pi is -1, that means that the i-th employee does not have an immediate manager.

    It is guaranteed, that no employee will be the immediate manager of him/herself (pi ≠ i). Also, there will be no managerial cycles.

    Output

    Print a single integer denoting the minimum number of groups that will be formed in the party.

    Examples

    Input

    Copy

    5 -1 1 2 1 -1

    Output

    Copy

    3

    Note

    For the first example, three groups are sufficient, for example:

    Employee 1

    Employees 2 and 4

    Employees 3 and 5


    Resolva esse problema usando python. Escreva as variáveis em português. Apenas comente o essencial

  2. Assistant

    Ideia

    Em cada cadeia hierárquica, empregados de níveis diferentes não podem ficar no mesmo grupo.
    Logo, o número mínimo de grupos é igual ao comprimento máximo de qualquer cadeia “empregado → gerente → … → diretor”.
    Basta calcular, para cada funcionário, a profundidade até a raiz da sua árvore gerencial e pegar o maior valor.

    Código em Python

    import sys
    sys.setrecursionlimit(10000)
    
    n = int(sys.stdin.readline())
    gerente = [0]*(n+1)         # gerente[i] = gerente imediato do funcionário i
    for i in range(1, n+1):
        gerente[i] = int(sys.stdin.readline())
    
    profundidade = [0]*(n+1)    # memoriza profundidades já calculadas
    
    def calcular_profundidade(func):
        if profundidade[func]:
            return profundidade[func]
        if gerente[func] == -1:
            profundidade[func] = 1
        else:
            profundidade[func] = 1 + calcular_profundidade(gerente[func])
        return profundidade[func]
    
    resposta = 0
    for func in range(1, n+1):
        resposta = max(resposta, calcular_profundidade(func))
    
    print(resposta)
    

    Comentários mantidos no mínimo essencial.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.