Pinned Tweet
Solução do Problema
O desafio pode ser resolvido ao transformá-lo em no problema de contar para um certo x quantos pares de (i, j) tem i + j = x.
Como podemos fazer isso?
Na descrição ele pede a você para contar as triplas (A, B, C) em que A^2 + B^2 = C^2 (mod N). Então, basta focar nos quadrados desses inteiros como input para o problema que eu mencionei logo acima. Porque, se nós tivermos um C^2 (mod N) fixo, com isso, podemos encontrar o número de pares em que a soma é esse valor.
Mas você pode me perguntar: o que isso tem haver com polinômios?
A resposta é a seguinte: se nós tivermos dois polinômios: P(x) = x^i e Q(x) = x^j e multiplicarmos P(x) * Q(x), nós temos x^(i + j). Assim, se nós criarmos um polinômio em que os expoentes são os números ao quadrado, por exemplo, P(x) = \sum x^(i ^ 2 mod N), para todos os números i entre 1 e (N - 1), no resultado dessa multiplicação poderemos consultar , para um expoente, a quantidade de pares em que a soma dos expoentes dos dois polinômios resulta, já que para cada par x^i e x^j, vai contribuir em uma unidade para x^(i + j) e com isso, com todos os pares teremos a quantidade de somas que resultam em (i + j).
Beleza, mas essa multiplicação não custa O(n^2)?
Sim, se for realizada ingenuamente. Porém, com usando FFT (Fast Fourier Transform) podemos encontrar o resultado de P(x)^2 em O(n log n)
Portanto, conseguimos focar no problema de encontrar a quantidade de pares que resultam em determinada soma. Temos porém que tomar cuidado apenas que os pares com módulos diferentes serão contados duas vezes e por isso devemos dividir o resultado em dois, claro tendo em mente em que os pares com mesmo módulo não serão contados mais de uma vez, então devemos encontrá-los e usá-los corretamente no cálculo.
Aqui deixo um tutorial sobre FFT no USACO Guide: usaco.guide/adv/fft?lang=cpp
Este é o código disponível no GitHub que submeti para resolver o problema:
github.com/ThiagoFBastos/com…
#programacao #dsa #competitiveprogramming
O desafio de programação de hoje é um problema do Beecrowd 🎉
O problema é o "Apenas Mais Alguns Triângulos!"
Como você resolveria?
Me diga nos comentários a sua solução!
Tenho duas dicas:
1. Trate isso como o problema de encontrar o número de pares que dão uma certa soma
2. Tente modelar isso como um problema de polinômios
A solução e o código disponível no GitHub serão liberados em pouco tempo
#programacao #competitiveprogramming #dsa
Thiago Bastos retweeted
É muito bizarro pensar que a linha do tempo original de Dragon Ball terminou com todos os guerreiros Z mortos
Finalmente eu consegui resolver esse exercício de SQL usando Postgres no LeetCode
Tinha um tempo que não escrevia consultas SQL: lag, lead e CTE
O erro era um NULL em um not in () que não devia existir e um coalesce resolveu.
github.com/ThiagoFBastos/SQL…
#leetcode #sql
1
102
Esse é um problema clássico de Dijkstra que todo programador competitivo já viu ou resolveu em algum momento e se não, deveria tentar, pois é bem recorrente em competições.
Dá para resolver no cses.fi !
#programming #CSES #competitiveprogramming #graph
103
Problema legal de programação dinâmica
É um problema hard, mas não foi complicado demais
Até usei aquele loop tipo Crivo de Erastóstenes para encontrar os divisores mais rápido ... diminuiu o tempo um pouco.
Código em C++
github.com/ThiagoFBastos/com…
#leetcode #dsa #programming
2
103
esse problema do CSES foi muto legal de resolver
levou um tempo até eu conseguir resolver, mas foi bem gratificante.
juntou duas coisas que gosto bastante que são grafos e combinatória.
#programming #competitiveprogramming #CSES #math
1
96
Solução do problema em Rust:
github.com/ThiagoFBastos/com…
#programming #competitiveprogramming #rustlang
This quoted post is unavailable.
56
Solução em C++ do problema:
github.com/ThiagoFBastos/com…
#programming #competitiveprogramming #cpplus
This quoted post is unavailable.
84
Thiago Bastos retweeted
Timbaland really came in and saved the drums on kanye’s “stronger” in just 5 minutes after kanye had been struggling with them for months
Sabia que em C++ você pode utilizar functor objects disponíveis em <functional> que fazem a mesma operação que operadores como +, -, *, /, |, ...
?
Por exemplo:
std::vector<int> vec {1, 2, 3};
auto sum = std::ranges::fold_left(vec, 0, plus<int>());
o plus<T>() é um ...
1
1
171
functor object que retorna a soma de dois tipos T que suportam o operator + de adição.
#programming #cpplus
148
Thiago Bastos retweeted
Vou compartilhar meus conhecimentos sobre programação competitiva com quem está querendo iniciar nisso.
Sites para praticar programação comepetitiva:
Quem quiser me adicionar no Leetcode
Deixo aqui o meu perfil:
leetcode.com/u/thiago_bastos…
#LeetCode
1
114
Existem dois casos:
A árvore geradora só possui um vértice no centro ou dois
Caso seja o primeiro caso, dá para encontrar essa árvore geradora a partir da árvore de caminho mínimo com uma BFS
No segundo caso, nós criamos um vértice para representar os dois no centro ...
Pergunta 🤔
Como encontrar a árvore geradora de um grafo com diâmetro mínimo?
#Math
1
1
99
Encontramos a árvore geradora como se tivesse somente um vértice no centro. (nós removemos a aresta que liga esses dois vértices e criamos outro vértice para representar os dois, preservando as suas vizinhanças)
A resposta é a árvore com o menor diâmetro
#Math
1
51













