D - All Your Paths são de Comprimentos Diferentes

Construa um grafo direcionado com no máximo \(20\) vértices e no máximo \(60\) arestas, com pesos de aresta não superiores a \(10^6\), de modo que haja exatamente \(L\) caminhos de \(1\) a \(N\), com comprimentos de \(0\) a \(L-1\).

Como \(2^{20}=1048576\), a ideia natural é usar a representação binária.

Para o maior \(n\) tal que \(2^{n-1}\leq L\), podemos construir com \(n\) vértices um grafo direcionado onde os caminhos de \(1\) a \(n\) têm comprimentos de \(0\) a \(2^{n-1}-1\): considere os vértices \(i=1\sim n-1\)

• Do vértice \(i\) para \(i+1\) coloque duas arestas, uma com peso \(0\) e outra com peso \(2^{i-1}\).

Seguindo uma abordagem semelhante à DP de dígitos, agora precisamos lidar com a parte maior que \(2^{n-1}\) até \(L\).

Percorrendo os bits de \(L\) do mais significaitvo para o menos, considere cada bit \(1\) de \(L\). Seja \(pre\) a soma dos bits já processados (ou seja, \(2^{n-1}\) mais a soma dos bits \(1\) já tratados). Então, adicione uma aresta do vértice \(i\) para \(n\) com peso \(pre\), repersentando os comprimentos de \(pre+0\) a \(pre+2^{i-1}-1\). Atualize \(pre\) e continue até que o intervalo coberto alcance \(L-1\).

Você pode entender melhor com o código.

//Autor: RingweEH
int L, n, m;

int main() {
    L = read();
    for (n = 1; (1 << n) <= L; n++);
    for (int i = 0; i < n; i++) if (L & (1 << i)) m++;
    printf("%d %d\n", n, m - 1 + 2 * (n - 1));
    for (int i = 1; i < n; i++) 
        printf("%d %d %d\n%d %d %d\n", i, i + 1, 0, i, i + 1, 1 << (i - 1));
    for (int pre = (1 << (n - 1)), i = n; i--; ) 
        if (L & (1 << (i - 1))) 
            printf("%d %d %d\n", i, n, pre), pre += (1 << (i - 1));
    return 0;
}

E - Stop. Caso Contrário...

Temos \(n\) dados, cada um marcado com um número de \(1\) a \(K\). Para cada \(i=2\) a \(2K\), calcule:

• O número de maneiras (dados não rotulados) em que NÃO existem dois dados cuja soma seja \(i\).

Considere o princípio da inclusão-exclusão. Seja \(cnt\) o número de pares que somam \(x\), e \(f[i]\) o número de maneiras com pelo menos \(i\) pares somando \(x\). A resposta é \(\sum_{i=1}^{cnt} (-1)^i f[i]\). Para calcular \(f[i]\), escolhemos forçadamente \(i\) pares e depois distribuímos o restante livremente:

int main() { k = read(); n = read(); Init(); for (int i = 2; i <= k + k; i++) { int cnt = (s[i] + 1) / 2, ans = 0; for (int j = 0, nw = 1; j <= cnt && j + j <= n; j++, nw = Mod - nw) bmod(ans, 1ll * nw * C(cnt, j) % Mod * C(n - 2 * j + k - 1, k - 1) % Mod); printf("%d\n", ans); } return 0; }

F - A Vingança de BBuBBBlesort!
-------------------------------

Dada uma permutação \\(p\\) de \\(1\\) a \\(n\\), determine se é possível transformá-la em \\(p\[i\]=i\\) usando a seguinte operação:

- Escolha \\(p\[i-1\], p\[i\], p\[i+1\]\\) tais que \\(p\[i-1\] > p\[i\] > p\[i+1\]\\), e troque \\(p\[i-1\]\\) e \\(p\[i+1\]\\).

Inicialmente, um algoritmo ingênuo que processava da esquerda para a direita e depois da direita para a esquerda passou em 2/3 dos casos. /jk

A solução correta é a seguinte:

Seja \\(a\[i\] = \[b\[i\] = i\]\\) (indicador se o elemento está na posição correta). Defina um intervalo como válido se ele for alternado em 0 e 1, começando e terminando com 0.

Observações:

- Uma posição (como centro) se move uma vez e nunca mais se move (considere as relações de ordem).
- Se houver três zeros consecutivos em \\(a\\), não há solução (consequência da observação anterior).

Primeiro, maximize o comprimento de cada sequência válida que contém uma posição. Se todas as sequências válidas satisfizerem simultaneamente as seguintes condições, existe uma solução. Para um intervalo \\(\[l, r\]\\),

- Os valores dos elementos pertencem a \\(\[l, r\]\\).
- Para posições cujo destino está à esquerda: \\(\\forall i<j, a\[i\] < a\[j\]\\).
- Para posições cujo destino está à direita: \\(\\forall i<j, a\[i\] < a\[j\]\\).

</div>