Math-O5/competitive-programming

From UVA, CODEFORCES, OBI, ACM-IPC, ADVENT-OF-THE-CODE

CP - COMPETITIVE_PROGRAMMING

Here are some resolutions of competitive programming. I like to do this problems to improve my skills coding, distract from the dayly tasks. Note, this code is really messy up, since is done only to be 'accepted".

Algorithms and Applications

The link of the problems is commented first line of each code. The sections are splitted by Event (Advent of Code, Daily Byte and etc) and by theme (Greedy, DP and etc). If there are more than one solution, then it will be chained as follow: [1][2]. Sometime, the complexity time is given in the link, instead of enumerating [O(n)][O(nlogn)]./p>

• Advent of the Code 2020 | 2021 solutions

  Cool challenges in increase difficulty order, summer challenges.

• Daily Byte solutions

  Every day a learning day.

• DP - Programming Dinamic

  • [1] Range Sum
  • [1] [2] Longest Increase Sequence
  • [1] Weithed Interval Schedule Problem
  • [1] Knapsack
  • [1] Coin Change

  Pratice DP

  • [1] [2] [3] Véi, dá meu troco! - (DP - Coins)
  • [1][2] Formas de me dar meu dinheiro! (ways to count) (DP - Coin)
  • [1] UVA 507 Jill Rides Again - (DP - Sum Range)
  • [1] OBI 2014 Letra - (DP - LIS)
  • [1] UVA 10534 - Wavio Sequence (DP - LIS)
  • [1] OBI 2007 Pizza - (DP - Sum Range)
  • [1] O(n²) - [2] O(n log n) UVA 10131 is bigger smarter?- (DP - LIS)
  • [1] O(n*m) DNA Sequence Alignment (DP - String)
  • [1] O(n²) OBI 2005 Pedido de desculpas - (DP - Knapsack)
  • [1] O(n²) UVA 10616 Sum Divisble by n chosen m - (DP - Knapsack)

• Strings - Strings in CP

  • [1] Counting Sort
  • [1] Radix Sort
  • [O(n)] Prefix Function
  • [O(mn)] KMP Naive

  Pratice Strings

  • [1][2] OBI Fusões - Guildas (Graph - Union Find)

• Graph - Graph in CP (Grafos)

  • [1] Union Find (DSU)
  • [1] DFS (Deep First Search)
  • [1] BFS (Breadth First Search)
  • [1] Dijkstra
  • [1] Prim's Algorithm
  • [1] O(M log N) - [2] MST (Minimum spanning - Kruskal)
  • [BFS] [DFS] versão da Ordenação Topologica (Top Sorting)
  • [1] O(|V| * |E|) - Bellforman Ford (Min Path)
  • [1] O(|V| * |E|) - Check Graph Bipartite (BFS/DFS)
  • [1] O(N³) - Floyd-Warshall (Min Path to all vertices)

  Pratice Graphs

  • [1][2] OBI Fusões - Guildas (Graph - Union Find)
  • [1] CODEFORCES 69 - C - new Distribution (Graph - DFS or Union Find)
  • [1] OBI 2016 - Taco do Saci (Graph - DFS)
  • [1] O(|V| + |E|) OBI 2011 - Escalonamento Ótimo (Graph - Ordenação Topológica)
  • [1] O(|M| log |N|) OBI - Copa do Mundo 2014 (Kruskal - MST)
  • [1] O(|V| * |E|) UVA 558 - Wormholes (Graph - Negative Cycles)
  • [1] CODEFORCES 617 - E - String Coloring, Easy Version (Graph - Bipartite)
  • [OBI- 2010 - Reuniao] Floyd Warshall

• Greedy / Brute Force Problems

  • [1] O(N logn N) - [2] O(N) OBI 2010 Dentista (Intervel schedule)
  • [1] CODEFORCES 617 - E - String Coloring, Easy Version (Greedy Solution)
  • [1] CODEFORCES - Palindromos
  • [1]

• DATA STRUCTURE

  • [1] STL 1 (vector, queue, stack, pair)
  • [1] STL 2 (map, set, tree)
  • [1] [2] Bits (Bits)
  • [1] Binary Search Tree
  • [1] Segmented tree (seg Tree)

  Pratice

  • [1] OBI 2016 - Times (Vectors and Pairs)
  • [1] OBI 2014 - Fila (Bits)
  • [1] CODEFORCES DIV3 570 - D Computer Game (Binary Search)
  • [1] UVA 540 Team Queue (Map)
  • [1] UVA 837 Light and Transparencies (Map, Set)
  • [1] OBI Banco (Priority Queue)
  • [1] U(n log n) OBI Banco (Binary Search)