### Alexander's blog

By Alexander, 10 years ago, translation,

Editorial.

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

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.

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.

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) .

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.

• +8

 10 years ago, # |   0 There is theorem (on a theoretical basis for a written task)More details?
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 I find it in one book of discrete mathematics.
•  10 years ago, # ^ | ← Rev. 2 →   +5 I mean some further explanations...any hints to prove it?
•  10 years ago, # ^ | ← Rev. 3 →   +9 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.
•  10 years ago, # ^ |   +9 Also you can do something like this: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.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 :)
•  10 years ago, # ^ |   0 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 0elserun dfs and orient the edges in the direction of the dfs so??
•  10 years ago, # ^ | ← Rev. 2 →   0 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 :/
•  10 years ago, # ^ |   0 i got it now ... :)
 10 years ago, # |   0 Nice editorial. Thanks
 10 years ago, # |   0 Problem C can be solved in O(10*n) time complexity.
 10 years ago, # |   0 Problem C can be solved in O(10*n) time complexity.
 » 8 years ago, # |   0 The tutorial for problem D is so poorly written. It's so hard to figure out what it means.
 » 7 years ago, # |   0 Someone please bother to re-explain the approach for problem D..!
 » 7 years ago, # |   0 In Problem A, 'y' is not considered a vowel. only 'a', 'e', 'i'. 'o', 'u' are considered vowels.
 » 7 years ago, # |   0 i didn't get the editorial of Task D. someone please explain the dp approach and how the states are changing????
•  » » 6 years ago, # ^ |   0 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
 » 6 years ago, # |   0 could not understand problem D . Someone please explain it
•  » » 6 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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].
•  » » » 3 years ago, # ^ |   0 beautiful
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 [can u identify the problem in my code.i tried implementing it with your idea but some problem is coming in the code. Here is the link:http://codeforces.com/contest/118/submission/34204597]
•  » » » 3 years ago, # ^ |   0 Good solution!
•  » » » 3 years ago, # ^ |   0 shouldn't DP[n1][n2][0] be the number of beautiful arrangements that 'end' with with horsemen ans similarly for DP[n1][n2][1] ...
•  » » » » 10 months ago, # ^ |   0 both are equivalent as far as this implementation is concerned.
 » 3 years ago, # |   0 Can somebody provide the link to the Theorem stated in explanation of task E.
 » 3 years ago, # |   0 Task-D is solved in detail on page 6 https://noi.ph/training/weekly/week3.pdf
•  » » 2 years ago, # ^ |   0 I can't thank you enough. You were really a great help. Thanks again.
•  » » 7 weeks ago, # ^ |   0 I have read the whole sub-topic and thank you so much. This pdf made it very clear.
»
2 years ago, # |
0

# include

using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

string str,arr="AEIOUYaeiouy"; cin>>str; string::iterator p=str.begin(); while(p<str.end()){ if(arr.find(*p)!=string::npos){ str.erase(p); } else{ str.insert(p,'.'); p++; *p = tolower(*p); p++; } } cout<<str<<"\n";

return 0; }

New to programming so please forgive mistakes.. The above code is for Problem A. the above code is failing for case 14 which requires the same algorithm for all other cases.. where am i going wrong?? (Also if this is the wrong place to ask this question , kindly guide me where i could do so).

 » 2 years ago, # | ← Rev. 2 →   0 D is one hell of a question.
 » 2 years ago, # |   0 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 !
 » 18 months ago, # |   0 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
 » 18 months ago, # |   0 Beautiful explanation of Problem-D: https://noi.ph/training/weekly/week3.pdf .
•  » » 16 months ago, # ^ |   0 Do you have any written else ?? If you have , would you send me some links?? Thanks a lot =))
•  » » 12 months ago, # ^ |   0 I think there must first assign dp state to ans
»
14 months ago, # |
0

In the problem B, the output that my program creates is visbly same as that stated in problem, however the judge tags it as incorrect because of extra white space. It should be judge's fault right ? Here's the code :

# include<bits/stdc++.h>

using namespace std;

int main() {

ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n,line; cin>>n;

// Upper
for (int line=0;line<=n;line++) {
for (int i=1;i<=n-line;i++)
cout<<"  ";
for (int i=0;i<=line;i++)
cout<<i<<" ";
for (int i=line-1;i>=0;i--)
cout<<i<<" ";
cout<<endl;
}

// Lower
for (int line=n-1;line>=0;line--) {
for (int i=1;i<=n-line;i++)
cout<<"  ";
for (int i=0;i<=line;i++)
cout<<i<<" ";
for (int i=line-1;i>=0;i--)
cout<<i<<" ";
cout<<endl;
}
return 0;

}

 » 2 months ago, # |   0 my output shows exact same output as given in problem B ,but still it gives wrong answer