Блог пользователя LightRay

Автор LightRay, история, 8 лет назад, По-английски

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

At least four links, please. Challenge others :)

  • Проголосовать: нравится
  • +104
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

Just a few more triangles

spoiler
»
8 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I don't think there's anything special in 456A provided you look at the constraints carefully.

»
8 лет назад, # |
  Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

This answer to similar question on quora by misof is interesting!

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Problem link: https://jutge.org/problems/P33851_en

Short 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 ≤ 26

Solution:

Spoiler

My code: https://github.com/srgrr/JutgeContests/blob/master/P33851_en.cpp

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Beautiful Fibonacci Problem from the last div 1 contest Amazed by the solution

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Nice one

Counting the number of undirected graphs that all degree of its vertices are even.

Spoiler