kostka's blog

By kostka, 6 years ago, In English

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.

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

»
6 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Now we got Codeforces round #1200 problems :)

»
6 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem "Turniej trójinformatyczny"?

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

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

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
    Rev. 59   Vote: I like it +83 Vote: I do not like it

    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)
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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