Alexander's blog

Разбор задач. Codeforces beta round #89.
By Alexander, 13 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.

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

Comments Comments (21)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
There is theorem (on a theoretical basis for a written task)

More details?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    the Theorem say that "graph admits an orientation to a strongly connected digraph if and only if every edge is part of what a cycle.". That All.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I find it in one book of discrete mathematics.
      → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      I mean some further explanations...

      any hints to prove it?

      → Reply
      • 13 years ago, # ^ |
        ← Rev. 3   Vote: I like it +9 Vote: I do not like it

        You can prove it by induction.

        1) If the graph has only one node, there are no edges and the result is true.

        2) Otherwise, if every edge is in a cycle, then consider one cycle, put arrows on the cycle so that it's connected.  For each chord in the cycle, put arrows in the direction you want, it doesn't matter.  Now contract the graph: i.e. consider the new graph where the cycle is replaced by one new node.  The contracted graph has every edge in a cycle, so by induction, it's possible to put directions on every edge. 

        Now for the converse, if there is an edge that is not part of any cycle:  It means that this edge is a bridge.  And if the bridge has one direction, then the graph can not be strongly connected.

        → Reply
      • 13 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it
        Also you can do something like this:
        1. Let there is at least one 'bridge' edge in our graph (which does not lie on any non-self-intersected cycle). Have a look at its ends - vertexes A and B. There is exactly one path from A to B. Obliviously, we cannot choose orientation for this edge.
        2. Now we don't have any bridges in our graph. Let's run DFS and prove that if we choose 'from root to leaves' orientation for all tree edges and reverse orientation for the remaining ones, everything will be OK. First, it's oblivious that it's possible to reach any vertex from root (let it will be X). Then, let's prove that from each vertex A we can reach vertex B (parent of A in DFS' tree). In this case we can reach root by induction and our graph became strong-connected. So, we want to reach B from A. Let's remove edge from A to B from our graph. Because this edge wasn't a bridge, we have second path from A to B. Obliviously, we have some reverse edge from A's subtree to some of A's parents (we don't have cross-tree edges because it's DFS' tree). So, let's go to this edge's start, use it and then go down the tree. Ta-da :)
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          i didn't understand your explanation well .. so that's what i came up with and correct me if i'm wrong .. 
          if there exists a vertex with only one edge .. this means that this edge is a bridge and we should return 0
          else
          run dfs and           orient the edges in the direction of the dfs 
          so??
          → Reply
          • 13 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            well, now i know why this is wrong .. 
            "if there exists a vertex with only one edge .. this means that this edge is a bridge and we should return 0"
            but i can't get the right Algorithm :/

            → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            i got it now ... :)
            → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i didn't get the editorial of Task D. someone please explain the dp approach and how the states are changing????

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is bigger. But it should be easier to understand.

    i took two 3D array hdp[a][b][c] and fdp[a][b][c] where in hdp array a=total number of men in the combination, b=total number of horsemen in that combination, c=number of consecutive horsemen at the end of the combination. The similar is denoted by fdp array with horsemen replaced by footmen.

    Now lets see how a previous state can contribute to the next state. Suppose we know hdp[i][j][k]. Then one possibility may be that we can add a horsemen at the end of this combination if k<k1 and j<n1 and we will get a combination for hdp[i+1][j+1][k+1]. Another possibility, we can add a footmen here if i-j<n2 and this will contribute in fdp[i+1][i-j+1][1].

    In the same way, you can find how fdp[i][j][k] can contribute to fdp[i+1][j+1][k+1] and hdp[i+1][i-j+1][1]

    base cases are fdp[1][1][1]=1 and hdp[1][1][1]=1

    the solution will be in the fdp[n1+n2][n2][] and hdp[n1+n2][n1][] part. you have to traverse k1+k2 times to find the ans.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could not understand problem D . Someone please explain it

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It says: for n1 + n2 Troops , Number of beautiful ways in which there are footmen in the very left is sum( dp[n1][n2 — 1][0] + ... + dp[n1][n2 — min(k2,n2)][0] ) cuz there shouldn't be more than min(k1,n1) footmen in the left. same goes for horsemen.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In counting the number of beautiful arrangements, we take some beautiful arrangement and we consider the prefix p1p2... pi where p1, ..., pi are all of the same type and pi + 1 is of the opposite type. i ≤ k1 when they are all horsemen and i ≤ k2 when they are all footmen. If you delete this prefix, the remaining arrangement is still beautiful but starts with a soldier of the opposite type. DP[n1][n2][0] counts the number of beautiful arrangements that begin with horsemen and DP[n1][n2][1] counts the number of beautiful arrangements that begin with footmen. Observe that DP[n1][n2][0] = DP[n1 - 1][n2][1] + DP[n1 - 2][n2][1] + ... + DP[n1 - min(n1, k1)][n2][1] and DP[n1][n2][1] = DP[n1 - 1][n2][0] + DP[n1 - 2][n2][0] + ... + DP[n1 - min(n1, k1)][n2][0].

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody provide the link to the Theorem stated in explanation of task E.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Task-D is solved in detail on page 6 https://noi.ph/training/weekly/week3.pdf

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

D is one hell of a question.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a hard time understanding the solution to D. Thanks to guys at Discord and also link mentioned by cobbishere , I was able to reach two solutions. Have written a post about it here: https://naman.dev/caesars-legions-codeforces.html .

One of the solution goes as follows: Let us construct a 4D DP array where DP[i][j][k][l] refer to number of ways given i footmen, j horsemen, such that we can still add k footmen or l horsemen to the back of the sequence.

Now the transitions are as follows:

Base Case: When i = 0 and j = 0, clearly we can have only 1 sequence (an empty sequence !). So, DP[0][0][k][l] = 1.

Now there are 2 possible cases:

We add a footmen to the back. Clearly, this is possible only if i > 0 (we have atleast one footmen) and k > 0 (we can atleast add a footmen to the back (there is no suffix of present sequence with k1 footmen)). Thus we add DP[i — 1][j][k — 1][l] . Similarly, for horsemen, we add DP[i][j — 1][k][l — 1] to the answer if j > 0 and l >0.

Thanks !

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, what I did was use 4D DP where dp[i][j][k][l] means number of ways of placing a footmen or horsemen depending on 'l'(l==0 means footmen & l==1 means horsemen), when we have already placed j footmen/horsemen depending on 'l' such that 'k' of them stand consecutively......

My submission : 66992305

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Beautiful explanation of Problem-D: https://noi.ph/training/weekly/week3.pdf .

→ Reply