Problem A. A Student's Dream.
There was a lot of troubles because of incorrect statement. Now I hope statement is ok. Let's solve it. =)
If boy will goes to the left he will take her left hand with his right one and boy's left hand and girl's right hand will be unused. Situation is looks like the same if we swap them vice versa. So, we need to check two situations and choose the best one.
There is a simple way to check comfortableness, let's assume that boy has B fingers on active hand and girl has G fingers on active hand, so:
- If B < G they will be happy only when B = G - 1, you may see a pattern GBGBGBG...GBGBG. In this pattern you can add no girl's finger for save the condition in statement
- If B > G the worst but correct situation for them is a pattern BBGBBGBB...BBGBB. As you may see this way must be satisfy 2G + 2 > = B condition
- Simple situation is B = G, obviously answer is "yes"
Problem B. Tyndex.Brome.
Let's define p as total length of all potential addresses c. In this problem obvious solution has O(p· k) difficulty and it is getting a TLE verdict. Let's speed up it by next way: we will save all position of letters 'a', 'b', ..., 'z' in address entered by user s separately in increasing order. After this step we can find closest position of letter ci in s for logarithmic time by binary search. This solution has O(p · logk) difficulty that gives "accepted".
Look carefully for length of potential address (it can be more than 105). Answer can be too big and asks you for using integer 64-bit type.
Problem C. Inquisition.
All triangles are located strickly inside of square. It makes problem more simplify, because you don't need to check situations of touching sides.
Let's save all segments of every triangle and cross them in pairs. There are many points at every segment - the results of crossing. Look at the every subsegment which do not contain any points of crossing inside. There are two situations: this subsegment completely lie on the side of some triangle or this subsegment completely lie inside of some triangle.
We may check what is situation by this way: let's take a point at the middle of subsegment. If this point is strickly inside of some triangle then all subsegment is located inside and vice versa. We should calculate only subsegments located on the side of triangles and print their total length.
If you are using integer numbers you should be careful for some operations like vector multiplication because it may leave 32-bit type.
If you are using real numbers you should change you types for as large as possible for good precision (long long in c++, extended in pascal).
Problem D. Wormhouse.
In this problem you asks to find lexicographically next euler cycle or say that there is no way. Let's solve this problem backwards.
We should repeat way of Arnie. Now it needs to rollback every his step and add edges for empty graph (graph without edges). Let's assume we had rollback edge from some vertix x to vertix y. We need to check is there some vertix z that is connected to x by an edge and value of z is more than y? Besides edge (x; z) shouldn't be a bridge because our component needs to be connected.
No solution answer if it's impossible to find such z at any step.
But if edge (x; z) satisfied to conditions upper is exists let's change it to move and after this step our problem is to find lexicographically smallest euler way. It is possible to find only in unbreaked component of graph so every next step must going along non-brigde edges in vertix with as low number as possible. Of course, we must destroy unachievable vertices and do not destroy initial vertix.
We can check is edge a bridge for O(E) time by depth first search. Total difficulty of algorithm represented above is O(N· E2).
Problem E. World Evil.
Author of this problem is Vasily Vadimov, NNSU. He wrote her own tutorial for you.
In this problem you were to find the maximal flow in network with a cyllinder structure. The dynamic solution with complexity O(mn2n) was considered.It's well known that the maximal flow is equal to value of the minimal cut. Also all the sources must belong to one part of the cut and all the drains --- to the other part. Then we look over all the vertices from the left to the right, from the top to the bottom and append to the one or the other part of the cut, recalculating the answer during the process. The trivial solution has complexity O(2mn) and doesn't fit the time limit.
But we can notice the number add to the answer after appending a new vertice to some part of the cut depends only on what parts of the cut the vertices in the current and the previous columns belong to. So we can calculate such a value using dynamic programming: what is the minimal cut can be obtained by adding i columns and the mask of belongings of vertices of the ith column to the parts of the cut is mask. Then we have 2n conversions because there are 2n different states of the i - 1th column. So we have the O(mn22n) solution.
But this solution also can be improved. We calculate the minimal cut, if i - 1 columns are added completely and j vertices from the ith column are added, and mask of belongings of vertices that have no neighbours on the right is mask. Then we append j-th vertice to one of the parts, recalculate the value of the cut and do the conversion. So we have mn2n conditions and O(1) conversions from the every condition and the solution's complexity is O(mn2n).
Also congratulations to the participants rng_58 and Ra16bit who solved this problem during the contest!
Thanks to boys from NNSU (Vladislav Epifanov, Alexey Shmelev) who helps us with alternating solutions and etc.
Sorry for poor english
Maybe few cases like
1 1
a
aa......a
where there are around 2*MAXN a's in the second line.(Actually this was a case that i were hacked with during the contest,but it failed due to a runtime error and not TLE).
Another tricky case where people tricked their greedy to work incase we already dont have minimum |j-i| = 0, could be
1 1
a....ab.....b
b....ba.....a
where the a's and b's = MAXN/2
MAXN = 99999 everywhere.
O(p*k) solutions could use the above tests to understand why according to the problem setter were expected to TLE and might have got lucky on the judge.
Hope this helps.Appreciate any comments.
If you make a queue to find When you find closest position,it will be O(P) :D
My Solution cost least time.