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.

Full text and comments »

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

By Fefer_Ivan, 14 years ago, translation, In English

For the first time, our team will write tutorials separetly, but we will unite the in one post after everything will be ready.
C. Bath Queue
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.

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.

Full text and comments »

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

By Fefer_Ivan, 14 years ago, translation, In English

A. Next Test
We will create an array of boolean used[1..3001] ans fill it with "false" values. For each of n given number, we will assign corresponding used value to "true". After that, the index of first element of used with "false" value is the answer to the problem.

B. Tournament
To solve this problem first of all we should find such numbers A and B that occur in the input data not (n - 1) times, but (n - 2). We can notice, that winner-loser relation in this problem is transitive. This means that if X wins against Y and Y wins against Z, than X wins against Z. So to find out who is harsher A or B, let's look for such C, that the results of the match A with C and B with C are distinct. If such C exists, than the one, who wins against C should be printed first. If there is no such C, than both results of the match A versus B satisfy problem's statement.

C. Unordered Subsequence
First of all, we should notice, that if answer exists, it consist of 3 elements. Here is linear time solution.
Let's path with for-loop through the given array and on each iteration let's store current minimul and maximun elements positions. When we are looking at some element, it is enough to check, whereas this element makes unordered subsequence along with min and max elements of the previous part of the array. It is not obvious, but not very difficult to prove. You should try it yourself.

D. Ring Road 2
Consider all m given roads as segments on numeric axis. Road from town a to town b should correspond to segment [min(a, b), max(a, b)]. For each pair of segments there are three types of positions: both ends of one segment are inside of the other one, both ends of one segment are outside of the other one and only one end of one segment is inside of the other one. In the first two cases positions of corresponding roads(inside circle or outside) are independend. But in the third case this positions must be opposite
Let's build the graph. Vertexes will correspond to segments/roads and edge between vertexes i and j will mean that positions of this roads should be opposite. Now we have another problem: for given undirected graph, we must paint all vertexes in 2 colours such that for each edge, corresponding vertexes will have different colours. This problem can be solved using DFS algorithm. First, we will paint all vertexes in -1 colour. Let's begin for-loop through vertexes. If loop finds -1-vertex, assing colour 0 to the vertex and run DFS from it. DFS from vertex V should look through all neighbor vertex. If neighbor has colour -1, than assing to that neighbor colour, opposite to the colour of V and run DFS from it. If neighbor already has non-negative colour, we should check whereas this colour is opposite, because if it is not, answer is "Impossible". Such DFS will either build the correct answer or prove that it is impossible.

E. Number With The Given Amount Of Divisors
 Consider the number, that is our answer and factorize it. We will get such product p1a1· p2a2· ... · pkak. Product through each i ai + 1 will be the number of divisors. So, if we will take first 10 prime numbers, their product will have 1024 divisors. This means that we need only first 10 primes to build our answer.
  Let's do it with dynamic programming: d[i][j] - the minimal number with i divisors that can be built with first j prime numbers. To calculate the answer for state (i, j) let's look over all powers of j-th prime number in the answer. If j-th prime number has power k in the answer, than d[i][j] = d[i / (k + 1)][j - 1] * prime[j]k. For each power of j-th prime we must select the power, that gives us minimal d[i][j].
You should be extremely careful during the implementation, because all calculations are made on the edge of overflow.

  This is it for now. I hope, you will puzzle out all problems, upsolve them and after next contest will get to the division 1. All questions and remarks you can post in the comments.
With best regards, Ivan

Full text and comments »

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