Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### MikeMirzayanov's blog

By MikeMirzayanov, 2 years ago, translation,

Many thanks to cannor147 and geranazavr555 for the help with the translation into English.

##### 1259A - Happy Birthday, Polycarp!

Problem Writer: MikeMirzayanov

Editorial
##### 1259B - Make Them Odd

Problem Writer: MikeMirzayanov

Editorial
##### 1259C - As Simple as One and Two

Problem Writer: MikeMirzayanov

Editorial
##### 1259D - Let's Play the Words?

Problem Writer: MikeMirzayanov

Editorial
##### 1259E - Two Fairs

Problem Writer: MikeMirzayanov

Editorial
##### 1259F - Beautiful Rectangle

Problem Writer: MikeMirzayanov

Editorial
##### 1259G - Tree Elimination

Problem Writers: Endagorion

Editorial
##### 1276E - Four Stones

Problem Writers: Endagorion

Editorial
##### 1276F - Asterisk Substrings

Problem Writers: voidmax

Editorial

• +50

 » 2 years ago, # | ← Rev. 2 →   +1 I didn't get it in DIV 1 A it is important to delete the middle letters in the last two paragraphs to avoid appearing a new occurrence after a line is collapsed can anyone provide some testcase
•  » » 2 years ago, # ^ | ← Rev. 2 →   +11 For instance: tttwoooneee. If you delete the letter t that is standing before w, after deletion you still get "two".
•  » » » 2 years ago, # ^ |   -9 thanks, i missed that
 » 2 years ago, # | ← Rev. 2 →   0 My solution to Div.2 E :1) Perform DFS starting at Vertex a. This DFS function returns when reached at Vertex b.2) Perform DFS starting at Vertex b. This DFS function returns when reached at Vertex a.3) When each function saves the visited vertex, there is the vertex that only the first function visited, the vertex that only the second function visited, and the vertex at which both functions visited.4) Multiply the number of vertices only the first function visited by the number of vertices only the second function visited, and it's the answer.For example, on this graph, the answer is 5 x 6 = 30.Code : 67127301
•  » » 2 years ago, # ^ |   -7 thanks man, easier than the editorial
•  » » 2 years ago, # ^ |   -13 Do we have to always consider that cities a and b are connected by some road? Can they be diconnected?
•  » » » 2 years ago, # ^ |   -10 The problem specifies "It is guaranteed that from any city you can pass to any other by roads."
•  » » » » 2 years ago, # ^ |   -10 Thanks...
•  » » 2 years ago, # ^ | ← Rev. 2 →   -10 Is the highlighted path valid ? from 2 to A to 1 to B to 3 ?
•  » » » 2 years ago, # ^ |   -7 In your example, the pair (2, 3) will not count towards the solution. The problem states that for a pair (U, V) to count towards the solution, every way to get from city U to city V or from V to U must go through A and B. If there exists a path between them that does NOT go through both A and B, then it does not count towards the solution.In your example, there exists a path from 2 to 3 that does NOT go through A and B, thus it does not count towards the solution.The only "valid" pairs in your example would be (X1, Y) and (X2, Y). Answer = 2;
•  » » » » 2 years ago, # ^ |   +3 Thanks ,understood!
•  » » 23 months ago, # ^ |   0 Thanks man.
 » 2 years ago, # | ← Rev. 2 →   -7 I really liked this contest, I wish I had participated live.Here's my solution for Div2-E using BFS. Uses very similar approach to what is mentioned in the editorial. 66995096
•  » » 2 years ago, # ^ |   -10 I found your solution more intuitive than editorial's solution. Here is DFS based implementation of your idea. 67419480
 » 2 years ago, # |   +4 VERY nice editorial MikeMirzayanov
•  » » 4 months ago, # ^ |   0 nice handle.
 » 2 years ago, # |   -10 Could anyone help me to hack this wrong solution?66896686
•  » » 2 years ago, # ^ |   0 input: 1 tttwoooooonneeeee output: 1 3 should be : 1 4
•  » » » 2 years ago, # ^ |   0 Thank you so much.
 » 2 years ago, # |   -10 Div2 D5th paragraph, 1st line "In fact, the set of words of kind n10 has no more than n10"Shouldn't it be "In fact, the set of words of kind n01 has no more than n10"?
 » 2 years ago, # | ← Rev. 2 →   +2 In the editorial for the problem G: In the recursive equation for dp[v][0], the first product should be "j = 1 to i — 1", not "j = 1 to i = 1". In the recursive equation for dp[v][1], the first product should be "j = 1 to d", not "j = 1 to i = d". In the recursive equation for dp[v][2], the first product should be "j = 1 to i — 1", not "j = 1 to i = 1".
•  » » 2 years ago, # ^ | ← Rev. 4 →   0
 » 2 years ago, # |   0 In the problem 1277D - Let's Play the Words?, how come the solution to the last sample testcase is given as 1 2
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 01 -> 10001 -> 100And so:10000110000001
 » 2 years ago, # |   0 can anyone give me a testcase that broke my code?
 » 2 years ago, # |   0 606 Problem D video explanation https://youtu.be/4QeGE1MsviM
 » 2 years ago, # |   0 I have a question about div1 E.How do you perform operations to make $\Delta$ decrease to $\frac{3}{4}\Delta$ for stones located at 0, 1, 99999, 100000 according to your alogrithm?
»
2 years ago, # |
0

# HAPPY BIRTHDAY POLYCRAP -> what is wrong in my code can anyone tell please???

int n; cin >> n; int digits = 0, min = INT_MAX;

while (n != 0) {
int d = n%10;
digits++;
if (min > d) min = d;
n = n /10;
}

cout << min + (9*(digits - 1)) << endl;

}

 » 2 years ago, # | ← Rev. 3 →   0 I Problem 1259 -D can anyone explain why the OUTPUT of the following INPUT is 0, not -1? Input: 10 0 11 
 » 2 years ago, # |   +3 In the editorial of question D: Let's Play The Words? Why do we need to reverse $n_{01} - n_{10} - 1$ strings and not $(n_{01} - n_{10}) / 2$. Also, can anyone give hints on how to prove that the problem is equivalent to "the Euler traversal of a directed graph with 2 nodes"? Thanks!
•  » » 2 years ago, # ^ |   0 It's probably a mistake.In the code below you have this:  int ans = max(0, (int(max(s01.size(), s10.size())) - int(min(s01.size(), s10.size()))) / 2); That is equivalent to $(n_{01}-n_{10})/2$.
 » 2 years ago, # |   0 can anyone help me in problem B I am getting WA on tc 2 https://codeforces.com/contest/1277/submission/81699789 thanks
 » 22 months ago, # |   0 In Two Fairs, I am not able to understand what exactly (alpha u ,beta u) represents.Can someone clarify? Any help will be appreciated thanks :)
 » 19 months ago, # | ← Rev. 2 →   0 For those confused with the editorial for div2 E, I think there is a much easier approach with a similar idea. build an adjacency list that removes the vertex A from the graph(i.e., don't include edges to/from A) and then calculate the number of vertices connected to B(by performing dfs, starting from B). Let the number be x. similarly, build an adj list without B and count the number of vertices connected to A. Let the number be y. Now, the answer is simply (n-x-1)*(n-y-1). This is because (n-x-1) is the number of vertices that cant reach B if A is not present(we subtracted 1 to exclude A). This means that to connect these vertices to B, a path should exist only via A. A similar conclusion can be made for the (n-y-1) vertices. Thus answer will be (n-x-1)*(n-y-1).Here is my submission.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Why is the answer of sample test 1(test case 2) is 0 what about the path 1->2->3->4upd: My bad understood now
•  » » 7 months ago, # ^ |   0 Thanks for the easy explanation!