TeaTime's blog

By TeaTime, 6 weeks ago, In English

Thanks to t.ravnushkin for helping in writing contents of this blog. Thanks to Alexdat2000 for proof-reading and to bashkort for announcing the month of blog posts. Even though I have started writing this blog before the announcement it would have probably been left in a trash bin due to my laziness.

Introduction

Matching is a beloved topic throughout competitive programming community due to its simple nature and fun applications. Matchings are not only useful in graph theory, but are also essential in topics such as game theory, partially ordered sets and combinatorics. In this blog we are gonna talk about less known applications of the subject. The main goal of the blog is explaining the intuition behind being able to associate the number of some combinatorial species to the amount of perfect matchings and understanding when it is possible to efficiently compute their counts. The blog mainly consists of two parts: one covering more general approach and the other one covering more combinatorial technique called graphical condensation which is applicable to some of the matching problems.

Prerequisites: basic linear algebra knowledge, gaussian elimination algorithm. Basically being able to compute determinant in $$$O(n^3)$$$ or having trust in possibility of doing so is enough

Full text and comments »

  • Vote: I like it
  • +335
  • Vote: I do not like it

By TeaTime, 2 years ago, In English

A — Burenka Plays with Fractions

Authors: glebustim

Solution
Code(C++)

B — Interesting Sum

Solution
Code(C++)

C — Corners

Authors: daubi

Solution
Code(C++)

D1 — Xor-Subsequence (easy version)

Authors: kirill.kligunov

Solution
Code(C++)

D2 — Xor-Subsequence (hard version)

Authors: kirill.kligunov

Solution
Code(C++)

E — Misha and Paintings

Authors: daubi, pakhomovee

Solution
Code(C++)

Full text and comments »

  • Vote: I like it
  • +154
  • Vote: I do not like it

By TeaTime, 2 years ago, In English

Hello, Codeforces!

We are proud to finally invite you to participate in Codeforces Round #815 (Div. 2), which will start on Aug/18/2022 16:35 (Moscow time). You will be given 5 problems, one of which contains a subtask and 2 hours to solve them. We greatly encourage you to read all the problems.

Round is completely set by SIS (Summer Informatics School) students. During the camp our students did their best to prepare interesting and creative problems. You can check previous rounds prepared by SIS students: Codeforces Round #612, Codeforces Round #530, Codeforces Round #694.

People who participated in the creation of the round:

  • Special thanks for testing to: Dmitry Sweezy Pugachev, Alexey Mangooste Mikhnenko.

Also, we would like to thank:

  • Artyom123 for the brilliant coordination.
  • fastmath for improving one of the tasks!
  • meshanya for improving the structure of the contest!
  • MikeMirzayanov for great platforms, Codeforces and Polygon!

Scoring distribution: $$$500-1000-1250-(1500-1000)-2750$$$.

Good luck & have fun!

UPD1: Editorial

UPD2: Winners!

Div 2:

Div 1:

Full text and comments »

  • Vote: I like it
  • +251
  • Vote: I do not like it