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

Автор kostka, 5 лет назад, По-английски

Hello Codeforces,

as promised, tasks from the last year Polish Olympiad in Informatics are finally translated:

https://szkopul.edu.pl/p/default/problemset_eng/oi/25

Please ignore Polish titles, if you set the language to English (top right corner), you should see English statements.

I also want to recommend some problems, which (in my opinion) deserve some attention. I won't say why, because I don't want to spoil them, but if you have some spare time, please check out the following problems:

We are aware that the translations are not flawless, please let us know if we've made some mistakes.

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

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

Now we got Codeforces round #1200 problems :)

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

Let me also announce that as for today, 350 problems from POI are avaliable on Szkopuł (88.38% of all POI problems).

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

Are the results of the competition avalible and are the editorials in Polish avalible?

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

How to solve problem "Turniej trójinformatyczny"?

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

    The description is intentionally rough to give you some thinking space.

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

How to solve problem "Pionek"? (and where can I find editorials?)

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

How To solve Round 2 day 1 Conductor https://szkopul.edu.pl/problemset/problem/lbADmW7d353d0F0iw4kXTjsl/statement/

I figured out how to do the first part(the minimum number of ticket inspections) but I can't figure out how to do the second part( the number of distinct minimum sets of such inspections)

Any hints?

  • »
    »
    4 года назад, # ^ |
    Rev. 59   Проголосовать: нравится +83 Проголосовать: не нравится

    This is a very educational problem, especially for purple/orange, and I encourage everyone in this rating range to try it.

    The hints are not independent (I just divided the solution into five parts, you have to read them in this order). Remember that you should not try to get help (reading next part) if you're not totally stuck since at least one hour (maybe less, maybe more, depends on your training habits). If you have new ideas, you must reset this "chronometer" :)

    I assume that the reader already know how to find minimum number of tickets inspection.

    Part 1 (point of view)
    Part 2 (dp state, global idea)
    Part 3 (dp state, details)
    Part 4 (dp transition)
    Part 5 (end)
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      I made some small modifications to make the solution more intuitive (removed some utterly formal things). Please re-read the parts you already read.

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

does anyone have a rigorous proof of the solution of stage 2 day 2 problem poetry
https://szkopul.edu.pl/problemset/problem/Hhip15j-8Ro2dOb_4oB98C-G/statement/

approach