MikeMirzayanov's blog

By MikeMirzayanov, 5 months ago, translation, In English,

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
 
 
 
 
  • Vote: I like it
  • +50
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    thanks man, easier than the editorial

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Do we have to always consider that cities a and b are connected by some road? Can they be diconnected?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      The problem specifies "It is guaranteed that from any city you can pass to any other by roads."

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Capture9017ce46dd042836.png

    Is the highlighted path valid ? from 2 to A to 1 to B to 3 ?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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;

»
5 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I found your solution more intuitive than editorial's solution. Here is DFS based implementation of your idea. 67419480

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

VERY nice editorial MikeMirzayanov

»
5 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Could anyone help me to hack this wrong solution?66896686

»
5 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Div2 D

5th 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"?

»
5 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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".
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem 1277D - Сыграем в слова?, how come the solution to the last sample testcase is given as 1 2

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give me a testcase that broke my code?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

606 Problem D video explanation https://youtu.be/4QeGE1MsviM

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;

}

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I Problem 1259 -D can anyone explain

why the OUTPUT of the following INPUT is 0, not -1?

Input:
    10
    0
    11

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me in problem B I am getting WA on tc 2 https://codeforces.com/contest/1277/submission/81699789 thanks