Please subscribe to the official Codeforces channel in Telegram via the link ×

Fefer_Ivan's blog

By Fefer_Ivan, 13 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

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

| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I just read the article, but it's in Russian, now English!!
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
2^40 fits in long type in java.
BTW, To avoid overflow you can use this idea - If A*B>C then A>C/B.
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C++ has "long long int" type that can hold numbers up to 9·1018.

    It is said that answer is lower than 1018. So when prime[j]k becomes to big, I just break from the cycle. Also, because 10-th prime is only 29 me can assume, that if some var is overflowed, this var is negative. So check this also.

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For problem we consider that the road can be build only in clockwise direction. What about the possibility that we can build the road in anti clock wise direction ? Was it implied in the problem statement that the roads will be clockwise?
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I meant problem D: Ring Road 2
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Sorry, for the silly question. It wouldn't matter as i just realized, since irrespective of direction they will have conflict and hence must be placed in opposite sides.
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem Div2D, could anyone explain why two color painting gives a correct answer and what the logic behind it is? Thanks.

EDIT 2: Fellow coder helped understanding the idea. SOLVED.