Thiago Bastos (@ThiagoFBastos) header
Thiago Bastos (@ThiagoFBastos) profile picture

Computer Scientist | Software Dev | C++ • Rust | Competitive Programming | Soluções de Leetcode, Beecrowd, CSES e outros

Rio de Janeiro, Brazil
Joined September 2023
Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)Photo by Thiago Bastos (@ThiagoFBastos)
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
1
2,293
Thiago Bastos retweeted
🏆 Flamengo vence o Palmeiras e conquista o título do Campeonato Brasileiro de 2026! #PALxFLA
7
53
5
322
8,165
Thiago Bastos retweeted
É muito bizarro pensar que a linha do tempo original de Dragon Ball terminou com todos os guerreiros Z mortos
138
602
51
13,011
825,571
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
Como você resolveria esse problema ?
47
Daqui a algum tempo eu posto a solução em C++ e Rust #CSES #cpplus #RUST #CompetitiveProgramming
113
Thiago Bastos retweeted
Microsoft364
489
16,811
1,040
86,245
3,511,500
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
15
251
41
8,545
1,796,068
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
Vou compartilhar meus conhecimentos sobre programação competitiva com quem está querendo iniciar nisso. Sites para praticar programação comepetitiva:
1
1
1
375
Thiago Bastos retweeted
Dragon Ball Super : Broly (2018).
43
752
233
10,135
2,030,472
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
Não sei se ficou claro, mas temos que testar todos os vértices e todas as arestas.
15