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.
Now we got Codeforces round #1200 problems :)
Let me also announce that as for today, 350 problems from POI are avaliable on Szkopuł (88.38% of all POI problems).
Are the results of the competition avalible and are the editorials in Polish avalible?
Editorials are not yet available (they are always published in a book but with some delay).
Scoreboards are available here:
Where can I find the books with previous years' editorials?
In Polish only: https://oi.edu.pl/l/40/
Thanks!
How to solve problem "Turniej trójinformatyczny"?
The description is intentionally rough to give you some thinking space.
You would like to implement kossaraju for calculating strongly connected components, however the graph is fairly big. You do a normal DFS with speedup in finding edges to unvisited vertices. You want a data structure for this. Although it seems like an ugly 2D problem, you can notice that it's enough to search for edges independently and use a "find max on an interval segment tree" to find the best candidate.
How to solve problem "Pionek"? (and where can I find editorials?)
We do not publish editorials in English, sorry.
I've explained one possible solution at the Brazilian ICPC Summer Camp.
Oh, thanks a lot!
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?
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.
First of all, I hope you thought about keeping only useful segments, the ones that doesn't include any other one. It is a very classical thing to do. This allows us to have all segments strictly sorted by $$$l$$$ and strictly sorted by $$$r$$$ at the same time. It is not necessary for this problem but it helps visualization.
About the point of view: it's hard to solve this problem focusing on the segments as a whole two-dimensional object, probably some unsolvable issues will quickly arise if you try this way and you will get stuck. So, it's time to consider another point of view!
There is only one other meaningful possible point of view: focusing on points instead. $$$m$$$ is large, but you can compress the line into $$$\mathcal{O}(n)$$$ weighted points (weight = size of the compressed interval).
When we have to create a dp state over points, trying to find an optimal set of points, $$$dp_x$$$ is often something like "how to satisfy all constraints after $$$x$$$, assuming $$$x$$$ is a chosen point and everything before is OK".
The rightmost already chosen point is a relevant parameter because it's the only thing we need to remember in order to "continue the exploration (the construction of the set)".
The transition will obviously be "choose the next point $$$y > x$$$". It is a classical type of DP.
The order in which we choose the crosses don't matter, so let's choose them from left to right.
For a given position $$$x$$$, assuming that all segments satisfying $$$r_i < x$$$ are already covered and that there is a cross on point $$$x$$$, let $$$opt_x$$$ be the minimum number of crosses we have to put in order to cover all remaining segments, the ones at the right of $$$x$$$ ($$$x < l_i$$$).
The transition is obviously "choosing where to put the next cross after $$$x$$$".
We can greedily compute $$$opt$$$ (finding ONE optimal transition, the righmost valid one works since $$$opt$$$ is non-increasing). Let $$$cnt_x$$$ denote the number of ways to do this optimally.
You must find a clear description of ALL the optimal dp transitions. For a fixed last point $$$x$$$, what can be the optimal next point $$$y > x$$$? Find two conditions $$$y$$$ must satisfy.
The next point $$$y > x$$$ must satisfy these two conditions:
there must be no segment such that $$$x < l_i < r_i < y$$$, otherwise it will not be covered (there is a "gap" between $$$x$$$ and $$$y$$$).
$$$opt_y = opt_x - 1$$$
It's obviously an interval:
The first condition only fix an upper bound $$$y_{max}$$$, the minimum $$$r_i$$$ over all $$$i$$$ such that $$$x < l_i$$$. Notice that $$$y_{max}$$$ is the rightmost valid transition, so we can set $$$opt_x := opt_{y_{max}} + 1$$$.
Since $$$opt$$$ is non-increasing, the second condition fix a lower bound $$$y_{min}$$$, the leftmost point such that $$$opt_{y_{min}} = opt_x - 1$$$.
We can see that $$$cnt_x = w_x \cdot (\sum cnt_y)$$$, where $$$w_x$$$ is the weight of the point $$$x$$$ (the size of the original interval we compressed in part 1) and $$$y_{min} \le y \le y_{max}$$$.
How to effeciently compute the array $$$cnt$$$? What will be the final answer?
We will compute $$$cnt$$$ in decreasing order. The bounds $$$y_{min}$$$ and $$$y_{max}$$$ can only move left during the process, so we can maintain them and maintain the sum of $$$cnt_y$$$ between these bounds in amortized linear time ("two pointers" technique).
The final answer will be $$$cnt_0$$$, where $$$0$$$ is a fictive position.
This solution has a final time complexity of $$$\mathcal{O}(n \log n)$$$, which would be $$$\mathcal{O}(n)$$$ if we didn't have to compress coordinates.
I made some small modifications to make the solution more intuitive (removed some utterly formal things). Please re-read the parts you already read.
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/
change every a_i to (a_i+1)%s then repeat this process
1.take element with maximum frequency
2.if it doesn't increase the answer if added at the last or there is only one distinct element take it
3.else take the element with second maximum frequency
break ties arbitarily
credits: RestingRajarshi