Fefer_Ivan's blog

By Fefer_Ivan, 14 years ago, In English

A. Bender Problem
Solution by Polichka
Let's look at the first nail. If it is occupied by the fold place, then Bender will put next fold place on the third nail, then on fifth and so on. Else, is the first nail occupied by end, than second, fourth, sixth and so on nail will be occupied by the fold places.
Let's see, if we can complete our polyline with the first nail, occupied by rhe fold place. It means we should check, if we have an unused pod with length dist(nails[n], nails[1]) + dist(nails[1], nails[2]). Then check the third nail and so on.
If we have completed the polyline, then we have an answer. Else repeat previous procedure, but starting from the second nail.

B. pSort
Solution by Polichka
Let's consider a graph. Vertexes will correspond to place of the permutation. Places will be connected by an edge if and only if we can swap theirs values. Our problem has a solution when for every i, vertex p[i] can be reached from vertex i.

C. Bath Queue
Solution by Fefer
This problem is solved by dynamic programming
Consider the following dynamics: d[i][j][k].
i --- number of not yet processed students,
j --- number of not yet processed rooms,
k --- maximum queue in the previous rooms.
The value we need is in state d[n][m][0]. Let's conside some state (i, j, k) and search through all c from 0 to i. If c students will go to jth room, than a probability of such event consists of factors: Cci --- which students will go to jth room.
(1 / j)c· ((j - 1) / j)i - c --- probability, that c students will go to jth room,and the rest of them will go to the rooms from first to j - 1th.
Sum for all ñ from 0 to i values of
(1 / j)c· ((j - 1) / j)i - c· Cci· d[i - c][j - 1][mx]. Do not forget to update maximum queue value and get the accepted.

D. Do not fear, DravDe is kind
Solution by RAD
Let's split all trucks into different classes by the sum of li + ci + ri. Answer sequence consists of trucks from only one class, so let's solve problem for different classes independently.
Let's loop through trucks from fixed class in the order, then follow in the motorcade and update values in dynamics z[k] - maximum profit we can get, if last truck has ri = k.
Truck with number i can update two values:
it can update value z[ri] with value z[ri + ci] + vi. It means this truck continued some motorcade, started from some previous truck.
if li = 0 it can update value z[ri] with vi. It means this truck started motorcade. Answer will be in z[0]
To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider i-th truck and doesn't change further: p[i] = -1 if truck i became beginning of the motorcade, otherwise p[i] = last truck that updated z[ri + ci]. We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

E. DravDe saves the world
Solution by Gerald
Problem by RAD
Let's look at geometrical locus where DravDe can land. It can be eigher an angle or a line(half-line).
1. Locus is an angle if and only if projection of vector v and vector u on Oxy plane is not collinear. This angle is easy to calculate. Angular vertex is DravDe starting point and one of half-lines is collinear with place speed vector projection. Second half-line is easy to calculate:
Az + Vz· tv + Uz· tu = 0
Ax + Vx· tv + Ux· tu = Bx
Ay + Vy· tv + Uy· tu = By
where A - starting point, B - landing point. Consider tv equal to 1 and calculate tu from first equation. From second and third calculate point B. This point lies on the second half-line of the angle.
2. If plane speed projection and wind speed projection is collinear, locus is half-line or line, depending on the difference between this two speeds.
If the answer exist, than polygon and locus have at least onecommon point. And t1 and t2 is minimal on edge points. So now let's cross all segments with locus, calculate t1 and t2 for each intersection point and select minimal answer. Thank you for your participation. Good luck with upsolving and incoming contests. Luck - is very useful and it is good to have it.
With best regards, Ivan.

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

| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Also, what does Cci  evaluate to?

--- which students will go to jth room 
does it mean c students are selected from the maximum number of students i, where c can vary from 0 to i.
 
i! / ( c! * (i-c)! )

Also, I think maximum number of students i is the same as  the maximum number of students in the input that is "n".
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mx - is the maximum queue in previous rooms.

    No. i - is different. When we select some c students for jth room, for (j-1)th room there will be only (i - c) students left.


»
10 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

what is the test 9 of Problem D?

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

Oh... I can't stand the decription of the problems any more. I have to read 5 times to understand.