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.

There is theorem (on a theoretical basis for a written task)~~I mean some further explanations...~~any hints to prove 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.

run dfs and orient the edges in the direction of the dfs

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 :/

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

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.

could not understand problem D . Someone please explain 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.

In counting the number of beautiful arrangements, we take some beautiful arrangement and we consider the prefix

p_{1p}_{2}...p_{i}wherep_{1}, ...,p_{i}are all of the same type andp_{i + 1}is of the opposite type.i≤k_{1}when they are all horsemen andi≤k_{2}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[n_{1}][n_{2}][0] counts the number of beautiful arrangements that begin with horsemen andDP[n_{1}][n_{2}][1] counts the number of beautiful arrangements that begin with footmen. Observe thatDP[n_{1}][n_{2}][0] =DP[n_{1}- 1][n_{2}][1] +DP[n_{1}- 2][n_{2}][1] + ... +DP[n_{1}-min(n_{1},k_{1})][n_{2}][1] andDP[n_{1}][n_{2}][1] =DP[n_{1}- 1][n_{2}][0] +DP[n_{1}- 2][n_{2}][0] + ... +DP[n_{1}-min(n_{1},k_{1})][n_{2}][0].Can somebody provide the link to the Theorem stated in explanation of task E.

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

I can't thank you enough. You were really a great help. Thanks again.

D is one hell of a question.

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 !

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

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

The trick in solving D is that, having 4 state variables lead to TLE. I had very hard time understanding how to solve with only 3 variables.

The main thing is to get rid of k1 and k2 from state, but then how do we know if the next person is going to be horsemen or footmen?

The trick is to generate all k persons at once. Iterate from k = 1 to k = k1 or k2 and get rid of that from state. My submission can be checked for more details

https://codeforces.com/contest/118/submission/167418441