Alexander's blog

By Alexander, 9 years ago, translation, In English

Editorial.

Task A.

First problem only is realization. In need read input string, delete all uppercase and lowercase vowels letter and print answer.

 

Task B.

Second problem is realization too. Good solution to calc count space in beginning of string. In handkerchief pattern there is 2 * n + 1 rows. In rows form 0 to N number of space is 2 * n – i. In rown number from N + 1 to 2 * N number of space is (I - N) * 2.

 

Task C.

In this task it need to find a minimal sum that to find a beautiful number of car. So, there are only 10 available digits. Let us try the minimum cost to have one of those digits repeat at least K times and the lexicographically minimum string that has such cost. Then we pick the best result among all digits. Therefore, we divide the task into subtasks and solve it for each digit separately. To spend the least amount of money and make the maximum number of substitutions for each digit it need replace all the numbers are different from her first modulo 1, then modulo 2, then modulo 3 and etc to increase the module, in this and only this if typed in the sum will be minimal. Of course, if produced the right number of substitutions of K, then the algorithm should stop. However, to get the lexicographically smallest string with K digit C, then the replacement should be performed as follows. Suppose that this step of the algorithm need to change all the numbers that are different from the numbers with modulo I, first time it need replace all digits C + I for digit C from begin to end of string. Second time it need replace all digits C – I for C for end to begin of string, because in need to lexicographically minimum one.
After choosing the best answer will be 10 rows. Thus, the asymptotic complexity of the algorithm is 10 * 10 * n.

 

Task D.

The problem is solved lazy dynamics. Let z[n1] [n2] [2] - a number of ways to place troops in a legion of Caesar. Indicate the following parameters, n1 – is a number of footmen, n2 – is a number of horseman, the third parameter indicates what troops put Caesar in the beginning of the line. If Caesar wants to put the footmen, the state dynamics of the z [n1] [n2] [0] go to the state

z [n1] [n2 - i] [0], where 0 <= I <= min (k2, n2) . If Caesar wants to put the riders, the state dynamics of the z [n1] [n2] [1] go to the state z [n1] [n2 - i] [1], where 0 <= I <= min (k2, n2) .

 

 

Task E.

We are given an undirected connected graph, it is necessary to orient its arc so as to obtain a strongly connected directed graph. There is theorem (on a theoretical basis for a written task) that a graph admits an orientation to a strongly connected digraph if and only if every edge is part of what a cycle.

To test this, simply run the bfs to the depth of any vertex and orient the edges in the direction of the bfs. The result of this procedure is an orientation of the graph. To make sure that in the original graph has no bridges, it need to take the orientation of the resulting graph, change the direction of arcs in it, and check that there remains a strong connection. This may be check by dfs too.

Read more »

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

By Alexander, 9 years ago, translation, In English

Hello World.

 The next Codeforces round is prepared by me. This is my debut in arranging contests. I invite everyone to participate in the second division. I hope that all goes well. I wish you have a nice time and be able to improve your skills in programming.

 Thanks to Artem Rakhov (RAD), and Mike Mirzayanov (MikeMirzayanov) for preparation of the round and for motivation.

 Good luck and high rating!

Read more »

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