LightRay's blog

Let's share problems with most unexpected solutions
By LightRay, history, 8 years ago, In English

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

At least four links, please. Challenge others :)

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

Comments Comments (15)
| Write comment?
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

My example:

Dima and Trap Graph
Jump (J)
King's rout
Task processing

(From easy to hard)

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

Just a few more triangles

spoiler
→ Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yeah, looks very hard. How to solve it?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it
        Hint
        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        There is an official analysis (look only at last subtask).

        → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

(Random order)
456A - Laptops
429E - Points and Segments
364D - Ghd
226D - The table

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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 :)

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Nice one

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

Spoiler
→ Reply