### LightRay's blog

By LightRay, history, 5 years ago,

Let's share it! Some tasks with original ideas or solutions that are not easy to guess.

• +104

 » 5 years ago, # |   +11 My example: (From easy to hard)
 » 5 years ago, # | ← Rev. 3 →   +23 Just a few more triangles spoilerThink in terms of generating functions.
 » 5 years ago, # |   +28 One beautiful task I've encountered is Friend from IOI 2014. The idea is so simple and elegant, yet pretty hard to come up with on your own. It was fully solved only by 13 participants during the contest.
•  » » 5 years ago, # ^ |   +30 I was so disappointed of myself when I read the solution. During the IOI itself I just threw the problem aside thinking "that's gonna be way too difficult and messy". Never have I been so wrong.
•  » » » 5 years ago, # ^ |   +6 Yeah, looks very hard. How to solve it?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 HintProcess the operations in reverse order and try to construct the answer.
•  » » » » 5 years ago, # ^ |   +8 There is an official analysis (look only at last subtask).
 » 5 years ago, # |   +13
•  » » 13 months ago, # ^ |   +5 I don't think there's anything special in 456A provided you look at the constraints carefully.
 » 5 years ago, # |   +5 My first guess will go to "Planar drawing" from last contest on last Petrozavodsk camp (that contest was used as part of OpenCup, so statement is googleable). Once you understand solution it sounds very logical, but at first sight it seems like a crazy idea to use what is used in that problem.
 » 5 years ago, # |   +16 This answer to similar question on quora by misof is interesting!
 » 5 years ago, # |   -6 Problem link: https://jutge.org/problems/P33851_enShort statement: Given a string s, count the strings of length n which contain s at least once. The strings (including s itself) must contain only letters chosen among the first m letters from the English alphabet. The result must be printed modulo 109 + 7.Constraints: 1 ≤ |s| ≤ 10, |s| ≤ n ≤ 109, 1 ≤ m ≤ 26Solution: SpoilerBuild the deterministic finite automaton (DFA) that accepts the strings that contain the input string at least once. Then build a square matrix where every cell m[i][j] contains the number of transitions between the state i and j. Raise the matrix to the n-th power and output m[initial_state][final_state].
•  » » 5 years ago, # ^ |   +38 Actually, this is a pretty standard task, the dp state (position,matches) is kinda obvious and when position can go up to 10^9 or more, it usually means that you should use matrices :)
 » 5 years ago, # |   -6 I think problem B in round 1B of the google code jam 2016 would be a good example
 » 13 months ago, # |   +11 Beautiful Fibonacci Problem from the last div 1 contest Amazed by the solution
 » 13 months ago, # | ← Rev. 4 →   0 Nice oneCounting the number of undirected graphs that all degree of its vertices are even. Spoiler2 ^ ( (n — 1) * (n — 2) / 2)